浙江省选一试

今天是浙江省选一试，晚上看到了题目，说一下初步思路：

第一题，本质上跟USACO的bigbrn以及rectbarn没区别，把状态转移方程略改一下即可。

第二题，第一问只需保存原序列及每个点处被插入的最后一个数，每插入一个数与前后比较更新当前答案这个思路是错误的，那么似乎可以用链表+堆乱搞出来？；第二问随便写一种平衡树，每插入一个数与其prev、next比较，注意如果发现重复则以后答案都是零不用再维护树了。

第三题，要每一行及每一列都存在1即可。例如，只要第一行有1，可以把那个1所在的那一列与第1列交换，就将规模为n的问题转换为了n-1的问题，且仍然每一行及每一列都有1。上述思路错误的，只是必要条件。应该是每行只选一个节点就能使每列都有节点，换句话说，行与列间存在完美匹配。

第四题，树形DP，对于每个节点把它当作“激发器”求解让它下面所有的叶子节点同步所需的代价以及同步后的时间。

题目的思路基本上都是一下子就想出来的，就是不知道若在比赛环境中还能不能这样思维敏捷，还有就是能在有限的时间内完美地实现多少。

不知道今天Jessica做得怎么样……今天一整天我都在默默祝福她。希望她顺利吧。