BearChild · Blog

字符串匹配 Time Limit: 10 Sec Memory Limit: 256 MB Description 对于一个字符集大小为C的字符串P，我们可以将任意两种字符在Р中的位置进行互换，例如P = abcba，我们交换a,b就变为bacab，交换 a, d就变为dbcbd，交换可以进行任意次。若交换后P变为了字符串Q，则我们称Q与P是匹配的。 现在给定两个字符集大小为C的字符串 S,T，请你求出S中有多少个连续子串与T是匹配的。 Input Output Sample Input 3 3 　　6 3 　　1 2 1 2 3 2 　　3 1 3 　　6 3 　　1 2 1 2 1 2 　　3 1 3 　　6 3 　　1 1 2 1 2 1 　　3 1 3 Sample Output 3 　　1 2 4 　　4 　　1 2 3 4 　　3 　　2 3 4 HINT Solution 发现题目中颜色的具体权值是对答案无关的，然后就是只要相对位置一样即可。 那么显然是一个KMP的模型，变相更改，条件改为：两个字符上一次出现的相对位置相同（也就是位置差值相等）。 那么我们只要求出差 ...

洞穴勘测 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 给定一棵有n个结点的树，结点从О开始编号，0号点为根。初始时i号点颜色为i。 从一个点出发可以移动到与它有边相连的点，若两个点颜色不同则代价为1，否则代价为0。 接下来会有若干次操作，操作有两种: 1、新增颜色操作：指定一个结点 u，将u到根的路径上的所有结点的颜色，统一染为一个从未出现过的新颜色。 2、询问操作：给定结点u，询问以u为根的子树内的所有结点，它们走到根结点(0号点)的代价和的平均值。 现在请你给出每次询问的答案。 Input Output Sample Input 13 　　0 1 　　0 2 　　1 11 　　1 10 　　1 9 　　9 12 　　2 5 　　5 8 　　2 4 　　2 3 　　4 6 　　4 7 　　7 　　q 0 　　O 4 　　q 6 　　q 2 　　O 9 　　q 9 　　q 2 Sample Output 2.0000000000 　　1.0000000000 　　0.8571428571 　　0.5000000000 　　1. ...

树点涂色 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: 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 ...

无聊的计算姬 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 ...

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 ...

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: 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 ...