A.取中间那个点即可。
#include<bits/stdc++.h> using namespace std; int a[3]; int main() { ios::sync_with_stdio(false); cin >> a[0] >> a[1] >> a[2]; sort(a,a+3); cout << a[2]-a[0] << endl; return 0; }
B.模拟，注意判断是否在括号内。
#include<bits/stdc++.h> using namespace std; int n; string s; int main() { cin >> n; getchar(); getline(cin,s); int maxx = 0,cnt = 0,now = 0,flag = 0; for(int i = 0;i < n;i++) { if(s[i] == '(') { flag = 1; now = 0; } else if(s[i] == ')') { flag = 0; if(now) cnt++; now = 0; } else if(s[i] == '_') { if(flag == 1 && now) cnt++; now = 0; } else { now++; if(flag == 0) maxx = max(maxx,now); } } cout << maxx << " " << cnt << endl; return 0; }
C.先算出ans，再把个数不到ans的数填满。
#include<bits/stdc++.h> using namespace std; int n,m,a[2005],b[2005] = {0}; int main() { ios::sync_with_stdio(false); cin >> n >> m; for(int i = 1;i <= n;i++) { cin >> a[i]; if(a[i] <= m) b[a[i]]++; } int ans = n/m,cnt = 0,now = 1; for(int i = 1;i <= n;i++) { if(a[i] <= m && b[a[i]] <= ans) continue; while(b[now] >= ans) now++; if(now == m+1) break; if(a[i] <= m) b[a[i]]--; a[i] = now; b[now]++; cnt++; } cout << ans << " " << cnt << endl; for(int i = 1;i <= n;i++) cout << a[i] << " "; cout << endl; return 0; }
D.dfs找出每一个湖泊，按面积排序，把cnt-k个小的填满。
#include<bits/stdc++.h> using namespace std; int n,m,k,vis[55][55] = {0},ok,sum; int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; string s[55]; struct xxx { int x,y,sum; friend bool operator <(xxx a,xxx b) { return a.sum < b.sum; } }a[2505]; void dfs1(int x,int y) { if(vis[x][y]) return; vis[x][y] = 1; sum++; for(int i = 0;i < 4;i++) { int xx = x+dx[i],yy = y+dy[i]; if(xx < 1 || xx > n || yy < 1 || yy > m) { ok = 0; continue; } if(s[xx][yy] == '*') continue; dfs1(xx,yy); } } void dfs2(int x,int y) { s[x][y] = '*'; for(int i = 0;i < 4;i++) { int xx = x+dx[i],yy = y+dy[i]; if(xx < 1 || xx > n || yy < 1 || yy > m || s[xx][yy] == '*') continue; dfs2(xx,yy); } } int main() { ios::sync_with_stdio(false); cin >> n >> m >> k; int cnt = 0; for(int i = 1;i <= n;i++) { cin >> s[i]; s[i] = " "+s[i]; } for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { if(s[i][j] == '*' || vis[i][j]) continue; ok = 1; sum = 0; dfs1(i,j); if(ok) { a[++cnt].x = i; a[cnt].y = j; a[cnt].sum = sum; } } } sort(a+1,a+1+cnt); cnt -= k; int ans = 0; for(int i = 1;i <= cnt;i++) { ans += a[i].sum; dfs2(a[i].x,a[i].y); } cout << ans << endl; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) cout << s[i][j]; cout << endl; } return 0; }
E.因为是无向图，所以有偶数个度为奇数的点，我们把他们与第n+1个点相连，则所有点的度都是偶数个，存在欧拉回路，输出这个回路的路径（不包括第n+1个点），符合要求。
#include<bits/stdc++.h> using namespace std; int n,m,d[205]; set<int> s[205]; void dfs(int now) { while(s[now].size()) { int t = *s[now].begin(); s[now].erase(t); s[t].erase(now); if(now != n+1 && t != n+1) cout << now << " " << t << endl; dfs(t); } } int main() { int T; cin >> T; while(T--) { cin >> n >> m; memset(d,0,sizeof(d)); while(m--) { int x,y; cin >> x >> y; s[x].insert(y); s[y].insert(x); d[x]++; d[y]++; } int ans = 0; for(int i = 1;i <= n;i++) { if(d[i]%2) { s[i].insert(n+1); s[n+1].insert(i); } else ans++; } cout << ans << endl; for(int i = 1;i <= n;i++) dfs(i); } return 0; }
F.原图无向连通，可以把原图的除s，t外的点分为三类团。
①与s相连。②与t相连。③与s，t相连。
若不存在第③类团，则把相应团与s或t相连，最后把s与t相连。
若存在第③类团，则s与t不必相连，可以通过第③类团来把他们相连，这样其中某个点的度就少了1，为最优情况。
#include<bits/stdc++.h> using namespace std; struct xx { int x,y; xx(int a,int b):x(a),y(b){}; }; int n,m,x,y,dx,dy,cnt = 0,a[200005] = {0},b[200005] = {0},vis[200005] = {0}; vector<int> v[200005]; vector<xx> ans; void dfs(int now) { vis[now] = 1; for(int i = 0;i < v[now].size();i++) { int t = v[now][i]; if(t == x) a[cnt] = now; else if(t == y) b[cnt] = now; else if(!vis[t]) { ans.push_back(xx(now,t)); dfs(t); } } } int main() { ios::sync_with_stdio(false); cin >> n >> m; for(int i = 1;i <= m;i++) { cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } cin >> x >> y >> dx >> dy; for(int i = 1;i <= n;i++) { if(vis[i] || i == x || i == y) continue; ++cnt; dfs(i); } int z = 0; for(int i = 1;i <= cnt;i++) { if(a[i] == 0) { ans.push_back(xx(b[i],y)); dy--; } else if(b[i] == 0) { ans.push_back(xx(a[i],x)); dx--; } else z++; } if(dx < 1 || dy < 1 || dx+dy-1 < z) { cout << "No" << endl; return 0; } if(z == 0) ans.push_back(xx(x,y)); else { int flag = 0; for(int i = 1;i <= cnt;i++) { if(a[i] == 0 || b[i] == 0) continue; if(flag) { if(dx) { ans.push_back(xx(a[i],x)); dx--; } else { ans.push_back(xx(b[i],y)); dy--; } } else { flag = 1; ans.push_back(xx(a[i],x)); dx--; ans.push_back(xx(b[i],y)); dy--; } } } cout << "Yes" << endl; for(int i = 0;i < ans.size();i++) cout << ans[i].x << " " << ans[i].y << endl; return 0; }