BearChild's Blog

消失之物 Time Limit: 10 Sec Memory Limit: 128 MB Description ftiasch 有 N 个物品, 体积分别是 W1, W2, …, WN。 由于她的疏忽, 第 i 个物品丢失了. “要使用剩下的 N - 1 物品装满容积为 x 的背包，有几种方法呢？” – 这是经典的问题了。 她把答案记为 Count(i, x) ，想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。 Input 第1行：两个整数 N 和 M ，物品的数量和最大的容积。 第2行： N 个整数 W1, W2, …, WN, 物品的体积。 Output 一个 N × M 的矩阵， *Count(i, x)*的末位数字。 Sample Input 3 2 　1 1 2 Sample Output 11 　11 　21 HINT 1 ≤ N ≤ 2 × 1e3, 1 ≤ M ≤ 2 × 1e3 Solution 首先，我们发现，对于L，R： 　　去掉L，就是要用**[1, L - 1]∪[L + 1, n]的物 ...

Count Time Limit: 10 Sec Memory Limit: 256 MB Description Input Output Sample Input 6 3 Sample Output 2248 HINT Solution 这必然是一道数学题。首先，显然的有：如果 π xi <= n ^ 2m 时，显然是没有限制的。并且 n ^ m = sqrt(n ^ 2m)。 我们记录：s1 表示 < n ^ m 的个数，s2 表示 = n ^ m 的个数，s3 表示 > n ^ m 的个数。 那么显然有 s1 = s3。并且无限制方案数 = (n的约数个数)^2m，这时候，我们只要求出 s2 即可。 问题转化为：在 2m 个位置中 填入若干个数，记 n的某一质因子为 x，那我们要满足 填入数中 x 的指数之和 = m * （n 中这个 x 的指数）。 那么显然对于n的每一个质因子 DP 一下，f[i][j]表示填到了第 i 个数， 和为 j 的方案数。（由于 填数只能是 n 的约数，还要保证 每个数的 x 的指数 < n 中这个 x 的指数）。显 ...

登山 Time Limit: 10 Sec Memory Limit: 256 MB Description 恶梦是一个登山爱好者，今天他来到了黄山 　　俗话说的好，不走回头路。所以在黄山，你只能往前走，或者往上走。 　　并且很显然的是，当你走到山脊的时候，你不能够往上走，你只能往前走一步再往上走。 　　抽象一点而言就是，你可以把黄山视为一个N * N格点图，恶梦从(0,0)开始出发，要走到 (N,N)。 　　当他走到位置(x,y)的时候，它可以往(x + 1,y),或(x,y+1)走。 　　并且当他走到(x,x)的时候，由于他已经处在了山脊上，所以他不能够往(x,x+1)方向上走。 　　当恶梦兴致勃勃准备开始爬山的时候，他的同伴告诉他，黄山由于年久失修，有一些位置出现了大坑，不能走。 　　恶梦觉得更刺激了，但他想先知道他能有多少种方式走到黄山顶。 　　由于这个数字很大，所以你只需要将答案对10^9 + 7取模输出即可。 Input 第一行包括两个整数N,C,分别表示你可以把黄山视作一个N * N的格点图，并且黄山上面有C个位置出现了大坑。 　　接下来的C行，每行包括两个整数X,Y,表 ...

Perm Time Limit: 10 Sec Memory Limit: 256 MB Description 很久以前，有一个 1~n的排列。 　　这个排列太杂乱无章了，方老师想要让它变得单调一些。 　　方老师打算把排列中的数划分成两个非空子序列，一个单调上升，一个单调下降。 　　需要注意的是，排列中的每个数必须恰在一个子序列中并保持原来在排列中的相对顺序不变。 　　由于方案可能会比较多，你只需要输出方案数 mod 666623333。 Input 第一行一个整数 n。 　　第二行 n 个 1~n 的整数，为一个 1~n 的排列。 Output 一个整数，满足题意的方案数 mod 666623333。 Sample Input 3 　　1 3 2 Sample Output 3 HINT 1 <= n <= 10^6 Solution 显然，我们运用DP。 我们记 f[i][j] 为做到了第 i 个数，i 为递增子序列结尾，j 为递减子序列结尾的方案数，g[i][j] 为做到了第 i 个数，i 为递减子序列结尾，j 为递增子序列结尾的方案数。 我们考虑 第 i 个数 和 ...

卡牌游戏 Time Limit: 10 Sec Memory Limit: 128 MB Description N个人坐成一圈玩游戏。一开始我们把所有玩家按顺时针从1到N编号。首先第一回合是玩家1作为庄家。每个回合庄家都会随机（即按相等的概率）从卡牌堆里选择一张卡片，假设卡片上的数字为X，则庄家首先把卡片上的数字向所有玩家展示，然后按顺时针从庄家位置数第X个人将被处决即退出游戏。然后卡片将会被放回卡牌堆里并重新洗牌。被处决的人按顺时针的下一个人将会作为下一轮的庄家。那么经过N-1轮后最后只会剩下一个人，即为本次游戏的胜者。现在你预先知道了总共有M张卡片，也知道每张卡片上的数字。现在你需要确定每个玩家胜出的概率。 这里有一个简单的例子： 例如一共有4个玩家，有四张卡片分别写着3,4,5,6. 第一回合，庄家是玩家1，假设他选择了一张写着数字5的卡片。那么按顺时针数1,2,3,4,1，最后玩家1被踢出游戏。 第二回合，庄家就是玩家1的下一个人，即玩家2.假设玩家2这次选择了一张数字6，那么2,3,4,2,3,4，玩家4被踢出游戏。 第三回合，玩家2再一次成为庄家。如果这一次玩家2再次选了 ...

