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;
}
View Code
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;
}
View Code
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;
}
View Code
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;
}
View Code
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;
}
View Code
标签：typedef,Rated,int,double,long,ai,Prizes,Div,define From： https://www.cnblogs.com/bible-/p/17861798.html