Contest Info

date: 2018.01.26 14:00-19:00

practice link

Solutions

D Designing the Toy

题目大意：有一个由 \(1\times1\times1\) 的正方体构成的立体图形，已知它的三视图的面积分别为 \(a, b, c\) ，要求构造一种这样的立体图形。

题解：经过旋转 \(a,b,c\) 可以任意交换，故不妨设 \(a\le b\le c\)。另外显然 \(c>ab\) 时不存在。下面分类讨论：

• \(a=1\) 时：只有 \(b=c\) 这一种情况，这时构造一个 \(1\times1\times n\) 的图形即可，例如 \(a=1,b=3,c=3\) 时如图：

• \(a=2\) 时：

  • \(b=c\) 时，例如 \(a=2,b=4,c=4\) 时如图：

  

  • \(b<c\le2b\) 时，例如 \(a=2,b=4,c=6\) 时如图：

  

• \(a\ge3\) 时：

  • \(c=a+b-3\) 时，例如 \(a=4,b=4,c=5\) 时如图：

  

  • \(c=a+b-2\) 时，例如 \(a=4,b=4,c=6\) 时如图：

  

  • \(b\le c<a+b-3\) 时，在 \(c=a+b-3\) 的基础上，把两边的立方体堆到第二层上，例如 \(a=4,b=4,c=4\) 时如图：

  

  • \(a+b-1\le c\le ab\) 时，将超过 \(a+b-1\) 的方块放入中间空白的部分，例如 \(a=4,b=4,c=10\) 时如图：

  

E Easy Quest

签到题，贪心即可。

F The Final Level

略。。实在是难以描述。

K Knapsack Cryptosystem

题目大意：有这样一套密码系统：给出 \(n\) 个数 \(a_{1},\cdots,a_{n}\) ，\(q=2^{64}\)，以及 \(r\)。它们满足 \(a_{i}>\sum_{j=1}^{i-1}a_{j}, q > \sum_{i=1}^{n}a_{i}\)，\(r\) 与 \(q\) 互质（即 \(r\) 是奇数）。设 \(b_{i}=a_{i}\cdot r\mod p\) ，对于一串 \(n\) 位的 \(0-1\) 信息 \(S\) ，其加密方式为 \(s=(\sum_{i=1}^{n}S_{i}b_{i})\mod q\)，\(s\) 即为密文。现在告诉你 \(b_{1},\cdots,b_{n}\) 以及 \(s\)，问原文 \(S\) 是什么。保证 \(b_{i}\) 和 \(s\) 按照上述方式生成。

