某屑比赛题解

· · 个人记录

某屑比赛题解

T1

直接令 a_1=400,b_1=500。

如果 c_i 是奇数，那么将 c_i 拆成 [0,1000] 间的整数 x_i,y_i，其中 x_i 个位数字为 5， y_i 个位数字为偶数，然后令 a_i=x_i\times 400/1000,b_i=y_i\times 500/1000。

如果 c_i 是偶数，同样地，将 c_i 拆成 [0,1000] 间的整数 x_i,y_i，其中 x_i 个位数字为 0， y_i 个位数字为偶数，然后令 a_i=x_i\times 400/1000,b_i=y_i\times 500/1000。

可以发现，在题目给定数据范围内，总存在合法的拆分方式。

好了，如果你陷入以上的思路，那么说明你成功被部分分误导了。

事实上，你直接令 A=a_1=400,B=b_1=600（取其它的也有可能可以），然后 a 从 0 枚举到 A，b 从 0 枚举到 B，1000(\frac{a}{A}+\frac{b}{B}) 四舍五入到整数位后仍然可以取遍 [10,1990]，所以你只需要预处理出每个 c\in[10,1990] 的答案然后依次输出即可。

T2

此题暂无正确做法，下面是原 std 错误做法。

如果对于某个点 x，它有两个儿子 l,r，并且 l 子树和 r 子树中都存在黑点，那么容易发现 x 也无法被删去，所以也把 x 染黑。

接下来将所有黑点连出去的儿子边删掉，整棵树就会被分成若干个连通块，可以将每个连通块视作是一个独立的游戏，那么整个游戏就是这些独立游戏的组合，所以只要求出每个连通块的 SG 函数值即可。

观察得到，每个连通块的 SG 函数值就等于这个连通块中非叶节点的数量，这个可以归纳证明：

单个叶子节点的 SG 函数值显然为 0；

考虑拥有 n(n>1) 个节点的连通块的根 x，假设这个连通块中非叶节点数量为 t，有假设可以知道一次操作后得到的状态 SG 函数值显然无法超过 t，接下来只需要证明一次操作后得到的状态 SG 函数值可以取遍 [0,t-1] 即可：

  1. 如果它只有一个儿子 y，那么 SG(y)=t-1，接下来的一次操作如果仅在儿子子树内部执行，那么得到的状态 SG 函数值就可以取遍 [1,SG(y)]，同时儿子节点中至多有一个节点为黑色，且这个节点必然是叶子节点，直接用这个节点替换掉根 u，SG 函数值就可以取到 0，所以得到 SG(x)=SG(y)+1=t。
  2. 如果它有两个儿子 y,z，那么 SG(y)+SG(z)=t-1，且 y,z 中至多有一个子树内部有黑色节点，不妨假设 y 内部有黑色节点，同样的，如果接下来的一次操作仅在 z 内部执行，那么得到状态 SG 函数值就可以取遍 [SG(y)+1,SG(y)+SG(z)]，如果用 y 内部的节点（包括 y）替换掉根，那么 SG 函数值就可以取遍 [0,SG(y)]。两段接起来就是 [0,SG(y)+SG(z)]，所以得到 SG(x)=SG(y)+SG(z)+1=t。

证完就剩下的就很好做了，第一步要赢就是第一步后让各个游戏 SG 函数值异或为 0 即可。

T3

首先猜测任意合法的输入都存在一组解，不然的话出题人的 generator 就会很难写。

由 d=2 的特殊情况可以知道，任意一棵树 T 经过两次淀粉树替换后可以得到任意一条链，由此启发我们先思考这个如何做，考虑到构造淀粉树本身就是一个点分治的过程，如果最终需要得到的链为 a_1,a_2,\dots,a_n ，那么就按照 a_1,a_2,\dots,a_n 自上而下的顺序对 T 进行点分治，这样得到的淀粉树对于任意的 i 都满足 a_1\sim a_i 是一个连通块，于是再按照 a_n,a_{n-1},\dots,a_1 自上而下的顺序再做一次点分治就可以得到这条链了。

对于 d>2 的情况，考虑逆推 S，每一次将淀粉树还原成原树都保证最大度数减小一。这个也好做，先取 S 的一个叶子为根，然后 dfs 整棵树，对于 u 的某个儿子 v ，如果当前 v 为最大度数 d，那么就删去 (u,v) 这条边，然后再在 v 子树中选择一个度数小于 d-1 的一个点 w（这样的点一定存在），连接边 (u,w) 即可。

T4

先不设置根，跑一遍最小树形图，将缩环的过程建树，即将 x_1\to x_2\to\cdots\to x_t\to x_1 缩成环 y 的时候令 x_1,\dots,x_t 都变成 y 的儿子，并且 x_i 父边权值设置为 x_i\to x_{i+1} 的边权减去上一条 x_i 的出边边权，其中 x_{t+1}=x_1。

最后缩环如果得到的不止一个节点，说明原图并不是强连通的，额外设置一个根节点 r 作为剩余节点的父节点，如果 x 有出边 x\to y，那么 x 父边权值设置为 x\to y 的边权减去上一条 x 的出边边权，如果 x 没有出边，那么 x 父边权值设置为 +\infty。

这个树的性质就是，原图中以节点 t 为根的最小树形图权值和就是除去 t 到根 r 路径上的边以外的边权的权值和，对于以一个点集 S 为根类似，不过除去的边权应该是点集内的点到根的这些路径的路径并。

所以答案就很简单求了，依次考虑每条边不被除去的概率即可。