2024 ICPC 成都 VP 游记

迟暮天复明

2024-11-02 21:46:54

Life & Travel

今天早上八点开场。

食堂门口没找到共享单车,于是 8:10 才到机房,然后两分钟过了 L。

@chen_jr 说会了 A,然后上去写,写了半个小时!!!!!!甚至没过,不知道发生了什么。于是把他赶下机,队友快速过 G,然后我五分钟就写完了 A!!!!!!同时我又很快过了 J。这时一个多小时,然后队友写 B 写完 WA 了,我写 I 写完也 WA 了!!!!!!我 I 算质因子算错了!!!!!!队友很快调完了 B,但是我 I 没意识到发生了什么!!!!!!完了过了半个小时队友拿走重构一发过了!!!!!!在这时大概会了 E 和 K 的正解。于是先让 @chen_jr 写 K,但是他建边建错了!!!!!!完了两个人一起调 K,@Chen_hx 写 E。过了半个小时就写完了,调了二十分钟就过了!!!!!!这时候 @chen_jr 跑路了,我和 @Chen_hx 一致认为 K 的做法是对的,于是换了个更好写的建图让他去重构,然后剩二十分钟的时候就过了!!!!!!其实这时候 D 大概会做了,但是没时间写。八题巨大罚时。

简要题解

A

先用若干次 1 k 把最后的 > 吃掉,完了之后从左到右吃掉每个 > 即可。

B

似乎是个背包 DP,没仔细想

D

分类讨论一下最开始的位置跟谁换,然后类似于字典树或者平衡树 kth 的过程固定下第一位之后往后继续扫。

E

换根 DP,没仔细想,0 没有乘法逆

G

没看

I

线段树维护 gcd。

J

按题意模拟。

K

每个 ai 往所有因子连一条权值为操作次数的边,然后费用流求最大权匹配。

L

按题意模拟。