【算法竞赛】相邻差值相等问题的前缀和解法

· · 算法·理论

这个问题名字是我自己口胡的。

其问题的大致模板是：题意可以转化或特殊设计前缀和变成求相邻两个位置之间连续“差值相等”的最长长度。

解法是根据前缀和的公式：\sum\limits^{r}_{i=l}a_i=s_r-s_{l-1}，得知若差值相等，则 s_r=s_{l-1}，然后用 hash 等数据结构记录某种差值状态最早、最晚出现的位置，相减即为答案。最后，对所有答案取最大值，就是最长长度。

例1.“非常男女”计划

我们可以对前缀和进行特殊设计，设男生为 1，女生为 -1。

那么，我们要找的区间 [l,r] 就会满足 sum[r]-sum[l-1]]=0，此时得到了 O(n^2) 暴力思路。

我们要记录最长的区间，实际上就是记录 sum[l-1] 和 sum[r] 最早、最晚出现的位置。

用桶记录一下即可，时间复杂度 O(n)。

注意：为了防止统计时出现负数导致RE，我们可以把每一次放入桶的sum[i]+n，这样就可以把负数转成正数。还有一些写代码时的细节。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;

int n;
int a[maxn], sum[maxn];
int tl[2 * maxn], tr[2 * maxn]; // 记录左边、右边的桶（别忘了开二倍空间，因为统计的是sum[i]+n）

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(a[i] == 0) sum[i] = sum[i - 1] - 1;
        if(a[i] == 1) sum[i] = sum[i - 1] + 1; // 前缀和
        if(tl[sum[i] + n] == 0){ // 记录第一次出现
            tl[sum[i] + n] = i;
        }
        tr[sum[i] + n] = i; // 因为i一定会越来越大，所以最后一次出现直接顺着记下来就行
    }
    tl[n] = 0; // 0第一次出现是在位置0（表示成0+n）
    int ans = 0;
    for(int i = 0; i <= 2 * n; i ++){
        ans = max(ans, tr[i] - tl[i]); // 此时看作区间是[ tl[i]+1,tr[i] ]
    }
    cout << ans << '\n';
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

例2.Gold Balanced Lineup G / 暗杀

可以看作 P1114“非常男女”计划 的升级版。

读懂题意后发现，我们要找到一段最长的序列，使得其相邻两个位置的差相同。

可以联想到前缀和，我们只要统计前面所有数的前缀和，然后看 当前前缀和-上一个前缀和的值 出现次数最多的长度即可。

（如果对于一组 l,r，s[l][i+1]-s[l][i]=s[r][i+1]-s[r][i]，即 s[l],s[r] 的差分数组相同，那么 a[l+1]~a[r] 就是一个合法的区间）

因为这个差值一定是全部相等的，我们可以用 map 记录下当前的差值状态第一次出现的位置，然后，之后每出现相同的差值状态，就用当前位置减去map记录的位置，得出中间的长度。

别忘了开 long long！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;

int n, m;
map<vector<ll>, int> vis; // 创新地使用vector+map来做桶
ll s[maxn][40];

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n;  i ++){
        int a; cin >> a;
        for(int j = 0; j < m; j ++){ // 提取出二进制的位数
            if(a >> j & 1) s[i][j] = s[i - 1][j] + 1;
            else s[i][j] = s[i - 1][j];
        }
    }

    vector <ll> now;
    for(int i = 1; i <= m - 1; i ++){ // 因为有可能1~n全相等，所以要加入全0的状态
        // 因为长度为k的数组只有k-1个差分值，所以这里放入k-1个数字即可
        now.push_back(0);
    }
    vis[now] = 0; // 当前时间是0

    int ans = 0;
    for(int i = 1; i <= n; i ++){
        now.clear(); // 先清空
        for(int j = 0; j < m - 1; j ++){
            now.push_back(s[i][j + 1] - s[i][j]); // 相邻两位的前缀和之差
        }
        if(vis.count(now)){ // 之前出现过，就统计答案
            ans = max(ans, i - vis[now]);
        }
        else{ // 否则记录第一次出现的位置
            vis[now] = i;
        }
    }
    cout << ans << '\n';
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}