Codeforces Global Round 15
A - Subsequence Permutation
思路:找出原串与排序后的串不同的个数
#include <bits/stdc++.h> using namespace std; void solve(){ int n;cin>>n; string s;cin>>s; string t=s; sort(t.begin(),t.end()); int ans=0; for(int i=0;i<n;++i){ ans+=(t[i]!=s[i]); } cout<<ans<<'\n'; } int main() { ios::sync_with_stdio(0), cin.tie(0); int T; cin>>T; while(T--){ solve(); } return 0; }
B - Running for Gold
思路:要找出一个人比所有人都好,依次比较所有人,找出一个最好的,再检查此人是否比其他人都好
#include <bits/stdc++.h> using namespace std; #define int long long void solve() { int n; cin >> n; vector a(n, vector<int>(5)); for (auto &i: a) for (auto &j: i) cin >> j; int t = 0; for (int i = 1, f; i < n; i++) { f = 0; for (int j = 0; j < 5; j++) f += (a[i][j] < a[t][j]); if (f >= 3) t = i; } int cnt = 0; for (int i = 0, f; i < n; i++) { if (i == t) continue; f = 0; for (int j = 0; j < 5; j++) f += (a[i][j] > a[t][j]); if (f >= 3) cnt++; else break; } if (cnt == n - 1) cout << t+1 << "\n"; else cout << "-1\n"; return; } int32_t main() { ios::sync_with_stdio(0), cin.tie(0); int t; cin >> t; while (t--) solve(); return 0; }
C - Maximize the Intersections
思路:对于初始没有弦的2n个点,可知连接1——1+n,2——2+n,...,n——n+n后的交点最多(弦的两边点的数量相同,弦与弦的较点更多);
那么忽略已定的点,剩余的点一定有偶数个,为1~2(n-k),连接1——1+n-k,2——2+n-k,...,n-k——2(n-k)后的图即为最优情况;
枚举所有两条边的情况,分别为x1、y1,x2、y2,当x1<x2时,满足x2<y1和y1<y2即满足两条边相交
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=200+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; vector<PII>g; vector<int>st,f; void solve(){ g.clear(); f.clear(); st=vector<int>(N,0); int n,k;cin>>n>>k; for(int i=0,u,v;i<k;++i){ cin>>u>>v; if(u>v)swap(u,v); g.push_back({u,v}); st[u]=st[v]=1; } for(int i=1;i<=2*n;++i){ if(!st[i])f.push_back(i); } for(int i=0;i<n-k;++i){ g.push_back({f[i],f[i+n-k]}); } int ans=0; auto check=[](PII x,PII y){ if(x.first>y.first)swap(x,y); return x.second<y.second&&y.first<x.second; }; for(int i=0;i<n-1;++i) for(int j=i+1;j<n;++j){ ans+=check(g[i],g[j]); } cout<<ans<<'\n'; return; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
D - Array Differentiation
思路:要构造一个数组b,满足ai=bj-bk;设a1=b1-b2,那么a2=b2-b3,...,an-1=bn-1-bn,还有一个an没有得出;
假设an=bn-b1,那么可以将b看作点,a看作边权,要得到所有的a,说明要有环,且有环的情况下:a1+a2+...+an=(b1-b2)+(b2-b3)+...+(bn-b1)=0;
由于边为有向边,且n<=10,可以用三进制表示出每条边的情况,判断是否有环;
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=200+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n,m=1;cin>>n; vector<int>a(n); for(auto &v:a)cin>>v,m*=3; for(int i=1;i<m;++i){ int now=i,sum=0; for(int j=0;j<n;++j){ if(now%3==1)sum+=a[j]; else if(now%3==2)sum-=a[j]; now/=3; } if(!sum){ cout<<"YES\n";return; } } cout<<"NO\n"; return; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
- Codeforces Global Round 15codeforces global round 15 codeforces guessing global round codeforces global round 16 codeforces global round 14 codeforces global round codeforces avoiding global round codeforces destroys universe global codeforces pegging global doremy codeforces perfect global doremy educational codeforces round rated