Codeforces #403(Div. 2) - Click Here
Preface
这场是我的第一场CF，原本应该在结束时就补完这套题的。然而懒癌发作，一直拖到了现在。(终于填完了万年老坑。)
Problem A(CF780A)
Solutions
签到题，直接用一个队列模拟在桌上的袜子即可。
CODE
CODE - Click Here
Problem B(CF780B)
Solutions
若答案为$T$，则小于$T$的时刻必定无法相遇，大于$T$的时刻必定可以相遇，所以答案满足单调性。
鉴于单调性的基础上，可以二分答案，根据每个人的坐标以及速度可以得到一个移动范围，对所有移动范围取交集即可判断答案是否合法。
CODE
CODE - Click Here
Problem C(CF780C)
Solutions
每个点的颜色，只会受到它父亲的父亲和同父亲的儿子节点的影响，因此直接DFS染色即可。
CODE
CODE - Click Here
Problem D(CF780D)
Solutions
设第一种命名方式为$a_i$，第二种命名方式为$b_i$。
题目的限制要求是1、各个club不能使用相同名字。2、当选取第一种命名方式时，不能够和已选取第二种命名方式的club的第一种命名名字相同。
限制二有点拗口。其实限制二就是想表达，若存在club $i$和club $j$，使得$a_i=a_j$，则两者必须选取第二种命名方式。而对于$a_i \neq a_j$的情况，则不会出现限制二的情况。
因此，得到如下做法：对于满足$a_i=a_j$的club，则必取$b_i$作为名字。而剩下未命名的club，必定是$a_i \neq a_j$的情况。这些club的命名，只需要满足限制一即可，因此是经典的2-SAT模型。
由于$a_i,b_i$均为字符串，还需要使用Hash来进行存储。
最后算法时间复杂度为$O(N)$。
CODE
CODE - Click Here
Problem E(CF780E)
Solutions
构造题。。。
注意到每个clone步数限制$\lceil \frac{2n}{k} \rceil$中的分子$2n$与欧拉序列的长度$2n-1$几乎相等，因此该题实质上是要求我们输出一棵树的欧拉序列。
由此得到该题的做法为，将题目给出的图转换为树，然后求得树的欧拉序列。将欧拉序列分段输出即可。
本人在做此题前，认为欧拉序列的长度是随机的，与树的形态有关，并不知道是严格的$2n-1$。故在此处给出合理的解释：欧拉序列的长度等价于所有节点在序列中的出现次数之和。对于每个节点而言，它每访问一次儿子节点，都会导致它在序列中出现。而每个节点的儿子都是不重复的，因此我们可以认为所有节点的额外出现次数其实等于除根节点外的所有节点数，即$n-1$。因此总次数为$2n-1$。
CODE
CODE - Click Here
Problem F(CF780F)
Solutions
定义$f_i,g_i$分别为长度为$2^i$且首位为0或1的序列。
根据序列的定义，容易得到$f_i=f_{i-1}+g_{i-1},g_i=g_{i-1}+f_{i-1}$。
有了这个定义，很容易想到一个倍增DP的做法。
令$f[0/1][k][i][j]$表示从$i$走$2^k$走到$j$，且第一步为0或1是否可行。
用类似于Floyd的做法，可以得到转移方程$f[x][k][i][j]=f[x][k-1][i][q] \, \, | \, \, f[x \, xor \, 1][k - 1][q][j]$
这种做法时间复杂度为$O(N^3log\,10^{18})$，对于这题而言显然是超时的。
我们发现，每一位其实存储的只有0或1。因此实际上可以对最后一位(即上面的$j$)进行压位，将那维变成一个二进制数，第$j$位表示取$j$时是否为1。
这样开个bitset就可以解决了。由于bitset是60位一压，所以时间复杂度就变成了$O(\frac{N^3log\,10^{18}}{60})$
解决了DP后，如何得到答案呢？很简单，运用贪心的思想即可。即先尝试走$2^k$，再尝试走$2^{k-1}$，这样子逐渐递减。
CODE
CODE - Click Here