11月杂题

1.10.30D/qoj6794 Sequence to Sequence

先观察到我们一定是先减后加。因为对于一个数 +1 -1 一定不会改变，但 -1 +1 就会有改变。那对于相邻的 +1 -1 操作，如果不交就直接交换；否则把相交的部分直接删掉，那要么删成两个 +1 ，要么成两个 -1 ，要么是不交的 +1 -1 。

如果我们指定一个数减的次数 \(d_i\) ，那加的次数就是 \(g_i=d_i+t_i-s_i\) 。然后操作次数就是 \(\sum \max(0,d_i-d_{i-1})+\max(0,g_i-g_{i-1})\) 。但是这个没有考虑 \(t_i=0\) 的情况，考虑一个极长的 \(t_i=0\) 连续段 $[l,r] $ 中 \(s_i\) 的最大值为 \(m\) ，若 \(m<\max(d_{l-1},d_{r+1})\) ，则费用还要加上 \(\max(d_{l-1},d_{r+1})-m\) 。

我们就能由此设计一个简单 dp 计算答案，即记下来末尾的 \(d_i\) ，复杂度 \(O(nV^2)\) 。考虑优化，猜测这个 dp 数组是凸的；进一步发现，它能分成三段，一段斜率为 \(0\) ，一段斜率为 \(1\) ，一段斜率为 \(2\) 。于是维护折点即可，复杂度 \(O(n)\) 。

具体转移：https://drops.dagstuhl.de/opus/volltexte/2016/6078/pdf/LIPIcs-CPM-2016-16.pdf

2.10.26D

算矩形个数可以算多少个 \(2*2\) 小方格里黑格子个数为 \(1\) 或 \(3\) 。

3.10.26B/P3776 [APIO2017] 斑斓之地

平面图联通块计算：\(C=V-E+F-1\) 。算 \(V\) 和算 \(E\) 都是容易的，而对于 \(F\) ，我们只需统计 \(2*2\) 小方格全黑的位置个数即可，因为这两个题都保证空腔的个数 \(\le 1\) 。剩下的就都好做了。

4.互测 1A

还是不会。差距。

5.topcoder13460 FrozenStandings

就是 AGC061C ，为啥看了半天才看出来？

6.P9257 [PA 2022] Mędrcy

先来翻译一下题意，对一个咒语我们连边 \((u,v)\) ，那我们考虑贤者 \(x\) 是怎么思考的：就是他一开始只知道不与他相连的边，设 \(f(G)\) 是 \(G\) 这个图第一次有人紫砂的天数，那如果到 \(f(G-\{x\})+1\) 天还没有人紫砂，就说明存在 \(x\) 不知道的边，\(x\) 就紫砂了。所以 \(f(G)=1+\min\limits_{x\in V} f(G-\{x\})\) 。特别的，对于 \(E=\emptyset\) 的图我们有 \(f(G)=0\) 来满足定义。

再看看上面的定义，发现就是删去最少的点使剩下的子图是独立集。考虑进行搜索，找到度数最大的点 \(x\) 并枚举我们是否要删去它。如果不删 \(x\) ，与它相邻的点都要被删。注意到 \(d_x\le 2\) 时我们能直接计算出答案，不需要再搜索。这个题就做完了。原因是，设 \(f(k)\) 是对答案限制为 \(k\) 的图至多要递归的次数，我们有 \(f(k)=f(k-1)+f(k-3)\) ，而 \(f(30)\) 大概是 \(10^5\) 级别的。

7.CodeChef Find a special connected block

如果颜色数少就是斯坦纳树。

神来之笔：考虑把这些颜色随机划分，即对每个颜色赋一个 \([0,k)\) 的权值，把这个权值当成新的颜色来跑。如果每个集合都有至少一个最优解中出现的颜色，那就 win 了。

考虑这样算一次正确的概率，就是 \(\frac{k^k}{k!}\) 的， \(k=7\) 时大概是 \(\frac{1}{164}\) 。这个题就做完了。

8. CF1089H Harder Satisfiability

先建出 2-SAT 的图，对每个限制 \(a\or b\) ，连边 \(!a\rightarrow b\) 和 \(!b \rightarrow a\) ，如果这个时候有矛盾就直接 G 了。

