省流
砍下铜中,又是主包猪鼻如果罚时管理优秀又银了(没错永远都是“差点”银)。
10.19
内含剧透,请vp后再来。
不是题解!!!!!!!
赛前
这一把没有中文题面,队伍决定读英文。我被我自己的英语和队友的英语都折服了。好好练吧。
赛时
上来一开始读英语慢的要命根本没进展,等到榜出现后队友开始跟榜写 C,我则是单独去开 E。C 题具体是什么我不太清楚,总之是一个很水的签到,队友两人读题二十分钟,写完还挂一发,\(30min\) 吃一发罚时通过。然后简过来和我看 E,叶神则是跟榜去开 J。
E 题是有 \(x\) 只羊,\(y\) 只狼,一艘容量为 \(p\) 的船,要求把所有羊运到对面,且中途人不在的一侧需要狼的数量小于羊的数量加 \(q\)。数据范围均为 \(100\)。我一开始想着优先运羊最后再运相等的狼和羊这样子贪心,但简把我 \(hack\) 了。然后我就想到了类似 bfs 的做法,状态是狼和羊的数量以及在河岸的哪一侧,每次转移是到河岸的另一侧,以及运载到对岸的狼和羊的数量,复杂度就算 \(O(n^4)\)。将给了简,他理解后去实现了,在 \(79min\) 一发通过。
然后我和叶神一起开 J,J 是两人在树上轮流进行一个操作,把一个点的所有边连到和他相连的另一个点上,要求前后不能同构,谁不能操作谁输。输出输赢或平局。\(n \leq 50\)。叶神和我说操作次数应该是固定的,而且他找不到平局的可能。我说要么平局是骗的要么你挂了,我也不是特别相信次数是固定的,他也没和我说过程,于是我自己去推。发现题目的要求其实就是选择一个非叶子点并删掉,问删掉几次,还真的次数固定且没平局,而且复杂度是 \(O(n)\) 的!于是我们两个都诚惶诚恐不敢写,等简下机后问他,结果他说他没听懂。最后只好让叶神上机赌一把,没想到真是对的。但是叶神的自动补全出了问题吃了一发罚时,他没写 \(n = 2\) 的特判吃了一发,最后在 \(97min\) 以两发罚时通过。
接着我和简一起去看 K。K 题给了一个长度为 \(n \leq 2e5\) 数组,要求自由排列数组,然后求前缀和,问前缀和的最大值更新次数有多少种。然后有 \(q \leq 2e5\) 次修改,每次修改数组中的一个数,问题同样。简很快贪出来了,答案就是正数的前缀和小于负数之和加一。然后我接手这个贪心,码权值线段树加二分就行。交了一发挂了,发现权值线段树中下一个位置不一定只剩一个,处理一下之后不 WA 了,但超时。发现是卡常,如果想不卡常应该把二分写到线段树里才行。此时简偷窥了一下榜发现罚时对牌子没有影响了,于是我试着卡常卡过去,结果一直挂。最后还是改了线段树上二分就过了。
赛后
由于最后没管罚时,总罚时 \(585\) 过 \(4t\),银线是 \(345\) 罚时。因为 K 题的九次罚时,J 题写的太保守,以及一开始看题速度的问题,如果能解决这些应该是有机会打到银的,我们的比赛策略应该还有改进的空间。
以及近期内可能不会利用区域赛学新知识了,而是把区域赛完全当作模拟用,所以可能不会补靠后的题目了。
电子技术基础的老师讲课真是激情,想要专心真挺艰难的,有种感觉要戴耳塞才能抗住的感觉,而且每次都要点名不能翘掉。
2025年10月20日