【算法】前缀和、模拟、位运算、差分

_小羊_

发布于 2025-03-15 20:55:43

3800

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

1、模拟

简写单词

BC149 简写单词

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str, ret;
    getline(cin, str);
    char ch = str[0];
    if (ch >= 'a' && ch <= 'z') ch -= 32;
    ret += ch;
    for (int i = 1; i < str.size(); i++)
    {
        if (str[i] == ' ')
        {
            char ch = str[i + 1];
            if (ch >= 'a' && ch <= 'z') ch -= 32;
            ret += ch;
        }
    }
    cout << ret << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str;
    while (cin >> str)
    {
        char ch = str[0];
        if (ch >= 'a' && ch <= 'z') ch -= 32;
        cout << ch;
    }
    return 0;
}

牛牛的快递

BC64 牛牛的快递

我还是太菜了，这题做了十多分钟…

#include <iostream>
using namespace std;

int main() 
{
    float a;
    char b;
    cin >> a >> b;
    int ret = 20; // 起步价20
    if (b == 'y') ret += 5;
    if (a > 1)
    {
        a--;
        while (a > 0)
        {
            ret++;
            a--;
        }
    } 
    cout << ret;
    return 0;
}

蛇形矩阵

蛇形矩阵

#include <bits/stdc++.h>
using namespace std;

const int N = 101;
int arr[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int main()
{
    int n, m;
    cin >> n >> m;
    int a = 0, b = 0, d = 1;
    for (int i = 1; i <= n * m; i++)
    {
        arr[a][b] = i;
        int x = a + dx[d], y = b + dy[d];
        if (x < 0 || x >= n || y < 0 || y >= m || arr[x][y])
        {
            d = (d + 1) % 4;
            x = a + dx[d], y = b + dy[d];
        }
        a = x, b = y;
    }
    for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cout << arr[i][j] << " ";
        cout << endl;
    }
    return 0;
}

除2！

除2！

先把所有的数加起来，在这个过程之中把偶数放到堆中，在遍历这个全是偶数的堆k次，每次让所有数之和减去最大偶数的一半，如果最大偶数除2后还是偶数还要重新添加到堆中，在这个过程中还要关注堆是否已经空了。

这道题还需要关注数据范围的问题，很明显需要用到 long long 类型。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
priority_queue<ll> q;
ll n, k, t, sum = 0;

int main()
{
    cin >> n >> k;
    while (n--)
    {
        cin >> t;
        sum += t;
        // 把偶数存进堆
        if (t % 2 == 0) q.push(t);
    }
    while (!q.empty() && k--)
    {
        t = q.top() / 2;
        q.pop();
        sum -= t;
        if (t % 2 == 0) q.push(t);
    }
    cout << sum << endl;
    return 0;
}

2、位运算

3、前缀和

前缀和题目做法的核心就两步：预处理前缀和数组 + 使用前缀和数组。

这两步通常需要我们总结出一个递推公式，类似于动态规划。

我们需要明确比如 dp[i] 的含义具体是什么，其中特别需要注意循环的区间。

前缀和 + 哈希表通常可以用来解决：子数组和为特定值、子数组和的频率等问题。

一维前缀和

前缀和

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<ll> arr(n + 1), dp(n + 1);
    for (int i = 1; i <= n; i++) 
    {
        cin >> arr[i];
        dp[i] = dp[i - 1] + arr[i];
    }
    int l, r;
    while (q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

二维前缀和

二维前缀和

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main()
{
    int n, m, q,x1, x2, y1, y2;
    cin >> n >> m >> q;
    vector<vector<ll>> arr(n + 1, vector<ll>(m + 1)), dp(n + 1, vector<ll>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j];
        }
    ll tmp = 0;
    while (q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        tmp = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
        cout << tmp << endl;
    }
    return 0;
}

寻找数组的中心下标

寻找数组的中心下标

注意：不是所有一维前缀和数组的递推都是 dp[i] = dp[i - 1] + arr[i]，要根据具体题目具体分析。

本题中的 dp[i] 表示的是 i 位置之前的前缀和，不包括 i 位置，所以 dp 表要多开一个位置，而且还要注意循环的区间。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++)
            dp[i] = dp[i - 1] + nums[i - 1];
        for (int i = 0; i < n; i++)
        {
            if (dp[i] == (dp[n] - dp[i + 1])) 
                return i;
        }
        return -1;
    }
};

除自身以外数组的乘积

除自身以外数组的乘积

其中 f[i] 和 b[i] 分别表示 i 位置之前、之后所有元素之积。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n), f(n, 1), b(n, 1);
        for (int i = 1; i < n; i++)
            f[i] = f[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; i--)
            b[i] = b[i + 1] * nums[i + 1];
        for (int i = 0; i < n; i++)
            ret[i] = f[i] * b[i];
        return ret;
    }
};

和为 K 的子数组

和为 K 的子数组

从前向后统计数组的前缀和，假设以 i 位置为结尾的子数组有 n 个和为 k，则在 i 位置之前的前缀和中有 n 个和为 sum - k 的前缀和，而我们可以在计算前缀和的过程中在哈希表中记录各前缀和出现的次数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // 前缀和及其出现的次数
        hash[0] = 1; // 表示整个数组的前缀和为k
        int sum = 0, ret = 0;
        for (int e : nums)
        {
            sum += e; // 前缀和
            if (hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};

和可被 K 整除的子数组（lqb真题）

和可被 K 整除的子数组

这道题和上道题类似，但是这道题主要考下面两个知识点。

假设以 i 位置为结尾的子数组中有 n 个子数组之和能被 k 整除，有 n 个这样的子数组，也就对应着有 n 个上面的 x 区间。根据同余定理我们只需要求 i 位置前面的所有前缀和中有多少个前缀和的余数等于 sum % k。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // 前缀和的余数及其次数
        hash[0] = 1;
        int sum = 0, ret = 0;
        for (int e : nums)
        {
            sum += e;
            int t = (sum % k + k) % k;
            if (hash.count(t)) ret += hash[t];
            hash[t]++;
        }
        return ret;
    }
};