ACM

1207: [HNOI2004]打鼹鼠 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2854 Solved: 1390 [Submit][Status][Discuss] Description # 鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个nn的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为（i,j）的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格，机器人不能走出整个nn的网格。游戏开始时，你可以自由选定机器人的初始位置。现在你知道在一段时间内，鼹鼠出现的时间和地点，希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

题目链接 题意：将一棵树的若干点染成黑色，要求满足对于任何一个点u，至少存在一个距离其k以内的点v被染成黑色，问染色方案数。 思路：还没完全搞懂。。。记录一些idea…

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

资料１

poj 3274 题目链接 题意：给出n个数和k，每个数不超过k位二进制。现在问最长的一段区间，满足该区间中所有数相加，k个位置上的数相等。 思路：k个位置上的数都相等的话…那这个和应该是(k«1)-1的整数倍…

题意：有n个雪花，每个雪花有６瓣，给出每一瓣的长度，问是否有两个雪花相同。（雪花相同的条件是：存在某个顺序使得两个雪花的每一瓣长度对应相等） 思路：一开始想到的是先最小表示法。。。然后hash。。。存set。。看set的大小。。。但是因为我是顺时针，逆时针都存了一次，那么如果有一个雪花顺时针和逆时针相同，就会出现错误的结果（虽然这个我应该判掉了。。。但是还是WA　orz）

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

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

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

1008: [HNOI2008]越狱 # Time Limit: 1 Sec Memory Limit: 162 MB Submit: 8165 Solved: 3486 [Submit][Status][Discuss] Description # 监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果 相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱

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

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

题目链接 d：题意：一棵树，给出边权和点权，定义点v控制点u，当且仅当u是v的子树中的点，并且dis(u,v)<=a[u]，其中dis(u,v)为点u到点v路径上的边权和，a[u]为点u的点权，现在问对于每个节点v，其能控制的点有多少个。

题目链接 题意： m个区间，要求构造一个长度为n的数组，满足m个区间中，每个区间的mex值中的最小值最大。 s思路：很容易想到的是…这个最大的mex 不可能超过每一组区间长度，假设最小的区间长度为mn

题目链接 题意： 地主小花有n座山，这些山在地主家门前排成一条直线。这些山一开始均有相同的高度。 每一天，小花都会要求ZJiaQ开挖机把几座山挖掉一定高度，或者给一些山堆上一些高度。并且要求报告ZJiaQ报告现在有多少座山属于“高山脉” 当一排山的高度相等，并且比这排山左边和右边的山要高时，这排山被称为高山脉。 当然，最左边和最右边的山不可能是“高山脉”的一部分 思路：线段树，要维护的域蛮多的。

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

http://codeforces.com/contest/740 A：现在有n个某种物品，要买k个使得n+k是4的倍数，可以的购买方案为a元1个，b元2个，c元3个，每种方案都可以买无限多。 思路：需要注意买多个未必比买少个贵..

题目链接 题意：给出n（n<=1E3）个不同的点，问最多组成多少个平行四边形。 思路：这道题的关键是，对于平行四边形的判断条件，要利用平行四边形对角线的交点平分两条对角线的性质。

题目链接 题意：一个字符串，其仅由nc种字符组成，问其所有长度为n的字串里，共用多少种不同的。 思路：一开始木有懂nc种字符有什么用… 然后写了hash，发现会TLE。。。因为用到了map，被卡了个log..

题目链接 题意：n个人，每个人有一个level值，用一个最长30位的，可能带前缀0的数字串表示，如果i的level大于j的level，那么i可以教j飞行，每个人只能有一个老师，每个人也只能收一个徒弟。师生可以共用一把扫帚飞行。现在问最少需要多少扫帚。