Difference between revisions of "2018 CCPC Qinhuangdao Onsite"

From EOJ Wiki
Jump to navigation Jump to search
 
(5 intermediate revisions by 3 users not shown)
Line 13: Line 13:
 
* 起手签了个到,好在没锅,真的好怕签到背锅。
 
* 起手签了个到,好在没锅,真的好怕签到背锅。
 
* 帮 U 看代码,没看出 break 的问题,觉得对得很,甚至一起怀疑数据有诈。
 
* 帮 U 看代码,没看出 break 的问题,觉得对得很,甚至一起怀疑数据有诈。
* G 题真的爽到了,题目没看清楚。在 kblack 的帮助下修了两个 bug,最后开始 TLE 了,修了一发也没过,又是 K 加了个剪枝和快速读过了。
+
* G 题真的爽到了,题目没看清楚。在 kblack 的帮助下修了两个 bug,最后开始 TLE 了,修了一发也没过,又是 kblack 加了个剪枝和快速读过了。
 
* 本来想 Rush G,好在没有。
 
* 本来想 Rush G,好在没有。
 
* 6 题后我就一直再搞 H 了,也没得出什么有用的结论,只是觉得这个分形挺神奇的。
 
* 6 题后我就一直再搞 H 了,也没得出什么有用的结论,只是觉得这个分形挺神奇的。
Line 20: Line 20:
 
* 哄 U 去写大模拟失败了,这题听说样例不对数据不对。封榜前故意乱交了一发大模拟,给出一种在开模拟题的假象。、
 
* 哄 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 80: Line 96:
  
 
题解:预处理每个包可以装哪些子集。因为数据范围很小,可以枚举哪些是包。然后对于这些包进行 DFS,每个包暴力枚举可能的东西。复杂度是看起来是 $\mathcal{O} (2^{2n})$,但实际上不知道是不是——就算是也常数很小。
 
题解:预处理每个包可以装哪些子集。因为数据范围很小,可以枚举哪些是包。然后对于这些包进行 DFS,每个包暴力枚举可能的东西。复杂度是看起来是 $\mathcal{O} (2^{2n})$,但实际上不知道是不是——就算是也常数很小。
 +
 +
UPD:听说枚举子集的子集复杂度是 $\mathcal{O} (3^n)$。
  
 
== Problem J ==
 
== Problem J ==
Line 87: Line 105:
 
题意:$N$ 个数字,中间随机插入 '''+''' 和 '''*''',求所有可能的表达式的结果的和。
 
题意:$N$ 个数字,中间随机插入 '''+''' 和 '''*''',求所有可能的表达式的结果的和。
  
题解:考虑用状态 $(a, b)$ 表示前缀的形状 $a+b$,其中 $a$ 是最后一个加号前的一堆东西的和,$b$ 是最后部分的积。当增加一个数字 $c$ 的时候,有两种转移方式,分别转移为 $(a+b, c)$ 或 $(a, bc)$,发现操作都是线性的,也就是说,用一个状态 $(2a+b, bc+c)$ 代替这两个状态和原式等效,特别的如果是第 $N$ 个,用 $(2a+bc+c^n)$。这个转移可以写作一个 $3$ 维的矩阵,初始向量 $(0, A_1, 1)$,第 $3$ 维用来加常数,线段树维护即可。
+
题解:考虑用状态 $(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$ 维用来加常数,线段树维护即可。