Codeforces Round #956 (Div. 2) and ByteRace 2024

A题：Array Divisibility

思路：

大水题

code：

inline void solve() {
     int n; cin >> n;
     for (int i = 1; i <= n; i ++ ) {
     	cout << i << " \n"[i == n];
     }
	 return;
}

B题：Corner Twist 

思路：

模拟

任意一个矩形的修改，都可以下放到最小的2x2的小矩形，因此，我们只需在要修改的地方用2x2的小矩形修改即可。

code：

inline void solve() {
     int n, m; cin >> n >> m;
     vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));
     for (int i = 1; i <= n; i ++ ) {
     	for (int j = 1; j <= m; j ++ ) {
     		char c; cin >> c;
     		a[i][j] = c - '0';
     	}
     }
     for (int i = 1; i <= n; i ++ ) {
     	for (int j = 1; j <= m; j ++ ) {
     		char c; cin >> c;
     		b[i][j] = c - '0';
     	}
     }
     function<void(int&, int)> add = [&](int &x, int c) {
     	x = (x + c) % 3;
     };
     for (int i = 1; i <= n - 1; i ++ ) {
     	for (int j = 1; j <= m - 1; j ++ ) {
     		if (a[i][j] == b[i][j]) continue;
     		int d = (b[i][j] - a[i][j] + 3) % 3;
     		add(a[i][j], d), add(a[i + 1][j + 1], d);
     		add(a[i + 1][j], 3 - d), add(a[i][j + 1], 3 - d);
     	}
     }
     if (a == b) cout << "YES\n";
     else cout << "NO\n";
	 return;
}

C题：Have Your Cake and Eat It Too 

思路：

贪心+二分，只是情况变多了而已。

code：

inline void solve() {
     int n; cin >> n;
     vector<vector<ll>> a(3, vector<ll>(n + 1));
     for (int i = 0; i < 3; i ++ ) {
     	for (int j = 1; j <= n; j ++ ) {
     		cin >> a[i][j];
     		a[i][j] += a[i][j - 1];
     	}
     }
     ll nd = (a[0][n] + 2) / 3;
     int cur[3] = {0, 1, 2};
     bool ok = false;
     function<bool(vector<ll>, vector<ll>, vector<ll>)> check = [&](vector<ll> a, vector<ll> b, vector<ll> c) {
     	int l[3], r[3];
     	l[0] = 0, r[0] = n + 1;
     	while (l[0] + 1 != r[0]) {
     		int mid = l[0] + r[0] >> 1;
     		if (a[mid] < nd) l[0] = mid;
     		else r[0] = mid;
     	}
     	l[0] = 1;
     	if (r[0] >= n - 1) return false;
     	l[1] = r[0], r[1] = n + 1;
     	while (l[1] + 1 != r[1]) {
     		int mid = l[1] + r[1] >> 1;
     		if (b[mid] - b[r[0]] < nd) l[1] = mid;
     		else r[1] = mid;
     	}
     	l[1] = r[0] + 1;
     	if (r[1] >= n) return false;
     	l[2] = r[1], r[2] = n + 1;
     	while (l[2] + 1 != r[2]) {
     		int mid = l[2] + r[2] >> 1;
     		if (c[mid] - c[r[1]] < nd) l[2] = mid;
     		else r[2] = mid;
     	}
     	l[2] = r[1] + 1;
     	if (r[2] == n + 1) return false;
     	r[2] = n;
     	ok = true;
     	for (int i = 0; i < 3; i ++ ) {
     		for (int j = 0; j < 3; j ++ ) {
     			if (cur[j] == i) {
     				cout << l[j] << ' ' << r[j] << ' ';
     			}
     		}
     	}
     	cout << endl;
     	return true;
     };
     do {
     	if (check(a[cur[0]], a[cur[1]], a[cur[2]])) break;
     }while (next_permutation(cur, cur + 3));
     if (!ok) cout << -1 << endl;
	 return;
}