然后考虑讨论 \(x_n\) 的符号和与它相关的限制，然后将式子递归到只剩 \(n-1\) 个数。如果 \(x_n\) 前面的符号是 \(\forall\) ，那考虑与之相关的限制，你发现对于 \(i<n\) ， \(x_i\) 的值直接被指定了。否则的话就无所谓啊。通过 \(i-n,j-n\) 得到的 \(i-j\) 限制已经通过 2-SAT 的图处理出了，所以直接递归下去就行了。

总结一下上面的过程。就是如果存在一个 \(a\rightarrow b\) 的限制 \((a<b)\) 且 \(b\) 符号是 \(\forall\) ，我们就能得到 \(x_a\) 的值。如果 \(a\) 符号也是 \(\forall\) 就直接无解了，体现在 2-SAT 图上，就是 \(a,!a\) 和 \(b,!b\) 两两不可达。否则，你发现把上面两个条件判掉后，对一个 \(a\) 只存在至多一个这样的 \(b\) 。那我们看 \(a\) 是否和 \(b\) 或 \(!b\) 在一个 SCC 即可。就做完了。

9.互测 2A

自个做出来的捏。考虑值域是纸老虎，算出 \(dp_{i,j}\) 为：长度为 \(i\) 有 \(j\) 个不同的数的本质不同序列个数，最后计算 \(\sum\tbinom{m}{i}dp_{n,i}\) 即可。考虑转移，就是枚举最大值位置，有多个最大值就钦定是第一个最大值。考虑左边有 \(a\) 个本质不同的数，右边有 \(b\) 个不同的数，然后把这三个部分拼起来，为了满足题目限制，只有两个地方可能拼起来，即：左 max 与右 min ，右 max 与 max 。这个就做完了。

10.互测 3A

自个做出来的捏（！！！）。

考虑二项式反演，钦定一些位置有 \(p_x<p_{x+1},p_y^{-1}<p_{y+1}^{-1}\) 。考虑此时填排列的方案数怎么算，现在 \(p\) 和 \(p^{-1}\) 都形成了一些链，考虑 \(p\) 中第 \(i\) 条长度为 \(x_i\) ，\(p^{-1}\) 中第 \(j\) 条长度为 \(y_j\) ，那方案其实就是构造矩阵 \(A\) 使得行和为 \(x\) ，列和为 \(y\) 的方案数。这是不可做的，但你考虑每个满足：一个前缀行和 \(>0\) 且一个前缀列和 \(>0\) 的矩阵都唯一对应了一个 \(p,p^{-1}\) 的钦定方式。

记 \(f_{i,j}\) 表示 \(i\) 行 \(j\) 列这样的矩阵个数。则 \(g_{i,j}=f_{n-i,n-j}\) 表示 \(p\) 中钦定 \(i\) 个位置，\(p^{-1}\) 中钦定 \(j\) 个位置的总方案数。有 \(ans_{i,j}=\sum\tbinom{i_2}{i}(-1)^{i_2-i}\sum\tbinom{j_2}{j}(-1)^{j_2-j}g_{i,j}\) 。这是二维卷积，可以直接 \(O(n^3)\) 。

然后考虑 \(f_{i,j}\) 的计算，直接容斥：\(f_{i,j}=\sum\tbinom{i}{i_2}(-1)^{i-i_2}\sum\tbinom{j}{j_2}(-1)^{j-j_2}\tbinom{(i-i_2)(j-j_2)+n-1}{n-1}\) 。还是二维卷积，可以直接 \(O(n^3)\) 。

11.互测 3B

维护点 kruskal 重构树，每次连边 \((x,y)\) 要做的是，令路径上最大点为 \(a\) ，我们把 \(x\) 到 \(a\) 和 \(y\) 到 \(a\) 归并起来。令 \(x<y\) ，我们找到 \(x-a\) 中最大的 \(\le y\) 的数 \(e\)，割掉 \((e,fa_e)\) ，连边 \((e,y)\) ，再递归做下去。

这是容易用 LCT 维护的。然后可以证明， 这样总操作次数不超过 \(O(n\log n)\) ，所以复杂度为 \(O(n\log^2n)\) 。

