csp七连day5
1.时间安排
6:00-6:04
自古T1大水题。4分钟码完。
6:05-6:15
今天T2竟然水了,发现O( n log ( n ) n\log(n) nlog(n))可过,直接码。
6:15-6:30
刚看到T3被吓到了,但是看到special judge就放心了,思考了一会,没思路,去看T4。
6:30-7:20
意识到T4有暴力分,就写了一份暴力枚举判断,虽然反复查了很多次,测试了很多数据,但是,这个判断还是出了大问题。
7:20-8:00
试图用状压写部分分,发现不可行,就写了一个玄学拓扑,然后写了随机数(埋下30分的伏笔)。
8:00-8:10
给T1,T2对拍,测试了很多数据都没问题,就放心了。
8:10-9:00
思考优化T4的判断,想到了三角形,但是不会推。
9:00-9:30
思考T3的暴力分,但是终究没思路,放弃了,全力搞T4。
9:00-9:30
一直到结束也没写出更好的判断,无奈提交。
得分:
T1:100
T2:100
T3:30
T4:0
2.赛后反思
1.算法的问题
T4考到了计算集合中的三角剖分,以及判断相交的CCW,都没学过。
虽然老师说不用学,但是觉得CCW挺方便的,可以试试学一下。
然后T3考到了拓扑排序,感觉拓扑排序不是很熟练了,可以练习一下。
2.策略的问题
感觉这次策略有一点失误了:不敢大胆尝试。
T3有60分的贪心,应该是很容易码对的,但是没有去尝试,把更多的时间花在了推T4上。
不能说推T4不值,但是更应该把更容易得到的分先拿到手,这样才最稳。
赛场上为了那分不择手段(当然平常比赛要讲武德),所以要大胆尝试,只要想到了,就去大胆码,只要有分就是胜利。
3.数学能力的问题
T4暴力挂了是最不应该的,明明判断也不复杂,写挂就一分没有了。
题目中有时候会涉及到复杂的数学计算(NOI1999棋盘划分),但是不算就没有分,需要加强在这方面的能力。
而且感觉几何图形的处理还是不熟练,可以找些题练练。
4.心态的问题
这次心态处理的自我感觉还是不错的,没有被T3吓到,也没有因T1、T2简单而轻敌。
没有大问题就继续保持。
3.题解
T1.游戏
题解:
小学数学题。
把数字和统计起来,先判断是不是三的倍数,然后判断有没有0,都满足把数字sort一遍降序输出即可。
T2.排列
题解:
按结构体存,存数值和编号,排一下序,然后遍历查找区间长度即可。
T3.照明
题解:
先拓扑排序,然后把每个边被遍历的编号存起来,之后按照42一小组,42小组一大组,进行小组内染色,小组外大组内染色,大组外染色,输出。
T4.相交
题解:
看不懂三角剖分,回来补上正解。
30分的暴力做法就是判断两条边是否相交,暴力枚举。
(不是我水啊,题解真的就这么多)
4.未来规划
1.学会如何判断线段相交。
2.练习拓扑排序。
3.练习几何类题目。
(麻人者,人恒麻之)