BearChild's Blog

采蘑菇 Time Limit: 20 Sec Memory Limit: 256 MB Description Input Output Sample Input 5 　　1 2 3 2 3 　　1 2 　　1 3 　　2 4 　　2 5 Sample Output 10 　　9 　　12 　　9 　　11 HINT Main idea 询问从以每个点为起始点时，各条路径上的颜色种类的和。 Solution 我们看到题目，立马想到了O(n^2)的做法，然后从这个做法研究一下本质，我们确定了可以以点分治作为框架。 我们先用点分治来确定一个center(重心)。然后计算跟这个center有关的路径。设现在要统计的是经过center，对x提供贡献的路径。 我们先记录一个记录Sum[x]表示1~i-1子树中 颜色x 第一次出现的位置的那个点 的子树和，然后我们就利用这个Sum来解题。 我们显然可以分两种情况来讨论： （1）统计center->x出现颜色的贡献： 　　　　显然，这时候，对于center->x这一段，直接像O(n^2)做法那样记录一个color表示到目前为止出现 ...

Bill的挑战 Time Limit: 4 Sec Memory Limit: 64 MB Description Input 第一行：一个整数T，表示数据的个数。 对于每组数据： 第一行：两个整数，N和K（含义如题目表述）。 接下来N行：每行一个字符串。 Output T行，每行一个整数表示答案 Sample Input 1 　　2 1 　　a? 　　?b Sample Output 50 HINT T ≤ 5，M ≤ 15，字符串长度≤ 50。 Solution 我们运用状压DP，令 g[i][c] 表示第 i 位，用 字符c 来匹配可行的串的集合。 然后显然就可以DP啦！f[i][opt] 表示做到了第 i 位，匹配集合为opt的方案数。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include<bits/stdc++.h>using namespace s ...

字符合并 Time Limit: 20 Sec Memory Limit: 256 MB Description 有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。 得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。 Input 第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。 接下来2^k行，每行一个字符ci和一个整数wi， ci表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符, wi表示对应的第i种方案对应获得的分数。 Output 输出一个整数表示答案 Sample Input 3 2 　101 　1 10 　1 10 　0 20 　1 30 Sample Output 40 HINT 1<=n<=300 ,0<=ci<=1, wi>=1, k<=8 Solution 我们显然考虑区间DP，再状态压缩一下，f[l][r][opt]表示[l, r]合成了opt的最大价值。 如果一个区间长度为len的话，最后合完会长度会变为len % ...

排列 Time Limit: 10 Sec Memory Limit: 128 MB Description 给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。 例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。 Input 输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。 Output 每个数据仅一行，表示能被d整除的排列的个数。 Sample Input 7 　　000 1 　　001 1 　　1234567890 1 　　123434 2 　　1234 7 　　12345 17 　　12345678 29 Sample Output 1 　　3 　　3628800 　　90 　　3 　　6 　　1398 HINT s的长度不超过10, 1<=d<=1000, 1<=T<=15 Solution 我们运用状压DP，令 f[j][opt] 表示当前余数为 j，状态为opt的方案。 状态记录的是：各个数字被用了几次。 那么我们就可以状压了。先DFS出每个状态，记sum ...

矩阵填数 Time Limit: 10 Sec Memory Limit: 128 MB Description 给定一个 h*w 的矩阵,矩阵的行编号从上到下依次为 1…h，列编号从左到右依次1…w。 在这个矩阵中你需要在每个格子中填入 1…m 中的某个数。 给这个矩阵填数的时候有一些限制，给定 n 个该矩阵的子矩阵,以及该子矩阵的最大值 v，要求你所填的方案满足该子矩阵的最大值为 v。 现在,你的任务是求出有多少种填数的方案满足 n 个限制。 两种方案是不一样的当且仅当两个方案至少存在一个格子上有不同的数。 由于答案可能很大，你只需要输出答案对 1,000,000,007 的取模即可。 Input 输入数据的第一行为一个数 T，表示数据组数。 对于每组数据，第一行为四个数 h,w,m,n。 接下来 n 行，每一行描述一个子矩阵的最大值 v。 每行为五个整数 x1,y1,x2,y2,v，表示一个左上角为(x1,y1),右下角为(x2,y2)的子矩阵的最大值为 v 。 Output 对于每组数据输出一行，表示填数方案 mod 1,000,000,007 后的值。 Sample Inpu ...

