A. Orange的作文排版
关于处理若干行输入，我们可以用while结合getline函数来完成，每次读取一行，就让行数+1，然后每次利用string的size方法得到当前行的列数，更新最长的列，最后得到答案。
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int a = 0;
int b = 0;
while(getline(cin, s))
{
a ++; // 行数
b = max(b, (int)s.size()); // 列数
}
cout << a << ' ' << b << '\n';
}
B. 最长连号
对于位置 \(x\),每次使用一个指针p开始向后扫描，如果 \(a_p = a_{p-1}\)，则说明是连续的，可以继续向后移动指针 \(p\)，直到 \(a_p \neq a_{p-1}\)，此时 \(p - x\) 就是当前的连续的长度，用它更新答案。每次扫过之后，将 \(x\) 移动到 \(p\) 的位置，继续向后扫描。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[50001];
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
int ans = 0;
for(int i = 1, j = 1; i <= n; i = j)
{
do j ++; while(j <= n && a[j] - a[j - 1] == 1);
ans = max(j - i, ans);
}
cout << ans << '\n';
}
C. Orange的区间和
一维前缀和
#include<bits/stdc++.h>
using namespace std;
long long a[200010], pre[200010]; // 原数组，前缀和数组
int main()
{
cin.tie(0) -> sync_with_stdio(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
pre[i] = pre[i - 1] + a[i]; // 计算前缀和
}
while(m --)
{
int l, r;
cin >> l >> r;
cout << pre[r] - pre[l-1] << '\n';
}
}
D. Orange的区间和II
二维前缀和
#include<bits/stdc++.h>
using namespace std;
long long a[1005][1005], f[1005][1005];
int main()
{
cin.tie(0) -> sync_with_stdio(0);
int n, m, T;
cin >> n >> m >> T;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
cin >> a[i][j];
f[i][j] = a[i][j] + f[i-1][j] + f[i][j-1] - f[i-1][j-1];
}
while(T--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << f[x2][y2] - f[x2][y1-1] - f[x1-1][y2] + f[x1-1][y1-1] << '\n';
}
}
E. Orange的区间修改
一维差分
#include<bits/stdc++.h>
using namespace std;
long long a[200010], d[200010];
int main()
{
cin.tie(0) -> sync_with_stdio(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
d[i] += a[i];
d[i+1] -=a[i]; // 计算差分数组
}
while(m--)
{
int l, r, x;
cin >> l >> r >> x;
d[l] += x;
d[r + 1] -= x;
}
for(int i = 1; i <= n; i ++)
{
d[i] += d[i - 1]; // 差分数组的前缀和就是原数组
cout << d[i] << ' ';
}
}
F. Orange的区间修改II
二维差分
#include<bits/stdc++.h>
using namespace std;
long long d[1005][1005];
void modify(int x1,int y1, int x2,int y2, int v)
{
d[x1][y1] += v;
d[x1][y2 + 1] -= v;
d[x2 + 1][y1] -= v;
d[x2 + 1][y2 + 1] += v;
}
int main()
{
int n, m, t;
cin >> n >> m >> t;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
int x;
cin >> x;
modify(i, j, i, j, x);
}
}
while(t --)
{
int x1, y1, x2, y2, v;
cin >> x1 >> y1 >> x2 >> y2 >> v;
modify(x1, y1, x2, y2, v);
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
d[i][j] = d[i][j] + d[i-1][j] + d[i][j-1] - d[i-1][j-1];
cout << d[i][j] << ' ';
}
cout << '\n';
}
}
G. Orange的闯关游戏II
假设我们将关卡进度分为主线(即首次通过该关卡)和扫荡,假设我当前主线通关到第 \(x\) 关时，我不选择继续向前推进主线，而是选择扫荡之前的关卡，那么为了保证收益最大，我们应该选择前 \(x\) 关中扫荡收益最大的一个关卡,即 \(Max_{i = 1}^x b_i\) 去通关，因此这样能够保证收益最大化。此时我们扫荡的收益为 \((q - x) \times Max_{i = 1}^x b_i\)(因为前面花费了 \(x\) 点体力去推主线)，加上之前主线的收益(即之前所有的首通奖励): \(\sum_{i=1}^x a_i\) 。最后我们可以得到推主线到 \(x\) 关时的最大收益:
然后我们去枚举主线从1推到 \(min(q, n)\) 关的最大收益(因为最多只有n个关卡或者q点体力)，取最大值即可。
对于 \(\sum_{i=1}^x a_i\) 我们可以对 \(a\) 数组作前缀和从而快速计算，对于 \(Max_{i = 1}^x b_i\) ，我们可以对 \(b\) 数组作前缀最大值从而快速计算。
时间复杂度: \(O(n)\)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
int a[200010], b[200010];
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
a[i] += a[i - 1];
}
for(int i = 1; i <= n; i ++)
{
cin >> b[i];
b[i] = max(b[i], b[i-1]);
}
int ans = 0;
for(int i = 1; i <= min(n, q); i ++)
{
ans = max(ans, a[i] + (q - i) * b[i]);
}
cout << ans;
}