目录

序列上满足等式类计数

题目一：

解题思路：

题目二：

解题思路：

C语言网题目 1882: 蓝桥杯2017年第八届真题-k倍区间

解题思路：

序列上满足等式类计数

题目一： 给你一个序列。问你有多少对满足 a[i] - a[j] = i - j；

解题思路：

将题目变形可以得到a[i] - i == a[j] - j，设数组b[i] = a[i] - i，那么我们只需要遍历数组b并判断当前位置与当前位置之前有多少个数相同即可计算出答案

#include
using namespace std;

#define ll long long
const ll maxn = 1e9 + 5;

int main()
{
    int n, a[100];
    ll ans = 0;
    //map存储之前出现过的数
    map b;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++)
    {
        //每移动到一个新的位置就加上之前出现的次数
        ans += b[a[i]-i];
        //每移动到一个新的位置将map内该数字的存放个数+1
        b[a[i]-i]++;
    }
    cout << ans;
    return 0;
}

题目二： 给你一个序列，问你有多少个子段和恰好等于k 解题思路：

题目要求是求出在序列中有多少[L，R]的和等于k

转换成前缀和的形式就是

继续变形

这样一来，我们只需要处理好前缀和，然后和题目一相同只需要判断每一个Sr对应之前有多少个Sl-1 + k与之相等，那么就可以求出答案

此题与第一题有所不同，需要先存map再去加，因为要考虑到一种情况，第一个元素等于k

#include
using namespace std;

#define ll long long
const ll maxn = 1e9 + 5;

int main()
{
    int n, k, a[100], s[100];
    ll ans = 0;
    //map存S(l-1)+k的值--用来与Sr判断
    map w;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++)
    {
        //前缀和处理
        s[i] = s[i-1] + a[i];
        //每一次将当前位置的上一个位置前缀和+k的map+1（因为区间和要包含当前元素）
        w[s[i-1]+k]++;
        //加上与当前Sr相等的S(l-1)+k
        ans += w[s[i]];
    }
    cout << ans;
    return 0;
}

C语言网题目 1882: 蓝桥杯2017年第八届真题-k倍区间

题目链接：题目 1882: 蓝桥杯2017年第八届真题-k倍区间

解题思路：

首先我们思考题目是求[L，R]的和为K的倍数

做前缀和处理可以转化为Sr - S(l-1) % k == 0

再转化可以得到Sr%k == S(l-1)%k

这样就又变成了第一个题目的类型

我们只需要处理前缀和，然后每次将当前的前一个位置的前缀和对k求余装进map+1，然后将答案加上当前位置求取k与map中相同的值即可（以当前位置结尾有多少个K倍区间），注意计数题一定要用longlong，否则会爆

#include
using namespace std;

#define ll long long
const ll maxn = 1e5 + 5;

int main()
{
    //不用long long会爆
    ll n, k, a[maxn], s[maxn];
    ll ans = 0;
    map w;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++)
    {
        //前缀和
        s[i] = s[i-1] + a[i];
        //除了S(l-1)%k在map中+1
        w[s[i-1]%k]++;
        //加上map中和Sr%k相等的值就代表有几个区间和是K倍数
        ans += w[s[i]%k];
    }
    cout << ans;
    return 0;
}