发布时间：2023-09-18

CF1864

A. Increasing and Decreasing

建一个数组， $a_1=x,a_n=y ,b_i=a_{i+1}-a_i$ ，a单调递增，b单调递减。
思路：
从后往前枚举每次减1，2，3,... 若 $a_1<x$ ,输出-1，否则输出数组

void solve(){
	int x,y,n;
	cin>>x>>y>>n;
	vector<int> ans;
	int last=y;
	for(int i=1;i<=n;i++){
		ans.push_back(last);
		last-=i;
	}
	if(ans[n-1]>=x){
		cout<<x<<" ";
		for(int i=n-2;i>=0;i--)cout<<ans[i]<<" ";
		cout<<"\n";
	}
	else cout<<"-1\n";
}

B. Swap and Reverse

题意：
给定长度为n的字符串s和整数k，可以进行以下两种操作：

• $swap(a_i,a_{i+2})$
• $reverse [i,i+k-1]$

求能得到的最小字典序 思路： 对于1操作，奇数可以互换，偶数可以互换， $[1,0,1,0,1,0,...]$
对于2操作，若k为奇数，可以发现中间数不变，左右两边互换，由于1，0一一对应交换后不改变能交换的位置，近似等于1操作，对奇偶分别排序输出
若k为偶数，$\to [i,i+k-1] \to [i+1,i+k]$ ,可以交换0和1位置，此时可以全排序输出

int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<char> odd, even;
for (int i = 0; i < n; ++i) {
    if (i % 2 == 0) {
        even.pb(s[i]);
    } else {
        odd.pb(s[i]);
    }
}
sort(all(even));
sort(all(odd));
string ans1 = "";
for (int i = 0, j = 0; i < sz(even) || j < sz(odd); ++i, ++j) {
    if (i < sz(even)) {
        ans1 += even[i];
    }
    if (j < sz(odd)) {
        ans1 += odd[i];
    }
}
if (k % 2 == 0) {
    sort(all(s));
    cout << s << "\n";
    continue;
}
cout << ans1 << "\n";

C. Divisor Chain

题意：
给定一个x，每次减一个数，直至x=1
不能减一个数超过两次 思路：
易看出与 $2^x$ 有关，将x拆成 $x=2^y \cdot A ,A为奇数$，若 $A!=1$ ，每次将A变为偶数即 $A-=1$ 相当于 $x-=2^y$ ,再从A中分解2的个数加入y，最后变成 $x=2^y$此时每次减一半直至x=1即可，每个2的倍数恰好用了两次

void solve(){
	ll n,a=1;
	cin>>n;
	vector<ll> ans;
	ans.pb(n);
	while(n%2==0)n/=2,a*=2;
	while(n!=1){
		n-=1;
		ans.pb(n*a);
		while(n%2==0)n/=2,a*=2;
	}
	n*=a;
	while(n!=1){
		n/=2;
		ans.pb(n);
	}
	cout<<ans.size()<<"\n";
	for(auto it:ans)cout<<it<<" ";
	cout<<"\n";
}

D. Matrix Cascade

题意：
给定一个只包含0和1的n*m的矩阵，选择 $(i,j)且a_{i,j}=1 使a_{i,j}=0$,则接下来 $x-i>=|y-j|$的部分也会改变，问最小次数使全部变为0
思路：
改变一个点，两边斜45度包含的所有点也会改变，可以利用前缀和差分，但要注意的是不能只用一个数组(因为如果抵消1和-1抵消了就无法继续往下传递1和-1了，会影响后面的值),用pre维护往左边传递的值即加1，suf维护减1，每次求出sum后，pre的值全部往左移一位，suf往右移一位；有如下两种情况需要传递新的值：

• $a_{i,j}=0且sum_j为偶数$
• $a_{i,j}=1且sum_j为奇数$

void solve(){
	int n;
	cin>>n;
	ll ans=0;
	for(int i=1;i<=n;i++)cin>>a[i]+1;
	vector<ll> pre(n+1),suf(n+1);
	for(int i=1;i<=n;i++){
		if(i==1){
			for(int j=1;j<=n;j++){
				if(a[i][j]=='1'){
					ans++;
					if(j>1)pre[j-1]++;
					else pre[j]++;
					if(j<n-1)suf[j+2]++;
				}
			}
		}
		else{
			vector<ll> sum(n+1);
			for(int j=1;j<=n;j++){
				sum[j]=sum[j-1];
				if(pre[j])sum[j]+=pre[j];
				if(suf[j])sum[j]-=suf[j];
			}
			for(int j=1;j<=n;j++){
				if(pre[j]&&j>1)pre[j-1]+=pre[j],pre[j]=0;
			}
			for(int j=n;j>=1;j--){
				if(suf[j]){
					if(j<n)suf[j+1]+=suf[j],suf[j]=0;
					else suf[j]=0;
				}
			}
			for(int j=1;j<=n;j++){
				if((a[i][j]=='1'&&sum[j]%2==0)||(a[i][j]=='0'&&sum[j]%2==1)){
					ans++;
					if(j>1)pre[j-1]++;
					else pre[j]++;
					if(j<n-1)suf[j+2]++;
				}
			}
		}
	}
	cout<<ans<<'\n';
}