BearChild's Blog

快速傅立叶之二 Time Limit: 10 Sec Memory Limit: 259 MB Description 请计算C[k]=sigma(a[i]*b[i-k]) 其中 k < = i < n。 a,b中的元素均为小于等于100的非负整数。 Input 第一行一个整数N,接下来N行，第i+2…i+N-1行，每行两个数，依次表示a[i],b[i] (0 < = i < N)。 Output 输出N行，每行一个整数，第i行输出C[i-1]。 Sample Input 5 　3 1 　2 4 　1 1 　2 4 　1 4 Sample Output 24 　12 　10 　6 　1 HINT n < = 10 ^ 5 Solution 显然是运用FFT，看到题目里 b 的下标为 i-k，于是乎我们就要想一个办法，把它弄成卷积的形式。 　　然后翻转一下，下标就变成了**(n-1)-(i-k)**。那 Ans[n-1+k]=Σa[i]*b[(n-1)-(i-k)] 啦。 Code 12345678910111213141516171819202122232 ...

Rectangle Time Limit: 50 Sec Memory Limit: 512 MB Description Input Output Sample Input 0 　　4 　　2 0 　　2 1 　　1 1 　　1 2 　　4 　　0 0 2 2 　　1 1 2 2 　　1 0 2 1 　　0 0 1 1 Sample Output 2 3 　　2 2 　　2 2 　　1 1 HINT Solution 显然，如果我们求出了 last[i] 表示 在某个相同横/纵坐标下，前一个纵/横坐标的取值，那问题就转化为了三维偏序，且要求在线。 限制显然形如：L1 <= xi <= R1, L2 <= yi <= R2, last_i <= L3。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677 ...

SJY摆棋子 Time Limit: 20 Sec Memory Limit: 128 MB Description 这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N个初始棋子，和M个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。 Input 第一行两个数 N M 然后N行，每行2个数 x y，表示初始棋子 以后M行，每行3个数 t x y 如果t=1 那么放下一个黑色棋子 如果t=2 那么放下一个白色棋子 Output 对于每个T=2 输出一个最小距离 Sample Input 2 3 　1 1 　2 3 　2 1 2 　1 3 3 　2 4 2 Sample Output 1 　2 HINT N<=500000 , M<=500000 Main idea 在平面上加入黑点，对于询问一个坐标到其它点的曼哈顿距离中最小的一个。 ...

Censoring Time Limit: 10 Sec Memory Limit: 128 MB Description 有一个S串和一个T串，长度均小于1,000,000，设当前串为U串，然后从前往后枚举S串一个字符一个字符往U串里添加，若U串后缀为T，则去掉这个后缀继续流程。 Input 第一行是S串，第二行是T串。 Output 输出一行，表示按照操作后得到的串。 Sample Input whatthemomooofun 　moo Sample Output whatthefun HINT 串长小于1000000。 Main idea 按照S串的顺序加入S串中的字符，一旦出现了一段和T串一样，则删去这一段，求最后得到的串。 Solution 运用KMP，我们显然只要先把T串加入到Stack里面，然后再按照S的顺序加入字符，每次求next（next[i]表示s[1…i]中最长的公共前后缀），显然next==T串长度的话删去相应长度即可。 Code 123456789101112131415161718192021222324252627282930313233343536373 ...

巧克力王国 Time Limit: 60 Sec Memory Limit: 512 MB Description 巧克力王国里的巧克力都是由牛奶和可可做成的。 但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。 对于每一块巧克力，我们设x和y为其牛奶和可可的含量。 由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数a和b，分别为他自己为牛奶和可可定义的权重，因此牛奶和可可含量分别为x和y的巧克力对于他的甜味程度即为ax + by。 而每个人又有一个甜味限度c，所有甜味程度大于等于c的巧克力他都无法接受。 每块巧克力都有一个美味值h。 现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少。 Input 第一行两个正整数n和m，分别表示巧克力个数和询问个数。接下来n行，每行三个整数x,y,h，含义如题目所示。再 接下来m行，每行三个整数a,b,c，含义如题目所示。 Output 输出m行，其中第i行表示第i个人所能接受的巧克力的美味值之和。 Sample Input 3 3 1 2 5 3 1 4 2 2 1 2 1 6 1 3 5 1 3 ...

动物园 Time Limit: 10 Sec Memory Limit: 512 MB Description 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。 　　某天，园长给动物们讲解KMP算法。 　　园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？” 　　熊猫：“对于字符串S的前i个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作next[i]。” 　　园长：“非常好！那你能举个例子吗？” 　　熊猫：“例S为abcababc，则next[5]=2。因为S的前5个字符为abcab，ab既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出next[1] = next[2] = next[3] = 0，next[4] = next[6] = 1，next[7] = 2，next[8] = 3。” 　　园长表扬了认真预 ...

发展城市 Time Limit: 20 Sec Memory Limit: 512 MB Description 众所周知，Hzwer学长是一名高富帅，他打算投入巨资发展一些小城市。 　　Hzwer打算在城市中开N个宾馆，由于Hzwer非常壕，所以宾馆必须建在空中，但是这样就必须建立宾馆之间的连接通道。机智的Hzwer在宾馆中修建了N-1条隧道，也就是说，宾馆和隧道形成了一个树形结构。 　　Hzwer有时候会花一天时间去视察某个城市，当来到一个城市之后，Hzwer会分析这些宾馆的顾客情况。对于每个顾客，Hzwer用三个数值描述他：（S， T， V）表示该顾客这天想要从宾馆S走到宾馆T，他的速度是V。 　　Hzwer需要做一些收集一些数据，这样他就可以规划他接下来的投资。 　　其中有一项数据就是收集所有顾客可能的碰面次数。 　　每天清晨，顾客同时从S出发以V的速度前往T（注意S可能等于T），当到达了宾馆T的时候，顾客显然要找个房间住下，那么别的顾客再经过这里就不会碰面了。特别的，两个顾客同时到达一个宾馆是可以碰面的。同样，两个顾客同时从某宾馆出发也会碰面。 Input 第一行一个正整数T ...

字符串匹配 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: 128 MB Description 阿米巴是小强的好朋友。 　　阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。 　　学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。 　　我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系： 　　一个食物网有 N个点，代表 N 种生物，如果生物 x 可以吃生物 y，那么从 y 向 x 连一个有向边。 　　这个图没有环。 　　图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。 　　如果某个消费者的所有食物都灭绝了，它会跟着灭绝。 　　我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。 　　举个例子：在一个草场上，生物之间的关系是： ...

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