题目链接 题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的val之和等于给定的sum。 思路：。。。直接搞就好。。。由于是比较经典的题目所以记录一下。。。注意递归的时候每一部分都要返回值orz..(我是多久没写代码了。。。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: …

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}, …

题目链接 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在树上的形态 …

hdu 1559 题意：给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。 思路：二维前缀和就好。。。和单调栈没有半毛钱关系吧。。。 /* *********************************************** Author :111qqz Created Time :2016年08月03日 星期三 21时08分18秒 File Name :code/hdu/1559.cpp ************************************************ */ #include <cstdio> #include <cstring> …

poj 2796 题意：给出一个人n（1E5）天的情绪值（0..1E6），一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。 现在求value的最大值，并且输出得到这个最大值的区间。 思路：单调栈。 考虑把每一天作为最小值的时候能向左向由延伸的最远的点的下标，两个方向各做一次单调栈来预处理。和的haunted前缀和搞下。。 然后最后想着了LL,但是读入的时候前缀和的那里忘了LL wa了一发。。。2A /* *********************************************** Author :111qqz Created Time :2016年08月03日 星期三 19时14分42 …

poj 2082 题目链接 题意：这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度，这些矩形并排顺次排列在x轴上，问最大面积。 思路：单调栈。 之前的最大矩形面积的宽度都是1.。这次不是1.。做个宽度的前缀和就好。。。1A /* *********************************************** Author :111qqz Created Time :2016年08月03日 星期三 18时54分40秒 File Name :code/poj/2082.cpp …

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), …

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 the height …

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 …