Contest Info

date: 2017.08.12 12:00-17:30

practice link

Solutions

A. Poker Shuffle

题目大意：给出一种洗牌的方式：每次操作将奇数位置的牌和偶数位置的牌分开，保证其内部的顺序不变。然后将奇偶数位置的牌分别放在左右边（右左边）。已知牌的张数为 \(2^n\) ，问是否存在一种方案使得经过若干次洗牌后，位置 \(A\) 是最开始时候位置 \(X\) 的牌，并且位置 \(B\) 是最开始时位置 \(Y\) 的牌。

题解：我们将牌的编号先减去 \(1\)，则两种洗牌操作就是使所有牌的编号二进制右移一位，然后选择在所有原来奇数位置或者偶数位置的牌的编号上最高位（第\(n-1\)位）同时补一个 \(1\)。

这样我们枚举洗了 \(k\leq n\) 次牌，\(X\) 的编号变为 \((opt<<(n-k))|(X>>k)\)，其中 \(opt\) 为这 \(k\) 次操作最高位补 \(1\) 的状态。我们要保证 \(X,Y\) 经过了同样的洗牌操作，所以 \(Y\) 的洗牌序列 \(opt' = opt\oplus ((X \oplus Y) >> k)\)。那么 \(Y\) 就变为了 \((opt'<<(n-k))|(Y>>k)\)。

然而实际上洗牌次数是可以大于 \(n\) 的。洗更多次的牌是在循环移动二进制位，因此我们还是只用枚举 \(k\in[1,n]\)，判断时候改为判断：

\[A[i-k+n]\oplus B[i-k+n]=X[i]\oplus Y[i]\]

是否对 \(\forall i\in [0, n)\) 成立即可。

B. Good Firewall

题目大意：给你一个防火墙的若干个策略组，每个策略组中有若干个 IP 子网。有三种操作：

• 添加一个策略组，给出它的所有 IP 子网
• 关闭一个策略组
• 询问两个 IP 是否同时在一个未关闭的策略组中

题解：用 trie 模拟即可。trie 每个节点用 vector 存储该 IP 子网的策略组编号，以及对应的最小 IP 地址。

C. Sky

题目大意：给出平面上 \(n\leq500\) 个整点，初始状态都不存在。接下来有 \(m\leq1000\) 次操作，每次操作使得编号为 \(i\) 的点改变出现状态，每次操作之后询问，用一些平行线来穿过存在的点，至少要用多少根平行线才能使得每个点都被穿过一次。

题解：先将坐标相同的点处理一下去重。当存在的点大于 \(1\) 的时候， 显然作为答案的平行线至少存在一根是同时穿过了两个以上的点的。于是我们先将 \(\mathcal{O}(n^2)\) 种斜率排序去重（用一个向量来搞，保证向量的 \(x\geq0\)，并且当 \(x=0\) 的时候 \(y>0\)，\(gcd(x,y)=1\) ）。然后将所有的直线搞出来，记录与每个点相关的直线，显然每个点最多和 \(n-1\) 条直线相关。

当出现一个新的点的时候，所有与这个点无关的平行线的答案都会增大 \(1\)，但是与它相关的平行线可能不增加。不增加，当且仅当它不是对应的直线上第一个出现的点，同理处理删除的情况。我们可以搞一个全局的答案 \(delta\)，然后记录每种平行线和全局答案的差值 \(ans_i\)，用一个 \(set\) 来维护一下就可以了。时间复杂度 \(\mathcal{O}(n^2\log{n}+nm\log{n})\)，空间复杂度 \(\mathcal{O}(n^2)\)。

D. Cut the Cake

题目大意：给你一个圆， \(n\) 个点随机落在这个圆上，问所有点落在一个弧度小于等于 \(\frac{2\pi}{m}\) 的扇形中的概率。

题解：枚举一个落在最左边的点，那么剩下 \(n-1\) 个点必须落在它右边弧度为 \(\frac{2\pi}{m}\) 的扇形中，答案为 \(n\cdot \left( \frac{2\pi}{m}/(2\pi)\right)^{n-1}=\frac{n}{m^{n-1}}\) 。

E. Theme Section

题目大意：每次给出一个字符串，询问最长的前缀，满足既是后缀又在中间出现。并且三次出现都不相交。

题解：kmp 建立 fail 数组，然后不断走 fail 数组，直到中间的区间长度大于当前的前缀。然后截取中间的区间去匹配当前的前缀。如果无法匹配，再继续走 fail 数组。

比赛的时候没想太多直接写就过了，其实复杂度比较玄学。更正确的做法是，二分一个前缀，然后将整个串去匹配这个前缀，判断是否合法。fail 数组只用求一次。

F. Stone

签到题， 巴什博弈。

G. Tsp

