2017-2018 ACM-ICPC Northern Eurasia (Northeastern European Regional) Contest (NEERC 17)

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 是个套路水题,还是昂神厉害啊。