杂题乱做1

退役前给自己看的,删了一些东西放出来了,有兴趣可以看看


cf674g

考虑维护出现次数超过一半的数的方法:维护当前数,当前数出现次数,遇到一样的+1,否则-1,次数变为0的时候改数。

这种方法可以推广到更多数。考虑维护一些这样的(数,次数)对,对于新数,如果在维护的集合内出现过,直接+1,否则如果集合大小<k,把这个对加入集合,不然把集合内所有对-1,清空为0的对。

这种操作可以用线段树维护。合并两个节点,枚举其中一个集合插入另一个集合。如果某次减的操作会减出负数,就交换集合内最小的数和当前插入的数,然后把集合内最小的数插回来,这样一定没有负数。

arc103_f

构造题。考虑找出重心,叶子的D最大,知道一个点的D可以求出父亲的D。注意构造完后用根check一下,因为构造过程不考虑父亲合法性。

cf1270g

i - n \leq a_i \leq i - 1,即1 \leq i - a_i \leq ni - a_i构成基环树,树上的环就是解。

cf1270h

这个写这里了https://baka.online/cf1270h-number-of-components-%e7%ba%bf%e6%ae%b5%e6%a0%91/

AGC034F

f,p分别为期望步数,概率,有:

f_i = \sum_{j < 2^n } p_j f_{i \oplus j} + 1

这个方程显然可以用高斯消元解,不过很慢...

+1移到左边,写成集合幂级数:

(f_0, f_1, ... f_{2^n - 1}) \oplus (p_0, p_1, ... ,p_{2^n - 1}) = (f_0 + 2^n - 1, f_1 - 1, f_2 - 1 , ... , f_{2^n - 1} - 1)

右边f_0 - 1的位置被换成了f_{0} + 2^n - 1,是因为在方程中没有定义。又因为\sum p = 1,可以知道左边和右边的\sum f相等。

那么可以推出:

(f_0, f_1, ... f_{2^n - 1}) \oplus (p_0 - 1, p_1, ... ,p_{2^n - 1}) = ( 2^n - 1, -1, -1 , ... , -1)

考虑使用FWT求解。

\hat{f}_S = \sum_{T \subseteq S} f_T (-1)^{ | S \cap T | }

那么观察到,等号右边的幂级数FWT后,第一项为0。这样是不行的。

不过注意到已知f_0 = 0,可以考虑假设右边的第一项为0,直接FWT求解,再把和f_0相差的大小补上即可。

agc030d

自己YY的DP又挂了。。。令f_{i,j}表示A_i < A_j的概率,每次交换只影响O(n)个位置,就可以简单计算。

cf1286c2

不限制询问长度的话,就问[1,n],[1,n-1]就好了。

限制的时候,令t= \lceil \frac{n}{2} \rceil,询问[1,t],[1,t-1],求出[1,t]

考虑令数组c_{i,j}表示i,在长度为j的串中出现次数。对于整个串的前后的j个计数,则某元素出现次数为c_{1,j}-(c_{i+1,j}-c_{i,j})。那么就可以求出答案了。

cf1286d

看了好久没看懂。。。最后有了中文题解才懂。。。

容易发现碰撞一定产生在相邻粒子间,那么枚举每对粒子,枚举碰撞方向,计算概率,就可以求出答案。

f_{i,0/1}表示考虑前i个,它们不碰撞的概率。

一个Trick:如果某DP的某一维是0,1,考虑矩阵。

于是写成矩阵。一开始,所有转移的概率都是存在的,在过程中逐渐有一些转移法不可用了,在矩阵中去掉即可。

按时间排序。

E = \sum_{i} p_i t_i = \sum_i (t_i - t_{i - 1}) \sum_{ j \geq i }p_j

线段树维护矩阵,矩阵的积就是p,前面的也可以算。

注意可能有根本不会碰撞的情况,最后减掉线段树上剩下的f t

cf1284d

不用想那么多,直接排序,主席树+区间加+标记永久化。

cf1284e

考虑统计五个点的集合,并求凸包,可以得出答案为2x_3+x_4,其中x是出现次数。可以求出x_3+x_4+x_5。考虑求3x_3+4x_4+5x_5,意义为凸包上的边数和。枚举边的一个点,极角排序双指针。

