111qqz的小窝

老年咸鱼冲锋!

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

题目链接
题意:一个舞会,每个人有一个val,给出n个人之间的领导和被领导关系,一个人不愿意与他的领导同时参加,问一种安排方案,使得参加的人的val和最大,问这个最大的和是多少。

思路:树形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).

 

 

树形dp学习资料

资料1

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

在最后一个标签 

加上两个
 

 
(空格的字符表示 & + nbsp)
就好了。。。。

poj 3274 Gold Balanced Lineup (抽屉原理?错题?)

poj 3274 题目链接

题意:给出n个数和k,每个数不超过k位二进制。现在问最长的一段区间,满足该区间中所有数相加,k个位置上的数相等。

思路:k个位置上的数都相等的话。。。那这个和应该是(k<<1)-1的整数倍。。。

于是抽屉原理搞了一发。。一直wa..

正解是数字hash。。。

不过我拍了一下。。。如果不是我理解错了题意的话。。。我是把一份ac代码 hack掉了。。。。。

用来对拍的ac代码:

 

 
 

我的代码:

 

 
数据生成器:

 

 
出错的输入:

 

 
我的输出:

 

 
ac代码的输出:

 

 

 

 
 

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

题意:有n个雪花,每个雪花有6瓣,给出每一瓣的长度,问是否有两个雪花相同。(雪花相同的条件是:存在某个顺序使得两个雪花的每一瓣长度对应相等)

思路:一开始想到的是先最小表示法。。。然后hash。。。存set。。看set的大小。。。但是因为我是顺时针,逆时针都存了一次,那么如果有一个雪花顺时针和逆时针相同,就会出现错误的结果(虽然这个我应该判掉了。。。但是还是WA orz)

归根结底我是没有搞定当hash相同的时候,如何判定这两个不是一组orz。

看了很多题解。。。(为什么大家这道题的代码都写得这么丑啊。。。。?

思路有:hash或者最小表示法,或者最小表示法+hash

思路是,把六瓣的长度求和,作为hash的key值。。。

然后。。。只在key相同的里面找一样的。。。

其实是根据这个和分了组。。。

因为和相同的,未必雪花一样,但是雪花的一样的,和一定相同,极大的缩小了范围。

也让我对hash有了新的理解:

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

 

 

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

题目链接

题意:一个人有n元前,他要交的税是n的最大因子(除n外),现在这个投机倒把者想把前分成k部分(k为大于等于1的任意值)每部分不能为1,分别交税,问最少交多少税。

思路:要说因子小。。很容易想到素数。。。然后就很容易想到了维基百科_哥德巴赫猜想

内容是:任何一个大于2的偶数可以写成两个素数的和。

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

那么任何大于2的偶数,答案就是2

奇数可以分成一个3和一个偶数,答案为3.

不过这可能还不够优,这也是这道题的两个trick所在:

如果该数本身为素数,那么不用分(k取1),答案为1

如果该数减去2为素数,那么答案为2.

 

codeforces #382 div2 C. Tennis Championship(打表找规律)

题目链接

题意:n个人进行淘汰赛制的比赛,输的人直接被淘汰,不进行下一轮,现在要求两个人可以比赛当且仅当两个人的胜场数相差小于等于1,现在问赢得最多场的那个人,最多可能赢多少场。

思路:打表找规律。。。麻蛋。。手算错了n=8。。。结果达成了f[1] = 2,fib[2] =4 的奇怪的fib数列。。。卡了一个多小时。。。气哭了。。。

 

 

bzoj 1257: [CQOI2007]余数之和sum (数学)

1257: [CQOI2007]余数之和sum

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

Description

给出正整数n和k,计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

输入仅一行,包含两个整数n, k。

Output

输出仅一行,即j(n, k)。

Sample Input

5 3

Sample Output

7

HINT

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

思路:一开始的想法。。。很容易想到当n>k的部分。。时可以是可以O(1)出来的。。。

然后对于n<k的部分。。。对于大于i/2的部分。。。是递减的等差数列。。也可以O(1)出来。。。

剩下的一半没时间好想法。。。现在复杂度仍然有5E8…gg\

打了很多表。。。也看出规律2333

于是看了题解。。

正解:k%i可以写成 k-k/i*i

而k/i一共有sqrt(k)种,相同的k/i位置相邻,他们的k%i的值是一个等差数列。。。

这道题就是求Σ(kk/ii)i=1..n简化一下是nkΣ(k/ii)i=1..n,显然我们可以发现⌊k/i⌋的取值是一个不上升序列,且有很多取值相同(事实上,⌊k/i⌋的取值只有√k个),那么我们就可以对i中的一段区间求和(这段区间内⌊k/i⌋取值相同),⌊k/i⌋相同且i单调增加1,可以直接算出来,时间复杂度O(√k)

 

 

 

bzoj 1008: [HNOI2008]越狱(对立事件,组合数学)

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取余

Sample Input

2 3

Sample Output

6

HINT

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

思路:越狱的情况很多,考虑不越狱的情况。

答案为:m^n – m*(m-1)^(n-1)

 

 

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

 

1192: [HNOI2006]鬼谷子的钱袋

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

Description

鬼谷子非常聪明,正因为这样,他非常繁忙,经常有各诸侯车的特派员前来向他咨询时政。有一天,他在咸阳游历的时候,朋友告诉他在咸阳最大的拍卖行(聚宝商行)将要举行一场拍卖会,其中有一件宝物引起了他极大的兴趣,那就是无字天书。但是,他的行程安排得很满,他他已经买好了去邯郸的长途马车标,不巧的是出发时间是在拍卖会快要结束的时候。于是,他决定事先做好准备,将自己的金币数好并用一个个的小钱袋装好,以便在他现有金币的支付能力下,任何数目的金币他都能用这些封闭好的小钱的组合来付账。鬼谷子也是一个非常节俭的人,他想方设法使自己在满足上述要求的前提下,所用的钱袋数最少,并且不有两个钱袋装有相同的大于1的金币数。假设他有m个金币,你能猜到他会用多少个钱袋,并且每个钱袋装多少个金币吗?

Input

包含一个整数,表示鬼谷子现有的总的金币数目m。其中,1≤m ≤1000000000。

Output

只有一个整数h,表示所用钱袋个数

Sample Input

3

Sample Output

2
思路:转化成二进制表示….还是蛮容易想到的吧。

 

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

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

思路:同时增加一个数很线段树。。。但是要维护什么呢。。。?

猜测:肯定要维护一个区间中hill的最大宽度…

但是合并的时候要怎么办呢。。。

考虑两个方向的合并。。。

所以还要维护一个区间中,包含右端点的向左单调减延伸的长度,以及左端点的值。

同理,要维护一个区间中,包含左端点的向右单调增延伸的长度,以及右端点的值。

那么每次pushup的时候,就是两个区间hill的最大值,以及两个方向合并的最大值中取最大。。。

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

upd:

口胡的还是有点靠谱的(并没有2333,还是漏了情况)

具体题解见代码注释

以及,为了过这道题先过了在岛老师空间题解中提到的两道题目:

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

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

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

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

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

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

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

题目链接

题意:

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

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

那么是否一定可以构造出mex为mn的数组呢?

是的。

只需要按照

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

 

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

题目链接

题意:

思路:线段树,要维护的域蛮多的。

下面高山脉简称”HM”

sum:区间中HM的总长度。

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

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

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

由于这道题n有1E9,没办法像以前的办法build 线段树,因此我们采用动态线段树的技巧。

官方题解:

对于求“高山脉”长度,可以利用线段树。树节点中保存左高度连续长度,左高度连续区间的高度,左高度连续区间的状态(即是否高于第一个高度不同的山),右高度连续长度,右高度连续区间的高度,右高度连续区间的状态,每段区间内的“高山脉”数量。每次更新时更新高度即可,在pushup过程中去计算新产生的“高山脉”。写起来难度不是很大,然后对于n很大且必须在线做这个条件只需对于线段树动态建立节点去维护即可

 

关于动态线段树:

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

 

 

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

题目链接

题意:长度为n的序列,单点更新,或者询问某一个区间中最长连续严格递增序列的长度是多少。(此处的连续为位置连续,并非数值连续,也就是3,5,7,9,这样的就是满足题意的长度为4的序列)

思路:线段树区间合并。维护三个域。

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

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

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

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

还有一种可能是左右区间各取一部分,此时必须满足左区间的右端点值严格小于右区间的左端点值。

需要注意的是,如果某区间的最长连续严格递增子序列的长度等于区间长度,那么该区间可以向相应方向延伸。

查询的时候也是如此,要记得查询的时候,某一段区间对答案贡献不会超过区间长度。。

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