前言

今天主要练习前缀和，有的是之前写的，源代码见 https://github.com/KiloMing/MyCode

P8649 k倍区间

原题链接：https://www.luogu.com.cn/problem/P8649 多注意转换思想，不要一上来就暴力

//前缀和->区间和， 转换为是否为K的倍数
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main(){
    int N, k;
    cin >> N >> k;
    vector<int> a(N);
    vector<long long> s(N+1);
    unordered_map<int, int> mp1;
    s[0] = 0;                       //初始化
    //cout << endl;
    for(int i = 0; i < N; i++){
        cin >> a[i];
        //cout << a[i] << endl;
    }
    for(int i = 1; i <= N; i++){
        s[i] = s[i-1] + a[i-1];
        //cout << s[i] << endl;
    }
    //cout << endl;

    /*使用暴力写出所有结果，有没有更好的方法？
    意料之内，给我踹回来了；
    int sum = 0;
    for(int i = 1; i <= N; i++){
        for(int j = i; j <= N; j++){
            if((s[j]-s[i-1]) % k == 0) sum++;  //还是要注意边界问题
        }
    }
    */

    /*
    使用哈希<unordered_map>,进行计数，发现如果在前缀和数组中，如果s[i] % k = s[j] % k,那么他们的区间和就是k倍
    在平常的算法题中，要多注意使用转换的方法，可以大大简化复杂度
    //打好摸板
    */
    long long ans = 0;   //区间可能会很多
    for(int i = 0; i <= N; i++){
        int temp = s[i] % k;
        ans += mp1[temp];
        mp1[temp]++;
    }

    cout << ans << endl;
}

P9533 区间翻转区间异或和

原题链接 https://www.luogu.com.cn/problem/P9533

//
//异或： 0^1 = 1; 1^0 = 1, 1^1 = 0, 0^0=0,说白了就是一样的就是0，不一样就是1；
//在C++中，其底层运算就是二进制，不需要再进行二进制转换，直接可以求出异或和
//题目中说可以翻转异或和0区间，但是无论反转还是不反转，给出数组的最大异或和都是一样的，所以这道题就是求异或和为0的区间有多少
//其本质与求区间和为0是一个道理

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
long long ans = 0;
long long sum = 0;
unordered_map<long long, int> mp1;

int main(){
    int N;
    cin >> N;
    vector<long long> a1(N);
    for(int i = 0; i < N; i++){
        cin >> a1[i];
    }
    mp1[0] = 1;
    for(int i = 0; i < N; i++){
        sum ^= a1[i];
        ans += mp1[sum];
        mp1[sum]++;
    }
    cout << ans << endl;

}

总结

以后再做算法题，要考虑清楚，讲求细节，今天就写了两道，效率还是有点低，主要是上午摸索，不知道学啥，以后就跟着题单做吧