题目均为人工翻译英文，不清楚的地方 请 连蒙带猜 结合样例理解

ABC来自atcoder, DEF来自codeforces

震哥写的题解

校内链接，时限开了三年，各位同学可以继续做的鸭

T1 A

#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5+5; const int INF = 1e8;//这里不可以设成1e9啊啊啊 int n, cnt=0; ll a[N]; int dis[205][205], e[205][205]; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { ll x; scanf("%lld", &x); if(x) a[++cnt] = x;//如果为0，无边 } if(cnt >= 130) { puts("3"); return 0;} //边界值 for(int i = 1; i <= cnt; i++) for(int j = 1; j <= cnt; j++) if((a[i]&a[j]) && (i!=j)) e[i][j] = dis[i][j] = 1; else e[i][j] = dis[i][j] = INF; //赋初值 int ans = INF; for(int k = 1; k <= cnt; k++) { for(int i = 1; i < k; i++) for(int j = i+1; j < k; j++) ans = min(ans, dis[i][j] + e[i][k] + e[k][j]); for(int i = 1; i <= cnt; i++) for(int j = 1; j <= cnt; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } //Floyed求最小环长度 ans>cnt ? puts("-1") : printf("%d\n", ans); return 0; }

T2 B

T3 C

T4 D

这题很清真啊~ 只要注意一下时间上的优化，用$deep[i]$记录第$i$号点下面深度为$deep[i]$的所有点都已经染色

#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5+10; struct qyx{int num, d, ans;} p[N]; int vis[N], deep[N]; int len=0, cnt=0, sum, n, m, Q; vector<int> e[N];//不知道为什么领接表会RE……就用Vector辽 void Insert(int a, int b, int c) { p[++cnt].num = a; p[cnt].d = b; p[cnt].ans = c; } void dfs(int k, int d, int ans, int fa) { if(deep[k]>d) return; deep[k] = d;//这是一个时间上优化，记录搜索的深度 if(!vis[k]) vis[k] = ans, sum--;//如果颜色没有被改过 for(int i = 0; i<e[k].size(); i++) { int y = e[k][i]; if(y == fa) continue; if(d) dfs(y, d-1, ans, k); } } int main() { scanf("%d%d", &n, &m); for(int i = 1, v, u; i <= m; i++) { scanf("%d%d", &u, &v); e[v].push_back(u); e[u].push_back(v); } scanf("%d", &Q); for(int i = 1,u, v, w; i <= Q; i++) { scanf("%d%d%d", &u, &v, &w); Insert(u, v, w); } sum = n; //倒着寻找颜色，因为颜色是会覆盖的 for(int i = Q; i >= 1&&sum; i--) dfs(p[i].num, p[i].d, p[i].ans, 0); for(int i = 1; i <= n; i++) printf("%d\n", vis[i]); return 0; }

T5 E

T6 F

这题也清真~ 但是我交了十几遍……是我太愚蠢……INF不能开到1e9，因为在Floyed中会爆

#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5+5; const int INF = 1e8;//这里不可以设成1e9啊啊啊 int n, cnt=0; ll a[N]; int dis[205][205], e[205][205]; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { ll x; scanf("%lld", &x); if(x) a[++cnt] = x; } if(cnt >= 130) { puts("3"); return 0;} //因为与的性质，一旦不为0的数超过130，必然有三个数在同一位上皆为1（鸽巢原理）,那么必然存在最小环3 //边界 for(int i = 1; i <= cnt; i++) for(int j = 1; j <= cnt; j++) if((a[i]&a[j]) && (i!=j)) e[i][j] = dis[i][j] = 1; else e[i][j] = dis[i][j] = INF; int ans = INF; for(int k = 1; k <= cnt; k++) { for(int i = 1; i < k; i++) for(int j = i+1; j < k; j++) ans = min(ans, dis[i][j] + e[i][k] + e[k][j]); for(int i = 1; i <= cnt; i++) for(int j = 1; j <= cnt; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } //Floyed求最小环 ans>cnt ? puts("-1") : printf("%d\n", ans); return 0; }

T7 G

这道题目超级巧妙的说，其实只要能想到怎么建图，一切就很清真辽！ 建图之前，在最外面框一圈0,，为什么呢，下面说。 我们把一种颜色看成一个点，只要与它相邻就建边，我们只考虑上下左右四个方向（因为题目中排除了对角线的情况），但只遍历右下两个方向，避免连边太多，因为左上的情况，它左上的点的连线会连向它。这很显然的叭！ 这样就建成了一颗假的树（会出现环的呢），仔细观察一下，发现如果一个点 $x$ 是割点，这意味着什么呢，如果 $x$ 的子树和 $x$ 断开了联系，就与最外层的 $0$ 隔绝，也就意味着 $x$ 的子树所代表的所有颜色都被 $x$ 包裹在里面，太好了，答案已经出来了。 首先进行建图。 然后 $dfs$ 计算子树大小，这时候最外圈的 $0$ 就有用啦！ $0$在最外面，自然就是那个年纪最大的祖先！ 然后遍历求割点，这里有一个坑！我刚开始就判断了一个点 $x$ 是否是割点，如果是就输出 $size[x]-1$，否则输出 $0$，但是这是不正确的，只能过 $9$ 个点（这可能是因为我 $RP$ 比较高，竟然能过 $9$ 个点）。因为这棵树是个假的树，它存在环，很有可能你求出的割点 $x$，分割出来的子树加上 $x$ 就是一个环或者子树直接与 $0$ 有连边，这个时候，这棵子树是不可以被加进答案里的，所以我们要判的其实是割边，如果是割边，就加入这个割边所相连的子树。 好了，做完了！

#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1000100; struct psx{int y, next;} e[N<<3]; int lin[N], size[N], vis[N], dfn[N], low[N], cnt[N]; int len=0, num, sum, root, n, m; int a[1010][1010]; void add(int yy, int xx) { e[++len].next = lin[xx]; lin[xx] = len; e[len].y = yy; } void dfs(int k) { if(k > num) num = k; size[k] = vis[k] = 1; for(int i = lin[k]; i; i = e[i].next) { int y = e[i].y; if(vis[y]) continue; dfs(y); size[k] += size[y]; } } void tarjan(int x) { dfn[x] = low[x] = ++sum; for(int i = lin[x]; i; i = e[i].next) { int y = e[i].y; if(!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); if(low[y] >= dfn[x]) cnt[x] += size[y]; } else low[x] = min(low[x], dfn[y]); } } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &a[i][j]); for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++) { if(a[i][j] != a[i+1][j]) add(a[i][j], a[i+1][j]),add(a[i+1][j], a[i][j]); if(a[i][j] != a[i][j+1]) add(a[i][j], a[i][j+1]),add(a[i][j+1], a[i][j]); } //建图 dfs(0);//求子树 tarjan(0);//求割点 for(int i = 1; i < num; i++) printf("%d ", cnt[i]); printf("%d\n", cnt[num]); return 0; }