吉夫特 Time Limit: 15 Sec Memory Limit: 512 MB Description Input 第一行一个整数n。 　　接下来n行，每行一个整数，这n行中的第i行，表示ai。 Output 一行一个整数表示答案。 Sample Input 4 　　15 　　7 　　3 　　1 Sample Output 11 HINT Main idea 给定一个序列，问有多少个子序列满足相邻的数构成的组合数都为奇数。 Solution 首先我们用Lucas定理推一推可以知道：C(n,m)为奇数当且仅当n&m=m。 有了这个定理就好办了，我们可以显然地想到DP：通过枚举数在二进制下的子集转移，这样保证了可以转移过去。 由于序列每个数都不同，且最大值为233333，所以效率是**O(3^18)**的。 Code 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;const int ONE = 3000 ...

字串变化 Time Limit: 10 Sec Memory Limit: 128 MB Description 定义一个（大写字母）字符串集合{S},初始时值包含一个给定的字符串S1，每次从中任意取出一个字符串，将它变换后再放入集合中。要求新的字符串在集合中没有出现过。 　　变换的规则：在变化前、后，字符串均有大写字母组成，每次只改动一个位置，使它的ASCLL加1。例如：‘A’ –> ‘B’。如果位置为‘Z’，则无法改动。 若干次操作后，该集合的元素个数一定会达到最大。 　　对最后的集合（已按字典序排列）中的Si（i >1），定义Sj=P[Si]（Si由Sj变化而来）。 　　求最大元素个数及{P}的方案数。（详情见样例。） Input 第1行有1个由大写字母组成的字符串。 Output 输出2行，每行包含一个数，第一行表示最大元素个数，第二行表示方案数，答案都模10007。 Sample Input XYZ Sample Output 6 　　4 explain： 　　最终集合为{XYZ,XZZ,YYZ,YZZ,ZYZ,ZZZ} 　　{P}方案有{0,1,1,2,3,4} ...

太空猫 Time Limit: 1 Sec Memory Limit: 256 MB Description 太空猫(SpaceCat)是一款画面精致、玩法有趣的休闲游戏，你需要控制一只坐在迷你飞碟上的猫咪在太空里不断探索，让大家看看你能飞得多远。 　　游戏地图可以看成一个二维的网格图，上下是两段障碍物。 　　在游戏的一开始，太空猫位于地图最左边的下边界之上，且重力方向向下。 　　在每个时刻，你可以用手指点击屏幕，翻转重力的方向，或者通过遥感控制太空猫往左或往右移动。 　　每次翻转重力方向时，你需要消耗的能量值等于上下底边之间的高度差。 　　在左右移动的时候，太空猫可以下降到对应重力方向更低的位置，但不能往上爬。 　　当然，太空猫也不能穿墙而过。在重力翻转的过程中，直到碰到地面之前，你都不能操控太空猫左右移动。 　　太空猫的终点位于地图的最右端的下底边之上，请计算为了让太空猫到达终点，需要消耗能量的最小值。 Input 第一行包含一个正整数n，即地图的宽度。 第二行包含n个正整数c_1,c_2,…,c_n，分别表示每个横坐标对应的上边界的高度。 第三行包含n个正整数f_1,f_2,… ...

巴厘岛的雕塑 Time Limit: 10 Sec Memory Limit: 64 MB Description 印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。 在这条主干道上一共有 N 座雕塑，为方便起见，我们把这些雕塑从 1 到 N 连续地进行标号，其中第 i 座雕塑的年龄是 Yi 年。为了使这条路的环境更加优美，政府想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。 下面是将雕塑分组的规则： 这些雕塑必须被分为恰好 X 组，其中 A< = X< = B，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。 当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。 计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。 请问政府能得到的最小的最终优美度是多少? 备注：将两个非负数 P 和 Q 按位取或是这样进行计算的： 首先把 P 和 Q 转换成二进制。 设 nP 是 P 的二进制位数，nQ 是 Q 的二进制位数，M 为 nP 和 nQ 中的最大值 ...

火星藏宝图 Time Limit: 10 Sec Memory Limit: 64 MB Description Input Output Sample Input 4 10 　1 1 20 　10 10 10 　3 5 60 　5 3 30 Sample Output -4 HINT 1<= M <=2000, 2<= N <=100000. Main idea 每个点上有一个收益，从一个点走到另外一个点的花费是欧几里得距离的平方，问从(1,1)走到(m,m)的最大收益。 Solution 首先，运用DP。而且若A < C < B，显然则有 (A-B)^2 > (A-C)^2 + (C-B)^2。 那么我们对横坐标排序一下，可以保证横向的大小关系。然后对于一个转移，每一纵向只有最接近它的点有用。这样就可以做到**O(nm)**了。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...