社区讨论

建议加强数据

P1360[USACO07MAR] Gold Balanced Lineup G参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m39nlozi
此快照首次捕获于
2024/11/09 12:16
去年
此快照最后确认于
2025/11/04 15:04
4 个月前
查看原帖
RT,在此题数据下 O(n2)O(n^2) 算法可以通过
CPP
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
struct dy;

int n, m, h[MAXN], prexor[MAXN], lisa[MAXN], tot = 0, mm, mac[MAXN];
vector<dy*> v[MAXN];

struct dy {
	int s[31];
	dy &operator+=(const dy &a) {
		for (int i = 0; i < 30; i++) s[i] += a.s[i];
		return *this;
	}
	dy operator-(const dy &a) const {
		dy ret = *this;
		for (int i = 0; i < 30; i++) ret.s[i] -= a.s[i];
		return ret;
	}
	bool operator()() const {
		bool ret = true;
		for (int i = 0; i < m - 1; i++) {
			if (s[i] != s[i + 1]) ret = false;
		}
		return ret;
	}
} dys[MAXN];

void handle(int x, int v) {
	for (int i = 0; i < m; i++) if (v >> i & 1) dys[x].s[i]++;
	dys[x] += dys[x - 1];
}

int main() {
	int ans = 0;
	scanf("%d%d", &n, &m);
	mm = (1 << m) - 1;
	for (int i = 1; i <= n; i++) scanf("%d", h + i), handle(i, h[i]), ans = h[i] == mm || h[i] == 0, lisa[++tot] = prexor[i] = prexor[i - 1] ^ h[i], lisa[++tot] = mm ^ prexor[i];
	lisa[++tot] = 0;
	sort(lisa + 1, lisa + tot + 1);
	for (int i = 1; i <= n; i++)  mac[i] = lower_bound(lisa + 1, lisa + tot + 1, mm ^ prexor[i]) - lisa, prexor[i] = lower_bound(lisa + 1, lisa + tot + 1, prexor[i]) - lisa;
	for (int i = 1; i <= n; i++) v[prexor[i]].push_back(dys + i);
	v[1].push_back(dys);
	for (int i = 1; i <= n; i++) {
		for (auto t : v[mac[i]]) {
			if (t < dys + i && (dys[i] - *t)()) {
				ans = max((long)ans, (long)(dys + i - t));
			}
		}
		for (auto t : v[prexor[i]]) {
			if (t < dys + i && (dys[i] - *t)()) {
				ans = max((long)ans, (long)(dys + i - t));
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...