Contest Info

date: 2018.12.08 10:21-15:21

practice link

Solutions

A. Create the Best Pet

暴力算盐即可。

C. Clique Festival

题目大意：

有一个\(n\le10^5\)个点的无向图，一开始没有边。

之后\(k\le18\)次操作，每次选出若干个点，增加一个选中点组成的团，团中每条边的权值为\(a_i\).

令\(dis(i,j)\)为\(i\)到\(j\)的最短路长度，求\(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} dis(i,j)\).

题解：

先floyd一次求出每两个团之间的最短路，然后就是计算每个最短路贡献多少个点对。

记\(\text{mask}[x]\)为点\(x\)出现在哪些团中的二进制状态，\(\text{mask}_{cnt}[s]\)为\(\text{mask}[x]=s\)的\(x\)的个数。

简单的用\(O(2^k\cdot k)\)算出\(dp[s]\)，表示\(\text{mask}[x]\subseteq s\)的个数。

之后记\(\text{mask}_{vis}[s]\)表示\(\text{mask}[x]=s\)的点已经计算过和\(\text{mask}_{vis}[s]\)中的团的贡献。

那么，将\(k^2\)条最短路径排序，从小到大计算点对数量。

当枚举到\((i,j)\)这一对最短路时，枚举包含\(i\)的\(s\)，并且\(\text{mask}_{vis}[s]\)不包含\(j\)，则点对数量有\(\text{mask}[s]\times(dp[s\oplus \text{mask}_{vis}[s]] - dp[s\oplus \text{mask}_{vis}[s]\oplus 2^j])\)，之后再将\(j\)加入\(\text{mask}_{vis}[s]\)中即可。

注意到这时，多算了每个点到自己的最短路，减去后，每一对最短路恰好被计算了两次，除以\(2\)就是答案。

时间复杂度\(O(n+k^3+k^2\log{k}+k^2\cdot2^k)\).

D. Distance in Crosses

题目大意：给出了一个无限大的棋盘，棋盘被分割成了无限个十字，问两个点到达对方最少经过多少个十字边界。

题解：把棋盘旋转 45 度，对十字中点建立坐标系，那么答案就是两个点所在十字中点的曼哈顿距离。

E. Lui and Lines

题目大意：给出 \(n\) 维空间中的两条直线，求它们的距离。

题解：列出两条直线的方程，可发现任意两点的距离是个二次型，相合到标准型即可求最小值。

F. Dominating Subarray

签到题。

G. Least Number

签到题。

H. Galactic Governments

题目大意：

在一个\(k\le10\)维空间中有一个大的立方体 \[ U={(x_1,\cdots,x_k)\in \mathcal{R}^k:0\le x_i\le C} \] 立方体中有\(n\le18\)个小立方体， \[ G_i=\{(x_1,\cdots,x_k)\in U:a_{i,j}\le x_j\le b_{i,j}\} \] \(a_{i,j}\)和\(b_{i,j}\)都是\([0,C]\)的整数。

求一个字典序最小的点\((\beta_1+\frac{1}{2},\cdots,\beta_k+\frac{1}{2})\)在\(U\)中而不在任何一个\(G_i\)中

题解：

如果\(n\)个立方体的体积并小于\(U\)的体积，就一定有解。

依次确定\(\beta_i\)，每一位都二分找到一个最小的\(mid\)，使得\(\cup G_i\)不能填满\([0,mid+1]\times\cdots\times[0,C]\)，那么\(mid\)就是这一位可以取得的最小值，然后再用\([mid,mid+1]\times\cdots\times[0,C]\)与每个\(G_i\)求交集，降维处理。

时间复杂度\(O(2^n\cdot nk^2\log{C})\).

I. Multiplication

题目大意：给出一个整数 \(x\)，要求你问 \(n\) 个数， interactor 返回其中任意 \(\frac{n}{2}\) 个数分别乘上 \(x\) 的值。要求你猜出 \(x\)。所有数在 \([0,2^{31})\) 内，运算在模 \(2^{31}\) 下。

题解：问前 \(n\) 个奇数，暴力筛出答案即可。

J. Guess Two Strings

题目大意：交互题，给定 \(N=100,K=15,Q=100\)，有两个长度为 \(N\) 的 \(0/1\) 串 \(s,t\)。你可以问 \(Q\) 次，回答会随机选择一个串，然后随机选择它的一个 \(K\) 子集把他们取反，然后输出给你。求原串。

题解：对于某位，如果 \(s,t\) 相同，那么它被改变的概率是 \(\frac{15}{100}\)，所以我们对每个位统计 \(0/1\) 的个数，如果出现了接近 \(15:85\) 的比例，那么我们能确定这一位。否则这一位 \(s,t\) 不同。

我们随便找到一个不同的位，把这一位按照 \(0/1\) 分成两堆（分别属于 \(s,t\)），然后对每一个还没有确定的位求众数。

K. Beautiful Tables

题目大意：

有一个\(n\times m\)的矩阵，一些格子是空的，一些格子填了整数。

定义一个矩阵是好的，当且仅当，每一个有左右邻居的格子，等于其左右邻居的和的一半；每一个有上下邻居的格子，等于其上下邻居的和的一半。

求是否有解，有唯一解输出该唯一解，有多解输出两组不同解（分数形式）。

题解：

直接列方程高斯消元，复杂度\(O(n^3m^3\log{\text{值域}})\).