Codeforces Round 874 (Div. 3)
A - Musical Puzzle
思路：记录两个长度字符串的种数
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e6+5,INF=0x3f3f3f3f,Mod=998244353; const double eps=1e-6; typedef long long ll; //#define int long long int T,n; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>T; while(T--){ cin>>n; string s,a; cin>>s; int res=0; map<string,int>mp; for(int i=0;i<n-1;++i){ a=s[i]; a+=s[i+1]; //cout<<a<<'\n'; if(mp[a]==0){ res++; mp[a]++; } } cout<<res<<'\n'; } return 0; }
B - Restore the Weather
思路：将a，b排序，一一对应即可
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e5+5,INF=0x3f3f3f3f,Mod=998244353; const double eps=1e-6; typedef long long ll; //#define int long long int T,n,k; PII a[N],b[N]; int ans[N]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>T; while(T--){ cin>>n>>k; for(int i=1;i<=n;++i)cin>>a[i].first,a[i].second=i; for(int i=1;i<=n;++i)cin>>b[i].first,b[i].second=i; sort(a+1,a+n+1); sort(b+1,b+n+1); for(int i=1;i<=n;++i){ ans[a[i].second]=b[i].first; } for(int i=1;i<=n;++i)cout<<ans[i]<<' ';cout<<'\n'; } return 0; }
C - Vlad Building Beautiful Array
思路：偶-奇=奇，奇-奇=偶，将所有奇数排序，对于每个数判断是否能为偶数和奇数，最后判断所有数是否能同时为偶或奇
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=2e5+5,INF=0x3f3f3f3f,Mod=998244353; const double eps=1e-6; typedef long long ll; //#define int long long int T,n; int ji[N],a[N]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>T; while(T--){ cin>>n; int aji=0; for(int i=0;i<n;++i){ cin>>a[i]; if(a[i]%2)ji[aji++]=a[i]; } sort(ji,ji+aji); vector<PII>ans(n,{0,0}); for(int i=0;i<n;++i){ int p= lower_bound(ji,ji+aji,a[i])-ji; if(a[i]%2){ ans[i].first=1; if(p>0)ans[i].second=1; } else { ans[i].second=1; if(p>0)ans[i].first=1; } } bool ok1=true,ok2=true; for(int i=0;i<n;++i){ if(ans[i].first==0)ok1=false; if(ans[i].second==0)ok2=false; if(!ok1&&!ok2)break; } if(ok1||ok2)cout<<"YES\n"; else cout<<"NO\n"; } return 0; }
D - Flipper
思路：要让序列字典序尽可能大，那么要让最大的数在前。先确立r的位置，找到除第一个数以外的最大的数，若该数不在最右侧，以该数的上一个位置为r；若该数在最右侧，有两种情况：r在最右侧和在该数上一个位置，取两种序列中最大的情况。再从r向左开始遍历，l为满足a[l]>a[1]的边界。找到了l和r，直接对原序列处理即可
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=2e3+5,INF=0x3f3f3f3f,Mod=998244353; const double eps=1e-6; typedef long long ll; //#define int long long int T,n,a[N]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>T; while(T--){ cin>>n; int ma=0,p; for(int i=1;i<=n;++i){ cin>>a[i]; if(i>1&&a[i]>ma){ ma=a[i];p=i; } } if(n==1)cout<<a[1]<<'\n'; else if(n==2)cout<<a[2]<<' '<<a[1]<<'\n'; else{ int l,r; vector<int>ans1(n+1,0),ans2(n+1,0); l=r=p-1; while(l-1>=1&&a[l-1]>a[1]){ l--; }//cout<<l<<' '<<r<<'\n'; int idx=0; for(int i=r+1;i<=n;++i)ans1[idx++]=a[i]; for(int i=r;i>=l;--i)ans1[idx++]=a[i]; for(int i=1;i<l;++i)ans1[idx++]=a[i]; //cout<<idx<<'\n'; if(p==n){ idx=0; l=r=n; while(l-1>=1&&a[l-1]>a[1])l--;//cout<<l<<' '<<r<<'\n'; for(int i=r+1;i<=n;++i)ans2[idx++]=a[i]; for(int i=r;i>=l;--i)ans2[idx++]=a[i]; for(int i=1;i<l;++i)ans2[idx++]=a[i]; //cout<<idx<<'\n'; ans1=max(ans1,ans2); } for(int i=0;i<n;++i)cout<<ans1[i]<<' ';cout<<'\n'; } } return 0; }
E - Round Dance
思路：求出环和链的个数，所有链可以组成一个。可以用并查集找到所有连通块，若为环，该连通块里所有点入度都不为0，否则为链。
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; //#define int long long int fa[N],in[N]; int find(int x){ if(fa[x]!=x)fa[x]=find(fa[x]); return fa[x]; } void solve(){ int n; cin>>n; for(int i=1;i<=n;++i){ fa[i]=i;in[i]=0; } for(int i=1,x;i<=n;++i){ cin>>x; in[x]++; int a=find(i),b=find(x); if(a!=b){ fa[a]=b; } } map<int,int>mp; for(int i=1;i<=n;++i){ int a=find(i); if(mp[a]!=-1)mp[a]++; if(!in[i])mp[a]=-1; } int a=0; for(auto v:mp){ if(v.second==2||v.second==-1)a++; } cout<<mp.size()-a+(a>0)<<' '<<mp.size()<<'\n'; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ solve(); } return 0; }
F - Ira and Flamenco
思路：选择m个不同的数，那么这m个数一定是连续的，对所有数排序去重并统计所有数的个数，维护所有满足条件的m个数
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; //#define int long long int n,m; ll ksm(ll a,ll b){ ll res=1; while(b){ if(b&1)res=res*a%Mod; a=a*a%Mod; b>>=1; } return res; } void solve(){ cin>>n>>m; vector<int>a(n); map<int,int>mp; for(int i=0;i<n;++i)cin>>a[i],mp[a[i]]++; sort(a.begin(),a.end()); a.erase(unique(a.begin(),a.end()),a.end()); if(m==1){ int ans=0; for(auto v:a)ans=(ans+mp[v])%Mod; cout<<ans<<'\n';return ; } int s=1,ans=0,b=mp[a[0]]; for(int i=1;i<a.size();++i){ if(a[i]==a[i-1]+1)s++,b=(b*mp[a[i]])%Mod; else s=1,b=mp[a[i]]; if(s==m){ ans=(ans+b)%Mod; s--; b=b*ksm(mp[a[i-m+1]],Mod-2)%Mod; } } cout<<ans<<'\n'; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
G - Ksyusha and Chinchilla
思路：通过切边形成都是三个节点的连通块，叶子节点只能与其父节点构成连通块，那么从叶子节点往上搜，求出以每个节点为根节点的子节点数（包括自己），为3时可删除连接该节点边，最后判断是否根节点被删完
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; //#define int long long void solve(){ int n; cin>>n; vector<vector<PII>>g(n+1); for(int i=1,u,v;i<n;++i){ cin>>u>>v; g[u].push_back({v,i}),g[v].push_back({u,i}); } vector<int>s(n+1),ans; bool ok=true; function<void(int,int,int)> dfs=[&](int u,int fa,int idx){ s[u]=1; for(auto [v,id]:g[u]){ if(v!=fa){ dfs(v,u,id); s[u]+=s[v]; } } if(s[u]>3){ ok=false;return ; } else if(s[u]==3){ s[u]=0; if(idx)ans.push_back(idx); } }; dfs(1,0,0); ok&=!s[1]; if(ok){ cout<<ans.size()<<'\n'; for(auto v:ans)cout<<v<<' '; cout<<'\n'; } else cout<<"-1\n"; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }