# 111qqz的小窝

## hdu 1520 Anniversary party (树形dp模板题)

dp1[v]表示包含v节点的子树的最大值。

dp2[v]表示，不包含v节点的子树的最大值。

Now, similar to array problem, we have to make a decision about including node V in our subset or not. If we include node V, we can’t include any of its children(say v1, v2, …, vn), but we can include any grand child of V. If we don’t include V, we can include any child of V.

So, we can write a recursion by defining maximum of two cases.
.

As we see in most DP problems, multiple formulations can give us optimal answer. Here, from an implementation point of view, we can define an easier solution using DP. We define two DPs, and , denoting maximum coins possible by choosing nodes from subtree of node V and if we include node V in our answer or not, respectively. Our final answer is maximum of two case i.e. .

And defining recursion is even easier in this case. (since we cannot include any of the children) and (since we can include children now, but we can also choose not include them in subset, hence max of both cases).

## 关于代码插件　crayon　无法高亮的解决方案

（空格的字符表示　＆　＋　nbsp）

poj 3274 题目链接

ac代码的输出：

## poj 3349 Snowflake Snow Snowflakes (利用hash分组)

hash未必可以唯一确定某个值，但是可以帮助缩小范围。

## codeforces #382 div2 D. Taxes(哥德巴赫猜想)

（虽然是一个猜想没有被证明。。。但是1E9这种级别正确性还是很显然的２３３３

## 1257: [CQOI2007]余数之和sum

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 3724  Solved: 1711
[Submit][Status][Discuss]

5 3

7

## HINT

50%的数据满足：1<=n, k<=1000 100%的数据满足：1<=n ,k<=10^9

## 1008: [HNOI2008]越狱

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 8165  Solved: 3486
[Submit][Status][Discuss]

## Description

监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果

## Input

输入两个整数M，N.1<=M<=10^8,1<=N<=10^12

## Output

可能越狱的状态数，模100003取余

2 3

6

## HINT

6种状态为(000)(001)(011)(100)(110)(111)

## 1192: [HNOI2006]鬼谷子的钱袋

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 3192  Solved: 2313
[Submit][Status][Discuss]

3

2

## codeforces #381 div2 E. Alyona and towers (线段树 区间合并)

e:题意：那个数，定义hill为一段连续的区间，满足该区间为严格单峰。现在有若干操作，每个操作是对某段区间的数同时增加一个数，问每次操作后，所有的hill中，宽度最大的（区间长度最大）的是多少。

。。。上面是我口胡的。。。

upd:

hdu 3308 题目链接

hdu 5367题目链接

## 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，其能控制的点有多少个。

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

## codeforces #381 div 2 C. Alyona and mex (构造)

m个区间，要求构造一个长度为n的数组，满足m个区间中，每个区间的mex值中的最小值最大。

s思路：很容易想到的是…这个最大的mex 不可能超过每一组区间长度，假设最小的区间长度为mn

0,1,2…mn-1,0,1….的方式构造即可。

## hdu 5367 digger(动态线段树，区间合并)

sum:区间中HM的总长度。

lsum,rsum,区间中包含左端点，右端点的高度相同的山的长度。

lh,rh：区间中包含左端点，包含右端点的的高度相同的山的高度。

llh,rrh:从左端点向右，从有段点向左的，第一个高度不相同的山的高度。

在本题中，n比较大，直接将所有线段树中的所有节点定义出来不现实，那我们注意到，这道题实际上是对区间进行的一系列操作，那么就可能存在一个区间【l，r】，在所有处理过程中，该区间都可以被当做一个整体来看待。   如果是这样的话，我们定义出与该区间的子区间相对应的节点就没有意义了。
动态生成线段树就是：假设对某一节点 p (代表区间【l，r】)进行处理时，并不是对整个区间[l，r]进行处理，而是对其某个子区间进行处理，那这个时候，该区间就不能一直被当做一个整体来看待，所以生成两个初始子节点lp、rp（节点之均为初始值），表示该区间的左半部分与右半部分，然后父节点 p 在对两个新生成的子节点进行更新。

## hdu 3308 LCIS (线段树单点更新，区间合并)

mx:区间中最长连续严格递增序列的长度

lm:包含区间左端点的最长连续严格递增序列的长度。

rm:包含区间右端点的最长连续严格递增序列的长度。

PushUp的时候，一个区间的答案显然可以从左右两个子区间的最大值得到。

hdu有点坑。。。函数名不能命名为update…update2也不行2333