ITMO 2018 China 流水账

ultmaster edited 6 年，9 月前

2017/3/8 已迁移至 WIKI。停止维护。

2017/3/3 zerol add: Day3 C

2017/2/23 ultmaster 更完。等待补缺。

      A B C D E F G H I J K L Rank  Rating
Day 1 · Ø · Ø · Ø O Ø O · O   14/24 42.59
Day 2 · · O O · Ø O Ø Ø O · Ø 52/81 50.33
Day 3 O O O · O O Ø · O Ø Ø O 34/81 83.33
Day 4 O · ! Ø Ø O · · O · O   34/84 77.42
Day 5 O O Ø Ø · O O · · Ø O   9/25  83.33
Day 6 O · O · · Ø Ø O Ø · O   59/88 48.78

O 表示现场通过，Ø 表示补题通过，! 表示尝试但未通过，· 表示尚未尝试。

Day 1

Problem A

Unsolved.

题意：用光线打砖块，问全部打掉的时间。

Problem B

Upsolved by ultmaster. 04:59 (-8)

题意：求能通过正向边达到的点的集合和通过反向边达到的点的集合的并集是所有点集的，有哪些点。

题解：先缩点，然后转换成拓补序上的问题。对于一个点只考虑拓补序比它小的点是否能都到达它（另外一边是对称的问题）。这个判断的充要条件是，删去所有指向右边（拓补序比它大）的点的边后，左边的点出度都大于 0。这样，左边的点总能通过一定的路径达到这个点。

比赛的时候过度纠结能达到的点的数量，而没有考虑这个题实际上不是问数量，而是问「是不是」。

Problem C

Unsolved.

Problem D

Upsolved by ultmaster | zerol.

题意：将所有子集以子集和为第一关键字，子集内的下标的字典序为第二关键字排序，求第 $k$ 大的。

题解：

ultmaster: 按照一定顺序生成所有子集，然后 Dijkstra。生成的方法是：对当前的集合：

zerol: 参考了标程，实在是炫酷。

Problem E

Unsolved.

Problem F

Upsolved by ultmaster.

题意：取出一些元素，元素的个数是 $d$ 的倍数，使得剩下的元素异或和为 $0$ 。问有多少种取法。

题解：先从小到大排序，$dp(i,j,k)$ 表示对于前 $i$ 个，取出的元素数量 $\bmod d = j$ ，异或和为 $k$ 的方案数，显然答案就是 $dp(n,0,0)$。对于第一维做滚动，对于第三维，这样的做法的正确性基于所有数的和不会太大，均摊下来是正确的。

Problem G

Solved by zerol. 01:19 (+)

题意：给定一颗树，求一条链使得 $2+\sum (d(u)-2)$ 最大（$d(u)$ 为结点 $u$ 的度数），输出这个值。

题解：很常规的树形 dp。但是要注意某个点只有一个儿子或者没有儿子的情况。

Problem H

Upsolved by zerol.

题意：求一个点到另一个点不经过起点和终点，中间的点和边可以经过任意多次的，一定长度的路径的方案数。询问特别多。

题解：

$$allPath(u,v,l)=\sum_{i=1}^{n} allPath(u,i,d-1) hasEdge(i, v) \ startNoCircle(u,v,l) = allPath(u,v,l) - \sum_{i=1}^{l-1} allPath(u,u,i) startNoCircle(u,v,l-i) \ circleOfUWithoutV(u,v,l) = allPath(u,u,l)-\sum_{i=1}^{l-1} allPath(u,v,i) circleOfUWithoutV(v, u, l - i) \ ans(u,v,l) = startNoCircle(u,v,l) - \sum_{i=1}^{l-1} ans(u,v,i) circleOfUWithoutV(v,u,l-i)$$

Problem I

Solved by zerol. 02:26 (+)

题意：从 1~n 的最小排列到当前排列依次变化，求每一步需要的最小交换次数之和。

题解：打表找规律。设当前是第 $k$ 个排列，那么答案为 $\sum_{i=0}^\infty \lfloor \frac{k}{(2i)!} \rfloor$。

Problem J

