ZJU 八月集训随记

  • Day1 - SWERC 2017 - 2018.8.9 - Codeforces
  • Day2 - GCPC 2010 - 2018.8.10 - vjudge
  • Day3 - NEERC Moscow 2017 - 2018.8.11 - Codeforces
  • Day4 - 2013 Andrew Stankevich Contest 43 - 2018.8.12 - opentrains
  • Day4.5 - Makoto Soejima Contest 3 (MIPT Workshop Open 2) - 2018.8.13 - opentrains
  • Day5 - 2018 Multi-University Training Contest 7 - 2018.8.14 - vjudge
  • Day6 - NEERC Northern Subregional Contest St Petersburg 2017 - 2018.8.15 - Codeforces
  • Day 7 - CERC 2017 - 2018.8.16 - Codeforces
  • Day 8 - JAG Autumn 2014, MIPT2014 Round 1 - 2018.8.17 - opentrains
  • Day 9 - NEERC 2014 - 2018.8.18 - opentrains
  • Day 9.5 - XVIII Open Cup named after E.V. Pankratiev. GP of Urals - 2018.8.19 - opentrains
  • Day 10 - AMPPZ-2015 MIPT-2015 ACM-ICPC Workshop, Round 1 - 2018.8.20 - opentrains
  • Day 11 - NEERC St Petersburg 2017 - 2018.8.21 - Codeforces
  • Day 12 - 2018 Multi-University Training Contest 8 - 2018.8.22 - PC^2
  • Day 13 - 2015 Moscow International ACM ICPC Workshop AIM Fund Contest - 2018.8.23 - opentrains

全程为 ACM 赛制组队训练,小数天数指队伍加训。Xnyttt 表示在时间 \(ttt\) 的时候提交了题目 X 的第 \(n\) 份代码并获得 AC。

从 Day5 开始 rated。

队友:郑鸿鹄(Codeforces@zhhhplus)、林思仪(Codeforces@LIN452)

已获区域赛资格一份。

Day1 - SWERC 2017 - 2018.8.9 - Codeforces

赛时流水账

开场读题并未发现签到题,看了一下榜发现 F 有人过,向 lsy 读了一下发现是傻逼题,于是 F1y18 ,之后 zhh A1y35,在 zhh 写题期间看到 J 也有人过,发现写一个前缀和就好了,于是 J1y40,之后 zhh 敲完了计算几何的板子,并写了 K 题,但一直 WA on 18,打印出来后发现把点到直线的距离写成了点到线段距离,改了之后 K4y121 ,期间我一直在想 C 的 DP 但发现会 TLE,zhh A 完 K 后也得出了 \(3^8 \times 3^8\) 的矩阵,最终未能得到正解。期间 lsy 觉得 D 能写,我则和 zhh 讨论 G,发现可以建图跑费用流,我抄了自己的板子但是 TLE 了,而 KM 算法感觉也不能过,于是一直让 lsy 去写 D。我读了一下 E 题,虽然没看懂样例,但感觉可以先拓扑排序在背包,但由于理解错了题意,写了完全背包,而正解是 01 背包,导致连样例都过不了。最后几十分钟时,zhh 打算抄一遍 KM 的板子写 G,但写完后发现不会用,同时也到点了。最终 4 题,rk11。

赛后

E 改了一下就 A 了。C 得知可以用斐波那契数列优化成 \(2^8 \times 2^8\) 的矩阵就可以做了。lsy 之后也补掉了 B 题。

Day2 - GCPC 2010 - 2018.8.10 - vjudge

赛时流水账

开场读题并未发现签到题,看榜发现了 H 题,差分三次即可,但是有一点细节写错了 WA 了两发,最终 H3y21。A 完 H 看榜发现 I 也是签到题,于是 zhh I1y35,lsy 觉得 D 是 Tarjan 也能做,于是 D2y98,期间和 zhh 讨论了一下 A,我想了想细节发现十分好写,于是 A1y89。我给 lsy 与 zhh 说了 G 的题意后,二人给出了不同的解法,其中 zhh 的做法听起来不太对,但是好写,于是 WA 了三发后交由 lsy 写状压,由于未清空数组,又 WA 了三发后 G7y147,期间给 zhh 说了一下 C 的题意后发现写个拓扑排序即可,但由于开小了数组,C2y124 。在 lsy 调 G 的时候,zhh 给我讲了 J 的题意和做法,感觉十分的正确,但当时还没有人 AC J 题,zhh 先敲了板子,在 lsy 过了 G 后 J1y182。期间 lsy 读了 E 题,zhh 听后感到奇怪,交由我确认了一下题意,感觉可以 sam,于是 lsy 去看板子回忆 sam。我读了 K 的题面后感觉是个傻逼题,但一直 WA 到比赛结束,lsy 的 sam 也没有调出来。最终 7 题,rk 12。

