Contest Info

date: 2017.10.11 13:15-18:15

practice link

Solutions

A. 传递

题目大意：把竞赛图 \(G=(V,E)\) 的 \(E\) 划分为 \(E_p,E_e\)，问图 \(P=(V,E_p),Q=(V,E_e)\) 是否同时为传递闭包。

题解：如果原图存在单向三元环，那么一定不同时为传递闭包。因为 \(a\rightarrow b\rightarrow c\rightarrow a\) 如果三条边全在 \(E_p\) 中，那么 \(P\) 不是传递闭包。不妨假设有两条边在 \(E_p\) 中，\(P\) 也不是传递闭包，此时另一条边（在 \(E_e\) 中）的朝向其实无所谓。所以我们只需要判断 \((V,E_p\cup E_e)\) 和 \((V,E_p\cup \displaystyle E_e')\) 是否存在单向三元环即可。竞赛图中，如果有 SCC 那么就一定存在单向三元环，我们只需要对两个图尝试做拓扑排序即可。

B. 凯旋三兵

题目大意：一个长度为 \(n\) 的环，开始全是白色。每次等概率选择两个点 \(i,j\)，从 \(i\) 顺时针到 \(j\)（不包括 \(j\)）染成黑色。当有至少 \(m\) 个点被染色时结束。问期望染多少次。

题解：所求答案等价于 \(\sum_{i=0}^{+\infty}P(A_{i})\)，其中事件 \(A_{i}\) 代表染 \(i\) 次未结束。而 \(P(A_{i})=\sum_{|S|\ge n-m+1}P(S,i)\)，其中 \(P(S,i)\) 表示 \(S\) 中的点未被染色，\(\sim S\) 中的点已被染色的概率。

这样概率仍不好求，考虑容斥。设 \(P'(S,i)\) 表示 \(S\) 中的点未被染色，\(\sim S\) 中的点随意的概率。那么显然有 \(\displaystyle{P'(S,i)=\frac{1}{(1-\frac{\text{cnt}}{n^{2}})^{i}}}\)，其中 \(\text{cnt}\) 表示至少染 \(S\) 中一个点的方案数。我们先给每个 \(P'(S,i)\) 配上一个容斥系数 \(c_{|S|}\)，稍后再求它的值。那么原式就变成了 \[ \begin{aligned} &\sum_{i=0}^{+\infty}\sum_{|S|\ge n-m+1}c_{|S|}P'(S,i)\\ =&\sum_{|S|\ge n-m+1}c_{|S|}\sum_{i=0}^{+\infty}\frac{1}{(1-\frac{\text{cnt}}{n^{2}})^{i}}\\ =&\sum_{|S|\ge n-m+1}c_{|S|}\frac{n^{2}}{\text{cnt}} \end{aligned} \] 我们要让每个集合恰好贡献一次，即为 \(\sum_{j=1}^{i}{n-m+i\choose n-m+j}c_{n-m+j}=1\) 对所有 \(1\le i\le m\) 成立。观察后容易发现，\(c_{n-m+j}=(-1)^{j-1}{n-m+j-1\choose n-m}\)。

事实上这是一个下三角矩阵，就算不能推出式子，也能直接 \(\mathcal{O}(n^{2})\) 暴力解出系数。

当然我们不可能枚举所有的 \(S\)。考虑对每种 \(\text{cnt}\) \(dp\)。

设 \(dp[i][j][k]\) 表示前 \(i\) 个点已经枚举完，第 \(i\) 个点属于 \(S\)，染前 \(i\) 个点中属于 \(S\) 的点有 \(j\) 种方案，前 \(i\) 个点中有 \(k\) 个属于 \(S\) 的 \(S\) 的方案数 。这里 \(i\) 是和 \(S\) 中第一个点的相对位置。\(dp\) 完以后枚举 \(S\) 中第一个点所在位置即可。

C. 朋友

题目大意：给你一棵有根树，每条边有一个权 \(0/1\)。每次可以选取一条权为 \(1\) 的边，将它到根的路径上的边全部取反，不能取者输。问先后手谁胜。

题解：经典的翻硬币游戏。局面的 \(sg\) 值就等于所有权为 \(1\) 的边的 \(sg\) 值的异或。我们用一个 \(0-1\) 串来记录从根到所选的边的权值序列。\(1\) 只能转移到 \(0\)，因此 \(sg\) 值为 \(1\)。\(01\) 只能转移到 \(10\)，因此 \(sg\) 值为 \(0\)。\(001\) 只能转移到 \(110\)，因此 \(sg\) 值为 \(0\)。可以归纳地证明后面的所有 \(sg\) 值均为 \(0\)。因此，当与根相连的边权值异或和为 \(1\) 时，先手胜，否则后手胜。

D. 平行四边形

题目大意：给定两根相交于原点的直线 \(L,L'\)（保证不重合），和一个点集 \(S=\{s_1,\dots,s_n\}\)。现在让你选择四个点 \(A,A',B,B'\) 满足 \(A\in L,A' \in L', B,B'\in S\)。且 \(AA'\) 的中点与 \(BB'\) 的中点重合。最大化四边形（可能退化） \(ABA'B'\) 的面积。

题解：我们把 \(S\) 中的点都变换到 \(L,L'\) 的坐标系下。假设基为 \(\vec{e_1},\vec{e_2}\)，那么 \(B(x_1,y_1),B'(x_2,y_2)\)，可得 \(A(x_1+x_2,0),A'(0,y_1+y_2)\)。面积为 \(|\vec{AB}\times \vec{AB'}|\)。可得：

