BearChild's Blog

骑士精神 Time Limit: 10 Sec Memory Limit: 162 MB Description 在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。 　　在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。 　　给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。 Input 第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。 Output 对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。 Sample Input 2 　10110 　01*11 　10111 　01001 　00000 01011 　110*1 　01110 　01010 　00100 Sample Output 7 　-1 HINT Ans<=15 Solution 看到这题，我们 ...

魔法猪学院 Time Limit: 10 Sec Memory Limit: 64 MB Description iPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。 　　经过了一周理论知识和一周基本魔法的学习之后，iPig对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。 　　iPig 今天就在进行一个麻烦的测验。 　　iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。 　　作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素……等等，iPig 的魔法导猪可没这么笨！ 　　这一次，他给 iPig 带来了很多 1 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 N 号元素，为了增加难度，要求每份样本的转换过程都不相同。 　　这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾……现在的你呀！ 　　注意，两个元素之间的转化可能有多种魔法，转化是单向的。 　　转化的过程中，可以转化到一 ...

连通图 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] 表示不选择该点的方案数，后面的式子表示 ...