CSPS_106

2024-09-01 07:47:31

　　　　这场

　　　　死的太惨了！

　　　　我也不把我的错误像倒垃圾一样放在blog里了qwq

　　　　通过这场考试我深深地认识到了情绪对人类的影响qwq

　　　　只要这种东西，不要出现在我的csp中就好了

　　　　T1

　　　　　　区间DP..

　　　　T2

　　　　　　枚举最后一次的动作，前方可以贪心

　　　　　　虽然水位错了个位，但是每次都是错相同的1位

　　　　　　所以直接处理错位情况下的RMQ，

　　　　　　把当前行动提到后边相当于错位后高度减去当前行动的增量

　　　　　　然后枚举时分“需要这个行动垫脚”和“不需要”两种情况二分，

　　　　　　其实就是排序后二分的位置在这个元素前还是后的区别

　　　　T3

　　　　　　发现行列是否翻转之间有限制

　　　　　　如果可以达成目标，两人必定合作达成目标

　　　　　　否则只与行列的奇偶有关，

　　　　　　

　　　　　　于是只考虑可以达成目标的情况下，

　　　　　　是否能做到必定由自己完成最后一次操作

　　　　　　发现所有操作聚成了一些集合，即做就一起做，不做都不做

　　　　　　

　　　　　　这个模型其实已经很板子了（对于刚颓完sg函数的我来说

　　　　　　考场上我还是很谨慎地完成了奇偶性的分类讨论的

　　　　　　

　　　　　　以上过程我都做的完全正确..

　　　　　　可是为什么死了呢，因为DP胜败态的时候出了点问题

　　　　　　这个问题为什么会出现，还在研究..

　　　　　　

　　　　　　诡异现象：

　　　　　　1.我的dp比skyh的多1.5维，考虑了很多不必考虑的因素。

　　　　　　　尽管如此如果转移合法，仍然不该导致错误

　　　　　　2.我的dp转移会出环..考虑dp定义的话，两个状态应该互相转移..

　　　　　　　而且如果强制断掉环上的一条边，使这两个状态只能单向转移的话，

　　　　　　　它作为一个不完整（正确性未知）的dp它AC了..

　　　　　　

　　　　　　将我的dp与skyh的对比，

　　　　　　我的dp多出来的无非是“剩余操作奇偶性"

　　　　　　　　与"剩余偶偶联通块"这两个无用的维度

　　　　　　考虑到"偶偶联通块"的使用只会影响

　　　　　　　　"剩余操作奇偶性”这一维，选用奇奇块则不影响

　　　　　　那个不完整的转移可能仅仅是抵消了我在第一维度所作的修改..

　　　　　　至于“奇偶联通块”的使用，虽然会影响第一维，

　　　　　　skyh的dp则使用了给“奇奇联通块”一维加一的做法实现了相同效果

　　　　　　在他的dp里，这样的确是一直简单的处理方法

　　　　　　

　　　　　　所以我的dp败在哪里了呢，状态不够简练，

　　　　　　没有体现博弈论的思想，

　　　　　　过分关注过程的变化，而不是只关心对结果有影响的元素

　　　　　　

　　　　　　dp状态的设计非常非常重要..

　　　　　　再说直接用sg函数真的香

最新文章

热门文章