agc035b

求一棵树,把其它边随便定向,然后DFS树,对每一个点通过改变父亲方向使其合法。发现对于边为偶数,这样一定有解。

agc035c

i = 2k, i \oplus i +1 = 1,那么把i,i+1,1,i,i+1串成一条链,是合法的。奇数即得解。如果n = 2 ^ k,显然无解,否则一定存在x \oplus y \oplus 1 = n,串起来即可。

agc035d

这个题不是状压。。。我们考虑把删除改成插入,那么考虑在两张卡里插入一张卡,对答案的贡献就是这两张卡被算了多少次乘插入的值。

定义DPf_{l,r,L,R},表示第一次插的是l,r这两张,各被算了L,R次。

f_{l,r,L,R} = \min \lbrace f_{l,k,L,L+R} + f_{k,r,L+R,R} + (L+R)A_k \rbrace

观察可以发现,这个DP的状态数是O(n^2 2^n)的。转移复杂度O(n^3 2^n)

agc035e

这里有一篇题解

一个Trick:把问题转化为图。用图表示删除xy就会被添加这样的关系,那么如果有环,一定不可以。

如果2 \mid K,可以发现只要不选超过\frac{K}{2}个连续同奇偶的即可。

如果2 \nmid K,可以把点按奇偶分成两部分,按照上面那篇题解中的样子摆好。可以发现,如果在左边,右边都选了点(连续环状),且超过K + 1个点,一定构成了环。有环是不可以的。

所以用DP求选点,且不构成环的方案数。令f_{i,j,k,lj,lk}表示考虑了前i层(以右边的数),左边选了j个,右边选了k个,左右分别有限制lj,lk,表示不能选到这个位置。

具体转移看这里。。。彻底蒙了的说。。。

agc035f

如果存在k_i = j - 1, l_j = i,那么可以操作让k_i + 1, l_j - 1,结果不变。称不能这么变的为标准形式。

一个标准形式唯一对应一种答案。通过反证可以证明。一个Trick:讨论某种顺序枚举下第一个不同的位置。

然后枚举有几对是那样的,简单容斥就行了。。。

[JXOI2017]数列

正着DP,那么需要记录上界,下界,选了什么,然后用前后缀和优化。

但是对于位置i依赖于i-1, < i-1的DP,可以考虑正着DP,那么就可以无视掉选了什么这一维。

从前向后求解答案,使用记忆化搜索。

[SCOI2014]方伯伯的商场之旅

可以分析出,移动到一个位置最优,但是不确定是哪个位置。对于这种问题,可以先移动到一个位置,再进行平移,动态维护答案。

cf1168d

猜一个结论:对于任意子数,每种字母在每条链上的\max之和(即要补充到的大小),不大于深度。可以按层归纳证明。然后简单DP即可。

考虑修改,发现只会在分叉的地方DP,有一个结论,把链缩起来,树深度是\sqrt n级别的(1 + 2 + 3 + ...),所以暴力修改就行了。

[SHOI2017]寿司餐厅

碰到选一个,必须选另一个,立马想最大权闭合子图!!!

[COCI2019] Quiz

wqs二分,斜率优化优化DP。wqs二分处理整数问题时,可以通过只在整数上二分求答案。但是遇到小数后还是要实数二分的说。

wqs二分中,每次转移都-mid,计算答案+K mid

[SHOI2017]组合数问题

\sum_{i} \binom{n}{ik+r} = \sum_i \binom{n}{i} [i \equiv r \pmod k]

这种技巧还是要熟悉的。

[JLOI2016]侦查守卫

带权值的树上选点覆盖问题。令f_{x,i},g_{x,i}分别表示x点向上覆盖i,向下i还没有覆盖的最小值。注意此处是包含更小的状态的。

转移的时候先计算向上覆盖,方法是讨论选择的点在原来的子树还是新的子树内。然后计算向下覆盖,这个加上子树的即可。

[JLOI2016]成绩比较

有难度的计数题。分数可以选,这个比较难处理,所以把分数分开。分别计算选人和排名的方案数,与分数分配的方案数。

