一、洛谷p1147 连续自然数和
题目描述
对一个给定的正整数 \(M\)，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 \(M\)。
例子：\(1998+1999+2000+2001+2002 = 10000\)，所以从 \(1998\) 到 \(2002\) 的一个自然数段为 \(M=10000\) 的一个解。
输入格式
包含一个整数的单独一行给出 \(M\) 的值（\(10 \le M \le 2,000,000\)）。
输出格式
每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。
样例 #1
样例输入 #1
10000
样例输出 #1
18 142
297 328
388 412
1998 2002
代码实现
#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long ll;
ll sum[2000005];
int main() {
int m;
ll now = 0;
cin >> m;
int l = 1, r = 1;
for(int i = 1; i <= m; i++){
sum[i] = sum[i-1] + i;
}
while(r < m){
now = sum[r] - sum[l-1];
if(now == m){
cout << l << " " << r << endl;
l ++;
r ++;
}
else if(now < m) r++;
else l++;
}
return 0;
}
二、洛谷p2697 宝石串
题目描述
有一种宝石串，由绿宝石和红宝石串成，仅当绿宝石和红宝石数目相同的时候，宝石串才最为稳定，不易断裂。安安想知道从给定的宝石串中，可以截取一段最长的稳定的宝石串，有多少颗宝石组成。请你帮助他。
绿宝石用 \(\texttt G\) 表示，红宝石用 \(\texttt R\) 表示。
输入格式
一行，一个由 \(\texttt G\) 和 \(\texttt R\) 组成的字符串。
输出格式
一行一个整数，表示最长的稳定的宝石串有多少颗宝石组成。
样例 #1
样例输入 #1
GRGGRG
样例输出 #1
4
提示
\(\texttt {RGGR}\) 为答案。
宝石数小于等于 \(10^6\)。
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int pos[2000005], sum[1000005];
int main() {
string s;
int ans = 0;
cin >> s;
int len = s.length();
for(int i = 0; i < len; i++){
if(s[i] == 'G') sum[i+1] = sum[i] + 1;
else sum[i+1] = sum[i] - 1;
}
for(int i = 1; i <= len; i++){
if(pos[sum[i]+1000000]) ans = max(ans, i - pos[sum[i]+1000000]);
else if(sum[i] == 0) ans = max(ans, i);
else pos[sum[i]+1000000] = i;
}
cout << ans << endl;
return 0;
}
三、洛谷p5638 【CSGRound2】光骓者的荣耀
题目描述
小 K 打下的江山一共有 \(n\) 个城市，城市 \(i\) 和城市 \(i+1\) 有一条双向高速公路连接，走这条路要耗费时间 \(a_i\)。
小 K 为了关心人民生活，决定定期进行走访。他每一次会从 \(1\) 号城市到 \(n\) 号城市并在经过的城市进行访问。其中终点必须为城市 \(n\)。
不仅如此，他还有一个传送器，传送半径为 \(k\)，也就是可以传送到 \(i-k\) 和 \(i+k\)。如果目标城市编号小于 \(1\) 则为 \(1\)，大于 \(n\) 则为 \(n\)。
但是他的传送器电量不足，只能传送一次，况且由于一些原因，他想尽量快的完成访问，于是就想问交通部部长您最快的时间是多少。
注意：他可以不访问所有的城市，使用传送器不耗费时间。
输入格式
两行，第一行 \(n,k\)。
第二行 \(n-1\) 个整数，第 \(i\) 个表示\(a_i\)。
输出格式
一个整数，表示答案。
样例 #1
样例输入 #1
4 0
1 2 3
样例输出 #1
6
样例 #2
样例输入 #2
4 1
1 2 3
样例输出 #2
3
数据范围：
对于所有数据，\(a_i > 0\)
思路分析
题目要求的是小K从第一个城市到第\(N\)个城市所花费的最短的时间。其中说明只能使用一次传送器，因此为了让时间最短，需要尽可能地发挥传送器的价值。
所以转换题目角度，本题要求的是\(1～N\)区间内区间地点编号差值长度为k的最大的距离和。
用前缀和处理原距离数组，再for循环遍历一遍长度固定为K的城市对的最大的距离差。ans = sum_dis - max_kdis
代码实现
#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long ll;
ll a[1000005];
ll sum[1000005];
int main() {
int n, k;
cin >> n >> k;
for(int i = 1; i < n; i++){
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
ll maxx = 0;
for(int i = 0; i < n-k; i++) maxx = max(maxx, sum[i+k] - sum[i]);
cout << sum[n-1] - maxx << endl;
return 0;
}
四、洛谷p1719 最大加权矩形
题目描述
给出一个 \(n\times n\) 矩阵。要求矩阵中最大加权矩形。
矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 \([-127,127]\) ,例如
0 –2 –7 0
9 2 –6 2
-4 1 –4 1
-1 8 0 –2
在左下角：
9 2
-4 1
-1 8
和为 \(15\)。
输入格式
第一行：\(n\)，接下来是 \(n\) 行 \(n\) 列的矩阵。
输出格式
最大矩形（子矩阵）的和。
样例 #1
样例输入 #1
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出 #1
15
提示
\(1 \leq n\le 120\)
代码实现
//最大子矩阵和
#include <stdio.h>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
ll a[125][125], sum[125][125];
ll temp[125];
int main() {
int n;
ll ans = -999999999;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> a[i][j];
sum[i][j] = sum[i-1][j] + a[i][j];
}
}
//枚举矩阵上下边界
for(int i = 0; i < n; i++){
for(int j = i; j <= n; j++){
//压缩矩阵，可以把当前边界内的二维矩阵看作是许多个由列前缀和差值组成的点
for(int k = 1; k <= n; k++) temp[k] = sum[j][k] - sum[i][k];
//求这些点的前缀
for(int k = 1; k <= n; k++) temp[k] += temp[k-1];
//遍历每个点，求以当前点为段尾的最大字段和
ll minn = 0;
for(int k = 1; k <= n; k++){
minn = min(minn, temp[k-1]);
ans = max(ans, temp[k] - minn);
}
}
}
cout << ans << endl;
return 0;
}
五、洛谷p7994 [USACO21DEC] Air Cownditioning B
题目描述
Farmer John 的 \(N\) 头奶牛对他们牛棚的室温非常挑剔。有些奶牛喜欢温度低一些，而有些奶牛则喜欢温度高一些。
Farmer John 的牛棚包含一排 \(N\) 个牛栏，编号为 \(1 \ldots N\)，每个牛栏里有一头牛。 第 \(i\) 头奶牛希望她的牛栏中的温度是 \(p_i\)，而现在她的牛栏中的温度是 \(t_i\)。为了确保每头奶牛都感到舒适，Farmer John 安装了一个新的空调系统。该系统进行控制的方式非常有趣，他可以向系统发送命令，告诉它将一组连续的牛栏内的温度升高或降低 1 个单位——例如「将牛栏 \(5 \ldots 8\) 的温度升高 1 个单位」。一组连续的牛栏最短可以仅包含一个牛栏。
请帮助 Farmer John 求出他需要向新的空调系统发送的命令的最小数量，使得每头奶牛的牛栏都处于其中的奶牛的理想温度。
样例1
样例输入
5
1 5 3 3 4
1 2 2 2 1
样例输出
5
写题思路
- 题目给了当前序列与目标序列，可以先处理题目数据，通过求对应位置差值生成新数组temp[ ]，从而将问题转换成通过多少次操作能够使cha数组的所有元素值都为0。
- 对于样例来说，temp = [0, 3, 1, 1, 3]
如果需要对同一区间进行加一或者减一的操作，则需要对该区间内所有数都处理，听上去有点儿麻烦。这时候想起来了之前学的求前缀差的差值能够仅修改区间前后两个的值，该操作就方便了很多，所以考虑对temp数组再次处理，得到cha = [0, 3, -2, 0, 2, -3]
在这一步骤中，需要注意的地方是要在原来的temp序列前后都补上0，不然可能会导致前后的数据处理不到。 - 回到题目给的两种操作。
此时区间内升高一度，等价于区间第一个元素值+1， 最后一个元素值-1。区间降低一度，反之。
由于题目要求最小的指令次数。可得不存在先把cha数组中的正数变成负数，再变成0。所以思路为找到一个正数，再找到一个负数，一个加一，一个减一。如果最后正数的值多了，或者负数的值多了，那就单独对这个区间操作。 - 上一点所说的操作等价于分别求cha数组中正数和与负数和，比较二者绝对值大小。ans=绝对值小的和+二者绝对值相减多出来的和。这里第一项就对应于能够通过一个操作改变两个值。第二项则是对多出来的数单独操作。
代码实现
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int p[100005];
int t[100005];
int temp[100005];
int cha[100005];
int main(){
int n, ans = 0;
int sum_z = 0, sum_f = 0;
cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1; i <= n; i++){
cin >> t[i];
temp[i] = p[i] - t[i];
cha[i] = temp[i] - temp[i-1];
}
cha[0] = 0;
cha[n+1] = 0 - temp[n];
for(int i = 0; i <= n+1; i++){
if(cha[i] > 0)
sum_z += cha[i];
if(cha[i] < 0)
sum_f -= cha[i];
}
if(sum_z > sum_f)
ans = sum_f + (sum_z - sum_f);
else
ans = sum_z + (sum_f - sum_z);
cout << ans << endl;
return 0;
}
六、洛谷p8092 「USACO 2022 January Contest, Bronze」Drought
题目描述
Farmer John 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，Farmer John 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。
FJ 的 \(N\) 头奶牛 \(（1\leq N\leq 10^5）\) 排成一行，队伍中的第 \(i\) 头奶牛的饥饿度为 \(hi（0\leq hi\leq 10^9）\) 。由于奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 \(i\) 和 \(i+1\) 并分别喂她们一袋玉米，令她们的饥饿度各减少 \(1\)。
FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。请帮助 FJ 求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出 \(−1\) 。
样例1
样例输入
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9
样例输出
14
16
-1
-1
-1
写题思路
- 读题，题目中一次操作的作用为：选中相邻的两只奶牛，从而各降低饥饿值1。最后希望所有的奶牛都降低到饥饿度相同。
- 先考虑特殊情况。可以发现，如果第一头奶牛的值要变化，那么必然是喂第一二头奶牛，最后一头奶牛同理。所以能够达到题目目标，首先需要满足的条件为第一头奶牛的饥饿值要小于第二头，最后一头奶牛的饥饿值要小于倒数第二头。
- 因为可以选中相邻两只奶牛进行操作，绑定分组的情况下，中间的奶牛会重叠在两个分组间，从而相互影响，所以不考虑这个思路。又因为在遍历的过程中，希望经过操作后，前后两头奶牛的饥饿值能尽可能接近。所以可以用贪心的算法来实现。
- 贪心具体实现过程如下
1） 先从前往后扫一遍奶牛，如果当前奶牛的饥饿值大于前一头奶牛，那么就喂当前奶牛和下一头奶牛，直到当前奶牛的饥饿值等于前一头奶牛。这样扫完一遍后，奶牛的饥饿值从左往右将会依次递减。而这时，如果答案有解的话，最后一头奶牛的饥饿值就是可能的答案ans。因为这个值代表了最大的“所有奶牛相同饥饿值”。这个值越大，题目所要求的喂的次数就越少。
2）扫的第一遍无法满足题目要求。所以要扫第二遍，第二遍在已知可能答案的情况下，就能模拟流程。但是其中可能存在将奶牛喂到负饥饿值的情况。所以扫完后最后核对一遍扫的末尾饥饿值与可能答案ans，如果二者相等，则验证该方案可行，并且最小投喂次数等于sum - ans * n。
代码实现
#include <stdio.h>
#include <iostream>
typedef long long ll;
#define maxn 100005
using namespace std;
ll h[maxn];
ll sum;
int n;
ll work(){
ll ans = 0;
ll t = 0;
if(n == 1)
return 0;
if(h[1] > h[2] || h[n-1] < h[n])
return -1;
//从前往后扫一遍
for(int i = 1; i < n; i++){
h[i] -= t;
h[i+1] -= t;
if(h[i] < 0)
return -1;
if(h[i+1] - h[i] > 0)
t = h[i+1] - h[i];
else t = 0;
}
ans = h[n];
if(ans < 0)
return -1;
//找到答案后再扫一遍
for(int i = 1; i < n; i++){
t = h[i] - ans;
h[i+1] -= t;
}
if(ans == h[n])
return sum - ans * n;
else return -1;
}
int main(){
int t;
cin >> t;
for(int i = 0; i < t; i++){
cin >> n;
sum = 0;
for(int i = 1; i <= n; i++){
cin >> h[i];
sum += h[i];
}
cout << work() << endl;
}
return 0;
}