【CSP-S2019模拟】11.06比赛总结

差点AK,数组又开小了,淦!

比赛思路

传送门

  • T1(困难的图论):求简单环。裸题。但是刚开始并不会做。。。想暴力跳返祖边,再用一个并查集。但是这种东西显然是Tarjan,思考一下发现求的是点双,并且要求点双内的点的个数等于边的个数,然后才裸。。。
  • T2(book):原本的T2是5月份的原题,样例都一样???在线换题。随便算算就好了。
  • T3(上网):线段树优化连边+拓扑。

赛后消化

  • T1还可以对于树边差分,求出每一条树边被覆盖的次数,只被覆盖一次的就是简单环内的了。
  • T3检查了好多次数组,数组还是炸了(只剩下30分)。。。

总结

  • 要用极限数据去检查自己的数组。
  • 今天的题目有点水。。。希望NOIP也能有这么轻松吧。但是NOIP一定不能炸啊啊啊啊。
  • 基础的算法掌握的还不够牢固。各种图论的经典操作缺少练习。
原文地址:https://www.cnblogs.com/DeepThinking/p/13090918.html