f(x),g(x)表示至少,正好x人被踩。

f(x) = \binom{n - 1}{x} \prod_i \binom{n - x - 1}{r_i - 1}

f(x) = \sum_{i=x}^{n-1} \binom{i}{x} g(x)

g(x) = \sum_{i=x}^{n-1} \binom{i}{x} (-1)^{i-x} f(x)

在需要对集合选取一个子集,满足某种性质时,对于一个更大的集合包含的小集合,选取小集合的方案要乘上大集合元素中选一部分为小集合的方案。

计算分数,枚举B神的分数,对于每科分别计算乘起来就行。

\sum_{i=1}^{u} n^{n - r} (u-i)^{r-1}

这个式子不用简化。因为次数不高,直接算n+1个值,然后拉格朗日插值即可。

一道考试题

题在这里

题目所求可以转化为减之前与之后所有数的积的期望差。

计算减之后的期望:

\frac{ 1 }{n^k} \sum_{\sum b_i = k} \frac{k!}{b_i!} \prod(a_i - b_i) ) = \frac{k!}{n^k} \sum \prod \frac{a_i - b_i}{b_i!}

这道题告诉我们,当一个式子长得像生成函数,那么她就是生成函数

定义指数生成函数F_i(x)

F_i(x) = \sum_{j=0} ^ {\infty} \frac{A_i - j}{j!} x^j = \sum \frac{A_i x^j}{j!} - x \frac{x^{j-1}}{(j-1)!} = e^x (A_i - x)

可知答案为

\frac{k!}{n^k} \sum_{i=0}^k (\prod F_i) [x^i] \frac{n^{k-i}}{(k-i)!}

分治NTT求一下卷积,化一下式子。

JZPTREE

对于求\sum n^k的问题,可以考虑使用第二类斯特林数。

n^k = \sum_{i=0}^k S(k,i) n^{\underline i}

(x+1)^{\underline i} = (x-j+j+1)x^{\underline {i - 1}} = x^{\underline i} + i x^{\underline {i - 1}}

[SHOI2008]cactus仙人掌图

对于仙人掌上问题,首先考虑圆方树。方点是和环有关的,对于一类与距离有关的题,可以把和方点边权设为和方点父亲的最长/最短距离。

一个月后的更新:然后做就行了。DP什么的。

一道奥妙重重的计数题

n,m,k, m \leq k \leq n,表示1n的排列,考虑选k个元素的所有子集。把它们内部按元素大小排序,然后再按字典序排序,求:

\sum| A_{i,m} - A_{i+1,m} |

做法:

考虑相邻两个排列第一个不同的位置,发现肯定是xx+1

枚举x,再枚举j,表示这个位置在j

把两个排列写出来,发现一定长这样:

...,x,n-(k-j)+1,...,n

...,x+1,x+2,x+3,...

分类讨论,当j < m时,贡献由后面的差决定,当j=m时,贡献为1。可以求出答案的式子:

\sum_{x=1}^n \sum_{j=1}^{m-1} \binom{x-1}{j-1} | n-k-1-(x-j) | + \sum_{x=1}^n \binom{x-1}{m-1}

枚举i=x-j。后面那个\sum很好求,下面只考虑前半部分

因为x-j=i,j=x-i \leq m - 1,可以知道x \leq m + i - 1

\sum_{i=?}^{??} |n-k-1-i| \sum_{x=i+1}^{m+i-1} \binom{x-1}{x-i-1}

\sum_{x=i+1}^{m+i-1} \binom{x-1}{x-i-1} = \sum_{x=0}^{m-2} \binom{x+i+1}{x} = \sum_{x=0}^{m-2} \binom{x+i+1}{i+1}

运用组合恒等式:

\binom{m+i-1}{m-2}

那么上文中的?是多少呢?

可以发现,为了使\binom{x-1}{j-1}有意义,有x-j \geq 0,且x, j \geq 1。注意到,x那个排列后面为一串递增的数,直到n,那么x \leq n - k

所以,0 \leq x - j \leq n - k - 1

bzoj3864

