zcmimi's blog
avatar
zc
2020-10-13 19:58:29

查看原题

点击跳转

f[i][j]表示用完前i个通配符,是否能匹配[1,j],

s为含通配符字符串,t为目标字符串,p_i为第i个通配符的位置

下文x|=y表示: 若y能,则x也能

若第i个通配符为*,*可以代替j之后的所有字符

那么f[i][j]|=f[i][j-1],也就是用*继续匹配下去(j-1位之后用*匹配)

s[p_i+1,p_{i+1}-1]=t[j+1,j+p_{i+1}-p_i-1],

那么f[i+1][j+(p_{i+1}-1)-(p_i+1)+1+[s[p_{i+1}]=?]]|=1

其中[s[p_{i+1}]='?']s[p_{i+1}]?时为1,否则为0

详见代码

avatar
zc
2020-10-12 16:35:55

查看原题

点击跳转

矩阵加速动态规划统计有多少长度为t的路径

附加条件: 不能走过一条边以后又立刻反着走一次

如果没有附加条件,用邻接矩阵加速即可

那么如何满足这个附加条件呢?

我们设f[i][j]表示第i个时刻在第j条有向边终点的方案数,这样就可以保证不会反着走

然后构建邻接表,枚举点,更新加速矩阵信息

初始矩阵为所有与起始点直接连接的边

答案为所有与结束点连接的边的答案之和

详细可以查看代码

avatar
zc
2020-10-10 17:22:12

查看原题

点击跳转

预处理出

  • s[i][j]表示前i块到中j出现的次数
  • b[i][j]表示第i块到第j块的答案

统计时,在块内答案的基础上,枚举块外元素更新即可

avatar
zc
2020-10-09 18:10:52

查看原题

点击跳转

题意: 给出一个长度为n序列a,m次询问,每次询问区间[l,r]里出现次数最多的数. 若有多个,输出最小的.

如果是严格区间众数可以用主席树,这里要求找到出现次数最多的数,只能使用分块

先对序列进行离散化

预处理:

  1. s[i][j]表示前i个块中j出现了几次
  2. p[i][j]表示第i块到第j块中出现次数最多的数,P[i][j]表示次数

复杂度\mathcal O(n\log n)

对于一个询问[l,r]

l,r在同一个块或相邻块,那么暴力求解

否则枚举块外的数,每个数的出现次数为块内的+块外的,与块内已经预处理出的答案比较,更新答案

avatar
zc
2020-10-07 20:03:39

查看原题

点击跳转

题意:

n个节点的树,有r种属性,每个点属于一种属性.有q次询问,每次询问给r_1,r_2,问有多少对点(e_1, e_2)满足e_1属性为 r_1,e_2属性为r_2,且e_1e_2的祖先. (n,q \le 2 \times 10^5, r \le 25000,时限5s)

首先将询问离线

不管枚举e_1统计子树中e_2的数量

还是枚举e_2统计到根节点路径上e_1的数量

都是\mathcal O(nr)

可以考虑将两种方法结合,使用根号分治

r_2的总数目为S

S\ge \sqrt n,枚举e_2,统计e_1(不超过\sqrt n个),复杂度\mathcal O(q\sqrt n)

否则枚举e_1,统计e_2(子树中的r_2不会超过\sqrt n个),复杂度\mathcal O(n\sqrt n)

具体看代码

avatar
zc
2020-10-06 10:38:49

查看原题

点击跳转

可以发现除了x地图,其他地图都只有两种状态,

如果没有x地图,那就是2-sat裸题,

x地图最多只有8张,我们可以暴力枚举x地图

avatar
zc
2020-10-06 00:18:02

查看原题

点击跳转

首先每条边(x,y)至少有一个端点是关键点

条件 连边
x,y任选一个 \neg x\to y,\neg y\to x

接下来是对每部分进行连边

若将每个点向该部分中出它以外的所有点连边,复杂度为\mathcal O(n^2)

我们可以前缀优化建图

设该部分为a_1,a_2,\dots,a_w

对每个点a_i新增一个状态pre_{a_i}表示a_{1\sim i}中有没有被选为关键点

条件 连边
a_i,pre_{a_i}必须同时选 a_i\to pre_{a_i},\neg pre_{a_i}\to \neg a_i
pre_{a_{i-1}},pre_{a_i}必须同时选 pre_{a_{i-1}}\to pre_{a_i},\neg pre_{a_{i-1}}\to \neg pre_{a_i}
pre_{a_{i-1}},a_i不能同时选 pre_{a_{i-1}}\to \neg a_i,a_i\to \neg pre_{a_{i-1}}

这样就可以\mathcal O(n)连边了

avatar
zc
2020-10-05 16:10:20

查看原题

点击跳转

avatar
zc
2020-10-03 11:47:30

查看原题

点击跳转

avatar
zc
2020-09-29 12:40:52

查看原题

点击跳转

s_i为每个连通块点数

对每个连通块构建prufer序列

由于度数为边数两倍,\displaystyle \sum_{i=1}^k d_i=2k-2

对于给定d序列构造prufer序列的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1} = \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdot(d_k-1)!}

对于第i个连通块,它的连接方式有s_i^{d_i}种,对于给定d序列使图连通的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

枚举d序列:

\displaystyle \sum_{d_i\ge 1,\sum d_i=2k-2} {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

换元,设e_i=d_i-1:

\displaystyle \sum_{e_i\ge 0,\sum e_i=k-2} {k-2\choose e_1,e_2,\dots,e_k}\cdot \prod_{i=1}^k s_i^{e_i+1}

根据多元二项式定理:

\displaystyle (x_1+x_2+\dots+x_m)^p=\sum_{c_i\ge 0,\sum c_i=p} {p\choose c_1,c_2,\dots,c_m}\cdot \prod_{i=1}^m x_i^{c_i}

原式化简得:

\displaystyle (s_1+s_2+\dots+s_k)^{k-2}\cdot \prod_{i=1}^k s_i

\displaystyle n^{k-2} \cdot \prod_{i=1}^k s_i

11/74
Search
search