首页 > 其他分享 >前缀和习题汇总

前缀和习题汇总

时间:2023-11-03 21:44:58浏览次数:31  
标签:前缀 int 样例 sum 汇总 ans 习题 奶牛 ll

一、洛谷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

写题思路

  1. 题目给了当前序列与目标序列,可以先处理题目数据,通过求对应位置差值生成新数组temp[ ],从而将问题转换成通过多少次操作能够使cha数组的所有元素值都为0。
  2. 对于样例来说,temp = [0, 3, 1, 1, 3]
    如果需要对同一区间进行加一或者减一的操作,则需要对该区间内所有数都处理,听上去有点儿麻烦。这时候想起来了之前学的求前缀差的差值能够仅修改区间前后两个的值,该操作就方便了很多,所以考虑对temp数组再次处理,得到cha = [0, 3, -2, 0, 2, -3]
    在这一步骤中,需要注意的地方是要在原来的temp序列前后都补上0,不然可能会导致前后的数据处理不到。
  3. 回到题目给的两种操作。
    此时区间内升高一度,等价于区间第一个元素值+1, 最后一个元素值-1。区间降低一度,反之。
    由于题目要求最小的指令次数。可得不存在先把cha数组中的正数变成负数,再变成0。所以思路为找到一个正数,再找到一个负数,一个加一,一个减一。如果最后正数的值多了,或者负数的值多了,那就单独对这个区间操作。
  4. 上一点所说的操作等价于分别求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。最后希望所有的奶牛都降低到饥饿度相同。
  2. 先考虑特殊情况。可以发现,如果第一头奶牛的值要变化,那么必然是喂第一二头奶牛,最后一头奶牛同理。所以能够达到题目目标,首先需要满足的条件为第一头奶牛的饥饿值要小于第二头,最后一头奶牛的饥饿值要小于倒数第二头。
  3. 因为可以选中相邻两只奶牛进行操作,绑定分组的情况下,中间的奶牛会重叠在两个分组间,从而相互影响,所以不考虑这个思路。又因为在遍历的过程中,希望经过操作后,前后两头奶牛的饥饿值能尽可能接近。所以可以用贪心的算法来实现。
  4. 贪心具体实现过程如下
    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;
}

标签:前缀,int,样例,sum,汇总,ans,习题,奶牛,ll
From: https://www.cnblogs.com/hsy2093/p/17808558.html

相关文章

  • 后端集合操作汇总
      1、获得集合中某一列数据形成一个新的集合List<String>setCode=resultList.stream().map(e->e.getSetCode()).collect(Collectors.toList());2、集合中对象类型转换List<RealityTaskEx>exList=ModelConverterUtils.convert(taskList,RealityTaskEx.class);public......
  • Vue+OpenLayers从入门到实战进阶案例汇总目录,兼容OpenLayers7和OpenLayers8
    本篇作为《Vue+OpenLayers入门教程》和《Vue+OpenLayers实战进阶案例》所有文章的二合一汇总目录,方便查找。本专栏源码是由OpenLayers结合Vue框架编写。本专栏从Vue搭建脚手架到如何引入OpenLayers依赖的每一步详细新手教程,再到通过各种入门案例和综合性的实战案例,带领大家快速......
  • CF练习题18
    这次的题都是什么怪物!!!ShortColorfulStrip因为\(n=m\),所以最终的形态一定是\(n\)的一个排列。根据题意,发掘几个性质:一个区间染色,一定最先对其中颜色最小的染色。染色要求覆盖的点颜色完全相同。对于第一次来说,先找到颜色为\(1\)的点,位置是\(p\)。染色的区间是\([......
  • 「UI 测试自动化selenium」汇总
    《selenium基础之java实现》seleniumRC环境配置菜鸟学自动化测试(一)----seleniumIDE菜鸟学自动化测试(二)----seleniumIDE功能扩展菜鸟学自动化测试(三)----selenium命令菜鸟学自动化测试(四)----selenium命令之验证页面元素菜鸟学自动化测试(五)-----selenium命令之定位页面元素菜......
  • vue3 用法汇总(二)
    1、列表中鼠标放在不同单元格显示不同的背景颜色<el-tablev-resize:44:data="tableData"class="tablemarking-table"borderstyle='margin:10px0px'highlight-current-rowelement-loadi......
  • 串口的相关知识汇总连接
    串口和USB的区别串口通信的介绍WIKI[RS-232]接口标准......
  • 前缀和差分
    前缀和什么是前缀和:简单来说,有一个\(x\)数组和\(y\)数组,\(y\)是\(x\)的前缀和数组。\(y_1=x_1\)\(y_2=x_1+x_2\)\(y_3=x_1+x_2+x_3\)\(y_n=x_1+x_2+x_3+……+x_n\)求区间和求前缀和的公式r[i]=r[i-1]+s[i]\(r\)为前缀和数组,要求\(x\)到\(y\)的区间和的话,那么......
  • Windows常用运维命令汇总-学习笔记
    基本网络命令ipconfig/all                                     查看IP地址whoami                                           查询账号所属权限whoami/all               ......
  • C语言经典练习题1
    1、题目:有5个人坐在一起,问第五个人多少岁?他说比第4个人大2岁。问第4个人岁数,他说比第了个人大2岁,问第三个人,又说比第2人大两岁。问第2个人,说比第一个人大两岁。最后问第一个人,他说是10岁。请问第五个人多大?程序分析:利用递归的方法,递归分为回推和递推两个阶段。要想知道第五个人岁数......
  • 前缀和和差分
    一维前缀和1#include<iostream>2usingnamespacestd;34constintN=100010;5intn,m;6inta[N],s[N];//初始化s[0]=078intmain()9{10scanf("%d%d",&n,&m);11for(inti=1;i<=n;i++)cin>>......