12.互测 3C

13.CF1895G Two Characters, Two Colors

维护 dp 数组的差分数组，假装它是上凸的，然后就有两种操作，一种是前缀减 \(1\) ，一种是插入 \(a\) 。你发现第一种操作会导致不是上凸的了。但你考虑此时凹的地方，比如 \(dp_i=a,dp_{i+1}=a+b,dp_{i+2}=a+2b+1\) 。那直接把 \(dp_{i+1}\) 改成 \(a+b+1\) 是不影响答案的，证明就是看 \(dp_i-ix\) 是怎么取到的最大的。

于是我们在减 \(1\) 时，把分界点左边的一段 \(X\) 和右边的一段 \(X+1\) 交换即可。

14.CF1895F Fancy Arrays

考虑确定了 \(a_i-a_{i-1}\) 后的最低点，那如果 \(x=0\) ，最低点在 \([0,k-1]\) 就是合法的。总方案数即 \(k(2k-1)^{n-1}\) 。\(x>0\) 时，最低点在 \([0,x+k-1]\) 在大多数时候都合法，除了全部 \(<x\) 的情况，原因是，若只有 \(<x\) 的数和 \(\geq x+k\) ，那肯定有一处差 \(>x\) 。就做完了。

15.gym102341B Bulbasaur

考虑最大流转最小割，转化为：删掉最小的点使两端不连通。

考虑已知了两端 \(l,r\) 该怎么做，就是 \(dp_{s,i}\) 表示考虑到第 \(i\) 层，当前与左端连通的点集是 \(S\) 需要删的最小点数。现在需要计算所有子段的权值和，考虑枚举 \(r\) ，同时我们发现上面的 dp 费用一定 \(\le k\) ，且随着层数的增加费用会越来越小。

\(k\) 非常小，于是交换一下值域和状态，设 \(dp_{s,c}\) 表示至多 \(c\) 次删点能使 \(r\) 层的状态是 \(s\) 的最大 \(l\) 。这样就做完了，复杂度 \(O(n2^kk^2)\) 。

16.gym102900F Fountains

把每个区间 \([l,r]\) 按 \(C(l,r)\) 从大往小排序，则每次加入一个区间，相当于把 \(1\le x\le l,r\le y\le n\) 的区间 \([x,y]\) 染成黑色，如果一个格子从白变黑了，就把权值加上 \(C(l,r)\) 。

于是有一个 \(dp_{S,i,j}\) 表示当前染色的状态为 \(S\) ，考虑到了第 \(i\) 个区间，选了 \(j\) 个区间的最大权值。

我们把 \([x,y]\) 看成一个格点 \((x,y)\) ，发现黑白之间的分界线就是一个从左下往右上的路径，每次只能向上/向右。所以可能的 \(S\) 个数不超过 \(4^n\) 。

17.CF1292F Nora's Toy Boxes

考虑如果 \(a_i|a_j\) 就从 \(i\) 往 \(j\) 连一条边，然后考虑每个弱联通块。首先入度为 \(0\) 的点肯定不会被删掉，而且对于每次操作 \((i,j,k)\) ，如果 \(i\) 入度不为 \(0\) ，我们可以调整为入度为 \(0\) 的。

除了入度为 \(0\) 的点，剩下的点中至少会剩一个。我们说明可以取到这个下界：考虑倒着来加点，如果有一个入度为 \(0\) 的点能到达某个新加的点，我们称它被激活了。设当前激活的集合是 \(S\) ，新加的点 \(x\) 能激活的点集合为 \(P_x\) ，则 \(S\cap P_x\) 非空。我们每次一定能找到这样的 \(x\) ，否则图就不是弱连通的了。

现在考虑计数，其实直接按上面的过程来做就行了。而入度为 \(0\) 的个数是 \(\le 15\) 的，原因是：若存在一个点 \(>30\) ，那它一定是孤立点，不用管；否则考虑把 \(1\) 到 \(30\) 表示成 \(a2^b\) 的形式 (\(a\) 是奇数) ，\(a\) 相同的数显然不能同时取。不同的 \(a\) 只有 \(15\) 个。

18. TopCoder 13792 Brainstuck

