BearChild's Blog

树点涂色 Time Limit: 10 Sec Memory Limit: 128 MB Description Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作： 1 x: 把点x到根节点的路径上所有的点染上一种没有用过的新颜色。 2 x y: 求x到y的路径的权值。 3 x: 在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。 Bob一共会进行m次操作 Input 第一行两个数n,m。 接下来n-1行，每行两个数a,b，表示a与b之间有一条边。 接下来m行，表示操作，格式见题目描述。 Output 每当出现2,3操作，输出一行。 如果是2操作，输出一个数表示路径的权值 如果是3操作，输出一个数表示权值的最大值 Sample Input 5 6 　1 2 　2 3 　3 4 　3 5 　2 4 5 　3 3 　1 4 　2 4 5 　1 5 　2 4 5 Sample Output 3 　4 　2 　2 HI ...

洞穴勘测 Time Limit: 10 Sec Memory Limit: 259 MB Description 辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一 ...

远行 Time Limit: 20 Sec Memory Limit: 256 MB Description Input Output Sample Input 0 　　5 10 　　1 4 5 　　2 3 　　2 5 　　2 1 　　1 5 3 　　1 1 4 　　2 3 　　2 5 　　1 5 2 　　2 1 Sample Output 0 　　1 　　0 　　3 　　2 　　3 HINT Main idea 每次连上一条边，询问一个点和其能到达最远的点的距离。 Solution 由于每次要连上一条边，我们显然使用LCT，然后一个点到达的最远的点必然是树的直径上的端点，我们合并两棵树维护直径的时候，暴力分几种情况讨论一下即可。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 ...

Gate Of Babylon Time Limit: 10 Sec Memory Limit: 162 MB Description Input Output Sample Input 2 1 10 13 3 Sample Output 12 　　 HINT Main idea 有若干个没有限制的道具，以及T个有限制个数的道具，取出m个，求方案数。 Solution 首先，看到有限制的只有15个，因此可以考虑使用容斥原理：Ans=全部没有限制的方案-有1个超过限制的方案数+有2个超过限制的方案数-有3个超过限制的方案数…。 以此类推。我们先考虑没有限制的，在m组无限制的数中选n个的方案数，显然就是C(n+m-1,n)。 因为这道题是要求不超过m的方案数，也就是那么运用加法原理，发现答案也就是C(n+0-1,0)+C(n+1-1,1)+C(n+2-1,2)+…+C(n+m-1,m)=C(n+m,m)。 然后考虑有限制的情况，有一个超过限制直接用总数减去（这个的限制+1)就是当前的总数，相当于强制要选限制+1个为空。 然后只要DFS，记录到当前为止选了几个，答案要记是b[i]+1 ...

无聊的计算姬 Time Limit: 10 Sec Memory Limit: 256 MB Description Input Output Sample Input 6 　　2 2 3 4 　　3 2 7 9 　　2 1 2 9 　　3 1 6 7 　　1 5 3 7 　　1 9 2 8 Sample Output Math Error 　　3 　　Math Error 　　6 　　6 　　1 HINT Solution 我们可以分步骗分。（Task1直接快速幂即可。） 对于前50分： 对于Task2，我们直接暴力枚举，出现一个重复的停止，判断是否存在即可，对于Task3，直接n^2递推组合数即可。 对于11~16的20分： 对于Task2，我们运用BSGS求解即可，对于Task3，直接上Lucas即可。 BearChild不会做满分，满分要运用exBSGS以及exLucas&&CRT。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445 ...

Interesting Time Limit: 30 Sec Memory Limit: 256 MB Description Alice get a string S. She thinks palindrome string is interesting. Now she wanna know how many three tuple (i,j,k) satisfy , S[i…j] and S[j+1…k] are all palindrome strings. It’s easy for her. She wants to know the sum of i*k of all required three tuples. She can’t solve it. So can you help her? The answer may be very large, please output the answer mod 1000000007. A palindrome string is a string that is same when the string is read ...

公共串 Time Limit: 3 Sec Memory Limit: 128 MB Description 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。 　　任务： 　　l　　读入单词 　　l　　计算最长公共子串的长度 　　l　　输出结果 Input 文件的第一行是整数 n ，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。 Output 仅一行，一个整数，最长公共子串的长度。 Sample Input 3 　abcb 　bca acbc Sample Output ２ HINT 2 <= n <= 5 Solution 因为要求所有串的最长公共子串，所以我们运用SAM，先对第一个串（基本串）构建一个SAM，然后用后面的串匹配即可。 记录 L[i] 表示当前串和基本串在 i 这个状态匹配的最长长度。显然，一个状态对答案的贡献是所有串和基本串匹配时 L[i] 的最小值。 然后取一个最大值即可。 Code 12345678910111213141516171819202122232425262728293031323 ...

弦论 Time Limit: 10 Sec Memory Limit: 256 MB Description 对于一个给定长度为N的字符串，求它的第K小子串是什么。 Input 第一行是一个仅由小写英文字母构成的字符串S。 　　第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。 　　T=1则表示不同位置的相同子串算作多个。K的意义如题所述。 Output 输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1 Sample Input aabc 　0 3 Sample Output aab HINT N<=5*10^5, T<2, K<=10^9 Solution 首先我们先构造一个后缀自动机，然后分类讨论： 1. 如果T=0，点权为1。为什么呢？一个点有一个Right集合，一个Right集合可以表达多个子串 ，然后我们一个点 -> 另外一个点 其实不止一条边，我们每条边涵盖了一个信息，意味着 这个点->(走这条边)->到达了下一个点 通过这条边得到的那个新子串，而这多个新子串构成了一个 新的点。所以一条合法的路径， ...

骑士游戏 Time Limit: 30 Sec Memory Limit: 256 MB Description 在这个游戏中，JYY一共有两种攻击方式，一种是普通攻击，一种是法术攻击。 两种攻击方式都会消耗JYY一些体力。 采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽； 而采用法术攻击则可以彻底将一个怪兽杀死。 当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统bug，并不保证这一点）。 游戏世界中一共有N种不同的怪兽，分别由1到N编号，现在1号怪兽入侵村庄了，JYY想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？ Input 第一行包含一个整数N。 接下来N行，每行描述一个怪兽的信息； 其中第i行包含若干个整数，前三个整数为Si，Ki和Ri，表示对于i号怪兽， 普通攻击需要消耗Si的体力，法术攻击需要消耗Ki的体力，同时i号怪兽死亡后会产生Ri个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。 Output 输出一行一个整数，表示最少需要 ...

生成魔咒 Time Limit: 10 Sec Memory Limit: 128 MB Description 魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。 一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。 例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。 S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。 最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。 每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。 Input 第一行一个整数 n。 第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。 Output 输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量 Sample Input 7 　1 2 3 3 3 1 2 Sample Output 1 　3 　6 　9 　12 　17 　22 HINT 1≤n≤100000 Main i ...