2024-11-26总结（杂题乱做）

今天没有模拟赛，也没有杂题选讲，于是就做了一些以前积累下来的题目。

ARC162E Strange Constraints

早上杂题讲的，不过比较简单，想到了 \(O(n^4)\) 的做法，实际上是 \(O(n^3)\) 的。

首先容易想到每次考虑同一个数，那么这个数肯定只能放在 \(A_i\) 比较大的地方，而且能选的位置一定是不断增加的。于是贪心的从出现次数大的向出现次数小的考虑，\(f_{i,j,k}\) 表示考虑到出现次数能够为 \(i\) 的数，已经填了 \(j\) 个数，已经填了 \(k\) 个位置的方案，每次转移枚举出现次数能够为 \(i\) 的（也就是 \(\le A_i\) 的）数的个数 \(l\)，然后转移到 \(f_{i-1,j+l,k+il}\) 就可以了。

然后想了一下发现 \(j\) 的个数不能超过 \(n/i\)，\(l\) 也不能超过 \(n/i\)，所以 \(\sum\frac{n^3}{i^2}=O(n^3)\)

HNOI2009 梦幻布丁 - 洛谷 | 计算机科学教育新生态

直接考虑暴力，然后一个变成另一个就从小合并到大，启发式合并乱做。

AGC016E Poor Turkeys

留着你是因为以后要炖了你。

先时光倒流。

先考虑如果只询问 \(i\) 这只鸡能不能活下来，那么她前面肯定要保证不能吃掉 \(i\)。我们维护一个集合 \(S_i\) 表示要 \(i\) 留下来，需要保护哪些，初始 \(S_i=\{i\}\)，然后对于一个操作 \((x,y)\)，如果 \(x\) 和 \(y\) 都被保护，那么这次因为一定要杀掉一只，所以 \(i\) 活不下来。如果只有一个被保护，那么另一个也要被保护。

直接用 bitset 模拟即可。

考虑怎么询问两只鸡，发现如果 \(S_i\cap S_j=\emptyset\) 也就是一只鸡只在一个保护名单里，那么她们一定都可以活下来，否则因为一只鸡不能被保护两次，那么就不能实现。 \[ O(\frac{nm}{w}+n^2) \]

P5126 鬼故事 - 洛谷 | 计算机科学教育新生态 💩

因为这个式子可以用矩乘做，但是懒了，所以考虑直接 BM，但是可能会遇到一点挫折。

难点应该在 \(N\) 和 \(M\) 都很大，那么怎么办：答案的循环节为 \(2P(P+1)\)，直接将 \(N\) 和 \(M\) 模一下就好了。

考虑证明，因为在这里斐波那契数列的循环节是 \(2(P+1)\)，但是答案什么时候才会取到一次 \(0\) 呢？发现当连续 \(P\) 个斐波那契数列拼起来使得答案取遍 \(P\) 中的每一个数最后面就可以取回 \(0\) 了，所以循环节为 \(2P(P+1)\)。