2018中国大学生程序设计竞赛 - 网络选拔赛
Contest Info
date: 2018.08.25 12:00-17:00
Solutions
A. Buy and Resell
题目大意：给出 \(n\) 个正整数 \(\{a_i\}\)。从左到右依次考虑，每次可以花费 \(a_i\) 购买一个物品，或者卖掉一个物品（手上有物品）获得 \(a_i\)。问你最大收益，收益相同时最小化买卖次数。
题解：从左到右考虑，每次我们默认 \(a_i\) 是卖出操作，把答案加上 \(a_i\)，然后把 \((-a_i,2)\) 和 \((-a_i,1)\) 两个 pair 放入大根堆中。然后从大根堆中取出堆顶，把答案加上 pair 的 first（保证买卖次数相等），同时根据 second 判断取出的这个 pair 将之前的某个 \(a_j\) 改成了不买不卖/卖出操作，相应更新买卖次数这个答案。
B. Congruence equation
题目大意：给出一个长度为 \(k\) 的数列 \(A\)，定义 \(f(m)\) 为满足下列条件的方案数：
- 若 \(A_{i}=-1\)，那么 \(C_{i}\) 可以在 \([0,m)\) 中任取，否则 \(C_{i}=A_{i}\text{ mod }m\)
- \(\sum_{i=1}^{k}C_{i}x_{i}\equiv1\pmod{m}\) 有解
求 \(\sum_{m=1}^{n}f(m)\)。
题解：根据裴蜀定理，该同余方程有解当且仅当 \(\gcd(C_{1},\cdots,C_{k},m)=1\)。
首先我们定义 \(g(x,k)\) 表示 \(k\) 个数在 \([0,x)\) 的范围内，且这 \(k\) 个数与 \(x\) 的 \(\gcd\) 为 \(1\) 的方案数。根据容斥原理，显然有 \(g(x,k)=\sum_{d\mid x}(\frac{x}{d})^{k}\mu(d)\)。
若全部的 \(A_{i}\) 均为 \(-1\)，答案为 \[ \begin{aligned} &\sum_{m=1}^{n}g(m,k)\\ =&\sum_{m=1}^{n}\sum_{d\mid m}(\frac{m}{d})^{k}\mu(d)\\ =&\sum_{d=1}^{n}\mu(d)\sum_{m=1}^{\lfloor\frac{n}{d}\rfloor}m^{k} \end{aligned} \] 其中右边的和式是自然数等幂和，容易用伯努利数计算，\(\sum\mu(d)\) 也容易用杜教筛计算。
若存在某些 \(A_{i}\) 不为 \(-1\)，设 \(\gcd\) 为所有不为 \(-1\) 的 \(A_{i}\) 的 \(\gcd\)，为方便设 \(k\) 为非 \(-1\) 的 \(A_{i}\) 的数量，那么答案为 \[ \begin{aligned} &\sum_{d\mid \gcd}\sum_{m=1}^{n}\left[\gcd(m,\gcd)=d\right]g(d,k)(\frac{m}{d})^{k}\\ =&\sum_{d\mid \gcd}g(d,k)\sum_{d\mid u, u\mid \gcd}\mu(\frac{u}{d})(\frac{u}{d})^{k}\sum_{i=1}^{\lfloor\frac{n}{u}\rfloor}i^{k} \end{aligned} \] 需要注意 \(A_{i}\) 全为 \(0\) 的情况。
时间复杂度 \(\mathcal{O}\left(n^{2/3}+\sigma_{0}^{2}(\gcd(A))\right)\)。
C. Dream
签到题。费马小定理。
D. Find Integer
签到题。费马大定理。
E. GuGu Convolution
题目大意：给你两个序列 \(A^{0},A^{1},A^{2},\cdots\) 和 \(0,B^{1/2},0,B^{3/2},\cdots\)，求它们的指数型生成函数的积的第 \(n\) 项乘以 \(n!\)。
题解：观察后可以发现，答案为 \[ \begin{aligned} &\sum_{i=0}^{n}[i\text{ mod }2=1]{n\choose i}A^{n-i}B^{i/2}\\ =&\frac{(A+\sqrt{B})^{n}-(A-\sqrt{B})^{n}}{2} \end{aligned} \] 注意到 \((A+\sqrt{B})^{n}\) 和 \((A-\sqrt{B})^{n}\) 共轭，因此答案就是 \((A+\sqrt{B})^{n}\) 带根号的部分。
F. Neko and Inu
题目大意：有两个大小为 \(n\) 的正整数集合 \(A,B\)，定义 \(A+B=\{u+v,|u-v|\mid u\in A,v\in B\}\)。定义 \((A,B)\) 是好的，当且仅当 \(A+B\) 取遍了 \(1\sim4n^{2}-1\) 间的所有奇数。求所有好的集合对 \((A,B)\) 的数量。\(n\) 是用 \(\displaystyle \prod_{i=1}^{t}p_{i}^{a_{i}}\) 的形式给出的，\(p_{i}\) 为质数，\(\sum a_{i}\le10^{5}\)。
题解：我们尝试将本题规约到 这个问题。向 \(A\) 和 \(B\) 中分别加入它们中所有元素的相反数，并将 \(A+B\) 定义为 \(A+B=\{u+v\mid u\in A,v\in B\}\)。那么此时 \(A+B\) 取遍 \(1-4n^{2}\sim4n^{2}-1\) 间的所有奇数。不妨设 \(A\) 由奇数组成，\(B\) 由偶数组成，将 \(A\) 中所有元素 \(x\) 变换到 \(\displaystyle \frac{x+2n^{2}+1}{2}\)，\(B\) 中所有元素 \(x\) 变换到 \(\displaystyle \frac{x+2n^{2}}{2}\)，此时 \(A+B\) 取遍 \(1\sim4n^{2}\) 间的所有整数。再将 \(A,B\) 往不同方向平移一下使得 \(0\in A\) 且 \(1\in B\)，就对应了原问题一个 \(n'=m'=2n\) 的解。观察原问题的一个解，容易知道它是对称的，逆着变换一下就能变成本题的解了（变换回去的时候会乘 \(2\)，所以奇偶性一样，关于一个数对称，于是可以变回若干对相反数）。因此本题的答案即为 \[ 2\sum_{i=1}^{+\infty}g_{i}(2n)(g_{i}(2n)g_{i+1}(2n)) \] 接下来考虑 \(g\) 的计算。设 \(h_{i}(n)\) 表示将 \(n\) 分解为 \(i\) 个正整数的乘积（有序），根据容斥原理显然有 \(\displaystyle g_{i}(n)=\sum_{j=0}^{i}(-1)^{i-j}{i\choose j}h_{j}(n)\)，这里可以用 FFT 加速。
又有 \(\displaystyle h_{i}(n)=\prod_{j=1}^{t}{a_{j}+i-1\choose i-1}\)，且不同取值的 \(a_{i}\) 只有 \(\sqrt{\sum a_{i}}\) 个，所有的 \(h_{i}\) 也容易计算。
时间复杂度 \(\mathcal{O}((\sum a_{i})\cdot \sqrt{\sum a_{i}}\log\sum a_{i})\)。
还有几道相似的题：51nod 1727 hdu 4304 ICPC Archive 4771 topcoder SRM 495 Div.1 C
G. Neko’s loop
签到题。讨论环的正负，然后把步数按照环长分解，case 分析。
H. Search for Answer
题目大意：给定一个 \(n(n\leq 200)\) 个点的 tournament，现在有不超过 \(200\) 条边没有定向。让你给它们定向，使得下列代码算出的 \(\text{ans}\) 最大：
int ans = 0;
for (int a = 0; a < n; ++a) {
for (int b = 0; b < n; ++b) if (b != a) {
for (int c = 0; c < n; ++c) if (c != a && c != b) {
for (int d = 0; d < n; ++d) if (d != a && d != b && d != c) {
if (s[a][b] == s[b][c] && s[b][c] == s[c][d] && s[c][d] == s[d][a]) {
++ans;
}
if (s[a][b] != s[b][c] && s[b][c] != s[c][d] && s[c][d] != s[d][a]) {
--ans;
}
}
}
}
}题解：容易发现，给答案贡献 \(1\) 的四元环形如：\(\overleftarrow {a\rightarrow b\rightarrow c\rightarrow d}\)，给答案贡献 \(-1\) 的四元环形如 \(\overrightarrow{a\rightarrow b\leftarrow c\rightarrow d}\)。
也即给答案贡献 \(1\) 的四元环没有出度为 \(2\) 的点，给答案贡献 \(0\) 的四元环恰有一个出度为 \(2\) 的点，给答案贡献 \(-1\) 的四元环恰有两个出度为 \(2\) 的点。可得：
\[ \text{ans}={n\choose 4}\cdot 4! - 8(n-3)\sum_{i=1}^n{\text{deg}_i \choose 2} \]
我们枚举一个点，选择两条出边，第四个点有 \((n-3)\) 种选择。有两个出度为 \(2\) 的环正好被减掉两次。我们要最大化上述式子，也即最小化 \(\displaystyle \sum_{i=1}^n{\text{deg}_i \choose 2}\)。用凸费用流解决。
\(\displaystyle {\text{deg}_i\choose 2}=\sum_{j=1}^{\text{deg}_i-1}j\)。我们先把每个点确定的出度的贡献预先算好，然后对于每条未确定的边 \(u\rightarrow v\)，我们从源点向这条边连 \(1\) 的容量，这条边向 \(u,v\) 两点各连 \(1\) 的容量。然后每个点连汇点若干条边，容量为 \(1\)，费用依次为 \(\text{deg}_i,\text{deg}_i+1,\text{deg}+2,\cdots\)。
I. Tree and Permutation
签到题。计算每条边贡献。
J. YJJ’s Salesman
题目大意：网格图 \((0,0)\) 到 \((10^9,10^9)\) 中有 \(1\le n\le10^5\) 个宝藏，第 \(i\) 个宝藏在格子 \((x_i,y_i)\) ，价值为 \(v_i\)。你从 \((0,0)\) 出发，位于 \((x,y)\) 时，可以到达 \((x+1,y)\) ，\((x,y+1)\) 或 \((x+1,y+1)\) 三个格子之一。如果 \((x,y)\) 处有一个宝藏，那么你只有从 \((x-1,y-1)\) 到 \((x,y)\) 才可以拿到这个宝藏。
求最多可以获得多大价值的宝藏。
题解：按 \(x\) 排序，树状数组维护 \(y\) 的前缀最大 dp 值，用 \(x\) 和 \(y\) 都严格小于当前点的状态进行转移。\(\mathcal{O}(n\log{n})\)。
Dirt Replay
A: -1 错误算法
E: -1 错把 n 奇数的时候当做另一种 case
