112. Path Sum

题目链接

 

题意:给一棵树。。问是否存在一条从树根到叶子的路径,使得路径上每个点的val之和等于给定的sum。

思路:。。。直接搞就好。。。由于是比较经典的题目所以记录一下。。。注意递归的时候每一部分都要返回值orz..(我是多久没写代码了。。。

 

 

BZOJ 1303: [CQOI2009]中位数图(前缀/后缀和乱搞)

1303: [CQOI2009]中位数图

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2480  Solved: 1529
[Submit][Status][Discuss]

Description

给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。

Input

第一行为两个正整数n和b ,第二行为1~n 的排列。

Output

输出一个整数,即中位数为b的连续子序列个数。

Sample Input

7 4
5 7 2 4 3 1 6

Sample Output

4

HINT

第三个样例解释:{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000

思路:这道题的思路还是比较经典的…把大于b的数看成1,小于b的数看成-1..于是一段以b为中位数的连续的长度为奇数的数列的和为0.

那么从b往前做一个后缀和,往后做一个前缀和…然后统计每个前缀和/后缀和的值的个数..

然后枚举前缀和/后缀和可能的值(-n..n,由于负数不好处理,整体+n,变成0..2n)

具体见代码

 

 

codeforces 381 div 2 D. Alyona and a tree(二分+前缀和)

题目链接

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

思路:先写了个rmq+dfs的lca。。。那么任意两个点的距离都可以O(1)得到了。然后不会了233333.

upd:和lca没有什么关系,因为一个点能控制另一个点这两个点一定在一条通向根的链上,因此距离直接减一下就好了。

机智的做法:dfs的时候维护一个栈,对于栈中序列,后面一半是对当前点有贡献的。问题时求对于每个v统计其能控制多少个u,现在我们固定u,考虑能控制他的v。这些v在树上的形态时一条链 ,借助第二类前缀和的思想,对于u标记+1,对于u往上的离根最近的且能统治u的v上面的一个标记-1,然后dfs后序遍历(也就是链的起点时距离根远的那一边),距离处理的时候,只需要在递归之后更新ans就好了。

栈里面维护,到哪个节点,从根下来,边权和最大,找边权和>=当前边权和-a[u]的地方。

启示:由于两个存在统治关系的点在一条链上,边权都为正,边权和具有单调性,单调的东西,容易想到二分处理。

hdu 1559 最大子矩阵 (二维前缀和)

hdu 1559

题意:给你一个m×n的整数矩阵,在上面找一个x×y的子矩阵,使子矩阵中所有元素的和最大。

思路:二维前缀和就好。。。和单调栈没有半毛钱关系吧。。。

 

poj 2796 Feel Good (前缀和,单调栈)

poj 2796

题意:给出一个人n(1E5)天的情绪值(0..1E6),一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。

现在求value的最大值,并且输出得到这个最大值的区间。

思路:单调栈。 考虑把每一天作为最小值的时候能向左向由延伸的最远的点的下标,两个方向各做一次单调栈来预处理。和的haunted前缀和搞下。。

然后最后想着了LL,但是读入的时候前缀和的那里忘了LL wa了一发。。。2A

 

 

poj 2082 Terrible Sets (前缀和,单调栈)

poj 2082 题目链接

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

思路:单调栈。 之前的最大矩形面积的宽度都是1.。这次不是1.。做个宽度的前缀和就好。。。1A

 

 

 

BZOJ 1651: [Usaco2006 Feb]Stall Reservations 专用牛棚 (前缀和)

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

有N头牛,每头牛有个喝水时间,这段时间它将专用一个Stall 现在给出每头牛的喝水时间段,问至少要多少个Stall才能满足它们的要求

Input

* Line 1: A single integer, N

* Lines 2..N+1: Line i+1 describes cow i’s milking interval with two space-separated integers.

Output

* Line 1: The minimum number of stalls the barn must have.

* Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.

Sample Input

5
1 10
2 4
3 6
5 8
4 7

Sample Output

4

OUTPUT DETAILS:

Here’s a graphical schedule for this output:

Time 1 2 3 4 5 6 7 8 9 10
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

Other outputs using the same number of stalls are possible.

HINT

不妨试下这个数据,对于按结束点SORT,再GREEDY的做法 1 3 5 7 6 9 10 11 8 12 4 13 正确的输出应该是3

 

 

思路:求所有点中的最大的厚度就是答案。前缀和搞之。1A.

 

BZOJ 1637: [Usaco2007 Mar]Balanced Lineup (前缀和乱搞)

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的牛的数量相等。 请算出最广阔的区间,使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛的坐标减去最做边的牛的坐标。 输入中,每个种族至少有一头牛,没有两头牛的坐标相同。

Input

行 1: 一个整数: N 行 2..N + 1: 每行两个整数,为种族 ID 和 x 坐标。

Output

行 1: 一个整数,阵容平衡的最大的区间的大小。

Sample Input

7
0 11
1 10
1 25
1 12
1 4
0 13
1 22

Sample Output

11
输入说明

有7头牛,像这样在数轴上。

1 1 0 1 0 1 1
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
输出说明

牛 #1 (at 11), #4 (at 12), #6 (at 13), #7 (at 22) 组成一个平衡的最大的区间,大小为 22-11=11 个单位长度。

<——– 平衡的 ——–>
1 1 0 1 0 1 1
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

题意:有n头牛,在一个数轴上,没头牛有一个坐标x和性别(0或者1)
现在要选一段最长的连续区间使得区间内公牛和母牛的个数相等(区间的端点必须有牛存在才可以选),问最长区间是多少。
思路:乱搞。先按照x排序。把性别为0的换成-1,这样比较好处理平衡。然后分三种情况,包含左端点,包含右端点,两个端点都不包含。前两种情况随便搞。最后一种情况,我的做法是正反扫两遍预处理出了sum1[i]和sum2[i],sum1[i]表示正向性别和为i的最左端的点的id,sum2[i]表示反向性别和为i的最右端的点的id。
如果所有奶牛的性别和为total,那么对于正向扫的时候,设当前性别的前缀和为X,中间选的奶牛的前缀和为Z,最后不选的奶牛的性别和为Y,那么就有X+Y+Z=total.
我们要使得Z为0,所以Y=total-x. 说白了就是对于从左往右的每个i,找到最右端的某个点使得这两个点中间的奶牛(不包含这两个点)的性别和为0.
注意下标可能为负,所以整体平移一下就好。
然后三种情况取最大值。
时间复杂度O(n)

BZOJ 1635: [Usaco2007 Jan]Tallest Cow 最高的牛 (差分序列(前缀和的逆))

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.

有n(1 <= n <= 10000)头牛从1到n线性排列,每头牛的高度为h[i](1 <= i <= n),现在告诉你这里面的牛的最大高度为maxH,而且有r组关系,每组关系输入两个数字,假设为a和b,表示第a头牛能看到第b头牛,能看到的条件是a, b之间的其它牛的高度都严格小于min(h[a], h[b]),而h[b] >= h[a]

Input

* Line 1: Four space-separated integers: N, I, H and R

* Lines 2..R+1: Two distinct space-separated integers A and B (1 <= A, B <= N), indicating that cow A can see cow B.

Output

* Lines 1..N: Line i contains the maximum possible height of cow i.

Sample Input

9 3 5 5
1 3
5 3
4 3
3 7
9 8

INPUT DETAILS:

There are 9 cows, and the 3rd is the tallest with height 5.

Sample Output

5
4
5
3
4
4
5
5
5
选区_053
选区_054
差分序列大概就是前缀和的逆过程…?
这道题对于一堆关系(a,b) 要使得【a+1,b-1】中每个都严格小于a,b,但是又要尽可能大,所以令每个[a+1,b-1]每个数-1. 之前其实遇到过,以为是前缀和的第二种应用。但确切来说其实是前缀和的逆过程。。。叫差分序列?
注意去重。对于完全相同的,做一遍就好啦。所以要先排个序

前缀和问题总结

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 a1, a2, …a, n. Each query give you numbers l and r and you should print al + al + 1 + … + ar .

Solution : You need to build another array s1, s2, …, sn which si = a1 + a2 + … + ai and answer is sr - sl - 1 .

2.Problems which you are asked to perform some queries asking you to modify a part of elements (without printing queries.)

Solution of all of this problems are the same. You just need to know how to solve one of them.

Example : You need to perform some queries on an array a1, a2, …a, n. Each query give you numbers l, r and v and for each i such that l ≤ i ≤ r you should increase ai by v, and then after performing all queries, you should print the whole array.

Solution : You should have another array p1, p2, …, pn which, all of its members are initially 0, for each query, you should increase pl by v and decrease pr + 1 by v .

An then, for each i, starting from 1 you should increase pi by pi - 1. So, final array would be a1 + p1, a2 + p2, …, an + pn .

 

先说最简单也是最常见的一种。
sum[i]=sum[i-1]+a[i] (初始sum[0]=0,所以a[i]的下标最好从1开始)
询问得到[l,r]的和,答案为sum[r]-sum[l-1];

还有一种遇到相对较少的用法。 每次对数组a的某区间[l,r]内的每个数增加x。最后要求输出经过所有变换后的数组a。做法是:声明另一个数组p,当对区间[l,r]增加x时, p[l]+=x,p[r-1]-=x; 所有的变换完成后,另p[i]+=p[i-1] ,那么最后的答案就是p[i]+a[i](i:1..n) (可以这样理解:p[l]+=x,表示从x开始被增加x这个变换影响,一直影响到r,也就是从r+1取消这种变换的效果,所以p[r+1]-=x,然后处理前缀和,把标记在开头的变幻累计到每个元素)

此外:前缀和不一定是“和”,加法可以推广到任何有“前缀和性质”的运算,比如乘积,异或(虽然那样就应该不叫前缀“和”了2333)

  cf617E异或前缀和

这些都是区间上的前缀和,我们可以进一步推广到树上。区间的前缀和是从第一个节点开始累加,树上则是从根节点开始做dfs然后累加。

树上前缀和hdu5416

 

hdu 5416 CRB and Tree ( 2015 多校 #10 )

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(T*q*n);

 

hdu 5327 Olympiad (2015 多校 #4 )

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

codeforces #340 div 2 E XOR and Favorite Number

http://codeforces.com/contest/617/problem/E

题意:给出n个数,m个查询,每个查询给定l,r,问在区间【l,r】内,有多少对i,j,满足i^(i+1)^(i+2)^…^j的值为给定的常数k.

思路:学了莫队算法以后。。。这题果然是莫队的一眼题。

入手点是,知道异或也像加一样有前缀和性质。如果我们处理一个按照异或规则的前缀和数组sum[i]=sum[i-1]^a[i],那么i到j的异或和就是sum[i-1]^sum[j]  (x^x==0,因此a[1]到a[i-1]的异或和被去掉了)

因此我们要找的就是区间内有多对i,j满足sum[i-1]^sum[j]==k,也就是sum[i-1]==k^sum[j]这和hdu 5213 a=k-b有如此类似的形式,做法也是类似的。

由于对于每个j,找的是i-1,在处理的时候记得将区间左端点-1,

最重要的一点是,莫队的添加和删除操作最好分开写,至少根据d的正负写个if else,因为顺序不一定相同。

最后一个注意的是,可能会爆int ,所以要用long long

 

 

 

cf 611 A||codeforces goodbye 2015 C. New Year and Domino

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

codeforces 18 C. Stripe

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