CSP 2022 S2 游记

· · 个人记录

可能更好的阅读体验

ZJ-S00283

Day -3

得知放在杭州学军海创园区考试，说是要住全季酒店，要全寄的节奏。
义乌的怎么在杭师大啊，看来不大可能见到 FLY 了。

Day -2

真·全寄酒店，整个考点都寄了。
得知考点换到了绍兴一中，不能和 FLY 面基了，伤心。
下午 zyq 的模拟赛 T2 过样例爆零，样例是真的水，下大分。
订正完模拟赛（指T1T2T4）晚上写了个网络流模板。

Day -1

上午复习模板，平衡树什么懒得写了，写了个 kmp 和费用流，写了道简单 数论+组合 *1900 的题。
下午就出发去绍兴一中了。
晚上和 rsj,lzy,xyh 三个人打了一晚上音游。

Day 1

上午和 cqy 打游戏。中午去和另外五个人出去吃火锅。绍兴一日游。
下午就是 tg 了。
早早到了考场，整个考场就只有 qzez 的。考场不让进就在休息室，好家伙我校 28 个人直接几乎占了一整个休息室（甚至不是所有人在同一个休息室）。

考点很良心，居然还有试机时间，赶紧敲了个巨长的码头。
密码是 belief 2022，pj 听说是 mountain2022。
公布密码后扫了下题目，怎么 4 题三个图论一个博弈？？？

下午 2:30 开考
先开 T1，看到 4 个不同景点感觉很奇怪，猜可能是分层图，然后瞎搞了一番，没有任何进展。
突然意识到 k\le 100，然后发现这没有任何作用。
不会做就去看部分分，发现有一档 k=0 的分，就开始思考。
然后发现无论 k 是多少都可以 bfs O(n^2) 求出所有两两可以转车 k 次以内到达的景点。
接着发现这是一个无向图，所以从 1\to A \to B \to C \to D \to 1 整个过程中两边是对称的。
然后就只要求出所以 1\to A\to B 的点对，然后枚举 B\to C这段就可以了。至于 A 和 D 直接贪心就好了。然后由于四个景点不能重合，所以需要多存几个最大值，然后枚举就可以了。
本来想拍一下的，但是发现暴力有点难写，仔细看了看代码就结束了。

然后开 T2。
先是手玩了下，为什么题目就不能说先手取完后手知道先手取的数吗？害我看半天。
随手搓了个 O(Tn^2) 的暴力。然后开始分类讨论，发现需要查询两个序列中正数和负数的最小值、最大值。反手写了个 class SGT，然后建了 4 个线段树。
写完测下样例，发现大样例死活过不去，也考虑这题分类讨论容易遗漏，就拿暴力拍着。也不知道为什么绍一的电脑对拍怎么这么慢。。。。。
中途查出来分类讨论问题很多，可以想象到我这题若果没拍的结果。
最后大概是大样例过了，但是调大数据范围还是能拍出来一些问题，然后就差不多了。
此时时间已经过去一半多（两个半小时），去厕所冷静了下，挂着 T2 的对拍，然后开始写 T3T4 的暴力。

T3 题面真的长，发现输出 YES 当且仅当 所以点的出度小于等于 1 并且出度为零的强连通分量点数大于 1，写了个 Tarjan，O(mq) 的 40 分暴力。
T4 没什么思路，就直接把那条链提出来 DP，但是不知道为什么有个样例怎么都过不去。时间不是很充足，所以 k=1 的树剖也没有敲。

出了考场，发现 T3 只要让所有点的出度为 1 就好了（内向基环森林），同时发现 T4 写假了（也有可能跳到链外面再跳回来的），不过好像这么写随机数据正确率还是很高的。
回去的路上在音游&和xjz辩论。

赛后回家自测，洛谷 100+100+?+40，infoj 95+100+40+40
没有挂很多，看样子大概 [260,280]，也算是平均水平了，满足了。

Day 4

洛谷 100+100+40+40
infoj 100+100+40+40 Hydro 100+80+40+56