TJOI2021翻盘记

# TJOI 2021 翻盘记 ## Day 0 本来想看板子的结果在学校摸了一天鱼。 大概中午的时候就开始摸鱼了。然后随便做了一个 HMOI 的题就开始颓废。 然后大概没有给 qs 带书，rp--。 出学校的时候听攀岩高手 Fake了几句，然后大概决定回家看板子。 回家打了几个板子，没怎么吃饭，就睡觉了。 睡前找Gaaaaa????聊了一会，一个可爱的陌生人。 ## Day 1 早上起来就很不爽，大概7：30到了之后没拿身份证，还要回家拿一波。 大概试机的时候什么都没打，写了一个 FastIO，然后发现我右边是 SingerCoder，后边是攀岩高手，在后边是 fnoi16wjhui。右后方是litanghui0000。都是TJ的希望。 然后大概8：20的时候就看到题目了。 我们省考 B 卷。 T1签到题。10min就打完了。 然后看T2，是A卷T1。大概看了眼数据，发现$n,m\le 1e6$ 似乎比较卡常数。难搞。 然后就bb了一个枚举最大值，然后可以二分极差，看看是否可以。大概bb了20min想出来一个 $O(n\log^2 n)$ 的做法。需要离散化和主席树。 然后大概仔细想了想发现不需要主席树，就删了。然后与处理一下二分的值就发现复杂度降到了 $O(n\log n)$ 然后一发过了大样例。 似乎比较水的样例？ 有点危。 然后看了眼 T3，这时候还有 3h，我心想这还搞不出来？ 然后没搞出来。写了44分暴力滚粗了。就是考虑一个 $O(nm(m+n))$ 的做法。 我们枚举分别计算 $H(G)$ 的值，然后去考虑 $O(nm+n^2)$ 的计算一个答案。 我们考虑同时考虑一个点 $i$ 对于 $f(i,G),\cdots,f(n,G)$ 的贡献。那么存一下反图，如果一个 $j\ge i$ 的点 $j$ 可以跟 $i$ 构成环那么就有一个贡献。 这时无论如何我们都可以删除 $i$ 点，这对于答案是没有影响的。因为我们考虑如果 $j$ 点经过前边一个没有贡献的点 $u$ 与 $i$ 构成了一个环，那么为什么 $u$ 的时候不计算这个环呢？根据反证法，这种情况不存在，直接删去即可。 然后打了44pts暴力之后就在考场上划水了一个半小时。划水的时候发现了某些不可告人的秘密。 出来大概估分是 $100+100+44$ 现在估分是 $100+[0,100]+44$ 听说 $SingerCoder$ AK了很强。 希望明天考个大众分数就可以进队了。希望T2数据够强 ## Day2 退役了 现在在用手机编辑 真的没有想过退役是这么近的一件事，我以为我能翻盘 **update**:似乎还可以活？D2T1好像对的？ 进队了 想哭 最后分数是 100+100+44+100+25+60 我太菜了