Unsolved.

题意：有一系列的堆对（每一对有两个堆）。先手可以从任意一堆中移除任意多的石子，后手可以在同一对石子中将一堆中的某一些移到另一堆中。先手希望尽快结束，后手希望进行尽可能长的时间。问轮数。

Problem K

Solved by ultmaster. 03:20 (+3)

题意：求一个最长的子序列，形如 $(a_1,a_1,a_2,a_2,\ldots)$。

题解：如果没有内存限制 32 MB 的话，显然有状态转移方程：$dp(i,j)=\max{dp(i-1,j),dp(i,j-1),dp(back(i)-1,back(j)-1)+2}$。但这样的状态显然是存不下的。我们考虑对于每一个状态在转移时所需要的状态。注意第三个状态，对于每一列，由于这一列上的数字是固定的，所以在经过多行之后，只要不遇到这个数，这个状态就不会改变。当更新时，从大往小刷新就好了。注意 $dp(i,j-1)$ 转移时要从小往大刷新。

Day 2

Problem A

Unsolved.

题意：有 $n$ 个柜台，每一个柜台有一个固定的处理时间 $t \sim U(l,r)$，实际需要处理的时间 $t’ \sim U(0,t)$。求 $\mathrm{Prob}(t \mathrm{\ is\ minimum}| t’ \mathrm{\ is \ minimum})$。

Problem B

Unsolved.

题意：一颗带边权的无向树，有巡逻路径 $v_1,v_2,\ldots,v_k$。目标是从 $s$ 到 $t$ ，不能在路径上与巡逻相遇。

Problem C

Solved by zerol. Upsolved by ultmaster. 03:59 (+9)

题意：交互题。起始时庄家拥有一块巧克力。游戏共进行奇数轮。玩家是先手，每一轮可以从对方的巧克力中选择一块切 $(\frac{1}{3}, \frac{2}{3})$ 收入囊中。庄家没有策略，随机选择，切 $\frac{2}{3}$ 。求一种策略，使得最终获得的巧克力大于 $0.55$。

题解：第一次取 $\frac{1}{3}$，最后一次将剩下的 $\frac{2}{3}$ 中取出 $\frac{2}{3}$。那么中间只需要获利 $0.1$ 即可。注意到每次取最大的取 $\frac{2}{3}$ 可以获利约 $0.5$。

其实一开始的做法就是对的，ultmaster 写错背了大锅。后来用一种诡异的做法过了。

Problem D

Solved by kblack. 01:49 (+1)

题意：给出 $2^n$ 个人的锦标赛，问排名为 $k$ 的人期望能打的轮数。

题解：$\mathrm{Prob}(\mathrm{Will \ participate \ in \ round} \ i) = \displaystyle\frac{\mathrm{worse} \choose 2^{i-1}-1}{\mathrm{all} \choose 2^{i-1}-1}$ 。求阶乘时取对数以避免浮点数误差。

Problem E

Unsolved.

题意：有 $n$ 个人的锦标赛（$n$ 可能为奇数）。每轮都重新分组（可能有人轮空），问有多少种可能性。

Problem F

Upsolved by ultmaster.

题意：求有多少个 $n \times m$ 的 01 矩阵满足：所有 0 都连通，所有 1 都不连通。

题解：首先状压 DP，可以使用类似并查集的方法记录状态，然后通过广搜的方法加边，搜出所有状态所有边。然后跑出 $n \le 2000$ 时的答案。然后猜通项满足一个齐次线性递推，使用 Berlekamp-Messy 算法在 $O(n^2)$ 时间内解出线性递推的系数。然后使用特征多项式优化转移矩阵快速幂，就可以在 $O(k^2 \log m)$ 时间内求到答案。这里 $k \approx 900$。

后两步有模板，难点在状压 DP。

Problem G

Solved by kblack. 01:33 (+2)

题意：有 $n$ 张椅子排成一排，每张椅子都有一个颜色，每种颜色都有 $1/c$ 的概率被裁判选中。一开始要选择一张椅子，使得走到被裁判选中的颜色的椅子的最少步数的期望值最小。