你发现每走出一个括号当前数就要清零。考虑当前数是 \(x\neq 0\) ，进入一对括号会发生什么。case1:这个括号内还有括号，那我们必须要走完一轮后 \(x=0\) ，否则 \(x\) 永远都不会为 \(0\) 。case2:没有括号，就是看这个部分的增量 \(k\) 是否满足 \(-\frac{x}{k}>1\)。

于是记 \(f_{i,j}\) 表示当前 \(x=j\) ，走完一遍后 \(x=0\) 的方案数。转移是容易的。最后要算合法串个数，就是考虑计算 \(g_j\) 是长度为 \(j\) 且末尾是右括号的方案数，这个可以结合 \(f\) 容斥算出，最后统计 \(\sum g_i2^{n-i}\) 即可。

19.UR26 B

20.UR26 C

21.互测 5B

就是分类讨论，傻逼题。

22.互测 5A

前面的步骤都很唐，但是最后一步卡常很妙。就是每个节点要维护 \(O(\log V)\) 个大小为 \(O(\log len)\) 个二进制数，这是不优的，考虑车一转，变成维护 \(O(\log len)\) 个 unsigned long long 。这样建树复杂度就从 \(O(n\log V)\) 变成 \(T(n)=2T(\frac{n}{2})+\log n=O(n)\) 的了。

23. gym101190C Cactus Construction

考虑建出圆方树。现在对于 \(x\) ，我们依次处理它的方儿子 \(o\) 。遍历 \(o\) 的儿子 \(v\) ，先递归构造 \(v\) 子树，要求它最后形如：\(c_v=1\) ，其它点都等于 \(4\) ，且子树内的边已经连完。

然后考虑，如果 \(o\) 代表的点双是一条边，那把 \(v\) 染成 \(2\) ，合并 \((x,v)\) ，连 \((1,2)\) ，再把 \(v\) 染成 \(4\) 即可。

如果是一个环，那依次连环上的边。设第一个点是 \(v_0\) ，则先染 \(v_0\) 为 \(2\) ，合并，连 \((1,2)\) ，然后顺次加入后面的点 \(v\)，如果上一个点颜色为 \(c\) ，则染 \(v\) 为 \(5-c\) ，合并，连 \((2,3)\) ，再染 \(c\) 为 \(4\) 。另则同理。再对环上最后一个点，如果颜色为 \(c\) ，就连 \((1,c)\) 并染 \(c\) 为 \(4\) 。

这样就完成了构造。

24. gym102059B Dev, Please Add This!

考虑每行/每列上的一些极长的空地，如果我们某个时刻停在其中一端，则我们能通过往返操作吃完上面的星星。所以考虑对把每个连续段建成点，然后对于一个横段，往外连两条边表示它两端的格子对应的竖段。则现在我们要从一个固定的起点出发，在这个图上游走。考虑每个星星能被吃到，当且仅当包含它的竖/横段中有至少一个走到了。

于是尝试 2-SAT 解决，设 \(x_u\) 表示一个点是否被走到，则一个星星对应了 \(x_u=1\) 或 \(x_v=1\) 的限制；而不能从起点走到的点一定有 \(x_u=0\) ；如果 \(u,v\) 互不能走到 ，那 \(x_u=0\) 或 \(x_v=0\) 。而现在我们说明，如果这个 2-SAT 有解，那原题也有解。首先这肯定是必要的；其次，考虑此时所有 \(x_u=1\) 的点，对它们建立一张新图，如果 \(a\) 在原图上能到达 \(b\) 就连一条 \(a\rightarrow b\) 的边，把 SCC 缩起来后就形成了一张竞赛图，然后要从一个固定的起点出发（且这个起点入度为 \(0\)）走哈密顿路。

这是一定有解的：首先能去掉原来的起点，变成选择一个起点出发。然后考虑归纳构造：先构造出 \(n-1\) 个点时的哈密顿路，然后加入点 \(n\) 。不妨设 \(n-1\) 时造出的路径形如 \(1\rightarrow 2\rightarrow3\dots \rightarrow n-1\) ,设当前边方向为 \(i \rightarrow n\) 则 \(x_i=0\) ，否则 \(x_i=1\) 。如果我们能找到 \(x_i=0,x_{i+1}=1\) ，或者 \(x_1=1\) 或者 \(x_{n-1}=0\) 就能插入 \(n\) 。如果此时不能插入 \(n\) ，那 \(x_1=0\) 。由于找不到 \(x_i=0,x_{i+1}=1\) ，那其余点 \(x_i\) 皆为 \(0\) 。但又有 \(x_{n-1}=1\) ，矛盾！

