周一 3.22（杂题）
Hongcow Builds A Nation (并查集 + 思维)
其实这道题并不难
只是在比赛中为了快点做出，乱猜是贪心，然后思路错误浪费了大量时间，依然WA
所以比赛中静下心和平时一样想题目才是发挥地最好的
这题就是用并查集处理出几个联通分量，没有被标记的联通分量看作一个大联通分量
然后联通分量内部连边，然后未被标记的大联通分量和被标记联通分量里面个数最多的连边
最后减去原来的边就ok了
其实蛮简单的
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int f[N], a[N], cnt[N], n, m, k;int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}int main()
{scanf("%d%d%d", &n, &m, &k);_for(i, 1, n) f[i] = i;while(k--){int x; scanf("%d", &x);a[x] = 1; } _for(i, 1, m){int u, v;scanf("%d%d", &u, &v);f[find(u)] = find(v);}int sum = 0, mx = 0, t = 0;_for(i, 1, n){if(a[i]) a[find(i)] = 1;cnt[find(i)]++;}_for(i, 1, n)if(f[i] == i && a[i]){sum += cnt[i] * (cnt[i] - 1) / 2;if(a[i]) mx = max(mx, cnt[i]);} _for(i, 1, n)if(!a[find(i)])t++;sum += mx * t + t * (t - 1) / 2;printf("%d\n", sum - m);return 0;
}Stairs and Elevators（二分查找）
这道题考试的时候都没读题，其实蛮简单的，二分一下就完事了
注意到这道题给的范围很大到1e8
所以给的坐标直接二分一下找到相邻的位置就好了
找到相邻的位置无非就四种可能，四种可能里面取最优就好了
注意可能并不需要走楼梯和电梯，当x相同的时候，要特判一下，我因为这个WA了一次
还有总是重复的量可以用变成存一下，代码会简洁很多，也容易调试
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
int n, m, l[N], e[N], cl, ce, v;int main()
{scanf("%d%d%d%d%d", &n, &m, &cl, &ce, &v);_for(i, 1, cl) scanf("%d", &l[i]);_for(i, 1, ce) scanf("%d", &e[i]);int q; scanf("%d", &q);while(q--){int ans = 1e9, x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);if(y1 > y2) swap(x1, x2), swap(y1, y2);if(x1 == x2){printf("%d\n", abs(y1 - y2));continue;}int dx = abs(x1 - x2), dy = abs(y1 - y2);int now = lower_bound(l + 1, l + cl + 1, y1) - l;if(now != cl + 1) ans = min(ans, dx + dy + 2 * max(l[now] - y2, 0));if(now - 1 >= 1) ans = min(ans, dx + dy + 2 * abs(y1 - l[now - 1]));now = lower_bound(e + 1, e + ce + 1, y1) - e;dx = (dx + v - 1) / v;if(now != ce + 1) ans = min(ans, dx + dy + 2 * max(e[now] - y2, 0));if(now - 1 >= 1) ans = min(ans, dx + dy + 2 * abs(y1 - e[now - 1]));printf("%d\n", ans);}return 0;
}D. Timetable（分组背包 + 暴力）
这道题真的一言难尽
考试的时候一读完题就知道是分组背包
要预处理一下每一天翘i节课最多能少掉多少时间
结果我没怎么想清楚，感觉是贪心，然后就写了贪心
比赛时一定要和平时一样想清楚，静下心。不要随便贪心，这道题的贪心是错误的
赛后发现贪心是错误的，如果暴力求这个，复杂度理论上是500的三次方，会超时
然后我就想什么方法优化，然后一直想不出
然而最后发现不会超时，可能是因为1.25e8比较极限，没超得太远，而且数据也没那么强
我在这浪费了很多时间，一直以为会超时。有时候到1e8比较极限的时候也可以试一下，说不定数据水
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 500 + 10;
struct node{ int w, v; };
vector<node> ve[N];
int f[N], L[N], R[N];
int n, m, k, sum;int main()
{scanf("%d%d%d", &n, &m, &k);_for(j, 1, n){int t = 0, cnt = 0, l; _for(i, 1, m) {int x; scanf("%1d", &x);if(!x) continue;if(!t) l = i;else L[++cnt] = i - t; t = i;} if(!t) continue;sum += t - l + 1;_for(i, 1, cnt) R[i] = L[cnt - i + 1];_for(i, 1, cnt) L[i] += L[i - 1], R[i] += R[i - 1]; int w = 0, mx = 0;_for(p, 1, min(cnt, k)){mx = 0;_for(i, 0, p)mx = max(mx, L[i] + R[p - i]);ve[j].push_back(node{++w, mx});}ve[j].push_back(node{++w, mx + 1});}_for(i, 1, n) for(int j = k; j >= 0; j--)REP(t, 0, ve[i].size()){int w = ve[i][t].w, v = ve[i][t].v;if(j >= w) f[j] = max(f[j], f[j - w] + v);}printf("%d\n", sum - f[k]);return 0;
}A. Zebras（思维 + set）
比赛时有两种思路，一种是推出规律，找1的个数和0的个数的关系，结果没推出来
第二种就是for很多遍，每一遍都得出一个序列
其实2e5的数据，尽管会删除数据，for很多遍肯定超时的，我当时就是太着急了，有一个思路还没想正确性就开始写，浪费时间又WA
那么正解肯定是for一遍，O（n）或者O（nlogn）
我想了挺久，发现可以边for就边加入各个序列当中，一个1就要找到末尾为0的序列，一个0就要找到末尾为1的序列
一开始遍历一遍末尾符合的序列结果超时
后来反应到可以用两个set来维护末尾为1的序列和末尾为0的序列的集合，每次都是logn
然后就AC了
还是挺有趣的，这个思维我还是过了很久才想到，还是做题太少，继续加油
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
vector<int> ans[N];
set<int> s1, s2; //s1末尾为1 s2末尾为0
int cnt;int main()
{ios::sync_with_stdio(0);cin.tie(0);string s;cin >> s;int len = s.size();int flag = 1;REP(k, 0, len){if(s[k] == '0'){if(s1.empty()){ans[++cnt].push_back(k + 1);s2.insert(cnt);}else{int t = *s1.begin(); //begin()是迭代器，看作指针 ans[t].push_back(k + 1);s1.erase(t); s2.insert(t);}}else{if(s2.empty()) { flag = 0; break; }else{int t = *s2.begin(); ans[t].push_back(k + 1);s2.erase(t); s1.insert(t);}}}_for(i, 1, cnt)if(ans[i].size() % 2 == 0){flag = 0;break;}if(!flag) puts("-1");else{printf("%d\n", cnt);_for(i, 1, cnt){printf("%d ", ans[i].size());for(auto x: ans[i])printf("%d ", x);puts("");}}return 0;
}
今天一口气补了四道题，都是独立做出，很爽
其实还是有实力做出来cf 1500到2000的题目的，但是考试时发挥不出来。
考试时应该静下心想题，想清楚，像平时一样，这是我要改进的
周二 3.23 （杂题 + 欧拉回路）
AtCoder - agc006_b（构造题）
说实话这道题我是一点思路都没有
感觉挺复杂，因为每三个数都要取一遍
最后看了题解
发现很巧妙，只要中间放上x - 1 x x + 1就可以了
可以推出来这样一直往上，x会一直在中间
没想到这么简单
这种构造题真的挺巧妙的，看似很复杂，却能用一种很简单的方式解决
构造题不要想太复杂，往往解法很简单。不要有心理障碍
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
int ans[N];int main()
{int n, x;scanf("%d%d", &n, &x);if(x == 1 || x == 2 * n - 1) {puts("No");return 0;}ans[n - 1] = x - 1;ans[n] = x;ans[n + 1] = x + 1;int now = 0;_for(i, 1, 2 * n - 1){if(ans[i]) continue;now++;if(now == x - 1) now = x + 2;ans[i] = now;}puts("Yes");_for(i, 1, 2 * n - 1) printf("%d\n", ans[i]);return 0;
}P2731 [USACO3.3]骑马修栅栏 Riding the Fences(欧拉回路模板题)
欧拉回路可以很形象地理解为一笔画问题
一笔画就是一条路径，每条边经过且仅经过一次
这样的路叫做欧拉路
如果是一条回路，就交欧拉回路
理解了这个定义，那么一些性质就很容易理解
无向图中，欧拉回路度数都为偶数，欧拉路仅有两个度数为奇数的点
有向图中，欧拉回路入度=出度，欧拉路中一个点入度多1，一个点出度多1，其他入度等于出度
那么这么求呢？
算法的思路是这样的，找到一个环，删除，继续找一个环，然后把两个环拼接成一个环，一直重复下去
看起来复杂，思路很简单，dfs的时候每走过一条边就删除掉
关键点在于在这个点的出边遍历完之后加入栈记录答案，这个过程恰好完成了两个环拼接的过程
注意这里不能边搜边记录答案，要遍历完出边，把这个点加入栈
最后倒序输出
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 500 + 10;
int g[N][N], d[N], m, mx, mi = 1e9;
stack<int> ans;void dfs(int u)
{_for(v, mi, mx)if(g[u][v]){g[u][v]--;g[v][u]--;dfs(v);}ans.push(u);
}int main()
{scanf("%d", &m);while(m--){int u, v;scanf("%d%d", &u, &v);g[u][v]++; g[v][u]++;d[u]++; d[v]++;mi = min(mi, min(u, v));mx = max(mx, max(u, v));}int st = mi;_for(i, mi, mx)if(d[i] & 1){st = i;break;}dfs(st);while(!ans.empty()){printf("%d\n", ans.top());ans.pop();}return 0;
}周三 3.24 （欧拉回路）
先再明确一下定义
欧拉路是每条边只经过一次且经过所有顶点，即一笔画经过所有点
是否存在欧拉路或欧拉回路的判定：
有两个条件
一个是 图是联通的，有向边则视为无向边（称为基图），可以用并查集维护，最后为一个联通分量
一个是度数的关系，这个是很容易推出来的
如果要求具体的路径才dfs
「一本通 3.7 例 2」单词游戏（建模 + 欧拉路判定）
这道题搞了我好久
建模真的太骚了
第一反应可以是单词为点，然后去连边，找一条路径使得每个点只经过一次
第一连边会超时，第二这种路径是哈密尔顿路，求这个路很麻烦
然后我就灵光一闪，把26个字母看作点，单词看作边
这样每条边只经过一次，这样建模不就刚好是欧拉路的定义吗
然后我又卡住了，单词看作边要怎么连呢
我开始是想末字母有一条出边，首字母有一条入边，然后看度数的关系
可是判顶的时候还要看联通，所以不能光看度数的关系
最后我看了题解，竟然是一个单词首字母向末字母连一条边
太秀了
这样子没那么直接，但是分析一波是对的，这样保留了这个单词的信息
因此根据前面说的那两个条件判定欧拉图就好了
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int in[30], out[30], f[30], vis[30], n, cnt;
char s[N];int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}int main()
{int T; scanf("%d", &T);while(T--){memset(in, 0, sizeof(in));memset(out, 0, sizeof(out));memset(vis, 0, sizeof(vis));_for(i, 0, 25) f[i] = i;cnt = 0;scanf("%d", &n);_for(i, 1, n){scanf("%s", s);int len = strlen(s);int u = s[0] - 'a', v = s[len - 1] - 'a';out[u]++; in[v]++; if(!vis[u]) vis[u] = 1, cnt++;if(!vis[v]) vis[v] = 1, cnt++;if(find(u) != find(v)) cnt--;f[find(u)] = find(v);}int cnt1 = 0, cnt2 = 0, flag = 1;_for(i, 0, 25){if(in[i] == out[i]) continue;if(in[i] - out[i] == 1) cnt1++;else if(out[i] - in[i] == 1) cnt2++;else { flag = 0; break; }}if(cnt != 1 || !flag || !( (!cnt1 && !cnt2) || (cnt1 == 1 && cnt2 ==1))) puts("The door cannot be opened.");else puts("Ordering is possible.");}return 0;
}也可以度数+dfs，看能否经过所有边
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int in[30], out[30], n, sum;
struct node{ int v, vis; };
vector<node> g[N];
char s[N];void dfs(int u)
{for(auto& x: g[u]) //如果要修改边的值的话，这里要引用 if(!x.vis){x.vis = 1;dfs(x.v);sum++;}
}int main()
{int T; scanf("%d", &T);while(T--){memset(in, 0, sizeof(in));memset(out, 0, sizeof(out));_for(i, 0, 25) g[i].clear();scanf("%d", &n);_for(i, 1, n){scanf("%s", s);int len = strlen(s);int u = s[0] - 'a', v = s[len - 1] - 'a';g[u].push_back(node{v, 0});out[u]++; in[v]++; }int cnt1 = 0, cnt2 = 0, flag = 1, st = -1;_for(i, 0, 25){if(in[i] == out[i]) continue;if(in[i] - out[i] == 1) cnt1++;else if(out[i] - in[i] == 1) cnt2++, st = i;else { flag = 0; break; }}if(!flag || !( (!cnt1 && !cnt2) || (cnt1 == 1 && cnt2 ==1))) {puts("The door cannot be opened.");continue;}if(st == -1)_for(i, 0, 25)if(out[i]){st = i;break;}sum = 0;dfs(st);if(sum == n) puts("Ordering is possible.");else puts("The door cannot be opened.");}return 0;
}hdu 1878 (判定欧拉图模板题)
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int deg[N], f[N], n, m; int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}int main()
{while(scanf("%d", &n) && n){memset(deg, 0, sizeof(deg));_for(i, 1, n) f[i] = i;int cnt = n;scanf("%d", &m);while(m--){int u, v;scanf("%d%d", &u, &v);deg[u]++; deg[v]++;if(find(u) != find(v)) cnt--;f[find(u)] = find(v);}int flag = 1;_for(i, 1, n)if(deg[i] & 1){flag = 0;break;}if(flag && cnt == 1) puts("1");else puts("0");}return 0;
}周四 3.25 （欧拉回路）
「一本通 3.7 练习 2」Ant Trip（欧拉回路 + 找规律猜结论）
一开始想暴力，就是不断跑欧拉路不断删边，看能跑多少次
然后超时了
后来想到可以通过度数来判定，不用真的去跑欧拉回路，要具体路径才跑
那么有欧拉路或者欧拉回路前提是联通，所以用并查集维护多个联通分量
然后我就任意画图看要几笔才能画完，感觉和奇点个数有关
然后我一直画不出奇点个数为奇数的图，一直是0 2 4 6
我还发现，0 和 2的时候是一次（也即欧拉路判定条件），而4个奇点要2笔，6个奇点要3笔
发现每画一笔会少两个奇点。那么就可以按照这个算个数了
交上去WA了一发，发现忽略了孤立点的情况。
孤立点要删掉，因为其根本没有边，欧拉路是经过每个边有且仅有一次。
因此统计答案时忽略孤立点就好了
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
int deg[N], f[N], cnt[N], n, m; int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}int main()
{while(~scanf("%d%d", &n, &m)){memset(deg, 0, sizeof(deg));memset(cnt, 0, sizeof(cnt));_for(i, 1, n) f[i] = i;while(m--){int u, v;scanf("%d%d", &u, &v);deg[u]++; deg[v]++;f[find(u)] = find(v);}_for(i, 1, n)if(deg[i] & 1)cnt[find(i)]++;int ans = 0;_for(i, 1, n)if(deg[i] && find(i) == i){if(cnt[i] <= 2) ans++;else ans += cnt[i] / 2;}printf("%d\n", ans);}return 0;
}「一本通 3.7 练习 3」John's Trip（欧拉回路模板题）
输出边的顺序就好了
注意两个点
1.dfs之前要先判断一下度数，度数正确是前提。如果度数不对，即使dfs可以得到一个路径，也是不行的
2.如果题目要求输出边的编号，那么删边的时候用一个vis数组来保存是否访问过就好。
3.注意重边和自环。删边用边的编号删去，不要用map<pair<int, int>, bool> 这个无法处理重边的情况
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 50;
const int M = 2000;
struct node{ int v, id; };
vector<node> g[N];
stack<int> ans;
int deg[N], vis[M], n, m, st, cnt;void dfs(int u)
{for(node x: g[u]){int v = x.v, id = x.id;if(!vis[id]){vis[id] = 1;dfs(v);ans.push(id);}}
}int main()
{int x, y, z;while(scanf("%d%d", &x, &y) && x && y){cnt = 1;REP(i, 0, N) g[i].clear();memset(deg, 0, sizeof(deg));memset(vis, 0, sizeof(vis));st = min(x, y);scanf("%d", &z);g[x].push_back(node{y, z});g[y].push_back(node{x, z});deg[x]++; deg[y]++;while(scanf("%d%d", &x, &y) && x && y){scanf("%d", &z);g[x].push_back(node{y, z});g[y].push_back(node{x, z}); deg[x]++; deg[y]++;cnt++;}int flag = 1;REP(i, 0, N) //一定先判度数 if(deg[i] & 1){puts("Round trip does not exist.");flag = 0;break;}if(!flag) continue;while(!ans.empty()) ans.pop();dfs(st);if(ans.size() != cnt) puts("Round trip does not exist.");else{while(!ans.empty()){printf("%d", ans.top());if(ans.size() == 1) puts("");else printf(" ");ans.pop();}}}return 0;
}周五 3.26 （欧拉回路）
「一本通 3.7 练习 4」太鼓达人（欧拉回路 + 建模）
我又一次跳坑，二进制数看作点，去连边
花了一个小时写完后发现错了。
突然意识这道题和单词接龙的非常像，可以说是一道题
同样，一个二进制数就是一条边，头向尾连，这时头是除去最后一个字符，尾是出去第一个字符
欧拉回路建模的核心在于明确什么是边，边经过且只经过一次
然后还有一些细节看代码
#include<bits/stdc++.h>
#define mp make_pair
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1100;
map<pair<int, int>, bool> vis;
vector<int> g[N];
stack<int> ans;
int k;int num(string s)
{int res = 0, len = s.size();REP(i, 0, len){res <<= 1; //乘2写上面，不然最后多乘一次 res += s[i] - '0';}return res;
}void dfs(int u)
{for(int v: g[u])if(!vis[mp(u, v)]) //没有重边可以用map删边. {vis[mp(u, v)] = 1;dfs(v);}ans.push(u); //点在循环结束后加入
}int main()
{cin >> k;REP(i, 0, 1 << k){string t = "", t1 = "", t2 = ""; //初始化，类似int x = 0 REP(j, 0, k){if(i & (1 << j)) t += "1";else t += "0";}REP(j, 0, k - 1) t1 += t[j], t2 += t[j + 1]; //注意string用法 是 += 不是 = g[num(t1)].push_back(num(t2)); //注意是有向边 }REP(i, 0, 1 << (k - 1)) sort(g[i].begin(), g[i].end()); //排序保证字典序 dfs(0);cout << (1 << k) << " ";while(ans.size() > 1) //最后回到起点不用输出 {int t = ans.top();if(t & (1 << (k - 2))) cout << "1";else cout << "0";ans.pop();}return 0;
}周六 3.27 （欧拉回路）
「一本通 3.7 练习 6」原始生物（欧拉回路 + 建模 + 找规律）
这道题感觉就像是前面几道题的综合
首先建模很套路了，一个遗传密码就是一条边，首向尾连接
然后问题就变成了一个有向图，需要几笔画才能画完
我开始跑欧拉回路，看能跑几次。发现在不存在一笔画完的情况下跑欧拉回路是错误的
这个图存在欧拉回路再去跑才是对的
那么显然就要看每个联通分量的度数了
这里我卡了很久，没什么思路
然后我意识到，一条路径，起点出度-1，终点入度-1，中间的点的出度和入度减去相同的数
也就是除非是作为起点和终点，否则一个点的出度和入度的差值是相同的
那么比如一个点出度比入度大3，那么这个点一定要以它为起点跑3次
所以我们可以统计所有出度大于入度时的差值和（入度大于出度叶可以，一样的），就是要跑的次数
这里有个坑点就是，差值和为0的时候也要跑一次，这时是欧拉回路
知道了跑欧拉路的次数之后，就可以按照题意算出答案了，答案为次数 + 联通分量中边的个数
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int in[N], out[N], f[N], cnt[N], cnt1[N], n;int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
} int main()
{_for(i, 1, 1000) f[i] = i;scanf("%d", &n);while(n--){int l, r;scanf("%d%d", &l, &r);out[l]++; in[r]++;int x = find(l), y = find(r);if(x == y) cnt[x]++;else{f[x] = y;cnt[y] += cnt[x] + 1;}}_for(i, 1, 1000)if(out[i] > in[i]) cnt1[find(i)] += out[i] - in[i];int ans = 0;_for(i, 1, 1000)if((in[i] || out[i]) && f[i] == i)ans += cnt[i] + max(cnt1[i], 1);printf("%d\n", ans);return 0;
}周日 3.28 （欧拉回路）
「一本通 3.7 练习 5」相框（欧拉回路）
这题太骚了，我独立做到80分，有一种情况没考虑到
首先抽象出模型，以度数为核心考虑
烧熔操作可以理解为把度数拆开，例如3拆成1 + 2
那么为了最终成一个环，要分两种情况
如果只有一个联通分量就简单，大于2的全部拆成一堆2，如果为奇数就多留下一个1
为什么要2呢，因为环上每个度数都为2
从度数满足去推为一个环，我手画了一下，发现度数对了一定有其中一种方式可以弄成环。不一定度数对了就是环，但一定有一种方式度数对了就是环
之后合并，把奇数对合并就好
如果有多个联通分量就麻烦
目标是每个联通分量弄成一条链，最后一起合并成一个大环
对于其中的一个联通分量
同样大于2的点拆，最后合并度数为1的点
这里有个特例，就是不存在奇数点的情况
我开始想的是最后再把环拆成链就行了
然后我没想到的是，当烧熔的过程中，如果度数大于2，比如4，是可以拆成2 + 1 + 1的
也就是说，如果有点度数大于2，就不用最后再把环拆为链
就是这个点让我一直80分
此外，如果有一端为0那就新创一个点，把它合并到体系当中。记得相应空间也改一改
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 1e3 + 10;
int deg[N], f[N], num[N], k[N], n, m;int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}int main()
{REP(i, 1, N) f[i] = i;scanf("%d%d", &n, &m);while(m--){int u, v;scanf("%d%d", &u, &v);if(!u) deg[u = ++n]++; else deg[u]++;if(!v) deg[v = ++n]++; else deg[v]++;f[find(u)] = find(v);}int cnt = 0;_for(i, 1, n)if(deg[i] && f[i] == i) //联通分量个数 cnt++;int ans = 0;if(cnt == 1){int t = 0;_for(i, 1, n){if(deg[i] > 2) ans++;if(deg[i] & 1) t++; //奇数个数 }ans += t / 2; //合并两端 }else{_for(i, 1, n){if(deg[i] > 2) ans++, k[find(i)] = 1; if(deg[i] & 1) num[find(i)]++; //奇数个数 }_for(i, 1, n)if(deg[i] && f[i] == i){if(num[i] == 0) ans += !k[i]; else ans += num[i] / 2 - 1; }ans += cnt;}printf("%d\n", ans);return 0;
}现在开始如果队内没有比赛的话，自己弄一套div1 abc，英文要适应
A. Basic Diplomacy（构造）
看似复杂的这种构造题
YES与NO的区分条件往往是很简单，很极端的
这道题只要必须选的人超过m/2就不行，其他时候一定行
行的话，那就把必须选的人先选，然后剩下就选那些选的次数最少的人就行
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
vector<int> g[N];
int cnt[N], n, m;int main()
{int T; scanf("%d", &T);while(T--){memset(cnt, 0, sizeof(cnt));scanf("%d%d", &n, &m);int mx = 0;_for(i, 1, m) {g[i].clear();int k; scanf("%d", &k);_for(j, 1, k){int x; scanf("%d", &x);g[i].push_back(x);if(k == 1) mx = max(mx, ++cnt[x]);}}if(mx > (m + 1) / 2) puts("NO");else{puts("YES");memset(cnt, 0, sizeof(cnt));_for(i, 1, m)if(g[i].size() == 1)cnt[g[i][0]]++;_for(i, 1, m){if(g[i].size() == 1) printf("%d ", g[i][0]);else {int ma = 1e9, t;for(int j: g[i]) if(ma > cnt[j]){ma = cnt[j];t = j;}printf("%d ", t);cnt[t]++;}}puts("");}}return 0;
}晚上做b做着有点疲惫了
明天把bc做了，每周一套div1 abc