Day 12

昨天的OJ似乎出了不少锅所以今天又回到了评测机评测估计是咱又要爆零了qwq今天题目上来就来了一句“题目按字典序排列”果然是有鬼。。还是先看题

T1 Graph

最开始的想法是类似于百度之星Day 3的思路，不过这题似乎边是走完了直接删除和百度之星差距有点大所以得换个思路。后来又证了一个联通块内边数为偶数一定有解，奇数可以断边得到偶数，找路径的时候就用类似于匈牙利算法去做。不过考场上写的有点惨最后只有10分。 实际上正解和我想的也差不了多少吧【趴，就是直接把这个图看作一棵树去跑BFS，先将孩子的边尽可能配对，否则就将这条边和其父亲配对。对于非树边我们也可以直接按照上述方法来处理。正确性可以用类似于匈牙利算法的思路去证。

T2 Permutation

考场上没看的题。。根据之前的经验来说T2一般都比较毒瘤，看了一眼题面也没啥思路就先扔掉了。。 我们发现题面里面|i-j| \le k这个条件并不是很好用，我们考虑对这个序列做一个映射。我们令b[a[i]]=i，因为最小的数尽可能靠前和最小的数下标尽可能小是等价的，这题要求的就变成了交换相邻两个差大于k的数能得到的字典序最小的序列。我们发现两个大小之差小于k的数在任何情况下都不可能交换顺序，即两者之间的相对位置关系已经确定了，我们可以考虑拓扑排序+优先队列来求出字典序最小的序列。注意到直接连边会使得边数十分巨大，我们考虑线段树优化建边。我们注意到图中存在A \to C，B \to C，A \to B这种情况。显然在这种情况下这三条边中有一条是不必要的，我们可以用线段树避免这一条边被建出来。每次对于每一个位置a[i]，我们向(a[i]-k,a[i]) \cup (a[i],a[i]+k)中下标最小的连一条边即可。

T3 Tree

这道题完美验证了这套题的题目顺序是有坑的 这题实际上是一道结论题。答案即为所有边权之和。具体证明看这里。