A,B
H₂O题。
A 题直接模拟,记得 \(-1^x\) 的性质。
B 题构造题,每次往空格里填最小的可用数字即可。
C
这道题就相当于有一个数字圆环,每次求其中的一段区间的和。、
嗯?怎么这么眼熟?这不破环成链吗!
复制一遍数组,记录一下偏移量(记得取模),求和用前缀和即可。
提交记录
D
直接模拟——好像不太行。
我们可以考虑怎么优化。
显然,在一轮模拟中,只有上一轮模拟中变黑的格子周围的四个格子才有可能变黑。
那么我们每次只用更新他们就行了。
由于最多只有 \(nm\) 个格子变黑,所以时间复杂度为 \(O(nm)\),可以通过本题。
提交记录
E
这题小学奥数秒(具体过程略,不会建议重学组合数学)。
不过由于非质数模数下阶乘可能没有逆元,故应该是杨辉三角来预处理出 \(n \choose m\)。
提交记录
F
考虑状压 DP。
首先,如果一个一个往上添是很难做的,那我们可以反着来,考虑一个一个往下删。
设 \(f_{S}\) 表示每一个字符是否删除的集合为 \(S\),总共有多少种可能。
对于每个 \(f_{S}\),很明显他能对所有比 \(S\) 多删了一个字符的 \(f_{T}\) 造成贡献,可以 \(O(n)\) 枚举,所以总时间复杂度为 \(O(n2^n)\)。
但你以为这样就结束了吗?不,如果你尝试运行样例,你就会发现答案比正确答案多了一点。
为什么呢?我们可以发现,有些删除整个字符串的操作序列会重复。比如有字符串 aabb
,先删第 \(1\) 位和先删第 \(2\) 是一样的。为了解决这种情况,我们规定如果当前字符串有多个字符相同,那么就必须从最左边开始删,这样问题就解决了。
提交记录
G
看到异或想到 01-Trie。
考虑对于每一个 \(x\),求出最小的异或值。
我们可以贪心地做。假如我们已经知道了一个数,什么情况下另一个数与这个数的异或值最小呢?对了,就是在这两个数相等的时候。
所以我们在 01-Trie 上从上往下走,每次尽可能走与 \(x\) 的这一二进制位一致的数即可。
但是这种方法的时间复杂度依旧过不去,怎么优化呢?
我们换种角度,从 01-Trie 节点的角度来考虑。
从上往下走,记录经过该点的 \(x\) 数量 \(cnt\) 和深度(从大到小) \(dep\)。
延续之前的贪心做法,如果两个子节点都存在,那么将所有 \(x\) 放进它的下一位对应的子节点里,否则全部放进唯一的子节点里,并且对答案产生贡献。
但有个问题,怎么求出下一位为 \(0\) 和 \(1\) 的 \(x\) 个数呢?
很明显,由于每个 \(x\) 都是连续的,所以经过这个节点的 \(x\) 的下一位一定是从 \(0\) 到 \(1\) 的,由于 \(0\) 是一定会先加满才会变成 \(1\),所以下一位为 \(0\) 的个数为 \(\min(cnt,2^{dep-1})\),为 \(1\) 的个数为 \(cnt-\min(cnt,2^{dep-1})\)。
可以发现,\(cnt\) 为 \(2^{dep}\) 的节点会经常出现,所以我们可以先预处理出所有这样的节点的答案。
这样时间复杂度就可以足够通过本题了。
提交记录