Difference between revisions of "2018 CCPC Qinhuangdao Onsite"
| (8 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
== Replay == | == Replay == | ||
| + | |||
| + | ultmaster: | ||
| + | |||
| + | * 忘记 break，甚至成功拉着一个队友一起自闭。比赛一开始就觉得自己凉了真是常见呢。 | ||
| + | * D 是假的。但奖杯是真的。真香预警。 | ||
| + | * 题目不是 LaTeX 的，差评。 | ||
| + | * 6 个签到签完，神仙题四选一。 | ||
| + | * 早班飞机要两天的睡眠才能补回来。 | ||
| + | |||
| + | zerol: | ||
| + | |||
| + | * 起手签了个到，好在没锅，真的好怕签到背锅。 | ||
| + | * 帮 U 看代码，没看出 break 的问题，觉得对得很，甚至一起怀疑数据有诈。 | ||
| + | * G 题真的爽到了，题目没看清楚。在 kblack 的帮助下修了两个 bug，最后开始 TLE 了，修了一发也没过，又是 kblack 加了个剪枝和快速读过了。 | ||
| + | * 本来想 Rush G，好在没有。 | ||
| + | * 6 题后我就一直再搞 H 了，也没得出什么有用的结论，只是觉得这个分形挺神奇的。 | ||
| + | * 无故 CE 坑啊，手动去提问区请求重测，反复了三四次。 | ||
| + | * 赛后发现我这个 G 题还有更爽的。 | ||
| + | * 哄 U 去写大模拟失败了，这题听说样例不对数据不对。封榜前故意乱交了一发大模拟，给出一种在开模拟题的假象。、 | ||
| + | * 这场真的打酱油了，躺杯。 | ||
| + | |||
| + | kblack: | ||
| + | |||
| + | * 早班机体验很差，人累得一批。 | ||
| + | * 比赛延误了 10 分钟，结果旁边有人已经拿出题来看了，还没人管。跃跃欲试.jpg | ||
| + | * 按惯例从 $J$ 开始倒开，看到题目名字心中一颤，题目刚看完两行这既视感已经满槽了，果断决定这题的复仇（后来发现是假的）加一血要定了。 | ||
| + | * 刚写几行，被写真签到的 zerol 赶下了机，期间重新整理了思路，把矩阵的细节敲定，等着再上机。 | ||
| + | * 差不多写完后发现完全过不了样例，于是切了半个屏幕下来，在一边检查，把位置让给 ultmaster 写 C。 | ||
| + | * 参上，自闭了，本着对一血的执念，又抢了机器调对了样例，获得一发 CE，受到惊吓，重新检查后改了根本没关系的地方，又收获一发 CE（两次 roll 到同一个挂掉的评测机还行？），提问后后台自动 AC，还愿成功。 | ||
| + | * 赛后发现其实这题区别还真挺大的，完全可以算两道题，所以当初没补其实是好事？ | ||
| + | * 之后一起修修题，确认题意，自闭一个 G，穿插吹逼，有说有笑，对着 H 的表自闭了 3 个小时，押 ultmaster 上 F 失败。 | ||
| + | * 期间想了想 D，甚至都想到多项式求导去了，幸好完全不会，不过分析得到了一些重要信息，考虑 nm 暴力的存在，这个数据范围和 30s 的巨型时间限制可能是强行卡的，就准备最后交一发强力优化玩玩，数组没清，没 T 但 WA 了一发，分析感觉是因为 WA 了所以没测到后面的数据，本着要玩玩到底的精神修完再交，等着 T 结果。。。AC 了？ | ||
| + | * <del>甚至还是一血？</del> | ||
| + | * <del>还靠这个翻身做主人了？</del> | ||
| + | * 直到现在还是无法接受这个假题。。。 | ||
| + | * '''真香。''' | ||
== Problem A == | == Problem A == | ||
| Line 28: | Line 64: | ||
题解：直接枚举即可。因为忘记找到了以后就 break OLE 两发，差点自闭（感谢 kblack）。 | 题解：直接枚举即可。因为忘记找到了以后就 break OLE 两发，差点自闭（感谢 kblack）。 | ||
| + | |||
| + | zerol: 这题打印后我检查了代码，觉得没毛病，我也有责任，以至于后面有一发是瞎交的。 | ||
== Problem D == | == Problem D == | ||
| Line 58: | Line 96: | ||
题解：预处理每个包可以装哪些子集。因为数据范围很小，可以枚举哪些是包。然后对于这些包进行 DFS，每个包暴力枚举可能的东西。复杂度是看起来是 $\mathcal{O} (2^{2n})$，但实际上不知道是不是——就算是也常数很小。 | 题解：预处理每个包可以装哪些子集。因为数据范围很小，可以枚举哪些是包。然后对于这些包进行 DFS，每个包暴力枚举可能的东西。复杂度是看起来是 $\mathcal{O} (2^{2n})$，但实际上不知道是不是——就算是也常数很小。 | ||
| + | |||
| + | UPD：听说枚举子集的子集复杂度是 $\mathcal{O} (3^n)$。 | ||
== Problem J == | == Problem J == | ||
| Line 65: | Line 105: | ||
题意：$N$ 个数字，中间随机插入 '''+''' 和 '''*'''，求所有可能的表达式的结果的和。 | 题意：$N$ 个数字，中间随机插入 '''+''' 和 '''*'''，求所有可能的表达式的结果的和。 | ||
| − | 题解：考虑用状态 $(a, b)$ 表示前缀的形状 $a+b$，其中 $a$ 是最后一个加号前的一堆东西的和，$b$ 是最后部分的积。当增加一个数字 $c$ 的时候，有两种转移方式，分别转移为 $(a+b, c)$ 或 $(a, bc)$，发现操作都是线性的，也就是说，用一个状态 $(2a+b, bc+c)$ 代替这两个状态和原式等效，特别的如果是第 $ | + | 题解：考虑用状态 $(a, b)$ 表示前缀的形状 $a+b$，其中 $a$ 是最后一个加号前的一堆东西的和，$b$ 是最后部分的积。当增加一个数字 $c$ 的时候，有两种转移方式，分别转移为 $(a+b, c)$ 或 $(a, bc)$，发现操作都是线性的，也就是说，用一个状态 $(2a+b, bc+c)$ 代替这两个状态和原式等效，特别的如果是第 $n \gt 1$ 个，用 $(2a+b, bc+c \times 2^{n-2})$。这个转移可以写作一个 $3$ 维的矩阵，初始向量 $(0, A_1, 1)$，第 $3$ 维用来加常数，线段树维护即可。 |
Latest revision as of 22:41, 28 September 2018
Replay
ultmaster:
- 忘记 break，甚至成功拉着一个队友一起自闭。比赛一开始就觉得自己凉了真是常见呢。
- D 是假的。但奖杯是真的。真香预警。
- 题目不是 LaTeX 的，差评。
- 6 个签到签完，神仙题四选一。
- 早班飞机要两天的睡眠才能补回来。
zerol:
- 起手签了个到，好在没锅，真的好怕签到背锅。
- 帮 U 看代码，没看出 break 的问题，觉得对得很，甚至一起怀疑数据有诈。
- G 题真的爽到了，题目没看清楚。在 kblack 的帮助下修了两个 bug，最后开始 TLE 了，修了一发也没过，又是 kblack 加了个剪枝和快速读过了。
- 本来想 Rush G，好在没有。
- 6 题后我就一直再搞 H 了，也没得出什么有用的结论，只是觉得这个分形挺神奇的。
- 无故 CE 坑啊，手动去提问区请求重测，反复了三四次。
- 赛后发现我这个 G 题还有更爽的。
- 哄 U 去写大模拟失败了，这题听说样例不对数据不对。封榜前故意乱交了一发大模拟，给出一种在开模拟题的假象。、
- 这场真的打酱油了，躺杯。
kblack:
- 早班机体验很差，人累得一批。
- 比赛延误了 10 分钟，结果旁边有人已经拿出题来看了，还没人管。跃跃欲试.jpg
- 按惯例从 $J$ 开始倒开，看到题目名字心中一颤，题目刚看完两行这既视感已经满槽了，果断决定这题的复仇（后来发现是假的）加一血要定了。
- 刚写几行，被写真签到的 zerol 赶下了机，期间重新整理了思路，把矩阵的细节敲定，等着再上机。
- 差不多写完后发现完全过不了样例，于是切了半个屏幕下来，在一边检查，把位置让给 ultmaster 写 C。
- 参上，自闭了，本着对一血的执念，又抢了机器调对了样例，获得一发 CE，受到惊吓，重新检查后改了根本没关系的地方，又收获一发 CE（两次 roll 到同一个挂掉的评测机还行？），提问后后台自动 AC，还愿成功。
- 赛后发现其实这题区别还真挺大的，完全可以算两道题，所以当初没补其实是好事？
- 之后一起修修题，确认题意，自闭一个 G，穿插吹逼，有说有笑，对着 H 的表自闭了 3 个小时，押 ultmaster 上 F 失败。
- 期间想了想 D，甚至都想到多项式求导去了，幸好完全不会，不过分析得到了一些重要信息，考虑 nm 暴力的存在，这个数据范围和 30s 的巨型时间限制可能是强行卡的，就准备最后交一发强力优化玩玩，数组没清，没 T 但 WA 了一发，分析感觉是因为 WA 了所以没测到后面的数据，本着要玩玩到底的精神修完再交，等着 T 结果。。。AC 了？
甚至还是一血？还靠这个翻身做主人了？- 直到现在还是无法接受这个假题。。。
- 真香。
Problem A
Solved by ultmaster. 02:50 (+1)
题意：给一个无向图，每条边加单位容量有一个代价，求在给定代价内能够达到的最小割的最大值。
题解：裸的最小费用最大流。如果当次 Bellman Ford 跑出来的流量已经不能全部买到了，那就切一部分买到的。
抄模板漏了一个 &，WA +1。
Problem B
Solved by zerol. 00:09 (+)
题意：问几点到几点时针分针重合几次。
题解 12 小时中只重合 11 次，其中 [11, 12) 没有重合过。
zerol: 这题我做过，小学奥数题。
Problem C
Solved by ultmaster. 01:00 (+2)
题意：答案有 36 种可能，求字典序最小的答案是输入串的子序列。
题解：直接枚举即可。因为忘记找到了以后就 break OLE 两发，差点自闭（感谢 kblack）。
zerol: 这题打印后我检查了代码，觉得没毛病，我也有责任，以至于后面有一发是瞎交的。
Problem D
Solved by kblack. 04:51 (+1)
题意：树上每个点一个多项式，求 $u$ 到 $v$ 路径上的多项式之积在 $x$ 点的值。
题解：正解似乎是多项式多点求值，以后补。考场上直接优化了暴力，添加了读入优化和一个常数优化，竟然直接跑过去了。
Problem G
Solved by zerol. 01:58 (+4)
题意：判断一棵树是不是完全 k 叉树，k 尽可能小。
题解：设最大度数是 x，那么 k=x 或 k=x-1，随便挑一个度数为 k 的为根做 dfs 判断所有叶子深度是否一样。
坑点：n=1 答案是 1，n=3 的链答案是 1 而不是 2，只有两层的树某些写法可能要特判。
一开始一通特判，后来觉得特判太多要出事就重写了。然后写完测了一下 n=1 答案是 0，觉得没问题。后来 k 最大最小搞反了。然后就 T 了，优化一下常数也没用。后来加了剪枝（n 必须能表示成 $1+k+k^2+\cdots$）和快速读过了。过完发现 dls&jls 这题已经 -7，突然觉得问题似乎也不大。
zerol: 题没读清楚，罚钱。但是签到题卡常，出题人也有责任。
Problem I
Solved by ultmaster. 02:03 (+)
题意：已知有一些值（糖果），另外一些值（包）是其中一些值的和（每个值至多只能被用一次）。现在把所有值都打乱了给你，求可能的方案数。
题解：预处理每个包可以装哪些子集。因为数据范围很小，可以枚举哪些是包。然后对于这些包进行 DFS，每个包暴力枚举可能的东西。复杂度是看起来是 $\mathcal{O} (2^{2n})$，但实际上不知道是不是——就算是也常数很小。
UPD：听说枚举子集的子集复杂度是 $\mathcal{O} (3^n)$。
Problem J
Solved by kblack. 00:51 (+)
题意：$N$ 个数字，中间随机插入 + 和 *，求所有可能的表达式的结果的和。
题解：考虑用状态 $(a, b)$ 表示前缀的形状 $a+b$，其中 $a$ 是最后一个加号前的一堆东西的和，$b$ 是最后部分的积。当增加一个数字 $c$ 的时候，有两种转移方式，分别转移为 $(a+b, c)$ 或 $(a, bc)$，发现操作都是线性的，也就是说，用一个状态 $(2a+b, bc+c)$ 代替这两个状态和原式等效，特别的如果是第 $n \gt 1$ 个，用 $(2a+b, bc+c \times 2^{n-2})$。这个转移可以写作一个 $3$ 维的矩阵，初始向量 $(0, A_1, 1)$，第 $3$ 维用来加常数，线段树维护即可。