U288469 Piggy 算路程
显然是简单贪心。黄。
U306825 Piggy 数编号
先推式子。
令 \(L(n,k)\) 为最长区块长度为 \(k\) 的方案数，则 \(Ans=\sum_{i=0}^n\limits{L(n,i)}\times k\)。下面转为求 \(L(n,k)\)。
我们考虑可能的区块长度分别为多少。那么就相当于我们要枚举所有的长度在 \(1\sim k\) 之间的区块，他们长度的和为 \(n\)。据此我们枚举区块数量，先写出 \(L(n,k)=\sum_{i=0}^n\limits{(g(n,i,k)-g(n,i,k-1))\times ???}\)。
考虑后面的部分应该是什么。粗略一看，似乎我们只需要指定区块间的相对大小，我们就能生成一个排列，因此后面是 \(i!\)，但实际上这是错误的。我们希望我们生成的 \(i\) 个区间不会退化，即相邻两个区间合并到了一起变成了一个区间。而这需要保证我们区间的相对顺序所构成的一个 \(1\sim i\) 的排列最长区间为 \(1\)。因此后面的部分是 \(L(i,1)\)，据此写出公式 \(L(n,k)=\sum_{i=0}^n\limits{(g(n,i,k)-g(n,i,k-1))\times L(i,1)}\)，其中 \(g(n,i,k)\) 表示在 \(1\sim k\) 中选 \(i\) 个可重复的数，且和为 \(n\)。
下面转求 \(h(n)=L(n,1)\)。我们枚举规模较小的情况，不难猜想 \(h(n)=d[n]+d[n-1]\)，其中 \(d\) 是错位重排数。
实际上这也可以归纳证明：假设 \(h(n)=d[n]+d[n-1]\)，那么对于\(h(n+1)\)，考虑递推，我们发现 \(n+1\) 这个数对于每个排列都有 \(n\) 个合理的插入位置，即除了 \(n\) 后边的所有位置。再结合 $ d[n]=n\times d[n-1] + (-1)^n $，结论是显然的了。
另一方面也可以考虑其组合意义，对于 \(h(n)\)，在插入 \(n\) 时，要么原本就合法，则此时有 \(h(n−1)\times(n−1)\) 种方案；要么原本有一对不合法，则把 \(n\) 插在两者中间，那么把这一对数看作一个，方案数有 \(h(n−2)\times(n−2)\) 种。把二者加和，这显然实际上就是 \(d[n]+d[n−1]\)，虽然即使并不承认这一点也可以用递推式来预处理出 \(h\)。
结合此结论，得到\(L(n,k)=\sum_{i=0}^n\limits{(g(n,i,k)-g(n,i,k-1))\times (d[i]+d[i-1])}\)。这就是我们心心念念的 \(L\)。
考虑如何计算。首先考虑 \(g\) 的组合意义，我们发现，若 \(ik\le n\)，直接置 \(g(n,i,k)=0\) 即可。那么对于剩下的情况，我们考虑其组合意义，并用插板法容斥得到公式 \(g(n,i,k)=\sum_{x=0}^i\limits{(-1)^x\binom{n-xk-1}{i-1} \binom{i}{x}}\)，对组合数预处理以后控制 \(x\) 的上界，可以 \(O(n^2\log n)\) 求出结果。
出题人起初给出的代码跑的奇慢无比，发现是因为出题人一些奇怪的习惯导致常数飞天。后来重新写了一个 std，常数略小。
TODO: 有无更优复杂度？
#include <bits/stdc++.h>
#define i128 __int128_t
using namespace std;
int n, p;
int c[3001][3001], d[3001];
bool vis[3001][3001]; int res[3001][3001];
inline int b(int m, int k)
{
if (!k)
return 0;
if (vis[m][k])
return res[m][k];
vis[m][k] = 1;
int upper = (n - m) / k, i;
upper = min(upper, m);
i128 ans = 0;
for (i = 0; i <= upper; i++)
ans += 1ll * c[n - i * k - 1][m - 1] * c[m][i] * (i & 1 ? -1 : 1);
ans = ans % p + p;
return res[m][k] = ans % p;
}
inline int T(int k)
{
if (n == k)
return 1;
int m;
i128 ans = 0;
for (m = 1; m <= n; m++)
ans += 1ll * (b(m, k) - b(m, k - 1) + p) * (d[m] + d[m - 1]);
return ans % p;
}
int main()
{
int i, j, k;
scanf("%d%d", &n, &p);
d[0] = 1;
c[0][0] = 1;
for (i = 2; i <= n; i++)
d[i] = 1ll * (d[i - 1] + d[i - 2]) * (i - 1) % p;
for (i = 1; i <= n; i++)
{
c[i][0] = 1;
for (j = 1; j <= i; j++)
{
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
if (c[i][j] >= p)
c[i][j] -= p;
}
}
long long ans = 0;
for (k = 1; k <= n; k++)
ans += 1ll * k * T(k);
printf("%lld", ans % p);
}
U289325 追
简单 dij 即可。
U305747 Piggy 算恋爱
疑似错题？
U292508 网络流加强版
专门卡 EK 的图。
U294297 未来的可能
这道题通项公式是很麻烦的。但是理论可做。
U294455 渺茫的希望
可以证明先手必胜。首先我们发现 \(1\) 若是被选中只能第一次被选中，因为他是所有数的约数。这样我们考虑一个新游戏，数据范围为 \(2\sim n\)，根据策梅洛定理且此游戏无平局，此游戏先手或后手必胜。
若先手必胜，原游戏的先手那么做就好。否则先手选 \(1\)，让自己成为新游戏的后手，这样也必胜。
U297506 Yet Another Card Game
我们把 \(2\sim n\) 里面，所有介于 \(\frac{n}{2}\sim n\) 的素数都取走。剩下的数当中，只需要任取一个其余的数都会被连锁反应取走。所以此问题等价于问 \(\frac{n}{2}\sim n\) 有多少素数。线筛解决即可。
注意 \(n\) 较小时有边界问题，而样例已经给出了唯一的特例 \(n = 4\)，所以本题是很良心的。
U306856 尽头的距离
考虑每片叶子在何处有贡献，在每个点处维护边的子树内各有多少叶子即可。
U297518 离别
我们充分发扬人类智慧。我们发现只要保留所有圆和其圆心即可。
我们考察全局 \(max\) 的点构成的图形，并只考虑其中一个连通块。如果该图形是一个点，则必为交点，算法正确；若为不规则图形，边界上必有交点，算法正确；若为规则图形则必定为圆，因此保留圆心，算法也正确。
U307878 树林
我们对于森林，有结论 \(c=v-e\)，其中 \(c\) 为连通块个数，\(v, e\) 分别为点数和边数。这个结论只要考虑对树断边是显然的。
那么这个问题变成了一个二维数点问题。用二维数据结构随便做。
U303230 小 L 的情书
咕咕咕。
U303437 小 X 的数论
答案显然就是 \(\gcd(a, x)\)。
U331541 历史版本和
只需要在普通主席树上维护创建此节点的版本编号。你需要注意的是，这个标记是要下放的，不是永久化。
U330288 野兽
只会线性。线性是显然的。
U325896 嫁接
其实就是线段树合并分裂板子！
U320514 对对碰（Hard Version）
好难，不会。
U320513 对对碰（Easy Version）
显然 \(O(n^4)\) 是可以通过本题的！
U316571 序列
这不就是用平衡树维护逆置换？洒洒水啦！
U316378 套娃
因为 \(a \operatorname{xor} b\le a + b\)，因此最后的权值一定是所有点的权值和，而且附带的结论是，我们绝不会做操作二。那么我们只需考虑操作一，这个操作对于每棵树互相独立。因此考虑一棵树的做法。
既然 \(a \operatorname{xor} b\le a + b\)，那么当我们遇见一个子树异或和小于子树权值和的节点时，这个节点必然断开，这个采用树形 DP 是容易求的。
而对于此做法的正确性，考虑反证法。假设最后得到的若干棵树存在异或和小于权值和的，那么此树根必然会被断开，这与这是一棵树矛盾。
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 10;
vector<int> edges[maxN];
int p[maxN]; bool root[maxN];
int ans, sumxor[maxN];
long long sum[maxN];
void dfs(int u) {
sum[u] = sumxor[u] = p[u];
for(int i: edges[u]) {
dfs(i);
sum[u] += sum[i], sumxor[u] ^= sumxor[i];
}
if(sumxor[u] ^ sum[u]) ans++;
}
signed main() {
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
int n, m; long long res = 0; cin >> n >> m;
memset(root, 1, sizeof root);
for(int i = 1, u, v; i <= m; i++) {
cin >> u >> v; edges[u].push_back(v); root[v] = false;
}
for(int i = 1; i <= n; i++) cin >> p[i], res += p[i];
for(int i = 1; i <= n; i++) { if(root[i]) dfs(i); }
cout << res << "\n" << ans;
}