Contest Info

date: 2018.12.01 13:00-18:00

practice link

Solutions

B. Origami

题目大意：

有一个\(1\times n\)的纸条若干次折叠后变成了\(1\times 1\)，给出从上到下是原来的哪一段，判断是否合法。

题解：

任意相邻的两端，需要一个左边或者右边的线段将它们连接起来，同时保证没有交叉（可以包含或相离），判断是否可行。

如果可行，每次随便从左边或者右边选能行的一边连接即可，否则就不行。

判断交叉，可以给每个线段随机一个权值，一对端点取相同的权值，然后询问区间异或和，如果不为零就不合法。

时间复杂度\(O(n\log{n})\).

D. The Easiest One

题目大意：定义 \(f(x,y)\) 表示使用如下两种操作将 \(x\) 变成 \(y\) 的最小操作次数：将 \(x\) 自减 \(1\)，或者将 \(x\) 的某个为 \(1\) 的二进制位置零。求 \(\sum_{i=0}^{n}\sum_{j=0}^{i}f(i,j)\)。

题解：假如 \(x\text{&}y=y\)，那么 \(f(x,y)\) 显然等于 \(\text{bitcount}(x\oplus y)\)。否则我们设第 \(i\) 位前面的部分 \(x\) 比 \(y\) 大，后面的部分 \(x\) 比 \(y\) 小，那么显然我们要把后面的部分清零，然后减 \(1\)，这时显然 \(x\text{&}y=y\)。

之后我们开始数位 \(dp\)。设 \(dp[i][0/1][j][0/1][0/1]\) 表示 \(dp\) 到第 \(i\) 位，\(x\) 是否已经大于 \(y\)，在最后一个 \(x\) 大于 \(y\) 后 \(x\) 和 \(y\) 有多少个位相等，\(x\) 的前 \(i\) 位是否和 \(n\) 相同，若 \(x\) 已经大于 \(y\)，在后面的位中 \(y\) 是否已经大于 \(x\) 的方案数。转移太恶心不想写了。

时间复杂度 \(\mathcal{O}(n^{2})\)。

E. Set

题目大意：设有 \(n\) 个集合，每个集合的大小为 \(m\)。且要求 \(|S_{i}-S_{i-1\mod{n}}|=l_{i}\)。求满足条件的 \(|\bigcup S_{i}|\) 的最小值。

题解：考虑二分，问题转化为 check 能否用不超过 \(mid\) 个元素填出所有的集合。设 \(min_{i}\) 表示前 \(i\) 个集合合法的前提下，\(|S_{0}\cap S_{i}|\) 的最小值，\(max_{i}\) 表示最大值。并且感受一下可以发现 \(|S_{0}\cap S_{i}|\) 在 \([min_{i},max_{i}]\) 中连续取值。转移时稍微讨论一下即可。

时间复杂度 \(\mathcal{O}(n\log m)\)。

F. Old Problem

题目大意：给你一个 \(n\times m\) 的网格（有 \((n+1)\times(m+1)\) 个格点），求面积为 \(\frac{s}{2}\) 的格点直角三角形的数量。

题解：这个问题的主要难点在于统计不与坐标轴平行的三角形的数量。该问题的本质是求不定方程 \(x^{2}+y^{2}=n\) 的所有本原解（\((x,y)=1\) 的解）。

由数论知识可以知道，上述方程有本原解，当且仅当 \(n\) 至多有一个 \(2\)，且其它质因子膜 \(4\) 余 \(1\)。本原解的数量为 \(2\) 的（不同的膜 \(4\) 余 \(1\) 的质因子的数量）次幂。并且可以证明，设 \((x_{1},y_{1})\) 和 \((x_{2},y_{2})\) 分别是 \(n\) 和 \(m\) 的本原解，且 \((n,m)=1\)，那么 \((x_{1}y_{1}+x_{2}y_{2},|x_{1}y_{2}-x_{2}y_{1}|)\) 和 \((|x_{1}y_{1}-x_{2}y_{2}|,x_{1}y_{2}+x_{2}y_{1})\) 是 \(nm\) 的两个不同的本原解。因此，我们可以对 \(s\) 的所有膜 \(4\) 余 \(1\) 的质因子的所有幂次求出唯一的本原解（只要 \(x<y\) 的那个）， 对于每个 \(n\) dfs 一次即可求出所有本原解。

H. Accel World

题目大意：给定一个带权无向图，有一些点是加速点。你需要从 \(1\) 走到 \(n\)，初始速度为 \(1\)，每经过一个加速点速度翻倍，不允许连续两次在同一个点加速。问你最少的时间，以及最少时间下最多经过多少个加速点，如果可以经过无穷个输出 Burst!。

题解：我们先 floyd 求出两两点不通过加速点互相到达的最短路，然后 dp。\(\text{dp}[i][j]\) 表示我目前已经经过了 \(i\) 个加速点，到达了加速点 \(j\) 的最短路，那么我可以用 \((\text{dp}[i][j] + \text{dis}[j][n]/2^i,i)\) 来更新答案。同时用 \(\text{dp}[i][j] + \text{dis}[j][k]/2^i\) 更新转移 \(\text{dp}[i+1][k]\)。

精度比较卡，要用 __float128，然后 \(\text{dis}\) 数组可以每次迭代乘 \(0.5\)，dp 第一维大概 \(300\) 次，然后判断答案大于 \(200\) 输出 Burst!。

I. Hello, Hello and Hello

题目大意：给你一个 \(0,1,2\) 组成的字符串，且 \(0\) 在 \(1\) 前，\(1\) 在 \(2\) 前。现在每次操作可以取出一个区间，将它放在最后。求一种方案，用最小的操作次数使得所有相邻的数不相等。

题解：分类大讨论。。就不写题解了。