赛后

K 发现是全队三人不认识 perpendicular,导致细节出错,改了之后 A 了。E sam 确实能做,但标算似乎是 trie,另外,用 std::set<std::string> 的暴力也可以过。

Day3 - 2018.8.11 - NEERC Moscow 2017 - Codeforces

赛时流水账

开场我因为少读了 E 的一个条件,WA 了一发(E 题全场唯一的一发提交)。之后 lsy 发现 D 可以签到,由于爆 long long WA 了一发,D2y63,之后 zhh A2y68。zhh 给我说了一下 H 的题意发现可写但细节比较多,我去推了推式子但是 WA 了三发,未能找到错误。期间 zhh 写 F 的模拟到心态爆炸,换了 lsy 去写 F,同时 lsy 告诉了 zhh C 的做法,最后 lsy F3y208。zhh 发现lsy 的 C 有问题,打算用树剖,于是告诉我了题意,因一些细节问题又 WA 了几发,最后 C7y266 。lsy 看了一下我的 H 的代码,不过还是重写了一遍 H 后 H4y282,最后十几分钟和 zhh 读了 G,随便写了一下果然 WA 了。最终 5 题,rk 12。

赛后

发现自己的 H 把一个减号写成了加号;G 发现是个很简单的题但由于卡题而没有去读。

Day4 - 2013 Andrew Stankevich Contest 43 - 2018.8.12 - opentrains

赛时流水账

开场和 lsy 交换了一下 B 的思路,我找了一下规律,得到了一个细节有点问题的做法,lsy 补充后 B1y98,之后 zhh 和 lsy 讨论了一下 I,于是 lsy I1y147。和 zhh 讨论了一下 H 后发现可以构建最小割模型,但一直 WA on 14。同时 zhh 告诉我了 K 的题意和做法,由于理解出了偏差,WA 了几发,最后 K5y258。期间 zhh 与 lsy 一直尝试构造 J 但是失败。最后 zhh 说了一下 L 可能 的解法,我写了一发但是 WA 了。最终 3 题,rk 10。

赛后

H 题把我们的拆点做法改为不拆点就能 A,但是对排了一百多组随机数据也没能找到拆点做法的错误。我在听了 J 的题意后便想到了标算的构造,到当时感觉有问题而没说,zhh 和 lsy 也没能想出这个构造(这个锅我背了。。。),L 发现 zhh 给的做法有一点问题。

Day4.5 - Makoto Soejima Contest 3 (MIPT Workshop Open 2) - 2018.8.13 - opentrains

赛时流水账

开场先和 zhh 想了 E 和 H,去机子上打了 E 的表,zhh 则打开 OEIS 书但是未能找到。lsy 发现 B 是个贪心,于是 B3y41。给 zhh 和 lsy 说了 C 的题意,自己则在打 H 的表,zhh 以为发现了规律,但多打了一些后发现是错的,不过我有了一个思路,但复杂度不对。lsy C2y121 后听了我的 H 的思路开始和 zhh 一起思考,同时给我说了 G 可以大力讨论,讨论了一下后我感觉能写,WA 了几发后发现了一个大 bug,lsy 提出了想法,但由于我理解处理偏差,半个小时后才意识到是对的,修完 bug 后还是 WA,并且还是想不到 WA 点,H 题那边 lsy 想到了做法,但感觉会 TLE 而没有写。最终 2 题。

赛后

赛后发现自己的 G 用到了可能未被算出来的数据,改了一下后 AC 了;lsy 的 H 题做法其实的对的。我学习了一下「竞赛图的强连通分量数等于划分成两个非空点集 \(S\)\(T\) 使得二者之间的边都是由 \(S\) 指向 \(T\) 的方案数加一」的姿势并补掉了 E,同时补掉了另一个计数题 D。