于是我们证明了这个结论。

25.P9194 [USACO23OPEN] Triples of Cows P

模拟赛的时候一直在想咋直接维护 \(\sum \tbinom{ru_i}{2}\) ，从而卡死了。就，这个题需要一些转化。搞一个新图，我们新建 \(n-1\) 个点，每个新点代表一条边，连接它的两个端点，然后每次删除点 \(u\) 相当于让当前与 \(u\) 相连的新点合并，并删掉 \(u\) ，此时两个点 \(u,v\) 有边，当且仅当它们中间隔了恰好一个新点。不妨以 \(n\) 为根，每次删除就可以当做是：把 \(u\) 的所有儿子合并进 \(u\) 的父亲。统计答案就是分类讨论，维护维护捏。

26.gym104128L Proposition Composition

27. CF1416E Split

28. ucup 2-8 A

29.CF1835D Doctor's Brown Hypothesis

来写一写这个经典问题吧。首先能对每个 SCC 单独求。

然后，在模 \(p\) 意义下若有一条从 \(u\) 到 \(v\) 的长度为 \(w\) 的路径，则一定存在一条 \(v\) 到 \(u\) 的长度为 \(-w\) 的路径，原因是我们任取一条从 \(v\) 到 \(u\) 的路径，从 \(v\) 出发绕 \(p-1\) 圈再走向 \(u\) 即可。

现在考虑求出所有环长的 gcd 为 \(d\) ，考虑 \(p|d\) 的充要条件：每对 \(u,v\) 之间的路径长度在模意义下是唯一的，因为两条长度为 \(a,b\) 的路径一定会得到一个 \(a-b\) 的环。

所以取一个 dfs 树求出深度 \(dis_u\) ，有 \(d=\gcd dis_v-dis_u-w\) 。然后在模 \(d\) 意义下，\(u\) 到 \(v\) 模意义下为 \(k\) 的路径，等价于 \(dis_u+k=dis_v\) 。这样就做完了。

30.互测 7A

场切喵。对每个值 \(x\) 分别考虑，看能有多少次 skip 掉 x 。把 \(<x\) 的看成 \(0\) ,\(>x\) 的看成 \(2\) ，\(=x\) 的看成 \(1\) 。找出第一个 \(2\) ，则在它前面的 \(1\) 才是有效的。但还有可能，这些 \(1\) 会被拿去填 \(2\) 后面的 \(0\) 。现在需要算每个区间的答案。还是像上面一样处理，把右边第一个 \(2\) 相同的 \(1\) 一起考虑：对于从右往左第 \(i\) 个 \(1\) 为 \(X\) ，找到 \(2\) 右边第 \(i\) 个 \(0\) 的位置 \(Y\) ，再设它左边第一个 \(2\) 位置在 \(P\) 。则我需要 \(P<l\le X\le r<Y\) ,这个 \(X\) 才会起贡献。二维数点即可。

31.互测 7B

好牛逼啊。首先“每个集合非空”可以用容斥解决，我们算出 \(g_i\) 表示使用 \(i\) 种颜色染色，使相同颜色的点距离 \(\geq k\) 的方案，然后一遍卷积即可得到原答案。

接下来考虑链的情况，从左往右依次染色，注意到染 \(u\) 时若存在两个前面的点满足 \(dis(u,v_1)<k,dis(u,v_2)<k\) ，显然有 \(dis(v_1,v_2)<k\) ，于是直接统计 \(c_u\) 表示前面的点中满足 \(dis(u,v)<k\) 的个数，则 \(g_m=\prod \max(0,m-c_i)\) ，多点求值即可。

再考虑树，发现按 dep 从小往大染色即可得到相同的结论！点分治计算 \(c\) 即可。多点求值和 点分治+BIT 都是 \(O(n\log^2 n)\) 的。

32. 互测 5C