前缀和前缀和子矩阵的和结语前缀和输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l,r对于每个询问，输出原序列中从第l个数到第r个数的和。输入格式第一行包含两个整数n和m第二行包含n个整数，表示整数数列。接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。输出格式共m行，每行输出一个询问的结果。数据范围1≤l≤r≤n,1≤n,m≤100000,−1000≤数列中元素的值≤1000输入样例：5321364121324输出样例：3610前缀和的用处：前缀和数组能以On(1)的方式求出给定范围内数组的和。在很多地方都用的上前缀和数组，只是它很容易被人忽略，所以得多练练加深印
竞赛链接A.糖果题目链接链接题目描述给定三个正整数a,b,c。请计算⌊a+b+c2⌋，即a,b,c相加的和除以2再下取整的结果。输入格式第一行包含整数T，表示共有T组测试数据。每组数据占一行，包含三个正整数a,b,c。输出格式每组数据输出一行结果，表示答案。数据范围前三个测试点满足1≤T≤10。所有测试点满足1≤T≤1000，1≤a,b,c≤10^16。输入样例：4134110100100000000000000001000000000000000010000000000000000233445输出样例：4551500000000000000051难度：简单时/空限制：1s/256MB总通过数
竞赛链接A.糖果题目链接链接题目描述给定三个正整数a,b,c。请计算⌊a+b+c2⌋，即a,b,c相加的和除以2再下取整的结果。输入格式第一行包含整数T，表示共有T组测试数据。每组数据占一行，包含三个正整数a,b,c。输出格式每组数据输出一行结果，表示答案。数据范围前三个测试点满足1≤T≤10。所有测试点满足1≤T≤1000，1≤a,b,c≤10^16。输入样例：4134110100100000000000000001000000000000000010000000000000000233445输出样例：4551500000000000000051难度：简单时/空限制：1s/256MB总通过数
AcWing传送门洛谷传送门题目大意\(\qquad\)给一个无向图，边权都是\(1\)，求出以\(1\)为源点，到各个点(\(1\simn\))的最短路数量解题思路\(\qquad\)边权都是\(1\)的图中最短路，我们选择用\(BFS\)解决这个问题\(\qquad\)对于每个点\(j\)，我们进行以下讨论：（假设这个\(j\)在这轮\(BFS\)中由\(i\)点转移而来)\(\qquad\)\(1.\)当\(dist_{\j}的时候，由于队列的性质，\(点1\)到\(点j\)的若干条最短路中\(\color{Red}{\huge必定没有i}\)，所以我们可以直接忽视这种情况\(\qqua
AcWing传送门洛谷传送门题目大意\(\qquad\)给一个无向图，边权都是\(1\)，求出以\(1\)为源点，到各个点(\(1\simn\))的最短路数量解题思路\(\qquad\)边权都是\(1\)的图中最短路，我们选择用\(BFS\)解决这个问题\(\qquad\)对于每个点\(j\)，我们进行以下讨论：（假设这个\(j\)在这轮\(BFS\)中由\(i\)点转移而来)\(\qquad\)\(1.\)当\(dist_{\j}的时候，由于队列的性质，\(点1\)到\(点j\)的若干条最短路中\(\color{Red}{\huge必定没有i}\)，所以我们可以直接忽视这种情况\(\qqua
算法分析棋盘型状态压缩dp这类dp有一个通用的状态表示法：f[i][j][k],表示前i行（放了j个棋子后）的状态表示为k。由于本题无棋子要求，因此可以省去中间一维，即: 用f[i][j]表示前i行土地的状态为j。首先由于玉米地有不肥沃的地方不能种植，因此需要通过二进制表示出来可以种植和不可以种植的地方，我们是将整行用一个二进制数表示的，可种为0，不可种为1，在输入的时候即可判断： g[i]+=(!x由于是棋盘型，因此根据我们的经验显而易见可以知道需要分别分析棋盘的列和行：根据题意相邻的两格内不能同时种玉米可知： （以x为当前格）则 (x&x>>1)=0; 这很容易理解，比如x的二进制
算法分析棋盘型状态压缩dp这类dp有一个通用的状态表示法：f[i][j][k],表示前i行（放了j个棋子后）的状态表示为k。由于本题无棋子要求，因此可以省去中间一维，即: 用f[i][j]表示前i行土地的状态为j。首先由于玉米地有不肥沃的地方不能种植，因此需要通过二进制表示出来可以种植和不可以种植的地方，我们是将整行用一个二进制数表示的，可种为0，不可种为1，在输入的时候即可判断： g[i]+=(!x由于是棋盘型，因此根据我们的经验显而易见可以知道需要分别分析棋盘的列和行：根据题意相邻的两格内不能同时种玉米可知： （以x为当前格）则 (x&x>>1)=0; 这很容易理解，比如x的二进制
题解借鉴两位大佬的解析墨染空&&野生铅笔本题是一道01背包的扩展题——二维费用01背包问题把野生宝可梦看做物品，则捕捉他需要的精灵球个数就是第一费用，战斗皮神要掉的血就是第二费用在背包问题中，体积w与价值v是可以互逆的！可以将f[i]表示为体积为i能装的最大价值，也可以将f[i]表示为价值为i所需的最小体积。以上就是本题的阅读理解分析部分，接下来直接上闫氏DP分析法#include#include#includeusingnamespacestd;constintN=110,M=1010,K=510;intn,m,t;intv1[N],v2[N];intf[M][K];intmain(){ci
题解借鉴两位大佬的解析墨染空&&野生铅笔本题是一道01背包的扩展题——二维费用01背包问题把野生宝可梦看做物品，则捕捉他需要的精灵球个数就是第一费用，战斗皮神要掉的血就是第二费用在背包问题中，体积w与价值v是可以互逆的！可以将f[i]表示为体积为i能装的最大价值，也可以将f[i]表示为价值为i所需的最小体积。以上就是本题的阅读理解分析部分，接下来直接上闫氏DP分析法#include#include#includeusingnamespacestd;constintN=110,M=1010,K=510;intn,m,t;intv1[N],v2[N];intf[M][K];intmain(){ci
题目链接题目描述一个商人穿过一个N×N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N−1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。题目模型子题目：摘花生因为要在（2N-1）个单位时间穿越出去，而从（1，1）走到（n，n）正好需要（2N-1）个单位时间，所以不能走回头路。题目代码#include#include#includeusin
