前缀和

题目链接 题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的val之和等于给定的sum。 思路：。。。直接搞就好。。。由于是比较经典的题目所以记录一下。。。注意递归的时候每一部分都要返回值orz..(我是多久没写代码了。。。

1303: [CQOI2009]中位数图 # Time Limit: 1 Sec Memory Limit: 162 MB Submit: 2480 Solved: 1529 [Submit][Status][Discuss] Description # 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

题目链接 d：题意：一棵树，给出边权和点权，定义点v控制点u，当且仅当u是v的子树中的点，并且dis(u,v)<=a[u]，其中dis(u,v)为点u到点v路径上的边权和，a[u]为点u的点权，现在问对于每个节点v，其能控制的点有多少个。

hdu 1559 题意：给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。 思路：二维前缀和就好。。。和单调栈没有半毛钱关系吧。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月03日 星期三 21时08分18秒 4File Name :code/hdu/1559.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <stack> 14#include <set> 15#include <map> 16#include <string> 17#include <cmath> 18#include <cstdlib> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28 29using namespace std; 30const double eps = 1E-8; 31const int dx4[4]={1,0,0,-1}; 32const int dy4[4]={0,-1,1,0}; 33const int inf = 0x3f3f3f3f; 34const int N=1E3+7; 35int a[N][N]; 36int sum[N][N]; 37int n,m,x,y; 38int main() 39{ 40 #ifndef ONLINE_JUDGE 41 freopen("code/in.txt","r",stdin); 42 #endif 43 int T; 44 cin>>T; 45 while (T--) 46 { 47 ms(sum,0); 48 scanf("%d%d%d%d",&n,&m,&x,&y); 49 for ( int i = 1 ; i <= n ; i++) 50 for ( int j = 1 ; j <= m ; j++) 51 { 52 scanf("%d",&a[i][j]); 53 sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1] + a[i][j]; 54 } 55 int ans = 0 ; 56 for ( int i = 1 ; i <= n-x+1 ; i++) 57 for ( int j = 1 ; j <= m-y+1 ; j++) 58 ans = max(ans,sum[i+x-1][j+y-1]-sum[i-1][j+y-1]-sum[i+x-1][j-1]+sum[i-1][j-1]); 59 60 printf("%d\n",ans); 61 } 62 63 #ifndef ONLINE_JUDGE 64 fclose(stdin); 65 #endif 66 return 0; 67}

poj 2796 题意：给出一个人n（1E5）天的情绪值（0..1E6），一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。 现在求value的最大值，并且输出得到这个最大值的区间。

poj 2082 题目链接 题意：这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度，这些矩形并排顺次排列在x轴上，问最大面积。

1651: [Usaco2006 Feb]Stall Reservations 专用牛棚 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 700 Solved: 393 [Submit][Status][Discuss] Description # Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows. Help FJ by determining: * The minimum number of stalls required in the barn so that each cow can have her private milking period * An assignment of cows to these stalls over time

1637: [Usaco2007 Mar]Balanced Lineup # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 503 Solved: 336 [Submit][Status][Discuss] Description # Farmer John 决定给他的奶牛们照一张合影，他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线，每头牛都有它的坐标(范围： 0..1,000,000,000)和种族(0或1)。 一直以来 Farmer John 总是喜欢做一些非凡的事，当然这次照相也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛中，种族0和种族1的牛的数量相等。 请算出最广阔的区间，使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛的坐标减去最左边的牛的坐标。 输入中，每个种族至少有一头牛，没有两头牛的坐标相同。

1635: [Usaco2007 Jan]Tallest Cow 最高的牛 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 472 Solved: 278 [Submit][Status][Discuss] Description # FJ’s N (1 <= N <= 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 <= H <= 1,000,000) of the tallest cow along with the index I of that cow. FJ has made a list of R (0 <= R <= 10,000) lines of the form “cow 17 sees cow 34”. This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17. For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints.

There are two types of problems solvable by partial sum. 1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries). Solution of all of this problems are the same. You just need to know how to solve one of them. Example : You are asked some queries on an array _a_1, _a_2, …a, n. Each query give you numbers l and r and you should print a__l + a__l + 1 + … + a__r .

http://acm.hdu.edu.cn/showproblem.php?pid=5416 # 题意：给出一棵树（n<=1E5），定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询（q<=10），每组一个s，问有多少对无序点对（u,v）满足f(u,v)=s. 思路：类似codeforces #340 div 2 E XOR and Favorite Number 先dfs，处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍，统计sum[i]^s出现多少次。 总的时间复杂度为O(Tqn);

http://acm.hdu.edu.cn/showproblem.php?pid=5327 题意：问给出的区间[a,b]中有多少个美丽数，美丽数的定义是所有数字都不相同，如123是，100不是，333也不是。 思路：预处理1..100000的美丽数，可以把每个数字拆开放在set里，比较set的size和位数来实现。 然后用前缀和。

http://codeforces.com/contest/617/problem/E 题意：给出n个数，m个查询，每个查询给定l,r，问在区间【l,r】内，有多少对i,j，满足i^(i+1)^(i+2)^…^j的值为给定的常数k. 思路：学了莫队算法以后。。。这题果然是莫队的一眼题。

http://codeforces.com/contest/611/problem/C 题意：给出一个n*m的地图，.表示可以空，#表示墙。一个东西需要占两个相邻的格子，问给定一个矩形，放一个东西的方案数。 思路：q很大。。应该是先预处理出来直接调用答案。。。计数问题累加性。。应该是前缀和之类。。需要做的就是怎么标记。。我的做法是竖着放和横着放的个数分开来存。从左往右从上往下，每次标记到后一个点。然后二维的前缀和。然后每次询问的时候，去掉最上边和最左边两条边界上对应的多加的点。

http://codeforces.com/contest/18/problem/C 题意：将一个序列分成两个非空的部分，保证和相等，问有多少种方法。 思路：做过一个三部分的。。。两部分直接一个前缀和就好了把。。。有一个需要注意的是。。判断负数是否是奇数的时候需要加个绝对值。。。

http://codeforces.com/contest/608/problem/B 题意：给定两个字符串a,b，问b中的每个连续的长度为a的子串与a的哈密顿距离的和是多少。哈密顿距离是对应位置的字符的差的绝对值的和。由于是01串，也就是字符不同的位置数。 思路：类似前缀和。0和1分别搞。注意开long long

比较水． 唯一一点需要注意的是… 可能有重复元素… 因为我的思路是用两棵一维树状数组搞.. 每个点标记为1 然后看矩形的两个方向中是否至少有一个方向上和等于长度…