题解：相当于是 $c$ 个函数。所有函数的拐点不会太多。所以从左到右扫描模拟即可。

kblack 看错题，以为是一个圈，居然神奇地过了样例。

Problem H

Upsolved by kblack.

题意：求一个排列 $p$，最小化 $\displaystyle\sum_{i=1}^n \min_{1\le j \le i} a_{p_i} \oplus b_{p_j}$。

题解：在 $i$ 和 $j$ 之间连双向边，代价是 $a_i \oplus b_j$。$-1$ 到 $i$ 连单向边，代价为 $a_i \oplus b_i$。以 $-1$ 为根跑最小有根生成树。

Problem I

Upsolved by ultmaster.

题意：给一个字符串，问有多少子串符合给定的模式。模式是：规定字符串的某些位置相等。

题解：在相等的两个关系之间列出一个多项式，然后将原串倒置，做卷积就能得到答案。例如：

模式串是 1 2 2 3 2 3，列出多项式 $a_1(x^2-x^3)+a_2(x^3-x^5)+a_3(x^4-x^6)$ ，其中 $a_1,a_2,a_3$ 是随机选取的。原串是 3 2 2 1 2 1 1，将其反转得到 1 1 2 1 2 2 3，对应的多项式为 $1 x^1+1 x^2 +2 x^3 + 1 x^4 + 2 x^5 + 2 x^6 + 3 x^7$。做卷积后可以发现每一个匹配的位置恰好对应多项式的一项。匹配成功当且仅当该项系数为 $0$。

Problem J

Solved by zerol. 01:50 (+)

题意：跳砖块。每次可以跳砖块上写的数字格，或者上次跳的长度。问 $1$ 到 $n$ 的方案数。

题解：

Problem K

Unsolved.

Problem L

Upsolved by ultmaster | zerol.

题意：考试考的知识点是服从 $U(0,1)$ 的一个随机变量。每天可以 cover 一段知识点，不通过当天的考试的话，明天继续。必须要在 $k$ 天内通过。知识点不会忘记。求学习知识量的期望的最小值。用分数 $\frac{P}{Q}$ 表示，分别求 $P \bmod M, Q \bmod M$。

题解：$f(1)=1,f(k+1)=\min_t (t^2+(1-t)f(k))=f(k)-\frac{f^2(k)}{4}$。这一递推关系会使得 $f(k)$ 的周期在 $\sqrt{M}$ 级别。所以先求出 $\frac{P}{Q} \bmod M$，再求出 $Q \bmod M$，最后求出 $P \bmod M$。

Day 3

Problem A

Solved by kblack. Upsolved by ultmaster. 02:33 (+1)

题意：将一个多重集分成两个集合，使得两个集合异或和的差的绝对值尽可能小。

题解：如果全体异或和为 $0$，那么显然答案就是 $0$。否则让较大的那个集合的异或和在全体异或和非零的位尽量保持 $100000\cdots$ 的形状。方法是求出所有数的异或线性基，从高位往低位贪心即可。如果某一位全体异或和为 $0$，那么直接将该位 ignore 掉。

比赛的时候只有 kblack 会线性基。不过现在我也会了（误）。

Problem B

Solved by ultmaster. 00:25 (+3)

题意：已知所有子集和，将原序列还原出来。

题解：选出最小的，一定是最小的元素，然后其余元素就能两两配成差为最小的元素的对，然后长度减半，迭代解决。

多校的时候有一道完全一样的题目。然而这道题还是三发。

Problem C

Solved by zerol. 01:45 (+)

题意：序列 $i_1<i_2<\ldots<i_k$ 满足 $a_{i_1} < a_{i_2} < \ldots < a_{i_k}, b_{i_1} < b_{i_2} < \ldots < b_{i_k}$，求最大的 $k$。

题解：树套树，查询的是左下方的一块区域内的最大值。但这样做空间复杂度是 $O(n \log^2 n)$，据说过不了（但是我们突然过了）。有空间复杂度 $O(n)$ 的做法待补。

