CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
A - Jagged Swaps
思路：a2到an的数只要相邻为逆序都可以交换，只需要判断a1是否为1即可
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n;cin>>n; bool ok=true; for(int i=1;i<=n;++i){ int x; cin>>x; if(i==1&&x!=1)ok=false; } if(ok)cout<<"YES\n"; else cout<<"NO\n"; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
B - AB Flipping
思路：可以发现A的后为B时，该位置可以交换，后为A时，同理，说明只要A后的串中存在B，那么A到B之间都可以交换，那么答案为第一个A到最后一个B的距离。
#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=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n; string s; cin>>n>>s; int l=-1,r=-1; for(int i=0;i<n;++i){ if(s[i]=='A'&&l==-1)l=i; if(s[i]=='B')r=i; } int ans; if(l==-1||r==-1)ans=0; else ans=max(0ll,r-l); cout<<ans<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
C - Matching Arrays
思路：贪心，需要恰好k个ai满足ai>bi，其余需满足ai<=bi，那么即为k个最大的ai对应k个最小的bi（升序一一对应），剩下的同样升序一一对应，看最后的序列是否满足条件
#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 = 2e5 + 5, INF = 0x3f3f3f3f, Mod = 1e9 + 7, mod = 998244353; const double eps = 1e-6; void solve() { int n,x;cin>>n>>x; vector<PII>a(n),b(n); vector<int>c(n); for(int i=0;i<n;++i)cin>>a[i].first,a[i].second=b[i].second=i; for(int i=0;i<n;++i){ cin>>b[i].first; c[i]=b[i].first; } sort(a.begin(),a.end()),sort(b.begin(),b.end()); vector<int>ans(n); for(int j=0,i=n-x;j<x;++i,++j){ if(a[i].first<=b[j].first){cout<<"NO\n";return ;} ans[a[i].second]=b[j].second; } for(int j=x,i=0;j<n;++i,++j){ if(a[i].first>b[j].first){cout<<"NO\n";return; } ans[a[i].second]=b[j].second; } cout<<"YES\n"; for(int i=0;i<n;++i)cout<<c[ans[i]]<<' ';cout<<'\n'; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; cin >> T; // init(); while (T--) { solve(); } return 0; }
D - Ones and Twos
思路：由于数的取值为1和2，对于一个区间，区间和为x，有以下情况：
[2，...，2] [1，...，2] [2，...，1] ，可以通过删去一个2使区间和为x-2
[1，...，1]可以通过删去两个1使区间和为x-2
那么对于一个区间，区间和为x，可以构成小于x的所有与x同奇偶的数
那么求出为奇数或偶数的最大区间和，在序列中奇偶由1的个数决定；
若所有数的和与s同奇偶，最大区间和为所有数的和，那直接判断s是否不大于最大区间和
若不同奇偶，需要通过删1来转变，最少删一个1，（如果没有1即NO），那用set维护所有1的位置，选择将左区间修改为第一个1的位置+1，或将右区间修改为最后一个1的位置-1，取最大的区间和，同样的判断s是否不大于最大区间和
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n,q;cin>>n>>q; int cnt=0; set<int>se; vector<int>a(n+1); for(int i=1;i<=n;++i){ cin>>a[i]; if(a[i]==1)se.insert(i),cnt++; } for(int i=0,op;i<q;++i){ cin>>op; if(op==1){ int v,s; cin>>v; if(abs(v-cnt)&1){ if(cnt==0){cout<<"NO\n";continue;} s=max(2*(n-*se.begin())-(cnt-1),2*(*se.rbegin()-1)-(cnt-1)); }else{ s=2*n-cnt; } if(v<=s)cout<<"YES\n"; else cout<<"NO\n"; }else{ int j,v; cin>>j>>v; if(a[j]==1)se.erase(j),cnt--; a[j]=v; if(a[j]==1)se.insert(j),cnt++; } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
E - Permutation Sorting
思路：由于需要循环，则将位置映射到2n。对于每一个ai，若ai>i：需要ai-i次循环，若ai<i：需要n-i+ai次循环。
但是由于当ai=i时，ai将不在循环的队列里。可以发现当队列的数量减少时，循环的次数只会减少；
对于ai来说，减少的循环次数等于在ai找到位置之前完成找到位置的aj的个数，且j>ai。
那么问题可以为：区间（x，y）表示x需要到达y，循环y-x次，那么x的答案为y-x-（x，y）中包含的区间个数；
求区间个数就用树状数组，方法不唯一。
从小到大遍历x（也是遍历位置），在x的位置单点修改+1，并且标记目的地y；如果当前遍历到的位置被标记（说明有数到达x位置），这时统计区间和（from（x），x）即为包含的区间个数，同时在from（x）的位置单点修改-1
也可以选择对y位置单点修改，那么就要先修改所有的y位置为+1，还是从小到大遍历x，统计区间和（x，y）即为包含的区间个数，这里的x一定是大于统计到的区间的x'
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; int n; vector<int>c; int lowbit(int x){return x&-x;} void add(int x,int k){ while(x<=n){ c[x]+=k; x+=lowbit(x); } } int getsum(int x){ int ans=0; while(x>0){ ans+=c[x]; x-= lowbit(x); } return ans; } int query(int l,int r){ if(l<=r)return getsum(r)-getsum(l-1); else return getsum(n)-query(r,l-1); } void solve(){ cin>>n; c=vector<int>(n+1,0); vector<int>ve(n+1),vis(n+1,0),fro(n+1),ans(n+1); for(int i=1;i<=n;++i){ cin>>ve[i]; fro[ve[i]]=i; } for(int i=1;i<2*n;++i){ int now=(i-1)%n+1; if(vis[now]){ ans[now]=query(fro[now]+1,now)+1; add(fro[now],-1); vis[now]=0; } if(ve[now]!=now){ add(now,1); vis[ve[now]]=1; } } for(int i=1;i<=n;++i)cout<<ans[i]<<' '; cout<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }