A BBQ Easy

排序贪心，两个两个选。

B Mysterious Light

容易归化成下面的形式，于是可以在与辗转相除法相同的时间复杂度内求解。

C Shorten Diameter

枚举树的所有可能中心，然后删掉那些距离中心超过 $\frac{K}{2}$ 的点即可。

D Arrays and Palindrome

首先考虑什么情况下无解：如果把两个排列所有相应位置连边，那么至少要是一棵树才能保证所有位置字符相同。一个排列中有一个奇数就少半条边，因此如果 $a$ 有多于两个奇数，那么边的个数必然小于 $N-1$。这时无解。

再考虑方案的构造。答案给的构造是：先把 $a$ 的奇数放两边，然后 $$b_i=\{\begin{array}{ll}{a}_i-1& \text{if }i=1\\ a_i+1& \text{if }i=M\\ a_i& \text{otherwise}\end{array}$$ 可以证明这样是合法的。

E BBQ Hard

考虑有两个串 $(a_i,b_i),(a_j,b_j)$，那么方案数就是 $\left(\genfrac{}{}{0ex}{}{a_i+a_j+b_i+b_j}{a_i+a_j}\right)$。那么答案就是 $$\sum _{1\le j<i\le n}\left(\genfrac{}{}{0ex}{}{a_i+a_j+b_i+b_j}{a_i+a_j}\right)$$ 这个不好计算，但是可以看出这个东西和一个 DP 模型很像：走路模型。即从坐标 $(-a_j,-b_j)$ 开始，只向右或者向上走，走到 $(a_i,b_i)$ 的方案数就是 $\left(\genfrac{}{}{0ex}{}{a_i+a_j+b_i+b_j}{a_i+a_j}\right)$。

刚好 $a_i,b_i$ 的数据范围很小，那么我们就做这样一个 DP，设 $f(a,b)$ 为走到 $(a,b)$ 的方案数，只不过初始条件改成 $f(a,b)=\left|\left\{i:1\le i\le n,a=a_i,b=b_i\right\}\right|$。然后递推一下即可。

这样 $f(a_i,b_i)={\sum }_{j=1}^n\left(\genfrac{}{}{0ex}{}{a_i+a_j+b_i+b_j}{a_i+a_j}\right)$，所以要减掉自己对自己的贡献，最后总贡献还要除以 2。

const int inv2 = 1000000008 / 2; const int offset = 2001; int fac[8005], inv[8005], invfac[8005]; int n, a[200005], b[200005]; int f[4005][4005] = {0}; void init(){ n = read(); for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = read(), ++f[-a[i] + offset][-b[i] + offset]; fac[0] = fac[1] = 1; inv[1] = 1; invfac[0] = invfac[1] = 1; for (int i = 2; i <= 8000; ++i){ fac[i] = 1ll * fac[i - 1] * i % MOD; inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD; invfac[i] = 1ll * invfac[i - 1] * inv[i] % MOD; } } void solve(){ for (int i = 1; i <= 4001; ++i) for (int j = 1; j <= 4001; ++j){ f[i][j] = modadd(f[i - 1][j], modadd(f[i][j], f[i][j - 1])); } int ans = 0; for (int i = 1; i <= n; ++i){ ans = modadd(ans, f[a[i] + offset][b[i] + offset]); int cc = 1ll * fac[2 * a[i] + 2 * b[i]] * invfac[2 * a[i]] % MOD; cc = 1ll * cc * invfac[2 * b[i]] % MOD; ans = modadd(ans, MOD - cc); } ans = 1ll * ans * inv2 % MOD; printf("%d\n", ans); }

F Wide Swap

可以转化成相邻元素排序问题：设 $po{s}_i$ 数组为元素 $i$ 在 $p$ 中的下标，那么 $po{s}_{p_i}=i$。对于 $pos$ 数组，只有当相邻元素差 $\ge k$ 时才可交换。而要让 $p$ 字典序最小，其实等价于让 $pos$ 字典序最小。

因此就变成了一个经典的拓扑排序问题（参见 SWERC 2019 G），我们让每一个 $i$ 连向 $j$，如果 $i<j$ 且 $|po{s}_i-po{s}_j|<k$。但这样连边数目是 $O(N^2)$ 的。因此优化一下，对于每一个 $j$，分别对于 $po{s}_j<po{s}_i$ 与 $po{s}_j>po{s}_i$ 两种情况，找到合法且最大的 $i$ 连边即可。

小结

弱项：树的中心、直径。

D 这个构造比较精巧，没有想到。无解的判定也没有很好的结合图论来思考。

E 虽然想到可能和走路模型有关，但并没有更深入地考虑，反而一直在想数学的做法。这是一个不好的地方。不过这种 DP 优化计数的问题以前似乎也见过…

F 初看没有任何思路，但通过下标序列巧妙地转化成了一个经典的排序问题。