陈老师的DP套DP题。大概是这样的:一个DP可以读入一串东西,输出一个东西。现在要统计输出的这个东西对应的输入有多少。那么考虑把那个“一个DP”的DP状态,放进新的DP里面。

拿这个题举例子,两个串匹配。枚举T,那么可以定义DPf_{i,j}表示T和S分别匹配到了i,j。发现确定i,对于j的变化,f最多上升15次。那么状压这个差分数组,就相当于储存了DP的状态,做一个DP就行了。

CF611H

有一种很厉害的做法:在每种长度中钦定一个点做关键点,可以证明可以构造一种方案,关键点连通,剩下的点挂在关键点上。那么枚举关键点的形状,对剩下的部分做一个网络流。

不过还有一种更厉害的做法:

钦定1为根,考虑一个一个扩展。钦定从长度i扩展,找一个长度j,判断可不可以在i到j中间连一条边。

实际上如果题目输入了i,j这条边,就为答案提供了两种可能:两种方向。这个非常二分图。

考虑建一张二分图:左边为所有的连边方案(即i到j这样),右边为所有长度。如果存在完美匹配,则存在解。

判断ij这条边,先在二分图中删掉它,然后判断是否仍然存在完美匹配。用Hall定理。

貌似想明白了,做题。。然而发现貌似左边的点很多啊,不是很能枚举子集。相反右边很可枚举的样子。

观摩了代码,发现解决方法是:已知左边的流量=右边-1,那么右边的一个子集一定流量<=左边,代表着可以匹配。那么枚举右边的子集判断就行了。

其实我不知道这个对不对。。。

agc024f

枚举子串,求出现次数。定义状态(S,T)表示已经匹配了S,还剩下没被匹配的部分是T,的方案数。

对于一个输入的串T,初始状态为(\phi,T),最终要被匹配到(S,\phi),则TS产生了贡献。

直接DP出所有的(S,\phi)。本题代码很难写。。需要大量实现技巧,列举在下面:

状态是两个数,注意到两个数总长度不超过n,可以记录成一个大数加上一个分界点。

h[s]表示s的最高位1在哪里。h[0]=-1,h[s]=h[s>>1]+1。

需要预处理在T里匹配一个字符后到了哪里。注意到不同长度的状态二进制表示可能不同,需要在最高位上加一个1,表示长度。

令v=s和t拼接起来的状态。在转移的时候,从f[i][v]转移到f[t拼一个数的长度][新s拼新t]

注意到当转移0的时候,s后面接一个0,转移1的时候,s后面接1。而从v中取出t后要在t后面手动加上最高位来做。

那么可以转移0的时候给s加1,转移1的时候给s加0,和新的t直接xor,就可以抵消掉这一位。

CF840C

一件这样的事情:有n个球,有标号,需要选i对出来,每一对内是有序的,一个球可以被选两次,求方案数。

那么答案为

\frac{n!(n-1)!}{i!(n-i)!(n-1-i)!}

理由:

考虑这i段一定有i个左端点,可以看作选了i个左端点出来,然后把这i个左端点随意排列,挨着它的就是右端点。

或者看作先选了i段,再把左端点填上。

[POI2014]RAJ-Rally

拓扑图求最长路是简单的。拓扑图有一个极好的性质:可以把图分成两部分,两部分之间只有单项边相连。实际上只需钦定一个位置,使得拓扑序比它大/小的在它一边就行了。

那么要求删一个点之后的最长路,可以考虑枚举这个划分,维护两个集合内的最长路,与跨中间的边的最长路。按照拓扑序每次把一个点放到另一个集合里,就可以动态维护删掉这个点的最长路了。

CF582D

考虑n!一共有多少p是因数:\sum_{i=1} \lfloor \frac{n!}{p^i} \rfloor,即p进制下,从高到低前缀和之和。

那么考虑\binom{n+m}{n}中,p的个数,发现如果p进制加法没进位,就是0,否则会+1。那么答案就是进位次数。

数位DP。一个蛋疼的东西:这个数位DP显然是从高到低考虑比较合适的,而不是从低转移到高,那么这种情况下直接递推比搜好。

f_{i,j,0/1,0/1}表示考虑前i位,进位j次,第i位是否上届,第i-1位是否进位到i。转移即可。

