题目链接 题意：一个舞会，每个人有一个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 …

资料１

poj 3274 题目链接 题意：给出n个数和k，每个数不超过k位二进制。现在问最长的一段区间，满足该区间中所有数相加，k个位置上的数相等。 思路：k个位置上的数都相等的话。。。那这个和应该是(k<<1)-1的整数倍。。。 于是抽屉原理搞了一发。。一直wa.. 正解是数字hash。。。 不过我拍了一下。。。如果不是我理解错了题意的话。。。我是把一份ac代码　hack掉了。。。。。 用来对拍的ac代码： #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using …

题意：有n个雪花，每个雪花有６瓣，给出每一瓣的长度，问是否有两个雪花相同。（雪花相同的条件是：存在某个顺序使得两个雪花的每一瓣长度对应相等） 思路：一开始想到的是先最小表示法。。。然后hash。。。存set。。看set的大小。。。但是因为我是顺时针，逆时针都存了一次，那么如果有一个雪花顺时针和逆时针相同，就会出现错误的结果（虽然这个我应该判掉了。。。但是还是WA　orz） 归根结底我是没有搞定当hash相同的时候，如何判定这两个不是一组orz。 看了很多题解。。。（为什么大家这道题的代码都写得这么丑啊。。。。？ 思路有：hash或者最小表示法，或者最小表示法＋hash 思路是，把六瓣的长度求和，作为hash的key值。。。 然 …

题目链接 题意：一个人有n元前，他要交的税是n的最大因子（除n外)，现在这个投机倒把者想把前分成k部分(k为大于等于１的任意值）每部分不能为１，分别交税，问最少交多少税。 思路：要说因子小。。很容易想到素数。。。然后就很容易想到了维基百科_哥德巴赫猜想 内容是：任何一个大于２的偶数可以写成两个素数的和。 （虽然是一个猜想没有被证明。。。但是1E9这种级别正确性还是很显然的２３３３ 那么任何大于２的偶数，答案就是２ 奇数可以分成一个３和一个偶数，答案为３． 不过这可能还不够优，这也是这道题的两个trick所在： 如果该数本身为素数，那么不用分（k取１），答案为１ 如果该数减去２为素数，那么答案为２． /* …

题目链接 题意：n个人进行淘汰赛制的比赛，输的人直接被淘汰，不进行下一轮，现在要求两个人可以比赛当且仅当两个人的胜场数相差小于等于１，现在问赢得最多场的那个人，最多可能赢多少场。 思路：打表找规律。。。麻蛋。。手算错了n=8。。。结果达成了f[1] = 2,fib[2] =4 的奇怪的fib数列。。。卡了一个多小时。。。气哭了。。。 /* *********************************************** Author :111qqz Created Time :2016年11月29日 星期二 10时16分50秒 File Name :code/cf/#382/C.cpp …

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 输出仅一行， …

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 …

1192: [HNOI2006]鬼谷子的钱袋 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 3192 Solved: 2313 [Submit][Status][Discuss] Description 鬼谷子非常聪明，正因为这样，他非常繁忙，经常有各诸侯车的特派员前来向他咨询时政。有一天，他在咸阳游历的时候，朋友告诉他在咸阳最大的拍卖行（聚宝商行）将要举行一场拍卖会，其中有一件宝物引起了他极大的兴趣，那就是无字天书。但是，他的行程安排得很满，他他已经买好了去邯郸的长途马车标，不巧的是出发时间是在拍卖会快要结束的时候。于是，他决定事先做好准备，将自己的金币数好并用一个个的小钱袋装好， …

e:题意：那个数，定义hill为一段连续的区间，满足该区间为严格单峰。现在有若干操作，每个操作是对某段区间的数同时增加一个数，问每次操作后，所有的hill中，宽度最大的（区间长度最大）的是多少。 思路：同时增加一个数很线段树。。。但是要维护什么呢。。。？ _猜测：肯定要维护一个区间中hill的最大宽度..._ 但是合并的时候要怎么办呢。。。 考虑两个方向的合并。。。 所以还要维护一个区间中，包含右端点的向左单调减延伸的长度，以及左端点的值。 同理，要维护一个区间中，包含左端点的向右单调增延伸的长度，以及右端点的值。 那么每次pushup的时候，就是两个区间hill的最大值，以及两个方向合并的最大值中取最大。。。 。。。上面是我口胡 …