CF-956(A-D)

期末以来第一场CF (っ °Д °;)っ

Problem - A - Codeforces

1~n的升序排列就满足条件

void solve(){
	int n;cin>>n;
	rep(i,1,n) cout<<i<<" ";
	cout<<endl;
}

Problem - B - Codeforces

两种操作：

+1 +2	+2 +1
+2 +1	+1 +2

在模3的情况下显然都一定不会改变每一行或每一列的和，由此可判断

const int N=505,M=2e5+5;
int a[N][N],b[N][N],sum[N*N+1];
void solve(){
	int n,m;cin>>n>>m;
	char x;
	rep(i,1,n) sum[i]=0;
	rep(j,1,m) sum[1+j*N]=0;
	rep(i,1,n){
		rep(j,1,m){
			cin>>x;
			a[i][j]=(x-'0');
			sum[i]=(sum[i]+a[i][j])%3;
			sum[1+j*N]=(sum[1+j*N]+a[i][j])%3;
		}
	}
	int res=0,f=1;
	rep(i,1,n){
		res=0;
		rep(j,1,m){
			cin>>x;
			b[i][j]=x-'0';
			res=(res+b[i][j])%3;
		}
		if(res!=sum[i]) f=0;
	}
	rep(j,1,m){
		res=0;
		rep(i,1,n){
			res=(res+b[i][j])%3;
		}
		if(res!=sum[1+j*N]){
			f=0;
			break;
		}
	}
	if(f) cout<<"YES";
	else cout<<"NO";
	cout<<endl;
}

Problem - C - Codeforces

要在三个数组中找到三个不重叠的连续区域，每个区域之和都要>=(sum+2)/3。我们可以暴力枚举第一部分的分界点，因为未知三个数组哪个取第一部分，哪个取中间部分，哪个取最后部分，所以要考虑六种情况

void solve(){
	int n;cin>>n;
	vector<int>a(n+1),b(n+1),c(n+1);
	int x;
	rep(i,1,n){
		cin>>x;
		a[i]=a[i-1]+x;
	}
	rep(i,1,n){
		cin>>x;
		b[i]=b[i-1]+x;
	}
	rep(i,1,n){
		cin>>x;
		c[i]=c[i-1]+x;
	}
	int sum=(c[n]+2)/3;
	int j=1;
	rep(i,1,n){
		while(b[j]-b[i]<sum&&j<n) j++;
		if(a[i]>=sum&&c[n]-c[j]>=sum){
			cout<<"1 "<<i<<" "<<i+1<<" "<<j<<" "<<j+1<<" "<<n<<endl;
			return;
		}
	}	
	j=1;	
	rep(i,1,n){
		while(c[j]-c[i]<sum&&j<n) j++;
		if(a[i]>=sum&&b[n]-b[j]>=sum){
			cout<<"1 "<<i<<" "<<j+1<<" "<<n<<" "<<i+1<<" "<<j<<endl;
			return;
		}
	}
	j=1;
	rep(i,1,n){
		while(a[j]-a[i]<sum&&j<n) j++;
		if(b[i]>=sum&&c[n]-c[j]>=sum){
			cout<<i+1<<" "<<j<<" "<<"1 "<<i<<" "<<j+1<<" "<<n<<endl;
			return;
		}
	}
	j=1;
	rep(i,1,n){
		while(c[j]-c[i]<sum&&j<n) j++;
		if(b[i]>=sum&&a[n]-a[j]>=sum){
			cout<<j+1<<" "<<n<<" 1 "<<i<<" "<<i+1<<" "<<j<<endl;
			return;
		}
	}
	j=1;
	rep(i,1,n){
		while(a[j]-a[i]<sum&&j<n) j++;
		if(c[i]>=sum&&b[n]-b[j]>=sum){
			cout<<i+1<<" "<<j<<" "<<j+1<<" "<<n<<" 1 "<<i<<endl;
			return;
		}
	}
	j=1;
	rep(i,1,n){
		while(b[j]-b[i]<sum&&j<n) j++;
		if(c[i]>=sum&&a[n]-a[j]>=sum){
			cout<<j+1<<" "<<n<<" "<<i+1<<" "<<j<<" 1 "<<i<<endl;
			return;
		}
	}
	cout<<"-1"<<endl;
}

Problem - D - Codeforces

思路

因为等距交换，所以可以都进行相邻交换，这样如果两数组操作数相差为偶数并且两数组元素都相同才是合法的

操作

处理操作数：相邻排序的话就是冒泡排序，也就是求冒泡排序的交换次数，而它就等于序列中的逆序对个数，可以用树状数组求得，又序列中会有重复元素，所以可以按权值降序、权值相同的按位置逆序排序，用树状数组点修区查求得

树状数组求逆序对个数还可以直接顺序的点修区查求，对当前数x，对树上x点加1，它对逆序对个数的贡献是[x+1,n]的和，不过这种方法当x的值域很大时需要离散化处理

判断两数组元素是否都相同：排序判断

代码

const int N=2e5+5;
int s[N],n;
struct node{
	int v,p;
}a[N],b[N];
bool cmp(node a,node b){
	if(a.v==b.v) return a.p>b.p;
	else return a.v>b.v;
}
int lowbit(int x){
	return x&-x;
}
void change(int x,int k){
	while(x<=n){
		s[x]+=k;
		x+=lowbit(x);
	}
}
int query(int x){
	int res=0;
	while(x){
		res+=s[x];
		x-=lowbit(x);
	}
	return res;
}
void solve() {
	cin>>n;
	rep(i,1,n){
		cin>>a[i].v;
		a[i].p=i;
		s[i]=0;
	}
	rep(i,1,n){
		cin>>b[i].v;
		b[i].p=i;
	}
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp);
	rep(i,1,n){
		if(a[i].v!=b[i].v){
			cout<<"NO\n";
			return;
		}
	}
	int cnta=0,cntb=0;
	rep(i,1,n){
		cnta+=query(a[i].p);
		change(a[i].p,1);
	}
	rep(i,1,n) s[i]=0;
	rep(i,1,n){
		cntb+=query(b[i].p);
		change(b[i].p,1);
	}
	if((cnta-cntb)%2==0) cout<<"YES";
	else cout<<"NO";
	cout<<endl;
}