Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

A.给定n*m的矩阵a，构造一个同样大小的矩阵b使得[1,n*m]都出现一次，且b和a在任意位置上都不相等。

特判完无解后循环移位即可。

#include<bits/stdc++.h>
using namespace std;
int a[12][12];
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	if(n==1&&m==1){
		cout<<-1<<"\n";
		return;
	}
	if(n==1){
		for(int i=1;i<m;i++) cout<<a[1][i+1]<<" ";
		cout<<a[1][1]<<"\n";
		return;
	}
	if(m==1){
		for(int i=1;i<n;i++) cout<<a[i+1][1]<<"\n";
		cout<<a[1][1]<<"\n";
		return;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++) cout<<a[i][j+1]<<" ";
		cout<<a[i][1]<<"\n";
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		//TODO
		solve();
	}
}

B.

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n;cin>>n;
	string s,t;cin>>s>>t;
	int cnt=0;
	for(int i=0;i<n;i++) cnt+=(s[i]==t[i]);
	if(cnt==n){
		cout<<"YES"<<"\n";return;
	}
	int prefix=-1;
	for(int i=0;i<n;i++){
		if(s[i]=='0'&&t[i]=='0') prefix=i;
		else break;
	}
	if(s[1+prefix]=='0'&&t[1+prefix]=='1') {
		cout<<"NO"<<"\n";
	}
	else cout<<"YES"<<"\n";
}
int main(){
	int t;cin>>t;
	while(t--){
		//TODO
		solve();
	}
}

C.

倒着dp+小二分

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N];
typedef long long ll;
ll sum[N],f[N];
void solve(){
	int k;ll n;
	cin>>n>>k;
	
	sum[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	
	sum[n+1]=0;
	f[n+1]=0;
	for(int i=n;i>=1;i--){
		if(a[i]>k){
			f[i]=f[i+1]+1;
		}
		else {
			int ans=-1;
			int l=i+1,r=n;
			while(l<=r){
				int mid=(l+r)>>1;
				if(sum[mid]-sum[i-1]>1ll*k){
					ans=mid;
					r=mid-1;
				}
				else l=mid+1;
			}
			if(ans!=-1) {
				f[i]=f[ans+1]+1;	
			}
			else f[i]=0;
		}
	}
	ll tot=n*(n-1)/2+n;
	for(int i=1;i<=n;i++) tot-=f[i];
	cout<<tot<<"\n";
}
int main(){
	int t;cin>>t;
	while(t--){
		//TODO
		solve();
	}
}

D.

考虑 |ai-aj| 能整除 x 其实就是在模x意义下同余，考虑到模数比较小，根据鸽笼原理肯定有两个点能连边。

又因为模数小的更容易满足，所以倒着从大开始做(从n-1开始)，比较好处理的小模数放后面。

对于n-1必然能找到两个点连边，设为(u,v)，接下来把u踢掉

问题转化成更小的子问题，从而一定有解。

#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int a[N+5];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int vis[N+5]={0};
    
    vector<pair<int,int>>ans;
    for(int i=n-1;i>=1;i--){
        
        vector<int>mo[i+1];
        for(int j=1;j<=n;j++){
            if(vis[j]) continue;
            mo[a[j]%i].push_back(j);
        }
        
        int flag=0;
        for(int j=0;j<i && (flag==0) ;j++){
            
            if(mo[j].size()>=2){
                vis[mo[j][0]]=1;
                ans.push_back({mo[j][0],mo[j][1]});
                flag=1;
            }
        }
    }
    cout<<"YES"<<"\n";
    for(int i=ans.size()-1;i>=0;i--){
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
}

E

比D简单的诈骗题，发现大小为sz的树可以通过删叶子得到[1,sz]内的任意数，所以不考虑树的形态

然后贪心+分类讨论

设当前or出来的最大值为ans，当前考虑的数为x

从大到小拆位后，若当前位上x为0，跳过；否则若ans=0，x就可以对该位产生贡献，ans | = 1<< j ；若ans = 1，说明该位的贡献都已经得到了，且x>=(1<<j)，就可以贪心地把x删成((1<<j)-1)使得后面的位都为1。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int a[N];
void solve(){
    int k;cin>>k;
    for(int i=1;i<=k;i++){
        cin>>a[i];
        int x;
        for(int j=1;j<a[i];j++) cin>>x;
    }
    sort(a+1,a+k+1);
    int ans=0;
    for(int i=1;i<=k;i++){
        for(int j=24;j>=0;j--){
            int b1=(ans>>j)&1,b2=(a[i]>>j)&1;
            if(b2==0) continue;
            if(b1==0) ans|=(1<<j);
            else {
                ans|=((1<<j)-1);
                break;
            }
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
}