有一个计数方面的Trick:需要求一个这样的式子的解数量:求有多少对(x,y)满足0 \leq x+y-p \leq d - 1

做法是这样的:考虑再减一个p

-p \leq x - p + y - p \leq d - p - 1

p + d - 1 \leq p - x + p - y \leq p

cnt = \sum_{i=p + 1 - d}^p \sum_{1 \leq x \leq p, 1 \leq y \leq p} [x+ y =i]

= \sum_{i=p + 1 - d}^p i - 1

那么算一下式子就行了

agc004f

首先,可以把题目改成把点两两配对,最短距离。

如果是树,那么只需考虑每条边被经过的次数,黑白染色,令两种点分别为1,-1,记子树和,答案即\sum|s_i|

显然,s_r必须为0

如果有奇环,可以通过绕奇环一次把根的和+-2。判一下要多少次,把环上点都更新一下。

如果有偶环,考虑可以把偶环上一些边改成走被断开的环边,答案为\sum|s-x|+\sum|s+x|+|x|x为走了几次。这个是中位数问题。

arc083f

看似是神题,其实是套路(?)题

因为一个机器人只能用一次,所以当出现拐角这样的形状时,就很捉急。

具体来说,可以考虑给每个点找一下它可能被哪个机器人干掉,其实只有两个是可能的

那么行列为点点为边建图,一定是基环数

考虑给每个点钦定一下它是被谁消掉的。显然就是给边定向。假设边x,y的意义是(x,y)的点被y消掉了。

那么就是一棵外向树。基环上的边有两种可能方向,枚举一下

考虑计数,当钦定了一个点被一个机器人消掉之后,发现如果一开始就走这个机器人,不一定能消掉这个点。也就是说存在一些关系,表示x必须在y之前选。连边。

这次连出来的是森林。满足题意的方案,一定是森林的合法拓扑序。数一下就OK了

注意多个基环树是独立的,要乘起来,并且还要乘一个多重集排列

P4705

就是一个东西:快速求\sum_{i=1}^n a_i^k

那么整个生成函数:F(x)=\sum_{k=0}^{\infty} x^k \sum_{i=1}^n a_i^k=\sum_{i=1}^n \sum_{j=0}^{\infty} a_i^j x_j=\sum_{i=1}^n \frac{1}{1-a_ix}

因为ln(1-a_ix)'=\frac{-a_i}{1-a_ix},令G(x)=\sum_{i=1}^n ln(1-a_ix)',则F(x)=-xG(x)+n

G(x)=\sum_{i=1}^n ln(1-a_ix)' = ln(\prod_{i=1}^n (1-a_ix))',分治NTT即可

[RC-02] 开门大吉

对于选i,就不能选j+k之前的的限制,直接从ij+k连INF,最小割即可。

[HNOI2019] JOJO

KMP跳NEXT的时候,如果有周期,可以直接取模。但是要判断有没有周期,先暴力跳一下,把x - p_x即可能的周期存下来,第二次再跳的时候如果长度一样,就是周期,就可以取模了。

CF1349A

LCM的GCD,考虑意义,就是第二大的因子。

CF1349B

找规律题。

考虑存在A \leq B,且A为要变成的答案。可以证明,在B右边无论存在什么数,都可以做出答案。左边同理。

CF1349C

发现如果两个块,颜色不同,且大小都不为1,那么永不影响。如果一个块大小> 1,另一个大小为1,只需一步就可以传染到。所以就是一个最短路问题。

CF1349D

首先令E_i表示i的答案,如果只有i满了才能结束游戏,就可以直接消元求了。

E_i'表示满了才能结束游戏的期望,那么有:

E_x = E_x' - \sum_{i=1}^n [i \neq x] (P_iC + E_i)

其中C是全部转移的期望。就是考虑提前结束在哪里。

那么考虑计算E_x',C,发现其实是一回事,就是要求已经有了一些,之后期望多少步win。

那么令f_i表示还需要i个才能win的期望。根据题解的说法,直接列式子会除0,所以考虑差分,令g_i=f_i-f_{i-1}

那么g_i的实际意义,就是现在差i个,期望几次可以获得一个。

