社区讨论
建议加强数据
P1360[USACO07MAR] Gold Balanced Lineup G参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m39nlozi
- 此快照首次捕获于
- 2024/11/09 12:16 去年
- 此快照最后确认于
- 2025/11/04 15:04 4 个月前
RT,在此题数据下 算法可以通过
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 条回复,欢迎继续交流。
正在加载回复...