111qqz的小窝

老年咸鱼冲锋!

112. Path Sum

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

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

1303: [CQOI2009]中位数图 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 2480 Solved: 1529 [Submit][Status][Discuss] Description 给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数

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

题目链接 d:题意:一棵树,给出边权和点权,定义点v控制点u,当且仅当u是v的子树中的点,并且dis(u,v)<=a[u],其中dis(

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

hdu 1559 题意:给你一个m×n的整数矩阵,在上面找一个x×y的子矩阵,使子矩阵中所有元素的和最大。 思路:二维前缀和就好。。。和单调栈没有半毛钱关系

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

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

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

poj 2082 题目链接 题意:这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度,这些矩

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

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,

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

前缀和问题总结

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 +

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组查

hdu 5327 Olympiad (2015 多校 #4 )

http://acm.hdu.edu.cn/showproblem.php?pid=5327 题意:问给出的区间[a,b]中有多少个美丽数,美丽数的定义是所有数字都不相同,如123是,100不是,333也不是。 思路:预处理1..10

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

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 题意:将一个序列分成两个非空的部分,保证和相等,问有多少种方法。 思路:做过一个三部分的。。。两部分直接一个前缀和就好了把。。。有一个需要注

codeforces #336 div 2 B. Hamming Distance Sum

http://codeforces.com/contest/608/problem/B 题意:给定两个字符串a,b,问b中的每个连续的长度为a的子串与a的哈密顿距离的和是多少。哈密顿距离是对应位置的字符的差的绝对值的和。由于是

hdu 5480|| bestcoder   #57 div 2 Conturbatio(前缀和||树状数组)

比较水. 唯一一点需要注意的是… 可能有重复元素… 因为我的思路是用两棵一维树状数组搞.. 每个点标记为1 然后看矩形的两