AGC020D

热动分析一下:首先最长段一定是K = \max \lbrace \lceil \frac{A}{B+1} \rceil , \lceil \frac{B}{A+1} \rceil \rbrace

那么可以得到答案一定长成AAAAABAAAAAB...A|...|BBBBBBBA...这样。

考虑一个位置,如果可以作为分界点,设前面放好之后剩下的A,B分别有a,b个,可以知道:aK \geq b。那么可以二分边界。

之后有一个问题:再变为BBBBBBA之前,会有一段可以多放一些A的位置。具体来说,因为后面有aK < b,可以多放一些A,到正好满足的地方。

知道这些就可以做了。

AGC020F

神仙题。。需要很多步操作。。

首先,环不好处理,考虑变成链。钦定最长的一根为在起点,那么其它的都无法超过它,就可以做了。

注意到一件这样的事情:(在很多题都很重要!!)

输入都是整数。

那么有一种做法:令某段的起点位置为s_i,则可以分解为p_i+f_i。其中p是整数,f是小数。

因为线段长度都是整数,所以两条是否相交,和f是多少无关,只和f相对大小关系有关。

又因为是随机的,f相同的概率可以看做0。那么枚举大小关系。

只关心大小关系的话,问题就可以离散了。可能的起点有nC= 300个。

做一个DP:f_{i,j,s}表示前i个位置存在线段,最长覆盖到了j,并且用过的线段是s

转移只需要讨论某位置放不放。注意到已经钦定了大小关系的顺序,实际上对于一个位置,可以算出下一个小数部分是多少,也就是转移是唯一的。DP一下就做完了。

得到了方案数,除以总数。总数是枚举的排列数量,乘上可能的起点位置。C的任何一个位置都可能是起点,并且钦定了一个线段,考虑了n-1个。所以是C^{n-1}

bzoj 4245

大概是说给一个序列,要你先分段m段再求值,值是每一段的xor和的or和。求最小值。

那么有一个Trick:a \oplus b | b = a | b。分类讨论可知。

于是考虑做一个前缀xor和,答案就是选一些数使得or最大。贪心即可。注意最后一个必须选。

CF1286E

只需要求出每次插入一个元素后,串的border即可。可以知道可能的border只有O(n)种。那么只需要维护。

考虑一个border,位置为i,如果插入字符c后还是border,那么str_{i+1}=c

于是考虑一种做法:维护每个串后面的字符是什么。但是这个每次修改的量是O(n)

可以这样维护:对于每个border,记录第一个和它颜色不同的祖先。这样跳着删就行了。

考虑正确性:新插入一个字符后,border集合的结束位置都变了。但是不需要重新计算每个位置的祖先,因为之前都算过了。只需要维护新插入的点的祖先,它就会自动跳到我们想得到的链上。

用单调栈维护区间min,用map维护每种串。每次插入一个元素后,把所有比新大小大的串都删掉。可以发现是O(nlogn)的。

[SDOI2017]龙与地下城

FFT的时候,把两侧比较小的数直接丢掉,可以快速得到近似解

[NOI2017]泳池

DP什么的不写了..记一个O(n^2)多项式取模:

inline void mod(int A[], int B[], int n) {
  for (int i = n * 2; i >= n; --i)
    for (int j = 0; j <= n; ++j)
      A[i + j - n] = (A[i + j - n] + P - 1ll * A[i] * B[j] % P) % P;
}

[SDOI2017]遗忘的集合

面对多项式连乘不要怕,微笑着面对它!消除连乘的最好办法就是求LN!

[ZJOI2015]地震后的幻想乡

期望时间和期望排名是可以互相转化的。

[HAOI2017]新型城市化

两个团意味着反图是二分图

[ZJOI2017]树状数组

树状数组的操作反向之后,就是后缀操作。

考虑贡献,是一对点相同的概率。

用最暴力的方法维护:直接维护点对的答案,二维数据结构。

[ZJOI2017]仙人掌

加边后是仙人掌->删掉环后的树,在上面加边,使得每条边最多覆盖一次->假装没覆盖的是被重边覆盖->一般通过DP

[SDOI2017]天才黑客