Day5 - 2018 Multi-University Training Contest 7 - 2018.8.14 - vjudge

赛时流水账

开场我先看了 E、F 和 H,感觉 E 可以做,稍微找了找规律,发现是完全积性的,同时回忆了一下某个经典式子的反演结果(懒地推了),敲完后发现样例过不了,又看了看发现只是普通的积性,改完后 TLE,删除了几次多余的取模操作后 E2y99,拿下 E 的一血。之后 zhh 给我说了 J 的题意,发现是傻逼签到题,写完后 J1y118。zhh 和 lsy 讨论了A,lsy 去写了,但是 TLE。zhh 卡了卡常后,lsy 发现了一处问题,修改后本地十组大数据 \(3\)s,时限 \(2.5\)s 且原题有二十组数据,但还是交了一发,A3y201。zhh 告诉我 H 可以树剖,I 可以 LCT,想了想确实都是板子题,考虑到我的 LCT 可能不是很好调 + LCT 的常数比较大,我选择去写 H,但是一直 WA。同时 lsy 想到了 K 的做法,也没有调出来。最终 3 题,rk 8。

赛后

H 发现一个细节写错了:二次修改一个点时我找的是初始值而非之前修改后的值,改了之后 AC,但实际上 H 有更短更好写的做法。lsy 调完了自己的 K 也 AC 了。之后用自己的 LCT 板子过了 I 发现并不用担心常数。

Day6 - NEERC Northern Subregional Contest St Petersburg 2017 - 2018.8.15 - Codeforces

赛时流水账

开场 lsy A1y12,zhh 想到了 L 的做法并去写,但死机了,之后 lsy B1y44,期间我发现 I 很可写,K 也是个傻逼构造,于是 K1y53,lsy 先写了一发 C,于是 C1y75,我想完 I 的细节,I1y93。十分钟后过了 L 的样例,但是 WA on 6,发现问题后又 WA on 13。lsy 和 zhh 想到了 E 的做法,但是 RE on 4 和 WA on 8。我又意识到了 L 可能会发生 long longdouble 间的精度问题,改了一发 WA on 29,又想到一点后 L4y169。lsy 与 zhh 发现 E 做法的问题,zhh 改正后 E5y212。之后 zhh 想到了 G 的做法,我和 lsy 也思考了一下 H,感觉做出 G 的概率更大,于是我去写了 G 的点双,写了各种细节后 RE on 2。最终 7 题,rk 7。

赛后

G 发现问题后不断地 WA on 2(有 \(1815\) 个子测试点),但其实有更简单的做法,lsy 补掉了 G。同时我和 lsy 补掉了 H。

Day 7 - CERC 2017 - 2018.8.16 - Codeforces

赛时流水账

开场先 WA 了三发 F,而且是 WA on 1,但是本地确实过了样例,期间修正了一些细节,我怀疑是多组数据或 PE,zhh 表示了否定,F 先放下了。之后 lsy A1y80,zhh 和我说了一下 J 的题意,发现很可写,于是 J1y85。之后 zhh 重写了 F,仍然 WA on 1,lsy 表示用 %lld 输出 int 可能会有问题,zhh 改了后 F6y114。我跟榜去看了 H,看了两遍后看懂了题意,发现直接建树跑 dfs 即可,于是 H1y133。这时发现总榜上只有 G、K 和 L 有人过,过 G 的人更多,于是 zhh 和 lsy 去想 G,不擅长期望的我准备开别的题。一段时间后,看到 EuropeSun(oyyf、wyh、zx)过了 L,于是去看 L,看到坐标范围很小,感觉可以差分,思考了一段时间细节。期间 lsy 想到了 G 的转移,在因为写错一个括号的位置 WA 了一发后 G2y228。之后我去写 L,调了一段时间细节后发现交不上去,五六分钟后 MLE on 1(算了一下只超了 \(4\)M),删去一个无用数组后 WA on 1,发现是修改时没有修改完,最后 L3y282,最后读了一下 D 的题意放弃。最终 6 题,rk 5。

赛后

自已的 F 改掉 %lld 也过了。

Day 8 - JAG Autumn 2014, MIPT2014 Round 1 - 2018.8.17 - opentrains

赛时流水账