题解：首先我们证明答案唯一：注意到 \(s\) 的生成方式只和 \(b,S\) 有关，故我们任取一个符合条件的 \(r\)，则有 \(sr^{-1}\equiv\sum_{i=1}^{n}S_{i}b_{i}r^{-1}\equiv\sum_{i=1}^{n}S_{i}a_{i}\pmod{q}\) ，由于 \(sr^{-1}\) 和 \(\sum_{i=1}^{n}S_{i}a_{i}\) 均大于等于 \(0\) 小于 \(q\)，故 \(sr^{-1}=\sum_{i=1}^{n}S_{i}a_{i}\)。设存在 \(S\) 和 \(S'\) 满足条件，则有 \(\sum_{i=1}^{n}S_{i}a_{i}=\sum_{i=1}^{n}S'_{i}a_{i}\) ，假设 \(S_{n}\neq S'_{n}\) ，不妨设 \(S_{n}=1,S'_{n}=0\)，则 \(\sum_{i=1}^{n}S_{i}a_{i}-\sum_{i=1}^{n}S'_{i}a_{i}=a_{n}+(\sum_{i=1}^{n-1}S_{i}a_{i}-\sum_{i=1}^{n-1}S'_{i}a_{i})>=a_{n}-\sum_{i=1}^{n-1}a_{i}>0\) ，矛盾，同理有 \(S_{i}=S'_{i}\) ，故答案唯一。\(\Box\)

当 \(n<=\frac{2\log_{2}q}{3}\) 时，我们将 \(b_{1},\cdots,b_{n}\) 分成两半，分别求出每一半所有能组合出的值，然后用 \(s\) 减一边的值在另一边查找即可。复杂度 \(\mathcal{O}(\sqrt[3]{q}\log q)\)。

当\(n>\frac{2\log_{2}q}{3}\) 时，我们可以暴力寻找所有满足条件的 \(r\) 。首先有： \[ \begin{aligned} \sum_{i=1}^{n}a_{i}&\le2^{64}-1\\ 1+2\sum_{i=1}^{n-1}a_{i}&\le2^{64}-1\\ \vdots\\ 2^{n-1}-1+2^{n-1}a_{1}&\le2^{64}-1\\ a_{1}&\le2^{64-n+1}-1\\ \end{aligned} \] 由于 \(r\) 是奇数，显然有 \(lowbit(b_{1})=lowbit(a_{1})\) ，故满足条件的不同的 \(a_{1}\) 有 \(\frac{2^{64-n+1}}{lowbit(b_{1})}-1\) 个。我们先枚举所有的 \(a_{1}\)，对于一个固定的 \(a_{1}\)，由于 \(a_{1}r\equiv b_{1}\pmod{q}\)，故 \(\frac{a_{1}}{lowbit(b_{1})}r\equiv\frac{b_{1}}{lowbit(b_{1})}\pmod{\frac{q}{lowbit(b_{1})}}\) ，\(r\equiv(\frac{a_{1}}{lowbit(b_{1})})^{-1}\frac{b_{1}}{lowbit(b_{1})}\pmod{\frac{q}{lowbit(b_{1})}}\) 。故在膜 \(q\) 的意义下，符合条件的 \(r\) 有 \(\max(1,\frac{lowbit(b_{1})}{2})\) 个。故满足条件的 \(r\) 至多有 \(2^{64-n+1}\) 个，对于一个满足条件的 \(r\)，很容易求出所有的 \(a_{i}\) ，然后我们就可以验证它们是否满足 \(a_{i}>\sum_{j=1}^{i-1}a_{j}, q > \sum_{i=1}^{n}a_{i}\) ，如果满足，就可以很容易地贪心求出答案了。这一部分的复杂度也是 \(\mathcal{O}(\sqrt[3]{q}\log q)\)。

Replay and Summary

Replay

进入考期已经一个月没有训练的鄙队终于想起来训练惹！

开场 W 先看了看 L 题，觉得怎么弄一弄搞成很多条链就可以做啦，然后就不知道该怎么判断满足题给条件。Z 过来把签到题 E 给切了，然后 D 说 B 题直接暴力就可以做。W 帮着 D 把 B 题细节搞了搞，让 D 接着暴力打表。

W 看了一下 C 题，感觉前向边肯定是没用的，横叉边和后向边不知道该怎么办。再仔细看了看只要求恰好保留 2n 条边，觉得非常傻逼，就过掉了。D 终于打完了表，也把 B 过掉了。Z 觉得 D 题分类讨论构造就行了，很麻烦，有点占用机时，然而 W 和 D 正在就 A 题吵架，于是 Z 就开始写 D 题。

W 觉得 A 题根本不用 KD 树来写，就不让 D 去写，然而 W 自己的算法也还差一点，于是就很僵硬。然后 D 就去做 G 题。Z 已经搞完 D 题开始做 F 了，太快啦！ F 据说也是个构造。W 突然发现自己似乎会做 L 题了，用一个单调栈维护闭区间套就可以解决一开始的问题，就写了一发过掉了。

D 写完了 G 题发现根本过不了，就开始 debug。Z 写完 F 改了改也过了。W 开始苦想被很多人过掉的 A 题，Z 开始爆搜 K 题。然而 W 并不能想出来 A，并发现 J 是个水题。只需要枚举瓶颈边，然后暴力最短路就行了，正确性很好证明。W 写了几发 J 因为各种傻逼错误被卡了 5 次，感人肺腑。

最后 D 也找到了 G 的 bug，过掉了 G。Z 的爆搜 K 没有使用类似 bsgs 的搜一半存一半的技巧，遗憾没过。

比赛结束后，昂神一语道破 A 是个套路水题，还是昂神厉害啊。