Codeforces Round #588 (Div. 1)

前言

寒假康复训练Day1，差点爆零了qwq。

题解

C - Konrad and Company Evaluation

题目要求维护，修改是把指向某个点的入边全部改成出边。
考虑对点按照度数不升序排序，那么我们尝试分成两部分来做。
1.对于位于左边的点，与相连的点必不可能超过。若超过，则说明有超过个点在左边且他们的度数都大于，总度数也大于，显然矛盾。因此，我们每次最多将条从左往右的边改成从右往左。
2.对于位于右边的点，我们这样考虑：刚开始从右指向左的总边数不超过，且每次修改最多新增条，那么显然总共出现过的从右往左的边数不可能超过，这一步修改的总边数也不超过这个数。
用维护每个点的入边，每次暴力修改完清空即可，总的复杂度为。

D - Wojtek and Card Tricks

因为最多种排列嘛，所以预处理一个表示第种排列（点）经过第种排列（边）之后得到的新排列（点）。
如果把排列看做边的话，那就是点经过范围内的边，能到达的点的个数。
枚举左端点，按顺序枚举每个没有访问到点，添加新的边，由于每次添加新的类型的边都会使被访问到的点的个数至少翻倍，因此最多添加条，每次枚举个顶点暴力添加，暴力搜索新的被访问到的点。
总的复杂度