Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)（B-D）

B Swap and Reverse

有点小妙哈哈哈
注意到 奇数位置和偶数位置的性质
就是说，对于swap操作，奇数位置的顺序永远可以直接排成最小序，同理偶数位置也可以排成最小序。
那么看reverse，就注意到奇数长度的reverse 后奇数

Code

Talk is cheap.Show me the Code.

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int n, k;
char sa[N], sb[N];
void solve() {
	string s;
	cin >> n >> k >> s;
	if(k%2 == 0) {
		sort(s.begin(), s.begin()+n);
	} else {
		for(int i=0;i<n;++i) {
			if(i%2 == 1) {
				sa[i/2] = s[i];
			} else {
				sb[i/2] = s[i];
			}
		}
		//cout << "test : " << sa << ", " << sb << endl;
		int la = n/2;
		int lb = n/2 + (n%2==1);
		sort(sa, sa+la);
		sort(sb, sb+lb);
		for(int i=0;i<n;++i) {
			if(i%2 == 1) {
				s[i] = sa[i/2];
			} else {
				s[i] = sb[i/2];
			}
		}
	}
	cout << s << endl;
}
int main()
{
	int T;
	cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}

C Divisor Chain

---看题解学的---
主要是注意到一个数的lowerbit一定是他的因数，例如：

/*
a = 10011011000
b = 00000001000
b 一定是 a 的因数
*/

用位运算很好看出来。之后就很好做了

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
int k;
int lowerbit(int x) {
	return x & -x;
}
void solve() {
	cin >> k;
	vector<int> ans;
	while(k - lowerbit(k) != 0) {
		ans.push_back(k);
		k -= lowerbit(k);
	}
	while(k > 0) {
		ans.push_back(k);
		//printf("%d ",k);
		k /= 2;
	}
	cout << ans.size() << endl;
	for(int i=0;i<ans.size();++i) {
		cout << ans[i] << " ";
	}
	cout << endl;
	return ;
}
int main()
{
	int T;
	cin >> T;
	while(T--) {
		solve();
	}
}

D Matrix Cascade

先读懂这个操作在做什么，例如，我点击 (1,3)，翻转操作的传播形式就是如下‘#’表示的（‘*’ 表示其他部分）

/*
****#****
***###***
**#####**
*#######*
*/

对，他是一个像金字塔型的传播。这个题之所以能做是因为这个传播形式有递归属性（我的理解是可复制）
做法：对于这样一个标记，向左右传播，并且向下传播（向下传播的时候带一个向左右传播的种子）。
因为下一行对前面这一行是没有影响的，所以从上到下依次处理就好了。

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3+7;
int n;
bool a[N][N];
bool fl[N][N][3];
void solve() {
	//memset(a, 0, sizeof(a));
	//memset(fl, 0, sizeof(fl));
	cin >> n;
	for(int i=1;i<=n;++i) {
		string s;
		cin >> s;
		for(int j=0;j<s.length();++j) {
			if(s[j] == '1') a[i][j+1] = 1;
			else a[i][j+1] = 0;
			memset(fl[i][j+1], 0, sizeof(fl[i][j+1]));
		}
	}
	//printf("-test: %d\n",a[2][3]);
	int ans = 0;
	for(int i=1;i<=n;++i) {
		fl[i][1][0] ^= fl[i-1][2][0];
		for(int j=2;j<n;++j) {
			fl[i][j][0] ^= fl[i-1][j+1][0];
			fl[i][j][1] ^= fl[i-1][j-1][1];
			//if(i==2 && j==2) printf("www %d\n",fl[i][j][0]);
		}
		fl[i][n][1] ^= fl[i-1][n-1][1];
		
		for(int j=1;j<=n;++j) {
			fl[i][j][2] ^= fl[i-1][j][2];
			if(fl[i][j][2] == 1) {
				//printf("if %d %d\n",i,j);
				fl[i][j][0] ^= 1;
				fl[i][j][1] ^= 1;
			}
			a[i][j] = a[i][j] ^ fl[i][j][0] ^ fl[i][j][1] ^ fl[i][j][2];
			if(a[i][j] == 1) {
				//printf("test: %d,%d; %d %d %d  \n",i,j, fl[i][j][0], fl[i][j][1], fl[i][j][2]);
				++ans;
				fl[i][j][0] ^= 1;
				fl[i][j][1] ^= 1;
				fl[i][j][2] ^= 1;
			}
		}
	}
	cout << ans << endl;
}
int main()
{
	int T;
	cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}