A. Dawid and Bags of Candies
乱搞。
B. Ania and Minimizing
贪心。
C. Anadi and Domino
题意：
存在一张图有\(n,n\leq 7\)个点，现在要给他们染上\(1\)~\(6\)的颜色。最后问怎样染色，能够使得\((c_1,c_2)\)这样的对数最多（不计算重复，不考虑顺序，\(c_1,c_2\)表示颜色）。
思路：
一开始想的是随机乱搞一发，结果出了不知道什么错wa了一个点= =
其实直接\(dfs\)就行了，复杂度不会超。
D. Marcin and Training Camp
题意：
先有\(n\)个人，每个人有两个属性：\(a,b\)。其中\(a\)的含义是，当前这个人会一些技能，技能的\(id\)就为\(a\)里面二进制\(1\)的位置。
\(i\)看不起\(j\)，当且仅当\(i\)会一项\(j\)不会的技能。
现在要选择一些人出来作为一支团队，要求不存在一个人看不起其它所有人并且\(b\)的和最大。
思路：
题意不好描述啊感觉= =
首先可以发现一个比较显然的结论：
- 团队中最大的\(a\)值至少有两个。
因为要\(b\)和最大，所以有推论：
- 若存在多个人的\(a\)相同，那么他们都可以选择。
处理完上面的情况，剩下的就是\(a\)只出现一次了。接下来又有一个结论：
- 一个\(a\)能够被选择，当且仅当他作为已选集合的一个子集。
如果不满足上面的条件，那么他就能够看不起其它所有人，除非有其他人\(a\)值和他相同，但这种情况已经排除了。
然后随便写写就好了。
E. Kamil and Making a Stream
题意：
给出一颗树，每个结点都有其权值，先求所有链的\(gcd\)的和。
思路：
- 比较直接的想法就是\(O(n^2)\)的暴力，对于每个点\(v\)，找到其所有的祖先\(u\)，计算\(gcd\)。
- 稍微改进一下，不用找到所有的祖先，只需要找到其父亲与所有祖先的\(gcd\)值就行，但复杂度还是没有变。
- 发现\(gcd\)的个数很少，大概为\(\log_{2}a[v]\)个，因为每个\(gcd\)都为\(a[v]\)因子。所以直接用一个\(map\)来存一下出现次数就行了。
似乎这里\(map\)的\(log\)和\(gcd\)的\(log\)的分开的...
F. Konrad and Company Evaluation
题意：
给出一个\(n\)个点\(m\)条边的有向图，现在有\(q\)次操作，每次可以选择一个点，然后将它所有的入边反转。
问每次操作过后形成的“三元环”数量，这里“三元环”的定义为对于点\(a,b,c\)，有\(a->b->c\)，那么这就算作一个。
\(n,m,q\leq 10^5\)。
思路：
- 统计三元环时，易知一个点的贡献为\(out[u]*in[u]\)，相当于枚举中点。
问题在于每次如何翻转边并且快速统计答案。然后题解就是暴力翻转就行了...
下面简略证明一下：
- 我们按照每个点的度从大到小排序，并且以度数为\(\sqrt{2m}\)划分界限，左边为“大点”，右边为“小点”。
- 易知左边点的个数不会超过\(\sqrt{2m}\)个，而右边点的度数不会超过\(\sqrt{2m}\)。
- 现在将所有边分为三类：在“大点”间的，在“小点”间的，以及跨过中线的，然后依次分析：
- 显然每次对“小点”操作不会超过\(\sqrt{2m}\)；
- 对于跨过中间的，我们先消耗一定复杂度让其全部指向“小点”，易知复杂度不超过\(O(m)\)。
- 那么每次对“大点”操作，第一类复杂度不会超过\(\sqrt{2m}\)（因为个数只有那么多），对于第三类边，只有可能一开始已经翻转过，那么这类边每次操作的复杂度最高为\(O(T)\)，\(T\)表示当前时间。所以对于一个“大点”而言，操作一次的最高复杂度为\(O(q+\sqrt{2m})\)，最多操作\(\sqrt{2m}\)次。
* 综上，总的复杂度为$O(q\sqrt{2m}+m)$的样子。
然后暴力就行啦，感觉证明的思想核心还是对度数进行分块然后来分析，挺巧妙的~其实简单点想就是，对于每个点只有可能第一次翻转复杂度较高，后面翻转就跟时间有关了，因为每次翻转对于一个点入度最多增加\(1\)。
代码很简单：
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int n, m;
vector <int> in[N];
int d[N];
void run() {
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
if(u > v) swap(u, v);
++d[u], ++d[v];
in[u].push_back(v);
}
ll ans = 0;
for(int i = 1; i <= n; i++) ans += 1ll * (d[i] - sz(in[i])) * sz(in[i]);
int q; cin >> q;
while(q--) {
cout << ans << '\n';
int x; cin >> x;
ans -= 1ll * (d[x] - sz(in[x])) * sz(in[x]);
for(auto v : in[x]) {
ans -= 1ll * (d[v] - sz(in[v])) * sz(in[v]);
in[v].push_back(x);
ans += 1ll * (d[v] - sz(in[v])) * sz(in[v]);
}
in[x].clear();
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n >> m) run();
return 0;
}