主要思路
我靠这是真的难，对着 pty 的题解傻看了一下午。
Continue reading →感觉有点傻逼啊。
对于 0 而言，我们只需要最后的答案为 0 即可。那么，我们从后往前进行维护，维护 \(0\) 位置上权值组合而成的线性基，然后每次到 \(1\) 位置的时候就在里面查即可，如果没查到，那么对于 \(1\) 而言，后面的 \(0\) 并不足以抵消该操作，所以可以判 \(1\) 获胜，亦而反之。
Continue reading →SB 题，不解释。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
int x;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int main()
{
scanf("%d", &x), printf("%d\n", 360 / gcd(x, 360));
return 0;
}
Continue reading → 好题目啊。
发现 \(f(x)\) 对于有平方因子的数都没有效益，所以我们只考虑 \(f(x) = \prod_{i = 1}^m p_i\)。那么很容易发现 \(f(x) = \prod_{r = 0}^m (-1)^{2^{(r – 1)}}\)，所以：
\[ f(x) = \begin{cases} -1, x \in primes or x = 1 \\ 1, otherwise \end{cases} \]
Continue reading →这也太他妈毒瘤了吧。
这个题首先肯定是要离线的，在线肯定没发做。事实上，我们可以对这个匹配分为三类：在上升链上、过 LCA 或者是在下降链上。这三者可以分开进行统计。上升链和下降链可以通过对询问字符串正反建 AC 自动机、然后在原树上做 DFS 即可；经过 LCA 的链有点难处理，发现能参与匹配的字符个数是与 \(|\text{询问串}|\) 相关的，所以我们把左右链的两个部分拼起来，然后单独跑 KMP 即可。
代码好长，狗屎一般。
Continue reading →