开场跟榜知道 A 是签到题,但理解了二十分钟,写完后 WA on 1,和 zhh 浪费了二十分钟找错,最后发现是交成了 13 号的 A 题,于是 A2y49。之后 lsy 与 zhh 讨论出来 G,因为未初始化 + 爆了 long long WA 了两发,G3y96。期间 zhh 给我讲了 B 的高斯消元做法,我去一旁回想高消,同时 zhh 去和 lsy 讨论 D。D 在 WA 了一次后 D2y223,我在期间写完了 B 并开始调试,一段时间后过了样例,但是 WA on 2,zhh 指出从上三角消成对角线时的错误,仍然 WA on 2,最后 zhh 意识到最后可能还是消不成对角线并且我会 WA 在这个地方,改正后 B6y265。最后写了些中途看的 K 题,一直过不了样例。最终 4 题,rk 12。

赛后

zhh 指出了一个问题,K 在赛后几秒过了样例,但是 TLE,改正几发后补掉了。同时发现 H 是个傻逼题,但是没有人读了题面,赛后十几分钟后一遍过掉了。网络流的 F 和 DP 的 J 则被 lsy 补了。

Day 9 - NEERC 2014 - 2018.8.18 - opentrains

赛时流水账

开场 zhh 快速 A1y13,之后我暴力 K1y23,再之后 lsy 爆搜 J2y48。之后我发现 F 暴力的复杂度是对的,但是 WA 了两发,期间 zhh 与 lsy 讨论出了 B,于是 zhh B1y86。之后我发现我的 F 是因为把 j 打成了 i,改正后 F4y110。再之后 lsy 发现了 I 的性质,于是 I1y150。后半场 zhh 与 lsy 在思考 E,我则在想了一会儿 E 后转去想 D,突然想到了祖暅原理,觉得可以暴力微分,zhh 则提出了蒙特卡洛,但无论是哪个,推了好久式子都没能推出来;zhh 想到了 E 的做法,但由于细节比较难写而没有写出。最终 6 题,rk 5。

赛后

赛后理清了思路写了 D 题,调了几个小时后过了样例一,但是 WA 样例二,又过了几个小时发现是打错了变量名(一天两次……),最后由于精度 WA on 48 一次过了。

Day 9.5 - XVIII Open Cup named after E.V. Pankratiev. GP of Urals - 2018.8.19 - opentrains

赛时流水账

开场发现 B 是签到,三人讨论了一下后 WA on 2,再次讨论后补上一个细节后 B2y53。之后一个多小时思考 A 和 C,但是毫无进展。lsy 想到了 K 的做法,写好后 WA on 4,改正一些后 WA on 7,此时还剩半场的时间,而 lsy 的代码看起来比较正确,在更改了感觉更正确的写法后仍然 WA on 7,zhh 提议面向评测机调试,但返回的结果却是最难调的情况。我仔细查过 lsy 的代码后,感觉正确无比,但是 WA on 7。期间我思考了一下 D,转化为若干个 \([0, 9]\) 的数和为某个数的方案数,但式子推不出来。最终 1 题。

赛后

lsy 用 K 的标程对拍,随机了几百组数据没有拍出错误。D 在容斥时钦定超过即为 \(10\) 就是对的。

Day 10 - AMPPZ-2015 MIPT-2015 ACM-ICPC Workshop, Round 1 - 2018.8.20 - opentrains

赛时流水账

开场发现 D 是签到,F 是签到,之后 zhh 与 lsy 又给出了 B 的做法,此时不到一个小时,但 opentrains 挂了(于是 unrated)。之后去想 opentrains 挂掉前有人过的题:A、H、K、L。zhh 说 A 可以不老老实实地算:当足够大时,那个 \(-1\) 可以忽略,但是一开始推错了式子,最后还是写出来了。lsy 尝试暴力过 H,但是 9s 时限本地跑了 13s,虽然加了一个优化跑到了 7.5s,但感觉优化会有无效的时候;之后 lsy 就去想 L,并发现了与子树遍历顺序无关的性质,但下一步没有走下去。我企图推 K 的式子,虽然长得有规律但是化简不能。zhh 说做过 G 中只有两种点的时的题目,后来提到昨晚两个可以合并,感觉可以分治。

不过以上均为嘴巴 AC,opentrains 在比赛结束五个多小时后仍未修复。。。

赛后

辣鸡 opentrains。

Day 11 - NEERC St Petersburg 2017 - 2018.8.21 - Codeforces

赛时流水账

