题目链接

题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的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的子矩阵，使子矩阵中所有元素的和最大。

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

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 <= …

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 总是喜欢做一些非凡的事，当然这次照相也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛 …

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 …

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 …

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

然后看矩形的两个方向中是否至少有一个方向上和等于长度…