序列计数 Time Limit: 30 Sec Memory Limit: 128 MB Description Alice想要得到一个长度为n的序列，序列中的数都是不超过m的正整数，而且这n个数的和是p的倍数。Alice还希望，这n个数中，至少有一个数是质数。Alice想知道，有多少个序列满足她的要求。 Input 一行三个数，n,m,p。 Output 一行一个数，满足Alice的要求的序列数量，答案对20170408取模。 Sample Input 3 5 3 Sample Output 33 HINT 1<=n<=10^9,1<=m<=2×10^7,1<=p<=100 Solution 先考虑容斥，用Ans=全部的方案数 - 一个质数都没有的方案，那么我们首先想到了一个暴力DP，令 f[i][j] 表示选了前 i 个数，%p时余数为 j 的方案数。那么显然 %p 同余的可以分为一类，那么就可以用矩阵乘法来优化这个DP了。 Code 12345678910111213141516171819202122232425262728293031323 ...

小Z的房间 Time Limit: 10 Sec Memory Limit: 256 MB Description 你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含n*m个格子的格状矩形，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。 　　你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时，你不希望在房子中有小偷的时候会很难抓，所以你希望任意两个房间之间都只有一条通路。现在，你希望统计一共有多少种可行的方案。 Input 第一行两个数分别表示n和m。 　　接下来n行，每行m个字符，每个字符都会是’.’或者’’，其中’.’代表房间，’’代表柱子。 Output 一行一个整数，表示合法的方案数 Mod 10^9 Sample Input 3 3 　… 　… 　.*. Sample Output 15 HINT n,m<=9 Main idea 给定n*m的矩形，由0和1构成，每个相邻的0点可连边，询问有几种连边方案使得0点两两相通且路径唯一。 Solut ...

组合数问题 Time Limit: 10 Sec Memory Limit: 512 MB Description Input 第一行有四个整数 n, p, k, r，所有整数含义见问题描述。 Output 一行一个整数代表答案。 Sample Input 2 10007 2 0 Sample Output 8 HINT 1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1 Solution 首先，不难发现，题目的本质是：从n*k个中选模k等于r个的方案数，那么轻易地写出了暴力DP：f[i][j]=f[i-1][j]+f[i-1][(j-1+k)%k]。 然后套个矩阵乘法优化一下即可。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include<bits/stdc++.h>using namespace std;typede ...

数学作业 Time Limit: 10 Sec Memory Limit: 128 MB Description Input 输入文件只有一行为用空格隔开的两个正整数N和M。 Output 输出仅包含一个非负整数，表示Concatenate(1~N) MOD M的值。 Sample Input 12345678910 1000000000 Sample Output 345678910 HINT 1<=N<=10^8 , 1<=M<=10^9 Main idea 给定一个n,m，创造一个数字顺序连接1~n，输出这个数对m取模的值。 Solution n<=10^18，排除找规律的可能性，立马想到了用矩阵乘法优化DP，令f[i]表示1~i的值，那么： 然后我们只要推出矩阵即可，轻松想到了： 然后分段矩乘得到答案。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#in ...

元素 Time Limit: 20 Sec Memory Limit: 128 MB Description 相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。 　　那时人们就认识到，一个法杖的法力取决于使用的矿石。 　　一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消”。 　　特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。 　　后来，随着人们认知水平的提高，这个现象得到了很好的解释。 　　经过了大量的实验后，著名法师 Dmitri 发现：如果给现在发现的每一种矿石进行合理的编号（编号为正整数，称为该矿石的元素序号），那么，一个矿石组合会产生“魔法抵消”当且仅当存在一个非空子集，那些矿石的元素序号按位异或起来为零。 　　并且人们有了测定魔力的有效途径，已经知道了：合成出来的法杖的魔力等于每一种矿石的法力之和。人们已经测定了现今发现的所有矿石的法力值，并且通过实验推算出每一种矿石的元素序号。 ...