偏差[清华复试机考THU20172C]

---

^^^ Notice:重在实现

preliminary:Acwing模板——regarding to KMP

这是笔者最开始学习的参考，挺不错的，强推！！！

题目背景

wangyurzee7 和 Yazid 是好朋友。

题目描述

wangyurzee7 是一个繁忙的工作者，他每天都要处理许多有趣、复杂的问题。但由于能力有限，他总会出各种各样的偏差，这让 Yazid 头疼不已。

有一天，wangyurzee7 收到了一个任务：他获得了一个长度为 $n$ 的序列 $A$（下标从 $1$ 开始），他需要选择这个序列中的一个长度为 $m$ 的连续子区间，然后把这段区间内的数按顺序写下来，得到序列 $B$。

这个任务非常简单，但 wangyurzee7 实在是太弱了，所以他在做的时候还是出了偏差。他有一个偏差值 $k$，当他在抄写得到序列 $B$ 的时候，他把 $B$ 中的每个元素都加上了 $k$（其中 $k$ 是一个整数）！

也就是说，假设原序列为 $A_1\cdots A_n$，wangyurzee7 取的子区间是 $[l,l+m-1]$，那么对于 $1\le i\le m$，都有 $B_i=A_{l+i-1}+k$。

Yazid 勃然大怒，他根本没想到这么简单的任务 wangyurzee7 都不能胜任。他把 wangyurzee7 狠狠地批判了一番。

当然啦，责任还是要由出偏差的人来承担。可是 wangyurzee7 并不记得他的偏差值 $k$。无奈之下，他只好退而求其次，提出了一些更模糊的问题：

1. 偏差值 $k$ 的取值有几种可能；
2. 偏差值绝对值 $|k|$ 的最小值是多少；
3. 他选择的子区间的左端点 $l$ 有几种取值可能；
4. 他选择的子区间的左端点 $l$ 最左可能是多少；
5. 他选择的子区间的左端点 $l$ 最右可能是多少。

输入格式

从标准输入读入数据。

本题包含多组测试数据。

第一行一个正整数 $T$ 表示数据组数。

对于每组测试数据：

• 第一行一个正整数 $n$，表示序列 $A$ 的长度。
• 第二行 $n$ 个用空格隔开的非负整数 $A_1\cdots A_n$，描述了序列 $A$。
• 第三行一个正整数 $m$，表示序列 $B$ 的长度。
• 第四行 $m$ 个用空格隔开的非负整数 $B_1\dots B_m$，描述了序列 $B$。

输出格式

输出到标准输出。

对于每组数据：

• 输出 $5$ 个用空格隔开的整数，依次表示 $5$ 个问题的答案。特别地，对于问题 $2,4,5$，如果无解，请输出 $0$ 作为答案。

输入数据 1

4  
5  
2 3 3 3 3  
2  
6 7  
10  
1 1 3 2 1 3 2 1 2 2  
3  
1 3 2  
5  
100 200 300 900 1000  
2  
800 900  
4  
2 3 3 3  
2  
1 233  

输出数据 1

1 4 1 1 1  
1 0 2 2 5  
3 100 3 1 4  
0 0 0 0 0  

子任务

• 对于 $30\%$ 的数据，保证 $n\le 100$，序列中元素的值不超过 $1000$。
• 对于另外 $20\%$ 的数据，保证 $n\le 1000$。
• 对于另外 $20\%$ 的数据，保证序列中元素的值不超过 $100$。
• 对于 $100\%$ 的数据，保证 $T\le 6$，$1\le m\le n\le 10^5$，序列中元素的值不超过 $10^9$。

---

问题分析

给定两个数组 a 和 b，要求找到所有满足 a 的子数组与 b 数组的差为常数的位置。具体来说，需要找到所有 i 使得存在常数 k 满足 a[i+j-1] + k = b[j] 对所有 j 成立。

解决思路

1. 转换问题：将原问题转化为寻找 a 的子数组与 b 数组的差分数组匹配的问题。这样可以将问题转化为字符串匹配问题。
2. 差分数组：计算 a 和 b 的差分数组 s 和 p，其中 s[i] = a[i+1] - a[i]，p[i] = b[i+1] - b[i]。
3. KMP算法：使用KMP算法在 s 中查找 p 的所有匹配位置。
4. 处理匹配位置：对于每个匹配位置，计算对应的常数 k，并统计这些 k 的唯一值和最小绝对值。
5. 特殊情况处理：当 b 的长度为1时，直接处理所有可能的 k。

