Codeforces Round 908 (Div. 2) A-D

Secret Sport

观察到数据不大，直接摁住x和y枚举即可，方案合法当且仅当刚好打若干局，且赢最后一局的人是赢家

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;
    string s;cin>>s;
    
    // x
    int wina=0,winb=0;
    for(int i=1;i<=n;i++){
        
        int a=0,b=0;
        int cnta=0,cntb=0,last=-1;
        for(int j=0;j<n;j++){
            if(s[j]=='A') a++;
            else b++;
            if(a==i){
                cnta++;
                a=b=0;
                last=1;
            } 
            else if(b==i){
                cntb++;
                a=b=0;
                last=0;
            }
        }
        if(!a&&!b){
            if(cnta>cntb&&last==1) wina++;
            else if(cnta<cntb&&!last) winb++;
            //cout<<i<<" "<<wina<<" "<<winb<<endl;
            //cout<<cnta<<" "<<cntb<<endl;
        }
    }
    if(winb==0) cout<<"A"<<endl;
    else if(wina==0) cout<<"B"<<endl;
    else cout<<"?"<<endl;
}
int main(){
    //freopen("lys.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

Two Out of Three

显然可以构造对于某一个数x( x 出现次数>=2 ) ，第一个x对应填1，其余都填2

同理对于某一个数y( y 出现次数>=2 )，第一个y对应填1，其余都填3

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int book[205],a[205];
void solve(){
	int n;cin>>n;
	memset(book,0,sizeof book);
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		book[a[i]]++;
	}
	int cnt=0;
	int use[5];
	for(int i=1;i<=100;i++){
		if(book[i]>=2) {
			cnt++;
			if(cnt<=2) use[cnt]=i;
		}
	}
	if(cnt<2) {
		cout<<-1<<endl;
		return;
	}
	int ok1=0,ok2=0;
	for(int i=1;i<=n;i++){
		if(book[a[i]]>=2){
			if(a[i]==use[1]){
				if(!ok1) {
					cout<<1<<" ";
				    ok1=1;
				}
				else cout<<2<<" ";
			}
			else if(a[i]==use[2]){
				if(!ok2){
					cout<<1<<" ";
					ok2=1;
				}
				else cout<<3<<" ";
			}
			else cout<<1<<" ";
		}
		else cout<<1<<" ";
	}
	cout<<endl;
}
int main(){
//	freopen("lys.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

C - Anonymous Informant

考虑怎么rollback一个操作（很显然只要能rollback  k 次，就能得到对应的合法解）

对于某个不动点x ，左移x次后必然在最后一位，所以当前序列的上一次操作必然是来自最后一个

那思路就很清晰了，又可以推上上个，对k和n取个min，看能否做k次即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn];
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    
    int last=n-1;
    k=min(k,n);
    for(int i=1;i<=k;i++){
        if(a[last]>n) {
            cout<<"No"<<endl;
            return;
        }
        last=(last-a[last]+n)%n;
    }
    cout<<"Yes"<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

D - Neutral Tonality

观察一些性质：下界是LIS(a) ，上界是LIS(a)+1 

考虑上界什么时候取到（显然很好取到，把b排序完放在末尾即可）

问题转化成能否恒等于下界，相当于考虑m=1，插入每个bi能否不对LIS造成影响（显然如果能影响肯定是某一个有问题）

构造bi放在第一个x前面，使得 bi > a_x 即可

证明：显然前面的数都比bi大，不会构成长度为2的递增序列

对于后面的数，bi有可能作为小的数插入吗？没有，因为不如选a_x

证毕。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int  a[maxn],b[maxn],c[maxn];
void solve(){
	int n,m;cin>>n>>m;
	int mx=-1,mi=INT_MAX;
	for(int i=1;i<=n;i++) cin>>a[i],mx=max(mx,a[i]),mi=min(mi,a[i]);
	for(int i=1;i<=m;i++) cin>>b[i];
	
	sort(b+1,b+m+1);
	int l=1,r=m;
	vector<int>ans;
	for(;l<=n||r>=1; ){
		if(l>n) {
			ans.push_back(b[r]);
			r--;
		}
		else if(r<1){
			ans.push_back(a[l]);
			l++;
		}
		else {
			if(b[r]>=a[l]) {
				ans.push_back(b[r]);
				r--;
			}
			else ans.push_back(a[l]),l++;	
		}
	}
	
	for(auto x:ans) cout<<x<<" ";
	cout<<endl;
}
int main(){
	//freopen("lys.in","r",stdin);
	int t;cin>>t;
	while(t--){
		solve();
	}
}