如何评价ICPC 2022 西安站
注意，本文有严重剧透，请需要VP的同学在VP后阅读！
注意，本文有严重剧透，请需要VP的同学在VP后阅读！
注意，本文有严重剧透，请需要VP的同学在VP后阅读！
我超，金！
开始前我说能稳定发挥就好，和VP一样，这次目标7题，除非罚坐场。
开局还是经典头尾三线开：
我一看A数据结构先跳过
郑豪杰一看说B不太好做
舒飘扬一看这个L好像能做
J题
这题有两个人通过了，郑豪杰跟了下榜，是个又短又简单的大签到，10minAC。
C题
我一看感觉这个C好像很可做，叫舒飘扬别做L了，先来一起秒掉C，讨论一下很快想到了结论，郑豪杰刚下机，让舒飘扬上机，14min的时候AC了。
此时我和郑豪杰在看E，找到了3进制的规律，但也没那么好写，先当个medium题，也还没人过，先屯一下，反正签到多，先开签到。
F题
放下E题后，队友一起做已经有思路的L，我跟榜开个F，一看是个大签到，24minAC。
看样例1还以为这是M（male）和F（female）不能分在同一房间，结果一看样例2，发现这题的gender种类有A到Z，差点看错（好像有同学不认识gender这个词，倒是不容易读错）。
L题
舒飘扬一开始就觉得很可做，我过完F，郑豪杰上机写掉了L，38minAC。
G题
写L前，郑豪杰跟榜发现这题好像也不难，他写L时我和舒飘扬开G，我发现了常见规律之答案最大不超过根号，可以枚举，舒飘扬提供了从小到大保留合法串的暴力做法，当时复杂度懒得算了，估计很快，现在仔细一想应该是n * sqrt(n) * logn * 小常数，暴力冲一发应该快的，那直接O（能过）冲一发啊犹豫啥？其实我也想了广义SAM或者更优解法，后来听隔壁说又On的AC自动机做法，但是吸取了上一次不敢冲复杂度估计为2e9的多个log带小常数sort暴力解法导致浪费大量时间的教训，郑豪杰刚下机后我立马上机写根号暴力，42minAC。
E题
我写G时，他们俩接着讨论E，高位分类讨论，我去开A了，他们想清楚写法后，68minAC了。
---------------- 1h分界线 -----------------
现在的时间时1h8m：哇从来没有这么顺畅过，这把要金了呀，估计我们三个人都是这么想的，但是都没有说。现在才过了一小时，我们能这么顺利通过，别人也一样。变数还非常大，我们开局顺利，也只是多了做题时间的优势，关键还得看后面的medium-hard题能否成功拿下。如果不能拿下，便会功亏一篑，这个局势下我们有很大希望拿金，不能松懈，继续开题。
PS：后来听同学说这时候看榜以为点错了，因为我们这一小时过的题已经比隔壁CCPC广州站4小时过的还多了
A题
一开始在想并查集，但是想了下没思路，舒飘扬想了个根号分块，诶，那不就随便写了吗？郑豪杰直接上机，然后一开始块大小写了个根号n，应该是根号m，TLE一发；郑豪杰写的更新方式，WA一发；我们检查完之后再段错误一发，哦原来是我的哈希存在重复，100005*x+y写成了10005*x+y，仔细一想这的确可能导致下标越界成负数。128minAC了，3发罚时。赛后听6队学弟同学说了LCT做法，发现确实比较简单，主要是没有想到连横边是相当于竖边断了，这样路线好像会变成n条链。
B题
这题想了好久，一开始想的矩阵行交换，发现有空缺的矩阵没法处理。好在郑豪杰想出了最大流暴力解法，把思路带向正轨。但是暴力解法点数n2，边数n3，复杂度过大，想了很久之后我给优化成了n个点n2条边，枚举k，每次给行列的限流增加流量，在残量网络上跑最大流，以为复杂度是n5，但实际上这个网络流建模就约等于二分图最大匹配，复杂度实际上是O（点数*sqrt{边数}）大概是250^3。在封榜前一分钟也就是239minAC，TLE了3发，因为加流量的时候我直接加了一条流量为1的边，仔细一想，应该边的流量直接+1，常数大大减小（但是本地造数据跑了1.几秒，pta上2s时限TLE了，可能本地数据不够强）。
封榜后没有过题。虽然已经8题rank21，但是最后一小时怎能摆烂？
K题
这题开了一会，三个人都想过一会儿，都发现完全没法做，根据输入数据范围猜复杂度，为什么限制xy都是1e5以内？很可能跟坐标值域1e5有关，也可能只是和c<1e12关联，让答案不要太大，复杂度很可能是nm+Tlogc，可能是nm+Tx，可能是......算了完全没思路，放弃治疗
H题
舒飘扬不熟悉网络流，于是让他开H。在此之前，我因为B题没思路，看了看别的。一看这H很可能是诈骗题，摆个看似很吓人的巨大公式（实际上跟题目没有关系，不知道出题人想表达什么），实际上很可能并不难，我们现在就是前排队，应该有开0人题的勇气。两个人想了一会也有一些思路，我的思路大概是从大到小贪心，异或要给奇数个，或是最优的放在后，与是最没用的放在前，舒飘扬有另外类似的分类讨论，但是都越想越复杂。后来我和郑豪杰跟榜做D去了，让舒飘扬继续分类讨论H。在最后35分钟的时候，我和舒飘扬确认了一下，H题到现在还没思考清楚，肯定做不了，就算想完也写不完了，就算写完也很可能WA，果断放弃，来集火D题。
D题
这题一开始完全没思路，只会求全源最短路，我和郑豪杰想D，舒飘扬想L，后来一起做。想到了强连通分量，最后时间很紧，我说赶紧写完读入和tarjan，你们继续想。想到了缩点后求树上最短路，想到了这是5条链，合并链缩点后还是链，链上距离即为到根距离相减，但SCC内部点怎么办呢？SCC之间有多条边怎么走呢？又开始想同一条链边权是0，跨链边权是1的最短路能否优化，又想到......怎么样都不优于n3的floyd或者qnlogn的多次dijkstra单源最短路。
最后五分钟，实在没有希望了。我们选择了放弃，并开始看榜，发现很大概率金牌了。虽然最后一小时都在罚坐，但至少还尽全力尝试过了道题。然后我们开始讨论哪题整一发main(){}，封榜后不提交，就不能给别人留悬念，本来想交D的，然后决定还是交一发H吧。。不知这一发是否让人感觉有30%的可能性是通过了。
训练了两年多，这是我们拿下的第一块金牌。一个小时签下6个道0dirt，虽然都是简单题，但这样的双线配合以及做水题能力也是100场左右5小时组队训练和人均1500题的刷题量换来的。
向来都是我上机为主，今天是难的一次我上机的最少的场，我几乎都在讨论思路，有效代码只有两个签到题。我发的VP视频中，大多是我上机占一半时间，这只是因为通常我手速比较快，大码量题写得比较熟练，实际上三个人都非常的给力，训练量都一样大。在一次又一次的配合之后，大家都能够自信地说，“这题我一个人写就行了，你去做别的题吧“，或者放心地说，“这题你来写吧，我去开别的题了”。
