社区首页 >专栏 >【今日三题】小乐乐改数字 (模拟) / 十字爆破 (预处理+模拟) / 比那名居的桃子 (滑窗 / 前缀和)

【今日三题】小乐乐改数字 (模拟) / 十字爆破 (预处理+模拟) / 比那名居的桃子 (滑窗 / 前缀和)

_小羊_

发布于 2025-04-11 01:47:20

5200

代码可运行

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

运行总次数：0

代码可运行

小乐乐改数字 (模拟)

小乐乐改数字

首先我们需要知道这个整数的长度来一位一位遍历，最容易想到的是通过模10除10操作用数组存储每一位；
可以以 string 类型读入整数，直接操作字符串，最后还可以用 stoi 函数自动去掉有前导0的情况。

#include <iostream>
using namespace std;

int main()
{
    string str;
    cin >> str;
    for (auto& e : str)
    {
        if (e % 2) e = '1';
        else e = '0';
    }
    cout << stoi(str) << endl;
    return 0;
}

十字爆破 (预处理+模拟）

十字爆破

通过预处理操作，用 row[N] 和 col[N] 统计每一行每一列所有数之和，方便后续使用；
因为每一行每一列总会相交于一点，因为还需要减去这一点的值。

#include <iostream>
using namespace std;

const int N = 1e6 + 1;
using ll = long long;
ll row[N], col[N]; 
ll n, m;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    ll arr[n][m];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
            row[i] += arr[i][j];
            col[j] += arr[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << row[i] + col[j] - arr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

比那名居的桃子 (滑窗 / 前缀和)

比那名居的桃子

固定窗口大小的滑动窗口问题，维护窗口内的值，在合适的时机<进窗口、判断、更新值、出窗口>。

#include <iostream>
using namespace std;

const int N = 1e5 + 1;
using ll = long long;
ll h[N], s[N];
ll sumh, sums, n, k;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> s[i];
    ll maxh = 0, mins = 0, day = 0;
    for (int l = 1, r = 1; r <= n; r++)
    {
        sumh += h[r];
        sums += s[r];
        if (r - l + 1 == k)
        {
            if (sumh > maxh)
            {
                maxh = sumh;
                mins = sums;
                day = l;
            }
            else if (sumh == maxh && sums < mins)
            {
                maxh = sumh;
                mins = sums;
                day = l;
            }
            sumh -= h[l];
            sums -= s[l++];
        }
    }
    cout << day << endl;
    return 0;
}

求一段区间内的和，也可以用前缀和来做，某两个前缀和的差 == 滑动窗口内维护的值，其他的操作没什么区别。

#include <iostream>
using namespace std;

const int N = 1e5 + 1;
using ll = long long;
ll preh[N], pres[N];
ll sumh, sums, n, k;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) 
    {
        int a; cin >> a;
        preh[i] = preh[i - 1] + a;
    }
    for (int i = 1; i <= n; i++) 
    {
        int b; cin >> b;
        pres[i] = pres[i - 1] + b;
    }
    ll maxh = 0, mins = 0, day = 0;
    for (int i = k; i <= n; i++)
    {
        if (preh[i] - preh[i - k] > maxh)
        {
            maxh = preh[i] - preh[i - k];
            mins = pres[i] - pres[i - k];
            day = i - k + 1;
        }
        else if (preh[i] - preh[i - k] == maxh)
        {
            if (pres[i] - pres[i - k] < mins)
            {
                maxh = preh[i] - preh[i - k];
                mins = pres[i] - pres[i - k];
                day = i - k + 1;
            }
        }
    }
    cout << day << endl;
    return 0;
}