Codeforces #410(Div. 2) - Click Here
Preface
段考爆炸，《具体数学》看得我身心俱疲，所以还是来填填CF的坑吧~
这场是构造题专场~
Problem A(CF798A)
Solutions
扫一遍计算不满足的回文组数，然后判断是否为1即可。
注意，如果回文组数为0且$n$为奇数，答案仍然为Yes。因为，可以通过修改中间字符来满足要求。
CODE
CODE - Click Here
Problem B(CF798B)
Solutions
既然最后的目的是使得所有字符串都相同，那么只需要枚举第一个字符串的交换次数，就可以包含所有情况。
所以暴力统计取最小值就好了~
时间复杂度$O(N|S|^2)$
CODE
CODE - Click Here
Problem C(CF798C)
Solutions
当初数论太差了，被这题卡死了QwQ。
如果$gcd(a_1,a_2,…,a_n)>1$，显然不需要任何操作即满足要求。
因此，现在只需要考虑$gcd(a_1,a_2,…,a_n)=1$的情况。
首先设该序列的最大公约数为$d$。
假设我们对序列中的$(a_i,a_{i+1})$进行操作，那么此时$d$应该满足，$d|(a_i-a_{i+1}) , \, d|(a_i+a_{i+1})$。根据整除的性质得$d|2a_i, \, d|2a_{i+1}$。
又因为，$d$是序列的公约数，因此$d|gcd(a_1,a_2,…,2a_i,2a_{i+1},…,a_n)$。
右式等价于$gcd(a_1,a_2,…,2gcd(a_i,a_{i+1}),…,a_n)$，因此$gcd(a_1,a_2,…,2a_i,2a_{i+1},…,a_n)|2$。
即$d|2$。
换句话说，我们经过变换后，$d$只能够成为$2$。要满足$d=2$，需要将序列中所有奇数变为偶数。
考虑如何变换。
如果$a_i$和$a_{i+1}$均为奇数，则只需要1次操作。(操作1)
如果$a_i$和$a_{i+1}$仅含有一个奇数，则需要2次操作。(操作2)
显然，要使得操作次数最少，最优策略是先执行操作1，后执行操作2。
因此直接扫一遍计数即可。
时间复杂度$O(Nlog \, a)$。
CODE
CODE - Click Here
Problem D(CF798D)
Solutions
好套路的一题构造题，然而我并不会QwQ。
题目要求选出一个集合$P$，使得$2\sum a_{p_k} > \sum a_i , \, 2\sum b_{p_k} > \sum b_i$。
通过对式子的简单变形得到$\sum_{k \in P} a_k > \sum_{k \notin P} a_k , \, \sum_{k \in P} b_k > \sum_{k \notin P} b_k$。
也就是说，我们选出的数字之和要大于未选出的数字之和。
同时注意到，选出的数字个数与未选出的数字个数的差为1或2。
因此，我们可以对$A$序列和$B$序列适当的分组，每个组仅包含两个元素，这样从中选出较大的数字，则必定能够满足要求。
但是$A$和$B$是互相制约的，$A$序列选取较大数字会导致$B$序列无法选取较大数字的情况。
为了处理这种情况，可以对$A$排序，然后仅考虑$B$来选择。
由此，我们得到最终的贪心策略：首先对$A$排序，然后必选最大的元素。接着，对剩下元素两两分组，选取$b$较大的元素。
而这种做法的正确性亦是显然的：因为对$A$进行了排序，因此上次选取的元素必定大于等于这次未选取的元素；对于$B$，因为每次选取的都是最大的，因此每次选取的元素都大于等于未选取元素。又因为两者个数不同，又保证了不等式不可能取等号。
CODE
CODE - Click Here
Problem E(CF798E)
Solutions
又是构造题，不过这题比D要好做啊>_<。
读入数据提供了一堆大小关系，因此根据差分约束的套路，可以由这些关系构造出一个有向图$G=(V,E)$，其中每条边$(u,v) \in E$都表示$p_u>p_v$。又因为$p_i$均不相同，所以这个图为有向无环图。
然后对这个图跑一遍拓扑排序，并根据拓扑序赋值，那么得到的答案必定是满足要求的。
所以只要求出拓扑序，该题就解决了。所以我们考虑图中含有哪些边。
令满足$a_i=-1$的值变为$a_i=n+1$。并定义$b_i=j$，其中$j$满足$a_j=i$，若不存在，则$b_i=n+1$。
根据题意，显然可知对于每一个$i$，需要连的边有两种，一种为$(i,b_i)$，另一种为$(i,j)$，其中$1 \leq j < a_i$且$b_j>i$。
第一种连边很好处理，但是另外一种连边就很难搞了，因为这种情况的边数最坏会达到$N^2$。要是使用Kahn算法，你必须要存储所有的边，或者是连续的加边并滋瓷用数据结构维护入度，而这两种方法都不能够实现。
但是拓扑排序还能够dfs实现，我们考虑下基于dfs的拓扑排序能否解决问题。
首先是第一种连边，显然可以实现。
接着是第二种连边，需要找到连续区间内满足$b_j>i$的节点，这个节点可以利用线段树在$logN$的时间内找到，而且每个节点只会访问一次。因此寻找这种节点的总时间为$O(2NlogN)$。
然后就解决问题啦~
在这里提下为什么Kahn算法和基于dfs算法会在处理上出现时间上的差距。
两种算法都是$O(V+E)$的，但不同之处在于Kahn算法需要利用到所有的边，而基于dfs的算法只需要找到与当前节点相连且未访问过的节点。
换句话说，基于dfs的算法不需要利用到所有的边。所以这种算法的时间是能够优化的~
CODE
CODE - Click Here