把每种特性的前缀出现次数都减去第一种特性，转成前缀差分状态；相同状态之间的最远距离就是答案。
OJ: luogu
题目 ID: P2843
难度:提高+/省选-
标签:前缀和哈希状态压缩差分思维
日期: 2026-06-20 22:42
题意
给出一个长度为 n 的序列，每个数是一个 k 位二进制数。
第 j 位为 1，表示这个人具有第 j 种特性；为 0 表示没有。
现在要找一个最长的连续区间，使得这段区间内 k 种特性出现的总次数全部相同。
输出这个最长区间的长度。
思路
先看最直观的小数据暴力：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
const int MAXK = 30;
int n, k;
int a[MAXN];
int pre[MAXN][MAXK + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
pre[i][j] = pre[i - 1][j];
}
for (int bit = 0; bit < k; bit++) {
if ((a[i] >> bit) & 1) {
pre[i][bit + 1]++;
}
}
}
int ans = 0;
// 直接枚举所有区间，检查这段区间内 k 种特性的出现次数是否完全相同。
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
int first_cnt = pre[r][1] - pre[l - 1][1];
bool ok = true;
for (int j = 2; j <= k; j++) {
int now_cnt = pre[r][j] - pre[l - 1][j];
if (now_cnt != first_cnt) {
ok = false;
break;
}
}
if (ok) {
ans = max(ans, r - l + 1);
}
}
}
cout << ans << '\n';
return 0;
}brute.cpp 先对每一种特性做前缀和，然后枚举所有区间 [l,r]，检查这段区间里 k 种特性的出现次数是否全部相等。
这个方法能帮助理解题意，但复杂度是 n = 10^5。
关键是把条件改写成前缀状态相等。
设 pre_t[i] 表示前 i 个人中，第 t 种特性一共出现了多少次。
如果区间 [l,r] 合法，那么：
pre_1[r] - pre_1[l-1]
= pre_2[r] - pre_2[l-1]
= ...
= pre_k[r] - pre_k[l-1]此时最自然的做法，是把所有特性都减去第一种特性，定义：
state(i) = (pre_2[i]-pre_1[i], pre_3[i]-pre_1[i], ..., pre_k[i]-pre_1[i])如果两个前缀位置 x < y 满足：
state(x) = state(y)那么对所有 t >= 2，都有：
pre_t[y] - pre_1[y] = pre_t[x] - pre_1[x]移项后得到：
pre_t[y] - pre_t[x] = pre_1[y] - pre_1[x]也就是说，区间 (x,y] 内每一种特性的出现次数都和第一种特性相同，因此这段区间就是合法区间。
于是原问题变成：
找两个相同的前缀状态，使它们之间的距离最大。
实现方式非常直接：
- 从左到右扫描每个人
- 更新每种特性的前缀出现次数
- 构造当前的差分状态
state(i) - 用哈希表记录这个状态第一次出现的位置
- 如果当前状态以前出现过，就用当前位置减去第一次出现位置更新答案
别忘了初始全 0 状态出现在位置 0，这样从开头开始的合法区间也能被统计进去。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXK = 30;
int n, k;
int a[MAXN];
int cnt[MAXK + 1];
struct State {
int d[MAXK];
bool operator==(const State &other) const {
for (int i = 0; i < MAXK; i++) {
if (d[i] != other.d[i]) {
return false;
}
}
return true;
}
};
struct StateHash {
size_t operator()(const State &s) const {
unsigned long long h = 1469598103934665603ULL;
for (int i = 0; i < MAXK; i++) {
unsigned long long x = static_cast<unsigned int>(s.d[i] + 100000);
h ^= x + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
}
return static_cast<size_t>(h);
}
};
// 根据当前前缀计数，构造“相对第 1 种特性的差分状态”。
State build_state() {
State s;
for (int i = 0; i < MAXK; i++) {
s.d[i] = 0;
}
for (int i = 2; i <= k; i++) {
s.d[i - 2] = cnt[i] - cnt[1];
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
unordered_map<State, int, StateHash> first_pos;
first_pos.reserve(n * 2 + 5);
State zero = build_state();
first_pos[zero] = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int bit = 0; bit < k; bit++) {
if ((a[i] >> bit) & 1) {
cnt[bit + 1]++;
}
}
State now = build_state();
unordered_map<State, int, StateHash>::iterator it = first_pos.find(now);
if (it == first_pos.end()) {
first_pos[now] = i;
} else {
ans = max(ans, i - it->second);
}
}
cout << ans << '\n';
return 0;
}复杂度
每扫描一个人：
- 需要枚举
k个二进制位更新前缀计数 - 再构造一次长度为
k-1的差分状态
所以总时间复杂度是：
空间复杂度主要来自哈希表中的状态：
总结
这题的关键不是去直接统计区间，而是把“区间内每种特性出现次数相等”改写成：
- 两个前缀位置的“相对第一种特性的差分状态”完全一样
一旦想到这一步，问题就从区间问题变成了“最长相同前缀状态距离”问题，做法会非常清楚。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
