CSPS模拟测试体验与解题策略

在这次CSPS模拟测试中，我的心情经历了极大的波动。开始时，对于第一题（T1），最初只能想到一个时间复杂度为$n^2$的方法，但随后意识到在使用BFS时，每个节点实际上只需被更新一次，多余的更新操作是没有必要的。基于这一点，我设想通过仅更新未被触及的节点来优化算法。

最初尝试使用链表来实现这一想法，但在删除链表中的元素后，发现无法有效地找到该元素的前后节点，这导致算法在大数据集上表现不佳，耗时过长。经过一番思考，转而考虑使用set来确保每个节点仅被更新一次。然而，由于对set的操作不够熟悉，花费了大量时间调试，特别是误解了set中begin()和end()函数的实际作用，进一步增加了调试难度。

尽管如此，经过约2小时的努力，我终于调整了算法，通过分别处理奇偶节点并适当缩小每个节点的影响范围，成功地解决了T1。在确认T1基本无误后，迅速转向T2，采用暴力方法解决，并在剩余不多的时间内对T1进行了进一步优化，确保其运行效率稳定在0.1秒。最后几分钟内，完成了T3的部分得分任务。

关于T1的具体解法，上述已有所提及。至于T2，关键在于认识到操作顺序对最终结果无影响。通过将所有数值按降序排列，可以发现每个值填充的区域呈现L形特征。为了保证填充的合法性，重点在于确保L形区域内的行列符合要求。利用组合数学中的容斥原理，可以通过计算特定条件下的组合数来解决这一问题，具体公式为$ans=\sum\limits_{i=0}^{a}{(-1)^{i}f_i}$，其中$f[i]$表示至少有i列不合法的情况，通过此公式可以直接计算出所需答案。