关于 NOIP T1
查看原帖
关于 NOIP T1
760266
xvl_楼主2024/12/1 12:12

我在民间数据 AC 的代码是这样的:

#include <bits/stdc++.h>

const long long IMX = 1ll << 30;
const long long LMX = 1ll << 60;

const long long MOD1 = 998244353;
const long long MOD2 = 1000000007;
const long long MOD3 = 1000000009;

using ll = long long;
using i128 = __int128;
using ld = long double;
using f128 = __float128;

namespace xvl_ { 
	#define SP(n, x) std :: setprecision(n) << std :: fixed << x
	#define DEBUG(x) std :: cerr << #x << " = " << x << '\n'
	#define SZ(x) (x.size())
	#define fst first
	#define snd second
	template <typename T> T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
	template <typename T> T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;
const int N = 100005;
int T, n, ans;
int s1[N], s2[N];
void work1(int l, int r) {
	if (l > r) return ;
	int c0 = 0, c1 = 0;
	for (int i = l; i <= r; i++) c0 += !s1[i], c1 += s1[i];
	for (int i = l; i <= r; i++) {
		if (s2[i] == 0) {
			if (c0) c0--, s1[i] = 0;
			else c1--, s1[i] = 1;
		}
		else {
			if (c1) c1--, s1[i] = 1;
			else c0--, s1[i] = 0;
		}
	}
}
void work2(int l, int r) {
	if (l > r) return ;
	int c0 = 0, c1 = 0;
	for (int i = l; i <= r; i++) c0 += !s2[i], c1 += s2[i];
	for (int i = l; i <= r; i++) {
		if (s1[i] == 0) {
			if (c0) c0--, s2[i] = 0;
			else c1--, s2[i] = 1;
		}
		else {
			if (c1) c1--, s2[i] = 1;
			else c0--, s2[i] = 0;
		}
	}
}
void work3(int l, int r) {
	if (l > r) return ;
	int c1 = 0, c2 = 0;
	for (int i = l; i <= r; i++) c1 += !s1[i], c2 += !s2[i];
	for (int i = l; i <= r; i++) {
		if (c1) c1--, s1[i] = 0;
		else s1[i] = 1;
		if (c2) c2--, s2[i] = 0;
		else s2[i] = 1;
	}
}
int main() {
	// freopen("edit.in", "r", stdin);
	// freopen("edit.out", "w", stdout);
	ios :: sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> T;
	while (T--) {
		ans = 0;
		int len1 = 0, len2 = 0, len3 = 0;
		string tmp1, tmp2, t1, t2;
		cin >> n >> tmp1 >> tmp2 >> t1 >> t2;
		for (int i = 0; i < n; i++) s1[i + 1] = tmp1[i] - '0', s2[i + 1] = tmp2[i] - '0';
		t1 = ' ' + t1, t2 = ' ' + t2;
		for (int i = 1; i <= n; i++) {
			if (t1[i] == '1') len1++;
			else {
				if (len1) {
					work1(i - len1, i - 1);
					len1 = 0;
				}
			}
		}
		if (len1) {
			work1(n - len1 + 1, n);
			len1 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t2[i] == '1') len2++;
			else {
				if (len2) {
					work2(i - len2, i - 1);
					len2 = 0;
				}
			}
		}
		if (len2) {
			work2(n - len2 + 1, n);
			len2 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t1[i] == '1' and t2[i] == '1') len3++;
			else {
				if (len3) {
					work3(i - len3, i - 1);
					len3 = 0;
				}
			}
		}
		if (len3) {
			work3(n - len3+ 1, n);
			len3 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t1[i] == '1') len1++;
			else {
				if (len1) {
					work1(i - len1, i - 1);
					len1 = 0;
				}
			}
		}
		if (len1) {
			work1(n - len1 + 1, n);
			len1 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t2[i] == '1') len2++;
			else {
				if (len2) {
					work2(i - len2, i - 1);
					len2 = 0;
				}
			}
		}
		if (len2) {
			work2(n - len2 + 1, n);
			len2 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t1[i] == '1' and t2[i] == '1') len3++;
			else {
				if (len3) {
					work3(i - len3, i - 1);
					len3 = 0;
				}
			}
		}
		if (len3) {
			work3(n - len3+ 1, n);
			len3 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t1[i] == '1') len1++;
			else {
				if (len1) {
					work1(i - len1, i - 1);
					len1 = 0;
				}
			}
		}
		if (len1) {
			work1(n - len1 + 1, n);
			len1 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t2[i] == '1') len2++;
			else {
				if (len2) {
					work2(i - len2, i - 1);
					len2 = 0;
				}
			}
		}
		if (len2) {
			work2(n - len2 + 1, n);
			len2 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t1[i] == '1' and t2[i] == '1') len3++;
			else {
				if (len3) {
					work3(i - len3, i - 1);
					len3 = 0;
				}
			}
		}
		if (len3) {
			work3(n - len3+ 1, n);
			len3 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t1[i] == '1') len1++;
			else {
				if (len1) {
					work1(i - len1, i - 1);
					len1 = 0;
				}
			}
		}
		if (len1) {
			work1(n - len1 + 1, n);
			len1 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t2[i] == '1') len2++;
			else {
				if (len2) {
					work2(i - len2, i - 1);
					len2 = 0;
				}
			}
		}
		if (len2) {
			work2(n - len2 + 1, n);
			len2 = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (t1[i] == '1' and t2[i] == '1') len3++;
			else {
				if (len3) {
					work3(i - len3, i - 1);
					len3 = 0;
				}
			}
		}
		if (len3) {
			work3(n - len3+ 1, n);
			len3 = 0;
		}
		for (int i = 1; i <= n; i++) ans += (s1[i] == s2[i]);
		cout << ans << '\n';
	}
	return 0;
}

我的代码中 83~121 行这一段代码我复制了 44 遍!

而如果不复制 44 遍会发生以下的事情:

  • 11 遍:80pts
  • 22 遍:90pts
  • 33 遍:95pts
  • 44 遍:100pts

考场上写的 22 遍。

2024/12/1 12:12
加载中...