2026.1

2026.1

P3526

还是周期性领域大神。

题目要求我们生成周期性相同的 \(01\) 串。

若 \(|s|=1\)，生成一个 \(0\) 好了。

否则你就考虑 border，没有 border 的 \(s\) 可以生成一个 \(0000\cdots 1\)。

若 border 大于 \(\frac{|s|}{2}\)，递归到 \(|s|\) 为 border 的子问题，然后直接复制剩下的位置就好了。

否则记你用 border 生成的串是 \(t'\) ，那你最后直接生成一个 \(t'at'\) 状物。然后这个 \(a\) 是 \(0000\cdots 0\) 或者 \(0000\cdots 1\) 。

证明太几把难了。不管了。

哥伦比娅我喜欢你awa，同学分享，放了几个计数题。

P11421

显然我们有一个基于栈的 \(O(nm)\) 做法。

不难想到对每个颜色都做括号匹配。如果我们将左括号看作 \(1\)，右括号看作 \(−1\)，那么失配的右括号就是 \(<0\) 的前缀最小值的位置。

由于单次失配位置的变化量为 \(O(1)\)，用线段树暴力维护即可。

CF1770F

好难啊，怎么还是有人场切 /jk 。

首先由对称性，知 \(n\) 为偶数是答案为 \(0\)，\(n\) 为奇数时答案为所有满足条件的序列的 \(a_1\) 的异或和。考虑拆位，对每一位 \(i\) 计算 \(a_1\) 这一位为 \(1\) 的方案数。

记 \(f(y)\) 表示按位或为 \(y\) 的子集的方案数。容斥，有答案为 \(\sum_{y'\sube y}(-1)^{|y|-|y'|}f(y')\)，只关心奇偶性，所以是 \(\bigoplus_{y'\sube y}f(y')\)。

牛逼的来了，逆用 lucas 定理，有 \([a_i\sube y']=\binom{y'}{a_i}\bmod 2\)。

由范德蒙德卷积，

\[\begin{aligned} f(y')&=\bigoplus_{\sum a_i=x-2^i}[a_1\sube(y'-2^i)][a_2\sube y']\cdots[a_n\sube y']\\ &=(\sum_{\sum a_i=x-2^i}\binom{y'-2^i}{a_1}\binom{y'}{a_2}\cdots\binom{y'}{a_n})\bmod 2\\ &=\binom{ny'-2^i}{x-2^i}\bmod 2\\ &=[(x-2^i)\sube (ny'-2^i)] \end{aligned}\]

枚举 \(i\) 和 \(y'\) 算答案即可。复杂度 \(O(y\log y)\) 。

P14718

发现从大到小直接选数是对的。

问题变成了加入一个数，判断匹配是否存在。考虑 Hall 定理。

对于答案集合 \(S\) ，合法当且仅当 \(\forall T\sube S,|T|\le|\bigcup_{x\in T}[l_x,r_x]|\)，有 \(R-L+1-\sum_{x\in S}[L\le l_x\le r_x\le R]\ge 0\) ，每次加入相当于修改 \((l_x,r_x)\) 左上角对应的矩阵。每行开一个线段树，每次 \(O(1)\) 判断能否加入即可。

总复杂度 \(O(n^2 \log n)\)。

QOJ6842

对询问建立 AC 自动机。一个点的答案为 fail 树的子树经过次数和。

记 \(w(l,r)\) 为 \([l,r]\) 形成的子串。记 \(W(n,0)\) 为 \(w(0,2^n-1)\)，\(W(n,1)\) 为 \(w(2^n,2^{n+1}-1)\)。有 \(W(n,i)=W(n-1,i)+W(n-1,1-i)\)。

又发现 \(w(l,r)\) 可分解为用 \(O(\log)\) 个 \(W(n,i)\) 表示。

记 \(f_{u,n,i}\) 表示 \(u\) 点走 \(W(n,i)\) 所到达的点。有 \(f_{u,n,i}=f_{f_{u,n-1,i},n-1,1-i}\)。

记 \(c_{u,n,i}\) 为 \(u\) 上调用 \(W(n,i)\) 的次数， \(g_{u,n,i}\) 为答案。

有 \(g_{u,n,i}=c_{u,n,i}+g_{u,n+1,i}+\sum_{f_{v,n+1,1-i}=u}g_{v,n+1,1-i}\)。

那 \(u\) 这个点就是 \(g_{u,0,0}+g_{u,0,1}\) 。弄个子树和就做完了。

P10627

以下认为 \(n,m\) 同阶。

套路的，考虑每个位置被填满的时间 \(t_i\) 。

发现需要用 Hall 定理判断这个 \(t\) 序列是否合法。有

\[|\bigcup_{i\in[l,r]}\{j|j\le t_i,X_j\in\{i-1,i\}\}|\ge \sum_{i\in[l,r]}C_i \]

移项，维护后缀 \(\min\) ，有这个 \(\min\) 时刻非负。

记 \(f_{i,j,k}\) 表示考虑了前 \(i\) 个位置，\(t_i=j\) ，上面说的 \(\min\) 是 \(k\) 的最大值。不难证明这个转移的总状态数是 \(O(n^2)\) 的，直接枚举，总复杂度为 \(O(n^3)\)。

P11810

考虑网格图常用技巧，即平面图转对偶图。

如果在网格图上割掉了边。那么在对偶图上，就加入当前对应的边。这样操作之后，对偶图上每个环内部的点就是原来的一个连通块。

因此每个环内部要么没有，要么包含所有点。考虑异或哈希。用可撤销的带权并查集维护即可。

具体的，需要维护并查集内每个点到所属连通块根节点的异或，这是可以合并时算出，可以看代码。

CF1458C

考虑将变换刻画成三元组。

比较神奇的是，这种信息的维护可以差分、合并，或许逆排列远远被低估了。

P14388

不是什么玩意？怎么都会这题的不平凡部分分 /jk

首先你发现并没有很直观的多项式级别的做法，这让你意识到了问题的严重性。

发现赶人下车的区间一定是连续的，而且一定是某两个服务区间最后一个周期里。

给乘客按 \(D_i\) 排好序，记 \(f_i\) 表示考虑到第 \(i\) 个人的最小花费。

不赶走这个人：\(f_i\gets f_{i-1}+W\times(\lfloor\frac{X-D_i}{T}\rfloor+1)\)

赶走这个人，即赶走一段区间：\(f_i\gets\min_{k=0}^{i-1} f_k+\sum_{t=k+1}^i C_t+W\times t_i\)

其中 \(t_i\) 表示这个人被赶走的时候要接多少水，可以简单预处理出来。

QOJ12334

这又是什么鬼。

利用加法和乘法的分配率，做分治乘法卷积。

P11303

首先有一个 \(O(k(n-k))\) 的区间 DP。

发现我们在决策的是拐弯的位置，于是尝试把贡献摊到拐弯上。具体地，每个点有一个初始的到达时刻 \(∣a_i​−a_m​∣\)。假设我们是从左侧的 \(l\) 走到了右侧的 \(r\)，那么 \(l\) 左侧的所有位置的到达时刻都会被延迟 \(2(r−l)\) 秒。

设到达左侧为 \(f_l\)，到达右侧为 \(g_r\)。

有 \(f_l=\min(g_r+2(a_r-a_l)(n-r)),g_r=\min(f_l+2(a_r-a_l)(l-1))\)。

发现转移成环了，没有关系，用 dij 思想优化即可。

P10436

不是这是啥啊？！吓哭了。

首先发现只关心和最终值的大小关系，有一个简单的区间 DP。

然后简单记一下思路，就是考虑最终的 \((T_j,W_j)\) 是怎么合并出来的，分讨一下情况，一共四种。

以下以其中一种为例，如 \((T_j,\le W_j)+(\le T_j,W_j)\)，考虑怎么样的序列可以合成 \((T_j,\le W_j)\) 。发现是存在 \((T_j,*)\) 并且这个序列可以合成 \((\ge T_j,\le W_j)\) 。 再考虑怎么样的序列可以合成 \((\ge T_j,\le W_j)\)，发现是存在一个 \((\ge T_j,\le W_j)\) 且这个位置的两边各有 \((\ge T_j,*)\) 或 \((*,\le W_j)\)。

然后用线段树上二分求出所有合法的前缀，同理求出后缀，拼起来就好了。