有一件事:多个点的LCP,建图优化,要考虑怎么建才不会让LCP变大(漏)

[ZJOI2016]线段树

一般通过DP:考虑一个点能对哪里贡献:是一个区间。钦定f_{v,i,l,r},表示vi次操作,[l,r]没它大,l-1,r+1比它大。

那么对于一个位置,方案和就是所有包含它的区间。f就是答案\leq v的,减一下就是=了,记为h

ans=\sum (h_v - h_{v+1})val_v。因为数据随机,跑得很快。

一类套路优化:考虑对答案的贡献,发现状态这么具体没用,只需要记录\sum h_i (val_i - val_{i+1})

[ZJOI2017]线段树

根据套路,线段树查询到的点,就是-1,+1到根的右/左儿子。(zkw那个)

于是树上维护一个点到根的信息,这个是可减的。分类讨论即可。

[ZJOI2019]线段树

每次进行线段树的复制,维护个数比较烦,考虑维护概率。那么一个点有三种情况:有值,祖先有值,祖先无值。

一个点有四种被影响的可能:在查询路径上,被覆盖,是被覆盖的孩子,是某个路过点的另一个儿子。矩阵维护。

[AGC036]D

无负环->最短路存在->每个点有一个距离->存在一些i或者符号相反的东西->差分之后,区间和\leq 1, \geq 1->观察发现差分数组只能是0/1 ->设计DP,f_{i,j}表示最后两个1的位置。

冷静分析一下,f_{i,j}f_{j,k}转移来。那么j,k之间的,以及一段在k,j,一段在i,n的一些可以留下。二维前缀和。

HDU6427

首先恶补一下置换套路:一个环旋转和翻转是独立的。因为如果先旋转再反转或者反过来这样,可以化简为一次翻转。

这个题又要移动又要做上面的操作,可以考虑分开求。总置换数是2nm

考虑翻转+移动:

如果n是奇数,不能移动,可以在顶点上转。

如果n是偶数,并且在顶点上转,那么不能移动。否则如果m是偶数,可以转m/2

考虑旋转+移动:

转了,动了分别i,j次。旋转次数是lcm(i,n)。移动循环节是lcm(j,m)

那么必须有lcm(j,m) | lcm(i, n)

所以式子是\sum_{i \leq n} m^{gcd(n,i)} \sum_{j \leq m} [lcm(j,m) | lcm(i, n)]

CF1286F

序列上两个点一起操作,考虑连边。那么发现对于树,可以节省一次操作。问题就是划分成尽可能多的树。

考虑一棵树:先假装没有+1的操作。把点划分为两组,如果它们的差为0,那么一定可以,接在一起就行了。加上+1后,可以加减不超过n,并且奇偶性要相同。

之后做一个DP就好了。用一个玄学剪枝:只通过枚举不能被表示的集合转移。速度会非常优秀。

循环之美

主要是记录一个Trick:推式子的时候在恰当的时候,把式子中的一部分用函数表示,可以大幅度减少工作量。

还有,就是注意观察有没有重复出现的部分。如果有,可以设函数递归。

怎样跑得更快

不可以高斯消元的话,考虑反演。还是上面那个话:恰当的时机,表示为函数。

Gosha is hunting

WQS可以套WQS

好图计数 / Count

本题用到的方法和有根树计数是类似的。

考虑令f,g分别表示不要求联通,一定联通的方案数。冷静一下可以发现g=f/2。那么考虑计算f。令生成函数F,考虑计算。

F(x)=\prod_{k \geq 1} (\sum_{i\geq 0} x^{ki})^{g_k} =\prod_{k \geq 1} (1-x^k)^{-g_k}

这个式子的含义,是考虑集合的划分,划分为若干联通子图。里面的\sum考虑了选几个,外面的幂给出了方案数。

求对数再求导:

