Contest Info

date: 2018.08.10 12:30-17:30

practice link

Solutions

A. City Wall

题目大意：有一个无限的正六边形密铺的平面，求能围出至少 \(n\) 个格子的围墙的最小长度。

题解：猜测围墙的形状应该近似是一个正六边形，为保证正确可以允许有一个 \(\pm10\) 的误差，暴力枚举长度即可。

comment: 最后的形状是

             i                                       i+1
       ______________                          _______________
      /              \                        /               \
   j /                \ j                j-1 /                 \ j-1
    /                  \                    \                  /                  
    \                  /                   j \                / j
   j \                / j                     \______________/
      \______________/                        
             i                                       i

其中 \(j\in [i-10, i+10]\)。

B. Domino Coloring

题目大意：给出一个 \(n\times m\) 的网格图（\(1\le n\le6,1\le m\le300\)）, 要用 \(1\times2\) 的骨牌去覆盖它。每个骨牌一半白一半黑，有多少种染色不同的局面, 答案取模。

题解：记 \(\text{dp}[i][j][\text{color}][\text{mask}]\) 为枚举到格子 \((i,j)\)，轮廓线上颜色的状态为 \(\text{color}\)，可能的插头状态的集合为 \(\text{mask}\) 的方案数。这样一来，考虑已经决策的部分，颜色完全相同的局面对应的 \(\text{mask}\) 插头状态集合也应该完全相同, 也就不必考虑重复计算的问题。

虽然看起来 \(\text{mask}\) 的范围是 \([0, 2^{2^6})\)，但是实际上经程序验证，对于一组确定的 \((i, j, \text{color})\)，不同的合法 \(\text{mask}\) 最多只有 \(74\) 个，可以用 map 实现。

时间复杂度为\(\mathcal{O}(nm\cdot2^{2n}\cdot S)\)，空间复杂度为 \(\mathcal{O}(2^{n}\cdot S)\) ，这里的 \(S\le74\)。

C. Counterquestion

题目大意：给出一个长度大概不会超过 \(30\) 的小写英文单词, 其中恰好有 \(10\) 个不同的字母。要求给单词每两个相邻字母之间插入一个\(<,>,=\), 使得满足这些不等关系的字母到 \([0,9]\) 的所有一一映射，有且仅有一个。或者判断不可能。

题解：等价于 \(n=10\) 个点的无向图, 在每两个有相邻关系的字母间连边, 原问题有解等价于图中有一条长度为 \(10\) 的简单链。

若有解, 则按这条链的顺序进行映射并输出不等关系即可。可以记录链上点的集合与端点来进行 dp （搜索）, 时间复杂度 \(\mathcal{O}(n^2\cdot 2^n)\)。

D. Galaxy Center

题目大意：一个无限大的坐标系，点 \((x,y)\) 表示在第 \(x(0\leq x\leq 35)\) 层的 \(y(0\leq y < 3^x)\) 位置。每一层是一个环，编号模 \(3\) 余 \(0\) 的位置与下一层有边相连。给出两个位置，问最短路。

题解：枚举它们在哪一层相聚，然后各自走到该层，最后通过同一层的路径拼起来。向下走的时候，找到离自己最近的 \(3\) 的倍数，可以证明这样答案不会更差。注意用答案对同一层的路径长度剪枝。

E. IBM 1403

题目大意：打印机有一个长度为 \(L\) 的循环纸带，以稳定速度每一秒循环移动一个长度。有若干行，每行长为 \(n\) 的文章需要打印，把文章上移一行也需要花费一秒。每次可以选择对齐文章的纸带上字符的子集，不花费时间对其进行打印。问最少的时间全打印完。

题解：预处理纸带上每个位置每个字符的右边最近一次出现。那么打印一行需要花费的时间，就是每个字符对应位置，和它第一次出现的距离的最大值。注意切换行的时候，全局秒数要 \(+1\)。

H. Product of Roots

题目大意：定义 \(f(x)=\prod_{i=1}^{n}(1+a_{i}x),g(x)=\prod_{i=1}^{m}(1+b_{i}x),h(x)=\prod_{i=1}^{n}\prod_{j=1}^{m}(1+a_{i}b_{j}x)\)，给出 \(f(x),g(x)\)，求 \(h(x)\)。

题解：对三个多项式取 \(\ln\)，有： \[ \begin{aligned} \ln f(x)&=\sum_{i=1}^{+\infty}(-1)^{i+1}\frac{\sum_{j=1}^{n}a^{i}_{j}}{i}x^{i}\\ \ln g(x)&=\sum_{i=1}^{+\infty}(-1)^{i+1}\frac{\sum_{j=1}^{m}b^{i}_{j}}{i}x^{i}\\ \ln h(x)&=\sum_{i=1}^{+\infty}(-1)^{i+1}\frac{\sum_{j=1}^{n}\sum_{k=1}^{m}a^{i}_{j}b^{i}_{k}}{i}x^{i}\\ &=\sum_{i=1}^{+\infty}(-1)^{i+1}\frac{\sum_{j=1}^{n}a_j^i\sum_{k=1}^{m}b^{i}_{k}}{i}x^{i}\\ \end{aligned} \] 比较系数可得 \([x^{i}]\ln h(x)=(-1)^{i+1}i\cdot \left([x^{i}]\ln f(x)\right)\left([x^{i}]\ln g(x)\right)\)。时间复杂度 \(\mathcal{O}(n\log n)\)。

I. Safe Landing

签到题

J. Perfect Square

题目大意：判断一个大整数是否是完全平方数。

题解：随机一些质数，判断该大整数在模该质数的意义下是否是二次剩余。使用欧拉定理判断时要注意 \(0\) 的情况。

Dirt Replay

C: -1 D 又双叒叕不套数组

D: -3 以为是枚举到 min 错了，改成 max；发现其实是拼 t 出发的时候，串翻转了操作没翻转；没有用答案剪枝

H: -1 模板用错

J: -2 用 python3 莽超时（本地为什么不测测呢？）；判二次剩余没判 0