20260617

挂分最惨的一次是谁想出来的不放大样例？前三题一个小时多一点就写完了正解结果全坠了，甚至 T1 freopen 写错了。

P6934 [ICPC 2017 WF] Posterize

P6934 [ICPC 2017 WF] Posterize。

我甚至用了决策单调性优化 dp。。。

其实只需要预处理 cost 就行了，但是我还是写了决策单调性。

挂在 solve(i,1,d,1,d);solve(i,1,d,1,d); 不能写成 solve(i,1,d,0,255);solve(i,1,d,0,255); 而且中间遍历的时候需要 i=max(L,x);i<=R&&i<=mid。

P6931 [ICPC 2017 WF] Mission Improbable

P6931 [ICPC 2017 WF] Mission Improbable。

很难想象有紫，二分图匹配做完了。

注意的是匈牙利算法最后需要返回 00，win 环境不会报错。

还有就是需要特判一行/一列不为 00 的情况。

P6933 [ICPC 2017 WF] Need for Speed

P6933 [ICPC 2017 WF] Need for Speed。

注意 check 里面不要把 ss 和 dd 写反。还有有的可能容易漏掉 1.0*。

P6932 [ICPC 2017 WF] Money for Nothing

P6932 [ICPC 2017 WF] Money for Nothing。

决策单调性。没有考，但是很恶心，洛谷数据很水，需要调很久。

初始化写法
C++
int l=2e9;
	for(int i=1;i<=m;i++){
		if(a[i].y<l){
			l=a[i].y;
			c[++M]=a[i];
		}
	}
	reverse(b+1,b+n+1);
	N=0;
	for(int i=1;i<=n;i++)if(N==0||b[i].y>d[N].y)d[++N]=b[i];
	reverse(d+1,d+N+1);

P6936 [ICPC 2017 WF] Scenery

P6936 [ICPC 2017 WF] Scenery。

当年考试没人 AC 的论文题。

反正死磕磕不出来然后去睡觉了。

20260620

P14347 [JOISC 2019] 灯 / Lamps

P14347 [JOISC 2019] 灯 / Lamps。

看完题感觉做过弱化版是区间 dp。然后先想想区间 dp，发现代码很长而且复杂度不正确，于是果断放弃了一道蓝题。。。

但是想想，根本不需要区间 dp！直接 fi,0/1/2,0/1f_{i,0/1/2,0/1} 表示是否被覆盖、翻转。

其实第二维可以判断 ai−1a_{i-1} 和 bi−1b_{i-1} 来判断。

P9055 [集训队互测 2021] 数列重排

P9055 [集训队互测 2021] 数列重排。

看完题肯定会尝试划分一些集合，然后我们发现交界处需要优化。我们想到我们想让不合法的尽量少。

观察到循环均匀排列最优，此时只要长度够就符合。

但是我们还需要考虑一下多余的元素，我们考虑插入他们然后计算破坏量。

  • 中间：(2i−2)+r+1(2i-2)+r+1，rr 是这个位置已经插入的数量。

  • 两边：(i−1)+r+1(i-1)+r+1。

每次我们贪心选择就行了。

≤2∗(i−1)\le 2*(i-1) 的时候放在两边每边 i−1i-1）。

20260624

P4786 [BalkanOI 2018] Election

P4786 [BalkanOI 2018] Election。

这种题一眼线段树，然后需要寻找题目要求的充要条件。

很容易想到计算前缀和后缀里面 C 的个数减去 T 的个数。

然后我们需要前缀和后缀都满足条件的话，就需要所有的 ii，能够满足其前缀和后缀的要求。

然后答案可以用线段树维护。

P4425 [HNOI/AHOI2018] 转盘

P4425 [HNOI/AHOI2018] 转盘。

trick：P4198 楼房重建。

我们发现中间的等待操作没用，可以直接在一开始等待。

复制一遍数组然后就不用考虑环了。

