BearChild's Blog

连通图 Time Limit: 20 Sec Memory Limit: 512 MB Description 给定一个连通的无向图和若干个小集合,每个小集合包含一些边。对于每个集合，你需要确定将集合中的边从原来的无向图中删除后该图是否保持连通。 一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。 Input 输入的第一行包含两个整数n和m(l≤n≤10000,1≤m≤100000)，表示无向图的点数和边数，每个点从1到n标号。 接下来的m行表示图的每条边，每行包含两个整数a和b——一条边连接的两个端点的标号。保证每对顶点最多被一条边连接。 没有一条边连接两个相同的顶点。 每条边按照输入的顺序标号为1到m。 接下来的一行包含一个整数k(1≤k≤100000)，表示需要测试的小集合的个数。 接下来的k行每行描述一个小集合。 每行的第一个数c(1≤c≤4)表示集合中边的个数,接下来有c个整数表示集合中边的标号,保证集合中的整数互不相同。 Output 输出k行,每行对应一个小集合的测试结果。 第i行包含“Connected”（没有引号)，如果给定的图去掉对应的集合中的边仍然连 ...

纸箱堆叠 Time Limit: 30 Sec Memory Limit: 256 MB Description P 工厂是一个生产纸箱的工厂。 　　纸箱生产线在人工输入三个参数 n p a , 之后即可自动化生产三边边长为 (a mod P,a^2 mod p,a^3 mod P) 　　(a^4 mod p,a^5 mod p,a^6 mod P) 　　… 　　(a^(3n-2) mod p,a^(3n-1) mod p,a^(3n) mod p) 的n个纸箱。 　　在运输这些纸箱时，为了节约空间，必须将它们嵌套堆叠起来。 　　一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。 　　你的任务是找出这n个纸箱中数量最多的一个子集，使得它们两两之间都可嵌套堆叠起来。 Input 输入文件的第一行三个整数，分别代表 a,p,n Output 输出文件仅包含一个整数，代表数量最多的可嵌套堆叠起来的纸箱的个数。 Sample Input 10 17 4 Sample Output 2 【样例说明】 　生产出的纸箱的三边长为 ...

Famil Door and Brackets Time Limit: 20 Sec Memory Limit: 512 MB Description Input Output Sample Input 4 1 　　( Sample Output 4 HINT Solution 显然，我们考虑运用DP。先求出 f[i][j] 表示 长度为 i 的括号序列，“)” 比 “(” 多 j 个的方案（时刻保证 j >= 0）。 然后我们考虑怎样获得答案。先预处理出L，R表示将读入的括号序列消去若干对之后剩下的**“)” “(”个数（消去吼显然形如“))(((”**）。 那么我们左边要加入的就要至少多R个“(”，右边类似。 但是显然，我也可以左边再多填几个“(”，右边再多填几个“)”。 那么我们就可以 枚举左边填 i 个括号（则右边填 need - i 个），左边多填 num 个“(”（则右边多填 num 个“)”）。 然后统计答案即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738 ...

BST again Time Limit: 10 Sec Memory Limit: 256 MB Description 求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模） Input 第一行一个整数T，表示数据组数。 以下T行，每行2个整数n和h。 Output 共T行，每行一个整数表示答案（对1000000007取模） Sample Input 2 　2 1 　3 2 Sample Output 2 　4 HINT 1<=n<=600,0<=h<=600,1<=T<=10 Solution 我们运用DP来求解。 记f[i][j]表示点数为i，深度==j的方案数； 　　记g[i][j]表示点数为i，深度<=j的方案数。 转移的时候所以枚举一个点k作为根，那么左边显然就有k-1个点，右边就有i-k个点。 此时深度恰好为j-1的方案数为： 　　g[k-1][j-1] * g[i-k][j-1] - g[k-1][j-2] * g[i-k][j-2]。 所以我们就可以得到答案了。 Code 123 ...

JOIOJI Time Limit: 10 Sec Memory Limit: 256 MB Description JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。 最近，JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成，并且想让“J、O、I”三个字母的出现次数恰好相同。 JOIOJI桑家有一份祖传的卷轴，上面写着一首长诗，长度为N，由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。 现在JOIOJI桑将这首长诗交给了你，请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。 Input 第一行一个正整数N，代表这首长诗的长度 接下来一行一个长度为N的字符串S，表示这首长诗，保证每个字符都是“J、O、I”三个字母中的一个 Output 输出一行一个正整数，代表最长的包含等数量“J、O、I”三个字母的最长连续子串的长度。如果不存在这样的子串，输出0 Sample Input 10 JOIIJOJOOI Sample Output 6 ...

Valera and Number Time Limit: 20 Sec Memory Limit: 512 MB Description Input Output Sample Input 5 3 25 Sample Output 1.9218750000 HINT Solution 考虑运用DP。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include<bits/stdc++.h>using namespace std;typedef long long s64;const int ONE = 800005;const int MOD = 1e9 + 7;const int all = 255;int x, n;double p;double f[205][260][255][2];double Ans;int ...

最大半连通子图 Time Limit: 30 Sec Memory Limit: 162 MB Description 一个有向图G=(V,E)称为半连通的(Semi-Connected)： 如果满足：∀u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。 若G’=(V’,E’)满足V’∈V，E’是E中所有跟V’有关的边，则称G’是G的一个导出子图。 若G’是G的导出子图，且G’半连通，则称G’为G的半连通子图。 若G’是G所有半连通子图中包含节点数最多的，则称G’是G的最大半连通子图。 给定一个有向图G，请求出G的最大半连通子图拥有的节点数K ，以及不同的最大半连通子图的数目C。 由于C可能比较大，仅要求输出C对X的余数。 Input 第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。 接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。 Output 应包含两行，第一行包含一个整数K。第二行包含整数C Mod ...

树 Time Limit: 10 Sec Memory Limit: 256 MB Description 有n个点，它们从1到n进行标号，第i个点的限制为度数不能超过Ai 现在对于每个s(1≤s≤n)，问从这n个点中选出一些点组成大小为s 的有标号无根树的方案数。 Input 第一行一个整数n， 第二行n个整数表示Ai Output 输出一行n个整数，第i个整数表示s=i时的答案 Sample Input 3 　　2 2 1 Sample Output 3 3 2 HINT Solution 由于是带标号的无根树的计数，于是我们运用prufer编码的性质来解题。 prufer编码的几个性质： 　　　　1.对于大小为s的树，prufer编码是一个长度为 s-2 的序列； 　　　　2.i在序列中出现的次数<deg[i]； 　　　　3.一个prufer编码表示一棵树。 所以这题可以转化为求prufer编码的计数。 我们令f[i][j][k]表示前i个点，选择了j个，prufer编码长度为k的方案数。那么显然有 其中 f[i-1][j][k] 表示不选择该点的方案数，后面的式子表示 ...

消失之物 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 的指数）。显 ...