题目大意：货车司机要给 \(n\) 位顾客送货，第 \(i\) 位顾客的包裹需要在点 \(i^{+}\) 取得，在点 \(i^{-}\) 放下。也即访问点 \(i^{-}\) 之前一定要访问点 \(i^{+}\)。货车的门可以理解为一个栈，后放入的需要先拿出。另外，每个点只能被访问最多一次，并且还需要遵循以下三个原则：

• 如果 \(j>i\)，那么不能从点 \(i^{+}\) 到点 \(j^{+}\)
• 如果 \(j<i\)，那么不能从点 \(i^{-}\) 到点 \(j^{-}\)
• 如果司机已经访问过了点 \(i^{-}\)，那么对 \(\forall j < i\)，点 \(j^{+}\) 会被移除掉，再也不能访问

你可以从任意点出发，求最短的路径使得所有顾客的包裹被送达。每个点以平面上的整点给出，距离为欧几里得距离。

题解：可以将每个顾客看做是一对括号，那么题目给的三个原则翻译一下，就是：编号小于 \(i\) 的所有括号要么在 \(i^{+}\) 之前出现，要么被 \(i^{+},i^{-}\) 给括起来（稍微画一下图就可以证明）。于是，任意一段合法的括号序列的编号都是连续的，是一段区间，我们考虑区间 dp。

那么我们用 \(dp[i][l][r]\) 表示当前在 \(i^{+}\) 点取货，接着要将区间 \([l,r]\) 内的货都送达，最后在 \(r^{-}\) 点结束的最小代价。那么我们的答案就是 \(\text{min}_{i=1}^ndp[i][1][n]\)。考虑状态转移，对于状态 \(dp[i][l][r]\)，我们大概是这样一个过程：

• 若 \(\exists j \in[l,i)\)
  • \(i^{+}\rightarrow j^{+}(j\in[l, i))\)
  • 然后通过 \(dp[j][l][i-1]\)，到达 \((i-1)^{-}\) 这个点，再到 \(i^{-}\)
• 否则，\(i^{+}\rightarrow i^{-}\)
• \(i^{-}\rightarrow k^{+}(k\in(i, r])\)
• 再通过 \(dp[k][i+1][r]\) 到达点 \(r^{-}\)

因为当前的状态表示区间 \([l,r]\) 还未送货，所以如果 \(\exists j\in[l,i)\) 那么说明编号 \(j\) 不在括号 \(i\) 之前出现。又由于合法的括号序列编号连续，所以编号为 \([j, i-1)\) 的都被括号 \(i\) 给括起来，那么最后一定是走到 \((i-1)^{-}\)，再走到 \(i^{-}\)。记忆化搜索即可。复杂度略高，实现的时候要小心常数。

H. Network

题目大意：给你 \(n\) 个点和一个特殊点 \(M\) ，在平面上找一点，满足该点到这 \(n\) 个点距离均不超过 \(d\)。最小化该点与 \(M\) 的距离。

题解：容易发现答案即为 \(M\) 到以这 \(n\) 个点为圆心，半径为 \(d\) 的所有圆的交的最小距离。如果 \(M\) 在这个交中，答案为 \(0\) 。若这 \(n\) 个圆没有交，则无解。

否则，这个交是由一些圆弧组成的凸的图形，距 \(M\) 距离最小的点一定在 \(M\) 到圆心连线和圆的交点处或者 \(n\) 个圆中任意两圆的交点处。这样的点总共有 \(\mathcal{O}(n^{2})\) 个，我们一一验证它们是否在 \(n\) 个圆内，把满足条件的点取距离的最小值即为答案。复杂度 \(\mathcal{O}(n^{3})\) 。但是由于圆个数变多的时候，相交区域就会随之变小，实际的有用的点的个数很少，可以通过本题。

I. Bell

题目大意：求贝尔数 \(B_{n}\text{ mod }95041567\)。

题解：Z 天真的认为这是个质数。还好 W 提醒他分解出来看看。

分解质因数，\(95041567=31\times37\times41\times43\times47\)。而贝尔数满足对任意质数 \(p\)， 有 \(B_{n+p}\equiv B_{n}+B_{n+1}(\text{mod } p)\)。所以我们可以在上述 \(5\) 个质数的模意义下通过快速幂分别求出答案，然后把这些答案通过 CRT 综合起来得到对 \(95041567\) 取模的答案。

J. Flyer

题目大意：有 \(n \leq 20000\) 份传单，第\(i\) 份传单会发给编号为 \(x=A_i+k\times C_i(k\geq 0, x\leq B_i)\) 的所有人。已知最多有一个人拿到了奇数份传单，问是否存在这个人，如果存在输出这个人的编号。

题解：二分答案。如果拿到奇数份传单的人的编号小于等于 \(mid\)，那么编号在 \([l,mid]\) 内的所有人收到的传单总数为奇数。复杂度 \(\mathcal{O}(n\log{ans})\)。