\frac{F'(x)}{F(x)} = \sum_{k \geq 1} g_k \frac{kx^{k-1}}{1-x^k}

[x^n]F'(x) = (n+1)f_{n+1}=...

后面的...是一坨卷积,最高次是n。那么就可以推出来f_{n+1}

Serval and Bonus Problem

实数上瞎选,可以看做等分线段后离散的做。

显而易见的数论

不会做,就是记一下,$\sum (i,n)=1$是积性的。

文艺计算姬

考虑prufer序列,因为是二分图,考虑式子:\sum_l + n = \sum_r + m,\sum_l + \sum_r = n - 2。就可以解出\sum是多少了。快速幂即可。

CF453E

每次修改,区间推平的操作,线段树维护,复杂度是很好的。

CF833D

两个数的比在0.5,1之间,可以转化为小的比大的在,进一步转化为互相的二倍关系

毒瘤

虚树树形DP,考虑链的贡献,把一个点表示为af0+bf1,可以向上推

CF1363F

冷静分析一下:题目中的旋转操作的实质,就是选一个数,从后面丢到前面。

那么考虑如何匹配:首先后缀的lcs是可以删掉的。删掉后的两个串的尾,是不同的。

那么考虑把s的尾巴拿起来,丢到前面。之后继续匹配。假设不同的位置是i,那么就是要求S_{i-1},T_i需要多少次才能匹配。此处的匹配就是可以空位置的匹配。显然空位置匹配后,丢进去就行。

那么考虑令f_{i,j},表示S_{1,i},T_{1,j}匹配需要多少次。显然此处i \leq j。考虑转移:

i拿起来,让剩下的匹配,再把i找个位置丢进去:f_{i,j}=f_{i-1,j}+1

如果两个位置相同,直接匹配:f_{i,j}=f_{i-1,j-1}

考虑c=T_j,如果在S_{1,i}出现次数更少,那么可以从后面移动一个c到前面匹配jf_{i,j}=f_{i,j-1}这里没有加,是因为这里的从后面移动相当于后面的向前丢,是匹配的,只在后面计算就可以了。

美团杯部分题解

半前缀计数

考虑如果两个串是本质相同的:那么一定是s,t有一些公共部分。考虑在s_{i+1}!=t_1的位置统计答案。SAM维护。

平行四边形

直接上原根。

114514

发现4前面一定是1,贪心匹配一波。就转化为了求1A5A。按顺序扫,遇到1加一个新的,遇到A优先匹配1

汉明距离

考虑一个随机游走问题:数轴上正负走n次后,期望距离的平方是什么。列一个DP式子,可以发现,走n次的期望是n。

考虑随机一个数列,权值为+-1。考虑对输入的序列和它点积一次,原序列点积一次,求一下两个值差的平方。发现和上面那个问题是等价的,所以期望就是题目所求的东西。多随机几个打个表就行了

版本答案

热动分析一下:不可能一方同时有两个没盾的。于是考虑DP,记录双方活着几个,进攻的有没有盾,防御的是否存在没盾的。手推一下,发现一些转移有环。解方程可以解出来

AGC001F && [HNOI2015]菜肴制作

一类为拓扑序标号的问题。综合思想:正序拓扑最小,等价于拓扑反序后最大,反序后贪心。证明大约和某种对偶性质有关?

回到AGC的题:j-i \geq K, |P_i - P_j| = 1,建立反排列Q后得到:Q_j - Q_i \geq K, |j - i| = 1。就是相邻的。

那么考虑如果两个数满足小于,永远不可能交换顺序。其它的都可以换。

于是回到原题,就是向周围K个内满足某种条件的连边。之后跑拓扑标号。

冷静分析一下优化复杂度:拓扑排序->入度为0->入度为0的条件是它是区间极值->用堆维护点,优先取出靠后的,线段树上删掉->检查左右两边最大的点,并检查这些点是否是区间极值,插入堆。

CF446D

看到高斯消元就蛋疼。。考虑钦定一个起点,求走到其它点的概率。那么令f_i表示这个概率,f_i就等于从挨着的点走过来的概率和。特别的,i=s的时候,加上1

考虑如何设置起点:我们要求从一个黑点走到另一个黑点的概率。那么考虑先从这个黑点走出来,再走。那么周围的点各获得一个度数的概率。

  1. 头像 cbio说道:

    第二道实际上题号是D

  2. 头像 cbio说道:

    原来是c开始编号的。。/kk

发表评论

电子邮件地址不会被公开。必填项已用 * 标注