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 我太菜了