ans=min⁡1≤i≤n(max⁡0≤j≤n−1(ti+j−j)+n−1)ans=\min_{1\leq i \leq n}(\max_{0 \leq j \leq n-1}(t_{i+j}-j)+n-1)

ans=min⁡1≤i≤n(max⁡i≤j≤i+n−1(tj−j)+i+n−1)ans=\min_{1\leq i \leq n}(\max_{i \leq j \leq i+n-1}(t_{j}-j)+i+n-1)

然后令 xix_i 是 xi+ix_i+i：

顺便 ≤i+n−1\leq i+n-1 也可以删掉，因为后面的跟前面的重复但是下标更大。

ans=min⁡1≤i≤n(max⁡i≤j≤2nxj+i)+n−1ans=\min_{1\leq i \leq n}(\max_{i \leq j \le 2n}x_j+i)+n-1

可以用线段树来维护。对于区间 [L,R][L,R]，mx=max⁡L≤j≤Rxjmx=\max_{L\le j\le R}x_j，mn=min⁡i∈[L,mid](i+max⁡i≤j≤Rxj)mn=\min_{i\in[L,mid]}(i+\max_{i\le j\le R} x_j)。（注意起始点在左区间）。

定义 get(x,mx)=min⁡i∈[L,R](i+max⁡(max⁡i≤j≤Rxj,mx)get(x,mx)=\min_{i\in[L,R]}(i+\max(\max_{i\le j\le R} x_j,mx)，我们只需要求出 get(ls,mxrs)get(ls,mx_{rs})。

P5852 [USACO19DEC] Bessie's Snow Cow P

P5852 [USACO19DEC] Bessie's Snow Cow P。

首先直接按照下标不好做，考虑值域。

我们，每一个颜色维护 set，保证里面存的点互不为祖先。插入每一个点就找前驱，如果已经覆盖了就跳过，否则删除被 xx 覆盖的后继。

然后我们需要计算询问，分成祖先的贡献和子树内的，可以用两颗树状数组进行维护。

P4359 [CQOI2016] 伪光滑数

P4359 [CQOI2016] 伪光滑数。

性质：最大的伪光滑数所有质因数相同，这个很好想到。

用堆维护，每次取出最大值，如果这个数最大质因数的幂次大于 11，把其中一个最大质因数换成较小的扔进堆里。

P5290 [十二省联考 2019] 春节十二响

P5290 [十二省联考 2019] 春节十二响。

链的情况就是很简单的，最大的和最大的匹配即可。

然后扩展到树上，每个节点维护大根堆，启发式合并。

20260701

P1397 [NOI2013] 矩阵游戏

P1397 [NOI2013] 矩阵游戏。

十进制矩阵快速幂，或者推通项公式+欧拉定理。

P5330 [SNOI2019] 数论

P5330 [SNOI2019] 数论。

这道题我想到用循环节来做，然后用 bitset AC 了，虽然自己的随机数据都过不了。

换一种思路，对于所有 a∈Aa\in A：

a mod Q,  (a+P) mod Q,  (a+2P) mod Q,  …a \bmod Q,\; (a+P)\bmod Q,\; (a+2P)\bmod Q,\; \dots

这个看着就是在一个有 QQ 个点的图上走路的过程。

于是问题就变成了：

从 a mod Qa \bmod Q 出发，走 kk 步（包括起点），一共经过了多少个标记点？

其中 k=⌊T−1−aP⌋+1k = \left\lfloor \dfrac{T-1-a}{P} \right\rfloor + 1，也就是 a,a+P,…a, a+P, \dots 的项数（若 a≥Ta \ge T 则 k=0k=0）。

对于每一个环，定点数为：

lcm⁡(P,Q)P=Qgcd⁡(P,Q)\frac{\operatorname{lcm}(P,Q)}{P} = \frac{Q}{\gcd(P,Q)}

图上一共有 gcd⁡(P,Q)\gcd(P,Q) 个不相交的环。

配合上前缀和，我们就可以求出答案了。

P4774 [NOI2018] 屠龙勇士

P4774 [NOI2018] 屠龙勇士。

之前做过，但是考场没有想。

貌似读错题了，每一条龙的剑是确定的。

于是只需要求：

{b1x≡a1(modp1)b2x≡a2(modp2)⋯bnx≡an(modpn)\begin{cases} b_1x\equiv a_1\pmod {p_1}\\ b_2x\equiv a_2\pmod {p_2}\\ \qquad\cdots\\ b_nx\equiv a_n\pmod {p_n}\end{cases}

excrt 就做完了。

20260704

[BJOI2019] 光线

[BJOI2019] 光线。

这道题肯定是 dp，但是我们发现缺了一些东西，所以我们需要设出两个 dp，一个是光线从上面进入下面出的概率，一个是从下面进入然后下面出去的概率。

P3211 [HNOI2011] XOR和路径

P3211 [HNOI2011] XOR和路径。

高斯消元求无限转移的概率。

P5982 [PA 2019] Trzy kule

P5982 [PA 2019] Trzy kule。

啊啊啊，这道题不是容斥一个满足两个满足...这样的，而是正难则反，求出三个都不成立的情况数。

很容易观察到不同的个数就是异或的 popcount。

考虑一共有四种情况，三个串这一位相同，s1s_1 和其余的不同，s2s_2 和其余的不同，s3s_3 和其余的不同。

然后我们现在只需要枚举 i,j,k,li,j,k,l 表示这四类的情况数。

d1=i+j+(c2−k)+(c3−l)d2=i+(c1−j)+k+(c3−l)d3=i+(c1−j)+(c2−k)+l\begin{aligned} d_1 &= i + j + (c_2 - k) + (c_3 - l) \\ d_2 &= i + (c_1 - j) + k + (c_3 - l) \\ d_3 &= i + (c_1 - j) + (c_2 - k) + l \end{aligned}

补集条件要求它们都大于各自的 rr：

d1>r1,d2>r2,d3>r3d_1 > r_1,\quad d_2 > r_2,\quad d_3 > r_3

然后固定 i,ji,j，对 k,lk,l 做二维前缀和。k,lk,l 的范围：

k+l≤i+j+c2+c3−r1−1k + l \le i + j + c_2 + c_3 - r_1 - 1 r2+j−i−c1−c3<k−l<i+c1−j+c2−r3r_2 + j - i - c_1 - c_3 < k - l < i + c_1 - j + c_2 - r_3

sumx,ysum_{x,y} 就表示所有满足 k+l≤xk+l \le x 且 k−l+C3≤yk-l+C3 \le y 的方案总数。（加 C3C3 是防止负数）。

20260708

靠前不敢睡那么晚了啊啊啊。

P5231 [JSOI2012] 玄武密码

P5231 [JSOI2012] 玄武密码。

AC 自动机。但是注意，标记需要一直向 fail 扩展：

C++
for(int i=order.size()-1;i>=0;i--){
		trie.vis[trie.fail[order[i]]] |= trie.vis[order[i]];
	}

P3538 [POI 2012] OKR-A Horrible Poem

P3538 [POI 2012] OKR-A Horrible Poem。

？为什么我突然想起我考试的时候脑子里面闪了一下正解，然后没写？

直接分解质因数看看这个是不是循环节就行了啊。

P3181 [HAOI2016] 找相同字符

P3181 [HAOI2016] 找相同字符。

比较巧妙的转化：问题就是后缀的 lcp 长度之和，需要保证后缀来自不同的字符串。

然后我们就可以利用 height 数组进行优化。

又想到了单调栈，我们可以分 A 前和 B 前的情况维护。

从左到右扫描 SA，用单调栈维护以当前后缀为右端点时，所有左侧 s1 后缀与当前 s2 后缀的 LCP 贡献。反过来也需要处理一遍。