zerol: 空间一手抖开小了，所以没爆内存。（所以是数据造弱了，还是代码写得好？）所以 CDQ 分治好，也更加好写，最重要的是线性内存。（伪题解）

Problem D

Unsolved.

Problem E

Solved by zerol. 03:08 (+2)

题意：有 $k$ 个长度为 $n$ 的 01 串等待鉴别。每次可以询问某一个位置上是 0 还是 1，可以根据上一次的答案进行追问。求全部鉴别出来的最小询问次数。

题解：由于 $n$ 不大，直接对每一位置三种状态：未知、已知 0、已知 1。每一种状态组合都恰好对应了一个子集。如果子集中元素恰好为 1 个，那么就需要 0 次。难点在于还有一种子集中没有元素的情况需要另外判断。

ultmaster 写错了，虽然赛后调了一会就过了。然而 zerol TLE 的程序 long long 改 int 突然 AC 了，于是，摊手。。。

Problem F

Solved by zerol. 00:15 (+)

签到。

Problem G

Upsolved by kblack.

题意：有一个 $2^n$ 个顶点的完全图，顶点标号为 $0$ 到 $2^n-1$。两个顶点之间边权是两个顶点标号位异或的二进制中 1 的个数。现求该图的最小生成树。

题解：考虑 Prim 算法的过程。每次新加进来一个点，就用广搜将这个点到所有点的距离进行更新。由于距离变化次数不超过 $n$ 次，所以总的复杂度是 $O(n 2^n)$ （均摊）。优先队列会超时，需要对每个距离开桶。

比赛的时候一直在想 Kruskal 的过程。据说 Kruskal 也能做？

Problem H

Unsolved.

题意：从左上走到右下，只能向右向下走；再回到左上，只能向左向上走，经过的格子被染色。现在已知每行每列的染色格子个数，求方案数。

题解：知道了格子个数之后，形状是唯一的。构造出来就好了。

Problem I

签到。

Problem J

Upsolved by kblack.

题意：给出了一个组合数 $n \choose k$ 的质因数分解，求 $n,k$。

题解：枚举 $n$，然后二分出 $k$ 可能的范围（通过对数计算），然后用随机数取模验证成立。

已经有好几题用到随机质数取模了。这个思想一定要注意。这个题刚开始从数论的角度考虑，只能说题目太有迷惑性了。

Problem K

Upsolved by zerol.

题意：问树上有多少无序三元组对使得两两距离相等。

题解：

Problem L

Solved by ultmaster. 01:36 (+2)

题意：求两个字符串允许有 $k$ 个位置不同的最长公共子串。

题解：平移一个字符串，然后将相邻的相同的位置合并为一个区间，然后就是经典的滑动窗口。

写错了好几次，差点对了拍，在 kblack 的帮助下艰难地过了。

Day 4

Problem A

Solved by zerol. 00:49 (+2)

题意：总共有 $n$ 个座位围成一圈，不能有同性相邻，所以肯定有位置是空着的。在一定询问次数内确定至少一个空位置。

题解：每次确定已知座位对面的座位，从而确定空着的座位在奇数的区间内还是偶数的区间内，然后转换成子问题。一定要注意边界！

Problem B

Unsolved.

Problem C

Unsolved. 04:59 (-8)

题意：给一个格点三角形，问是否存在一个格点在三角形内。

Problem D

Upsolved by ultmater.

题意：有一个背包支持三种操作：

  1. 放一个东西，东西的重量是递增的~~（好像并不显然）~~。
  2. 拿掉一个质量最小的东西。
  3. 查询重量和 $\bmod MOD$ 在 $[l,r]$ 内的东西的价值和的最大值。

题解：用两个栈来模拟一个队列，这样的话 pop 和 push 操作都仅会对 DP 的最上面一层产生影响。一个栈空了要把另外一个栈倒过去全部重算。合并两个栈最顶层的时候可以用滑动窗口 + 单调栈。

Problem E

Upsolved by ultmaster.

题意：每次可以选择树上的一条路径异或一个数，问要几次操作把整棵树都变成 0。

题解：大力分析。

第一步：树上的任意路径可以转换成两条到根上的路径，由于异或的特殊性，不加不减正正好好。

