link

Day1

因为2号点的父亲一定是1号点,所以可以把nn个点的树拆分成2号点的子树2号点子树外的部分

这是相互独立且比原问题规模更小的两部分,因此可以进行DP。设f(i,j)f(i, j)表示ii个点度数为jj的方案数,讨论两部分谁深度更大,再枚举另一部分的深度,方案数相乘即可

复杂度O(n4)O(n^4)除大常数,很优秀

仙人掌

若是树,则f(i,0/1)f(i, 0/1)表示考虑完ii子树,ii是否连向父亲的方案数。

20-5-16

发现是把所有儿子直接卷起来,可以分治 + NTT优化

对仙人掌建出圆方树,目的是把原图中所有环都拉出来并破环为链,大概呈现出这样的结构:

20-5-16-1

于是可以DP,g(i,0/1)g(i, 0/1)表示考虑到环上第ii个点(从sstt),第ii个点是否向i+1i + 1连边的方案数

先枚举AAss是否有边以确定初始状态,然后依次转移,最后通过g(t,0/1)g(t, 0/1)转移到AAff数组上。

因为AA最多可以往下连两条边,所以把ff定义改一下,改成f(i,0/1/2f(i, 0/1/2表示ii点已经被钦定连出去0/1/20/1/2条边的方案。若为树,则只有0/10/1

ff依然可以 分治 + NTT 优化

link

Day2

农民

把一个点看成一个限制,它左子树的点权都要小于它,右子树都要大于它。可以用树链剖分 + 线段树维护这个限制

线段树上维护这个dfs序对应点的重儿子的限制,树剖的时候把区间的限制合并。从轻儿子跳父亲的时候直接把该轻儿子的限制合并即可

对于翻转操作,只需在线段树上同时维护相反的限制(同样也需要合并)。需要翻转的时候交换一下该点当前限制相反限制即可

颜色

分块 + bitset。用ST表预处理块到块的信息

操作

有点神仙。暴力贪心是每次从左往右贪,考虑在差分数组上优化

先不考虑区间端点的问题,那么就是每次把两个距离为kk的差分一起取反,最后将差分全变成00

在模kk意义下考虑,从左往右,模kk意义下位置最近的两个11两两匹配,位置差除kk之和即为答案。若模kk意义下某个值有奇数个差分则不合法

直接模拟是O(nm)O(nm)的,考虑预处理,用前缀和优化

每种差分个数是不是偶数可以把每个值随机赋权,看区间异或值来判断

答案的前缀和可以每次在新加进一个11时,直接把模kk与其相同的位置的答案加个符号,再加上这个位置的值,再加到前缀和中

因为保证了模kk为每种值的11差分都是偶数个,所以前缀和直接相减即为答案

左右端点要特殊处理一下,注意要处理右端点 + 1那个位置

Day4

Cube

f(n,m)f(n, m)表示答案,那么f(n,m)=f(n1,m1)+2×f(n1,m)f(n, m) = f(n - 1, m - 1) + 2 \times f(n - 1, m)

打表找规律发现答案为2nm×(nnm)2^{n-m} \times \binom{n}{n - m}

Divide

好巧妙的题,我又不会做

把权值升序排序,若w1+wnw_1 + w_n配合默契,那nn1n11 \sim n - 1都能配合默契,把nn删除递归处理;否则112n2 \sim n都不能配合默契,把11删除递归处理

把每次删除的数倒序取出后,一个数前面的数要么都能和他配合默契,要么都不能

于是可以DP了,f(i,j,0/1)f(i, j, 0/1)ii个数AA组有jj个的最大配对值/方案,简单转移即可

Magic

容斥,求钦定kk个魔术对的方案。普通的容斥是只考虑钦定的kk个元素,其他元素随便选,但这里需要考虑所有元素,否则难以统计

若某种颜色的数总共有aa个,在序列中被分成了bb段,则会形成aba - b个魔术对(就像是蛋白质和肽键的关系233)

从这个角度出发计数,颜色ii钦定kk对也就是形成aika_i - k段。而不好保证这些段一定不相连,所以要容斥

f(i,j)f(i, j)表示前ii种颜色,分成至少jj段(相邻段不一定颜色不同)的方案数

f(i,j)=k=0aif(i1,jk)×(ai1k1)(jk)\displaystyle f(i, j) = \sum_{k = 0}^{a_i} f(i - 1, j - k) \times \binom{a_i - 1}{k - 1} \binom{j}{k}

左边的组合数是插板算该颜色分段情况,右边的是把kk个段插到之前的所有段中

把右边那个组合数拆开之后有

f(i,j)j!=k=0aif(i1,jk)(jk)!×(ai1k1)k!\displaystyle \frac{f(i, j)}{j!} = \sum_{k = 0}^{a_i} \frac{f(i - 1, j - k)}{(j - k)!} \times \frac{\binom{a_i - 1}{k - 1}}{k!}

ii种颜色的生成函数F(i)=k(ai1k1)k!xk\displaystyle F(i) = \sum_k \frac{\binom{a_i - 1}{k - 1}}{k!} x^k,答案就是iF(i)\displaystyle \prod_i F(i)

分治 + NTT就好了

Day5

Convex

莫队。在凸包上插入点必须二分,而删除 + 撤销很简单,直接链表维护可做到O(1)O(1)

回滚莫队

Day7

A

与操作相当于把某些二进制位置,或操作相当于把某些二进制位置1

势能分析线段树。 对每一个需要操作的位单独考虑,若区间中的数字该位不完全相同,则递归;否则变成区间加减操作。看上去复杂度就非常对,因为每次暴力递归完后该区间这一位上的数就相同了

具体实现上不需要把位拆开。判断区间某位上的数是否相同可以通过维护区间的min\minmax\max来判断

B

因为(a,n)=1(a, n) = 1,所以 [0,n)[0, n)的排列不断重复

考虑Ti=1T_i = 1的情况,若Sp+iTiS_{p + i}\ne T_i,则有

Sp+i[0,c)Sp[0ai,cai) \begin{aligned} S_{p + i} &\in [0, c) \\ S_p &\in [0 - ai, c - ai) \end{aligned}

Ti=0T_i = 0的情况同理。 注意上述的区间是模意义下的, 实际上可能对应着一个或两个区间

TT每一位的限制放到线段树上维护即可

C

Day 8

A

最小树形图

Day 10

足球大战

ans=i=1npi(1p)ni(ni)j=0i1qj(1q)nj(nj) ans = \sum_{i=1}^np^i(1-p)^{n-i}\binom{n}{i}\sum_{j=0}^{i-1}q^j(1-q)^{n-j}\binom{n}{j}

文明

统计无法被占领的点数。无法被占领的点一定是以a1a_1为根时的一些子树

具体而言,另每个aia_ia1a_1路径的中点为关键点。以a1a_1为根时,若某个关键点到根的路径上没有其他关键点,则答案加上它的子树

先树剖找中点,后半部分可以用虚树或线段树实现

贪玩蓝月

双栈维护背包。但在此题中,若某个栈为空并不能直接把另一边的所有元素都倒过来,不然每次左右各删一个复杂度就错了。但是可以每次倒过来一半,总复杂度乘一个log\log

这题还有一个难点,如何快速求[l,r][l, r]的DP值的max\max

枚举左栈的特征值ii,此时右栈的特征值可行范围是一个区间(注意处理模意义下的问题)。当左栈变为i+1i + 1时,右栈可行的区间左右端点都+1

双端队列维护滑动窗口

Day11

进攻

考虑每个单位格子的贡献。统计有 ss 个全 11 矩形覆盖它,那么将 sks^k 加入答案

显然会算重,考虑一个神奇的容斥:统计包含至少1×11 \times 1的矩形的方案(即上述方案),减去1×21 \times 2,减去2×12 \times 1的,加上2×22 \times 2

对于最终矩形交的一个aba * b矩形而言,它总共会被统计a×b(a1)×b(b1)×a+(a1)×(b1)=1a \times b - (a - 1) \times b - (b - 1) \times a + (a - 1) \times (b - 1) = 1

接下来考虑统计方案数,以1×11\times 1的为例

差分,对于一个矩形,在它四个角进行+1/-1操作。换个视角看,也就是对每个格子统计有多少矩形以它为左上角/左下角/右下角/右下角,再进行加减。转化后的问题直接对每一列单调栈计算即可

字符串

猜的做法,写了5.4K,没想到对了

设序列pp表示把合法的gg排序后的数组,则答案为(L2)(pi+1pi12)\displaystyle \binom{L}{2} - \sum \binom{p_{i + 1} - p_i - 1}{2}

考虑Trie + 莫队,插入/删除一个串时暴力把它所有前缀的权值加上/减去它的vv并判断是否对gg产生影响

动态(插入/删除)维护上式需要用set找前驱后继,复杂度带log\log,考虑回滚莫队,用链表串起来,只用删除和撤销就行了