w h y ? y o u a r e h e r e ?

cf616F(SAM+树dp)

Posted on 2019-04-04 | In 字符串 , dp

题意给你n个串每个串都有一个价值

c_{i}

$c_i$ 然后让你构造一个串

S

$S$

S

$S$ 的价值定义为:

F (S) = \sum_{i = 1}^{n} c_{i} p_{S, i} | S |

$F(S)=\sum_{i=1}^{n}c_ip_{S,i}|S|$

p_{S, i}

$p_{S,i}$ 表示在第

T_{i}

$T_i$ 中

S

$S$ 出现的次数

| S |

$|S|$ 表示串的长度问如何选择

S

$S$ 能得到最大价值输出最大价值题 ...

cf232D(后缀数组+主席树+ST表+二分)

Posted on 2019-04-03 | In 数据结构 , 字符串

题意给定长度为

n

$n$ 的整数序列

q ​

$q$ 次查询区间

[l, r] ​

$[l,r]$ 能’’匹配’’多少长度与其一致且不相交的区间匹配的定义是for all

i ​

$i$

(0 \leq i \leq r 1 - l 1) ​

$(0 ≤ i≤ r1 - l1)$ the following condition holds: $h1 + i + hl2 + i = hl1 ...

cf524F(后缀数组+线段树)

Posted on 2019-04-03 | In 字符串 , 数据结构

题意给定一个括号序列,现在能进行两类操作: 循环移位,将末尾的字符移动到开头在任意位置加入任意类型字符问在满足加入字符最小的情况下,输出合法的括号序列,如果有多种情况满足长度最下,则输出字典序最小的题解首先对于加入字符最少必然是加入

| 左 括 号 n u m - 右 括 号 n u m |

$|左括号num-右括号num|$ 个若左括号多必 ...

cf86C(AC自动机+dp)

Posted on 2019-04-02 | In 字符串

题意给定

m

$m$ 个字符串问构造长度为

n

$n$ 的串的方案数构造串需满足对于任意位置

i

$i$ 都存在一个子区间[l,r] 包含

i

$i$ 且子区间对应m个串中的任意一个题解AC自动机+DP 我们可以设

d p [i] [j] [k]

$dp[i][j][k]$ 表示已经构造了长度为

i

$i$ 的串且在自动机中第

j

$j$ 状态且存在

k

$k$ 字符属 ...

cometOJ#0C.项链与计数(并查集)

Posted on 2019-04-01 | In 数据结构

题目描述在图论中，“简单环” 被定义为一个点数和边数相等的回路，并且这条回路上没有出现重复的点或边。对于一个无向图，小象定义 “项链” 是由一些简单环组成的子图，不妨设项链包括 k 个简单环

C_{1}, C_{2}, \dots \dots, C_{k} (k \in N^{+})

$C_1, C_2, \ldots…, C_k (k \in \mathbb{N}^+)$ ，那么项链需要满 ...

bzoj4229(并查集)

Posted on 2019-04-01 | In 数据结构

题目描述现在，我想知道自己是否还有选择。给定n个点m条边的无向图以及顺序发生的q个事件。每个事件都属于下面两种之一： 1、删除某一条图上仍存在的边 2、询问是否存在两条边不相交的路径可以从点u出发到点v 题解神奇的并查集 %%%% 我们考虑离线下来从后到前做把删边处理成加边(注意重边) 把剩 ...

bzoj1758(点分治+单调队列+二分)

Posted on 2019-03-20 | In 数据结构

题解经典

0 / 1

$0/1$ 分数规划二分答案

a n s

$ans$ 对于所有的边权减去

a n s

$ans$ 问题转化成树上是否存在一条路径

L <= l e n <= R

$L<=len<=R$ 并且路径和大于等于0 比较直观的做法用点分+线段树查询复杂度

O (n l o g^{2} n l o g w)

$O(nlog^2nlogw)$ 然而会T飞我们考虑每个深度对应的是一段区间总体 ...

hdu5664(点分治+容斥+树状数组)

Posted on 2019-03-19 | In 数据结构 , 数学

题解很牛逼的点分啊 !!!!! 我们考虑二分答案然后直接点分统计大于等于k的点对个数复杂度

(O (n l o g^{2} n l o g w))

$(O(nlog^2nlogw))$ 据说卡卡常数肯定是能过的但是我们主要用下面这种方法我们对于当前重心的子树节点按照点到重心的距离排序因为点只有

n l o g n

$nlogn$ 个 (点分的性质) 所以预处理复杂度$O ...

bzoj4598(点分治+hash)

Posted on 2019-03-19 | In 数据结构

题解点对问题考虑点分我们考虑子树合并有两种情况分别是当前子树链作为开头或者结尾对于长度大于

m

$m$ 和小于等于

m

$m$ 再分情况讨论下然后分别维护已经合并完的子树在长度为

x

$x$ 时分别作为开头和结尾的情况下的方案数统计贡献的话就直接用hash判当前的子串是否合法即可 hash我们考虑自然溢出 ...

bzoj3648(点分治+树状数组)

Posted on 2019-03-15 | In 数据结构

题解分为两部分对于树形结构直接点分然后排序/树状数组统计贡献对于基环树结构我们先把环取出来以环上的点为根做点分治统计每个子树内的贡献然后考虑环上点的相互影响对于每个子树维护每种深度的个数然后我们可以考虑到每个点作用的是一段连续区间可以采用树状数组来维护答案时间复杂度是$ ...