第二步：这样我们就可以从叶子节点往上消，每个节点到根的那条路径要异或多少也知道了。

第三步：然后两两配对，能配的先配。最后 $[0,15]$ 顶多剩 $16$ 个。暴算一下就好了。

Problem F

Solved by kblack. 02:27 (+2)

题意：在树上装 $k$ 个雷达，使得每个点对应一个 $k$ 维向量，这个向量的每一维就是到这 $k$ 个雷达的距离。现在求最小的 $k$ 把所有点区分出来。

题解：不大会。

Problem G

Unsolved.

神题。

Problem H

Unsolved.

题意：一棵有根树，每个节点上都有个权值。要在规定操作次数内使得 $a_0,\ldots,a_{N-1}$ 有序。每次操作可以选中一个节点，把这个节点到根的链做一步旋转。

Problem I

Solved by ultmaster. 03:41 (+)

题意：区间操作：加，除，求最大值。

题解：由于除法操作会使得数与数之间的差变小，多除几次就全相等的。我们不妨将除法操作转换成加法操作：也就是说，如果区间内最大值除过后与最小值除过后造成的影响（delta）相等，我们就直接执行加法操作，不然就递归。复杂度 $O(n \log n \log C)$ ，不会证。

Problem J

Unsolved.

题意：$H \times W$ 的方格纸，有 $N$ 个禁手，求剩下的 $H \times W - N$ 个格子两两之间的距离之和。

Problem K

Solved by kblack. 00:33 (+2)

题意：给一个森林，加边使得森林连通。用过的点不能再用，加边的代价是点权之和。

题解：关键在于要选哪些点，显然要选 $2(N - M - 1)$ 个点。每个连通分量里至少要有一个。剩下的乱选。选尽量小的。

Day 5

Problem A

Solved by ultmaster. 00:07 (+)

签到。

Problem B

Solved by kblack. 00:57 (+)

题意：将 $n$ 分成若干个数，使得每个数的出现的次数二进制上 1 的个数之和最大。

题解：不会。

Problem C

Upsolved by ultmaster.

题意：构造一个 $n$ 边形，使得恰好有 $k$ 条内对角线。

题解：先构造一个内对角线最少的 $n$ 边形，然后逐步增多对角线。

Problem D

Upsovled by ultmaster.

题意：有 $n$ 个猴子，$i<j$ 可以保证有 $p$ 的概率能打赢。求选出 $k$ 个使得这 $k$ 个猴子能全部战胜 $n-k$ 个猴子的概率。

题解：

若 $p=\frac{1}{2}, f(k)={n \choose k} 2^{k(k-n)}$

若 $p\ne \frac{1}{2}$，$$f(k+1)=f(k) \frac{(1-p)^{n-k}-p^{n-k}}{(1-p)^{k+1}-p^{k+1}}$$

Problem E

Unsolved.

题意：电影院中有些座位已经被占了，求有多少种方案可以买到一排中连续的若干个座位。

Problem F

Solved by zerol. 02:49 (+)

题意：每个选民有一个有序的候选名单。每一轮投票时，选民会选出候选名单中票数最多的那位，如果有两人并列，则选择名单上靠前的。投票结果不变时不再投票。构造一份名单集，使得投票至少要进行 $p$ 轮。

题解：使得每一轮恰好有一个人倒戈给 1。

Problem G

Solved by kblack. 04:55 (+8)

题意：问有多少个不同的等差数列 ${a_i}$ 使得 $l_i \le a_i \le r_i$。

题解：考虑枚举 $d$，求可能的 $a_0$ ：由 $l_i \le a_0 + d \cdot i \le r_i$，可以得到 $a_0$ 有关 $d$ 的两个函数：$a_0=l_i-id,a_0=r_i-id$。总共可以得到 $2n$ 的函数，这 $2n$ 个函数可以交出一块区域。对于每一个 $d$，在可行域内都有 $a_0$ 的一个上界和一个下界。

kblack 绝杀，完成唯一一个 Last Hour。

Problem H

Unsolved.

