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

发现一个神奇的事情。

#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], t1[N], t2[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;
	}
}
void solve1() {
	int len = 0;
	for (int i = 1; i <= n; i++) {
		if (t1[i] == 1) len++;
		else {
			if (len) {
				work1(i - len, i - 1);
				len = 0;
			}
		}
	}
	if (len) {
		work1(n - len + 1, n);
		len = 0;
	}
}
void solve2() {
	int len = 0;
	for (int i = 1; i <= n; i++) {
		if (t2[i] == 1) len++;
		else {
			if (len) {
				work2(i - len, i - 1);
				len = 0;
			}
		}
	}
	if (len) {
		work2(n - len + 1, n);
		len = 0;
	}
}
void solve3() {
	int len = 0;
	for (int i = 1; i <= n; i++) {
		if (t1[i] == 1 and t2[i] == 1) len++;
		else {
			if (len) {
				work3(i - len, i - 1);
				len = 0;
			}
		}
	}
	if (len) {
		work3(n - len + 1, n);
		len = 0;
	}
}
void solve() {
	solve1();
	solve2();
	solve3();
}
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;
		string tmp1, tmp2, tmp3, tmp4;
		cin >> n >> tmp1 >> tmp2 >> tmp3 >> tmp4;
		for (int i = 0; i < n; i++) {
			s1[i + 1] = tmp1[i] - '0', s2[i + 1] = tmp2[i] - '0';
			t1[i + 1] = tmp3[i] - '0', t2[i + 1] = tmp4[i] - '0';
		}
		for (int i = 1; i <= 4; i++) solve();
		for (int i = 1; i <= n; i++) ans += (s1[i] == s2[i]);
		cout << ans << '\n';
	}
	return 0;
}

以上是我的民间数据 AC Code。 但如果将的 137 行 solve() 的执行次数进行更改会发生这样的事情:

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

考场上写的是 22 次,是不是药丸了。

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