开场发现 D 是签到,11 分钟写完后 WA on 9,之后发现是没有处理 0 比较多的情况,改了一发 D2y15。同时发现 B 是签到,zhh 推了推 B1y44。看总榜发现 D 的过题数仅次于 A 和 C,A 没有思路,C lsy 与 zhh 在讨论,于是去想了 D 的构造,但感觉细节需要想一下。期间 lsy 想出来 C,于是 C1y89。我想清了 D 的细节,在打错一次变量名后 D2y98,拿下 D 的一血。A 题 zhh 和 lsy 有一点想法,总榜上下一道是 L,于是去看了看,感觉可以树剖 + 染色做,抄了一会儿板子意识到有点问题,说出来后意识到可以按集合大小排个序,于是继续去写了,在提交前被 lsy 提醒边的数组是否够大,发现又一次忘写 << 1,于是 Ly151,拿下 L 的一血。之后给 zhh 说之前 A 的某一个做法,应该可以实现线段树维护一段集合进行区间加一个元素,复杂度 \(O(n \log n \log \log n)\),写了之后 WA on 2 改了一个 bug 后仍然 WA on 2。lsy 理了理 F,但是 RE on 2。zhh 表示用他之前 \(O(n \log^2 n)\) 的做法重写,此时只剩不到 20 分钟。听清细节后 WA on 1(本地测错代码了。。。),改正后 WA on 15,zhh 表示枚举时直接 set.erase(it) 可能会挂,改成 goto 后 WA on 2,意识到问题后再次 WA on 15,zhh 表示数组应该开到 30,于是 A7y294。最终 6 题,rk 3(Legilimens 虽然不是一起打的,但还是算上吧)。

赛后

在此处,set.erase(it) 并不会出问题(但其他地方确实会有出问题的可能)。

Day 12 - 2018 Multi-University Training Contest 8 - 2018.8.22 - PC^2

赛时流水账

开场发现 E 是签到题,于是 E1y8,之后发现 A 是 Day 9.5 - D 约化后的问题,于是 A1y31(两题都是一血)。之后觉得 B 是一道水题,但是 WA 了,直到比赛结束也不知道 WA 在什么地方;zhh 给 lsy 讲了 J 错的题意,于是 WA 了;构造的 D 也是几个 WA。一段时间过去,D 终于给出了最优的构造,于是 D5y190;lsy 在知道 J 的正确题意后 J3y268。最终 4 题,rk 6。

Day 13 - 2015 Moscow International ACM ICPC Workshop AIM Fund Contest - 2018.8.23 - opentrains

赛时流水账

开场发现 E 是签到题,向 zhh 确认过后 E1y4(总榜并列一血)。之后发现 I 就是个大模拟,写完后意识到可能会 MLE,于是把 int 改成 shortI1y27(校内一血)。同时,lsy 与 zhh 在想 A 和 H,一段时间后 lsy A1y50,zhh 在写错一次数组下标后 H2y82。给 zhh 说了 G 的题意后,zhh 很快给出了做法,但是不停地 TLE on 1,加了 assert 交互次数后发现迷之爆了交互次数,于是决定在最后一次时直接当做答案,于是 G4y119(现场校内一血,但是比 Legilimens 要晚)。之后 lsy 在想 J,写了一个错误的贪心,但一开始并没有意识到;我则觉得 F 只需要求出 \(k \sim 2k\) 内满足条件的数,其倍数均可以且不会有漏,但是 WA,zhh 说搞到 \(k^2\),发现确实漏了一些,但仍然是 WA。lsy 意识到 J 的错误后改写 DP,但没有调出来。最终 5 题,rk 11。

赛后

F 再多搞一搞就是对的了……

大总结

最终在 \(12\) 支队伍中排名第 \(8\),在预备队中排名第 \(2\),踩了一支 B 队。在最后一天被 ACetic_ACid 反超,总 rating 只相差 \(0.6\),有点可惜。不过有区域赛资格总是好的。

自己读错题意、打错变量名、数组开小三项错误的次数在队伍中位居第一(由于 zhh 从 Day 3 开始计数,导致自己读错题的次数其实少记了三次),正式赛时不能再这样了。

希望自己能在区域赛上表现得好点,希望能在区域赛上碰到能让我一眼有想法的中档题,希望队伍拿个颜色好看点的牌子,就是这样了。