\[ \begin{aligned} |\vec{AB}\times \vec{AB'}|&=|(-x_2,y_1)\times (-x_1,y_2)|\\ &=|(-x_2\vec{e_1}+y_1\vec{e_2})\times (-x_1\vec{e_1}+y_2\vec{e_2})|\\ &=|-x_2y_2\vec{e_1}\times \vec{e_2}-y_1x_1\vec{e_2}\times \vec{e_1}|\\ &=|x_1y_1-x_2y_2|\cdot |\vec{e_1}\times \vec{e_2}| \end{aligned} \]

我们维护 \(x_iy_i\) 的最大和最小值即可。

E. 扫雷

签到题。

F. 跳蚤国王的游戏

题目大意：给出一个 \(K\) 子棋的残局，问有多少位置先手走了之后在三步之内可以获胜。

题解：维护先后手的制胜（直接获胜）位置集合 \(a,b\)。如果 \(|a|\geq 2, |b|=0\)，那么所有位置都是答案。否则我们枚举第一步的位置，然后维护 \(|a|,|b|\) 的改变，如果 \(|b|=0,|a|\geq 2\) 那么该位置可行。注意枚举位置的时候，只用枚举先手棋子的直接相邻位置，或者直接相邻位置的直接相邻位置（可以在下一步将它连通）。

G. 小R与手机

题目大意：\(n\)个点，每个点有一个后继或者没有。\(m\)次操作，或者修改一个点的后继，或者询问从一个点沿着后继链走会结束在哪个点，永远不会结束输出-1.

题解：模板题，lct不换根维护基环树

H. 异或密码

签到题。

I. 最大的位或

签到题。

J. 最大公约数

定义

int f(int x, int y){
	int c = 0;
	while (y > 0){
		++ c;
		int t = x % y;
		x = y;
		y = t;
	}
	return c * x * x;
}

求 \(\sum_{i=1}^{n}\sum_{j=1}^{m}\lfloor\frac{ij}{f(i,j)}\rfloor\)

题解： \[ =\sum_{j=1}^{m}\sum_{k=0}^{j-1}\sum_{i=0}^{\lfloor\frac{n}{j}\rfloor+[n\mod{j}\ge k]-1}\lfloor\frac{j^{2}i+jk}{f(j,k)+\gcd^{2}(j,k)}\rfloor \] 用类欧计算即可。

Dirt Replay

D: -3 输入太慢；式子推错了（没验证 n=1）；四舍五入用 int。。。。

E: -1 没清空数组，builtin popcount太慢

G: -3 D 不相信自己的模版，瞎改