注意事项

• 差分数组长度：差分数组的长度比原数组少1，因此在处理时需要调整索引。
• KMP的next数组：正确构造 next 数组是KMP算法的关键，确保匹配过程高效。
• 唯一值和最小绝对值：对找到的 k 值进行去重和排序，方便统计唯一值和最小绝对值。
• 边界条件：处理 b 长度为1的特殊情况，避免复杂的差分匹配。
• 输出格式：按照题目要求的格式输出结果，包括唯一 k 的数量、最小绝对值、匹配位置的数量、起始和结束位置。

代码实现

1. 输入处理：读取输入的数组 a 和 b。
2. 特殊情况处理：当 b 的长度为1时，直接计算所有可能的 k 并统计结果。
3. 差分数组构造：计算 a 和 b 的差分数组 s 和 p。
4. KMP算法：
   • 构造 next 数组。
   • 在 s 中搜索 p 的所有匹配位置。
5. 结果统计：对匹配位置计算 k，去重后统计唯一值和最小绝对值。
6. 输出结果：按照要求输出统计结果。

示例

假设输入：

1
5
1 3 5 7 9
3
2 4 6

差分数组：

• s = [2, 2, 2, 2]
• p = [2, 2]
  匹配位置为 i=1 和 i=2，对应的 k 值为 1 和 3。唯一 k 的数量为2，最小绝对值为1，匹配位置数量为2，起始和结束位置为1和3。

总结

通过将原问题转化为差分数组的匹配问题，并利用KMP算法高效解决，能够有效处理大规模数据。注意特殊情况的处理和结果的正确统计是确保算法鲁棒性的关键。

上代码:

###一定要自己手搓，看着答案写没意义的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m;
const ll N=1e5+5;
vector<ll> a(N),b(N);
vector<ll> s(N),p(N);
ll ne[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        cin>>m;
        for(int i=1;i<=m;i++) cin>>b[i];
        
        //单列特殊情况
        if(m==1){
            vector<ll> temp;
            for(int i=1;i<=n;i++){
                ll k=a[i]-b[1];
                temp.push_back(k);
            }
            sort(temp.begin(),temp.end());
            temp.erase(unique(temp.begin(),temp.end()),temp.end());
            ll k1=temp.size();
            ll k2=abs(temp[0]);
            for(auto item:temp){
                k2=min(k2,abs(item));
            }
            cout<<k1<<" "<<k2<<" "<<n<<" "<<1<<" "<<n<<endl;
            continue;
        }
        //构造差分数组
        for(int i=1;i<=n-1;i++){
            s[i]=a[i+1]-a[i];
        }
        for(int i=1;i<=m-1;i++){
            p[i]=b[i+1]-b[i];
        }
        //构造next数组
        ne[1]=0;
        for(int i=2,j=0;i<=m-1;i++){
            while(j&&p[i]!=p[j+1]) j=ne[j];
            if(p[i]==p[j+1]) j++;
            ne[i]=j;
        }
        //KMP Matching
        vector<ll> temp,templ;
        for(int i=1,j=0;i<=n-1;i++){
            while(j&&s[i]!=p[j+1]) j=ne[j];
            if(s[i]==p[j+1]) j++;
            if(j==m-1){
                ll st=i-j+1;
                ll k=b[1]-a[st];
                temp.push_back(k);
                templ.push_back(st);
                j=ne[j];
            }
        }

        if(templ.empty()){
            cout<<"0 0 0 0 0\n";
            continue;
        }
        sort(temp.begin(),temp.end());
        temp.erase(unique(temp.begin(),temp.end()),temp.end());
        ll k1=temp.size();
        ll k2=abs(temp[0]);
        for(auto item:temp){
            k2=min(k2,abs(item));
        }
        ll l3=templ.size();
        ll l4=templ.front();
        ll l5=templ.back();
        cout<<k1<<" "<<k2<<" "<<l3<<" "<<l4<<" "<<l5<<endl;
         
    }
    return 0;
}