正文
Codeforces_723
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
A.取中间那个点即可。
#include<bits/stdc++.h>
using namespace std; int a[]; int main()
{
ios::sync_with_stdio(false);
cin >> a[] >> a[] >> a[];
sort(a,a+);
cout << a[]-a[] << endl;
return ;
}
B.模拟，注意判断是否在括号内。
#include<bits/stdc++.h>
using namespace std; int n;
string s; int main()
{
cin >> n;
getchar();
getline(cin,s);
int maxx = ,cnt = ,now = ,flag = ;
for(int i = ;i < n;i++)
{
if(s[i] == '(')
{
flag = ;
now = ;
}
else if(s[i] == ')')
{
flag = ;
if(now) cnt++;
now = ;
}
else if(s[i] == '_')
{
if(flag == && now) cnt++;
now = ;
}
else
{
now++;
if(flag == ) maxx = max(maxx,now);
}
}
cout << maxx << " " << cnt << endl;
return ;
}
C.先算出ans，再把个数不到ans的数填满。
#include<bits/stdc++.h>
using namespace std; int n,m,a[],b[] = {}; int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = ;i <= n;i++)
{
cin >> a[i];
if(a[i] <= m) b[a[i]]++;
}
int ans = n/m,cnt = ,now = ;
for(int i = ;i <= n;i++)
{
if(a[i] <= m && b[a[i]] <= ans) continue;
while(b[now] >= ans) now++;
if(now == m+) break;
if(a[i] <= m) b[a[i]]--;
a[i] = now;
b[now]++;
cnt++;
}
cout << ans << " " << cnt << endl;
for(int i = ;i <= n;i++) cout << a[i] << " ";
cout << endl;
return ;
}
D.dfs找出每一个湖泊，按面积排序，把cnt-k个小的填满。
#include<bits/stdc++.h>
using namespace std; int n,m,k,vis[][] = {},ok,sum;
int dx[] = {,,-,};
int dy[] = {-,,,};
string s[];
struct xxx
{
int x,y,sum;
friend bool operator <(xxx a,xxx b)
{
return a.sum < b.sum;
}
}a[]; void dfs1(int x,int y)
{
if(vis[x][y]) return;
vis[x][y] = ;
sum++;
for(int i = ;i < ;i++)
{
int xx = x+dx[i],yy = y+dy[i];
if(xx < || xx > n || yy < || yy > m)
{
ok = ;
continue;
}
if(s[xx][yy] == '*') continue;
dfs1(xx,yy);
}
} void dfs2(int x,int y)
{
s[x][y] = '*';
for(int i = ;i < ;i++)
{
int xx = x+dx[i],yy = y+dy[i];
if(xx < || xx > n || yy < || yy > m || s[xx][yy] == '*') continue;
dfs2(xx,yy);
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m >> k;
int cnt = ;
for(int i = ;i <= n;i++)
{
cin >> s[i];
s[i] = " "+s[i];
}
for(int i = ;i <= n;i++)
{
for(int j = ;j <= m;j++)
{
if(s[i][j] == '*' || vis[i][j]) continue;
ok = ;
sum = ;
dfs1(i,j);
if(ok)
{
a[++cnt].x = i;
a[cnt].y = j;
a[cnt].sum = sum;
}
}
}
sort(a+,a++cnt);
cnt -= k;
int ans = ;
for(int i = ;i <= cnt;i++)
{
ans += a[i].sum;
dfs2(a[i].x,a[i].y);
}
cout << ans << endl;
for(int i = ;i <= n;i++)
{
for(int j = ;j <= m;j++) cout << s[i][j];
cout << endl;
}
return ;
}
E.因为是无向图，所以有偶数个度为奇数的点，我们把他们与第n+1个点相连，则所有点的度都是偶数个，存在欧拉回路，输出这个回路的路径（不包括第n+1个点），符合要求。
#include<bits/stdc++.h>
using namespace std; int n,m,d[];
set<int> s[]; void dfs(int now)
{
while(s[now].size())
{
int t = *s[now].begin();
s[now].erase(t);
s[t].erase(now);
if(now != n+ && t != n+) cout << now << " " << t << endl;
dfs(t);
}
} int main()
{
int T;
cin >> T;
while(T--)
{
cin >> n >> m;
memset(d,,sizeof(d));
while(m--)
{
int x,y;
cin >> x >> y;
s[x].insert(y);
s[y].insert(x);
d[x]++;
d[y]++;
}
int ans = ;
for(int i = ;i <= n;i++)
{
if(d[i]%)
{
s[i].insert(n+);
s[n+].insert(i);
}
else ans++;
}
cout << ans << endl;
for(int i = ;i <= n;i++) dfs(i);
}
return ;
}
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 = ,a[] = {},b[] = {},vis[] = {};
vector<int> v[];
vector<xx> ans; void dfs(int now)
{
vis[now] = ;
for(int i = ;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 = ;i <= m;i++)
{
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
cin >> x >> y >> dx >> dy;
for(int i = ;i <= n;i++)
{
if(vis[i] || i == x || i == y) continue;
++cnt;
dfs(i);
}
int z = ;
for(int i = ;i <= cnt;i++)
{
if(a[i] == )
{
ans.push_back(xx(b[i],y));
dy--;
}
else if(b[i] == )
{
ans.push_back(xx(a[i],x));
dx--;
}
else z++;
}
if(dx < || dy < || dx+dy- < z)
{
cout << "No" << endl;
return ;
}
if(z == ) ans.push_back(xx(x,y));
else
{
int flag = ;
for(int i = ;i <= cnt;i++)
{
if(a[i] == || b[i] == ) continue;
if(flag)
{
if(dx)
{
ans.push_back(xx(a[i],x));
dx--;
}
else
{
ans.push_back(xx(b[i],y));
dy--;
}
}
else
{
flag = ;
ans.push_back(xx(a[i],x));
dx--;
ans.push_back(xx(b[i],y));
dy--;
}
}
}
cout << "Yes" << endl;
for(int i = ;i < ans.size();i++) cout << ans[i].x << " " << ans[i].y << endl;
return ;
}
