目錄
- 小樂樂改數字 (模擬)
- 十字爆破 (預處理+模擬）
- 比那名居的桃子 (滑窗 / 前綴和)
小樂樂改數字 (模擬)
- 小樂樂改數字
- 首先我們需要知道這個整數的長度來一位一位遍歷，最容易想到的是通過模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;
}
本篇文章的分享就到這里了，如果您覺得在本文有所收獲，還請留下您的三連支持哦~
)