题意：在 $1$ 到 $n$ 的数轴上走路，要走成哈密尔顿回路。有一定条件可以飞（互质的情况下）。问最少要飞几次。

题解：（口胡）据说最多只要 3 次。3 次的时候 Randomly check 一下。

Problem I

Unsolved.

Problem J

Upsolved by ultmaster.

Problem K

Solved by zerol. 03:20 (+1)

题意：求有多少个非空集合满足 $gcd=1$ 且 $lcm=m$。

题解：$m=p_1^{k_1}p_2^{k_2} \cdots p_n^{k_n}$。这个集合中一定满足对于每一个质因子都有一个数质因子幂为 $0$，都有一个数质因子幂为 $k_i$。也就是说对于每一个质因子而言都存在两个规定要存在的东西。运用容斥原理。答案等于：全体，减去不存在一个的数量，加上不存在两个的数量，云云。问题在于 $n=15$，$2n=30$，直接这样做会超时。我们注意到对于每个质因子有两部分的答案是对称的。由此可以优化到 $O(3^n)$。

Day 6

Problem A

Solved by ultmaster. 01:27 (+)

题意：非常复杂。大致就是说有一堆人按顺序选大技能小技能，大技能只能选一个。最优化队伍技能和。求最优策略下的结果。

题解：状压一下暴搜搜就好了。没大写过博弈类状压的 ultmaster 现在也学会了。

Problem B

Unsolved.

题意：一棵树，每条边的期望长度服从 $U(0,1)$，求树的期望直径。

Problem C

Solved by kblack. 00:50 (+)

待补。

Problem D

Unsolved.

Problem E

Unsolved.

题意：$Oneness$ 是指，一个数十进制下 1 的个数。求 $\sum_{i=1}^n Oneness(i)$。$n$ 是随机生成的，不超过 $250~000$ 位。

Problem F

Upsolved by ultmaster.

题意：给定一个偶数长的字符串，规定 $\mathrm{shuffle}(s)=s_1s_3\ldots s_{n-1}s_2s_4\ldots s_n$。求需要多少次 shuffle 操作才能把 $a$ 变成 $b$。

题解：shuffle 是一种置换操作，能够求出置换环。在置换环内用 KMP 求出最小达到的步数，并求出置换的周期。用 CRT 求得答案。

Problem G

Upsolved by ultmaster. 04:58 (-41)

题意：给定一些点，问这些点连成的直线能否表示成 $f(x)=\sum_{i=1}^m \lambda_i |x-a_i|$。

题解：简单列出方程就可以求出所有 $\lambda$，由于方程比未知数数量多一个，必须代入一个方程验证是否成立。遗憾的是，此题精度上无法卡过，GG。

正确的做法是 $\bmod P$ 进行验证，也可以大力化简方程 $O(1)$ 验证。ultmaster 立了个大 flag。然后使用各种语言，交了 40 多次。。。对此题的失败负有重大责任。

Problem H

Solved by kblack. 02:14 (+2)

题意：说不清楚。

Problem I

Upsolved by ultmaster. 02:15 (-2)

题意：交互题。给出 $n$ 个栈，每个栈有 $k$ 个元素。每次你选择一个 $x$，然后机器会选择一个符号 $\ge$ 或 $\le$，表示移除栈顶上 $\ge x$ 或 $\le x$ 的元素，然后会返回栈顶的所有元素。要求在若干次操作内全部移完。

题解：一种明显的错误解法是每次选择中位数，这样选择的错误之处在于可能有一些栈永远得不到移除，我们有的时候需要迫使机器将那些高度大的栈进行移除（选择相等的元素）。由此我们需要做一些小修改，将中位数改成加权中位数，权重为 $2^h$（$h$ 为栈的高度）。

Problem J

Unsolved.

Problem K

Solved by zerol. 01:37 (+2)

待补。

Past Versions

Comments

zerol
6 年，10 月前

催更

回复
ultmaster
6 年，10 月前

我在更 Polygon。各路破事积压，又持续摸鱼。效率极差。

回复
kblack
6 年，10 月前

摸鱼侠路过点赞（捂脸）

回复

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn