Codeforces gym Hello 2015 Div1 E

Codeforces gym 100570 problem E

(一种处理动态最长回文子串问题的方法)

Problem

给一个长度为N的字符串S,字符集是‘a’-‘z‘。进行Q次操作,操作分三种。一,修改位置X的字符为C;二,查询以P位置为中心的最长回文子串的长度,并输出;三,查询以P与P+1的中间位置为中心的最长回文子串的长度,并输出。

More

第二种操作子串长度为奇数,一定存在;第三种操作子串长度为偶数,若不存在,输出 -1。

Limits

Time Limit(ms): 4000(1s足以)

Memory Limit(MB): 256

N, Q: [1, 10^5]

S[i], C: [‘a‘, ‘z‘]

X, P: [1, N]

Solution

(Thanks Fcdkbear

More

对于第二、三种操作,用hash和二分搜索来查询长度。由于中心位置P给定,所以每次查询复杂度为O(log)*O(hash)。

用线段树来hash,hash方程为:H(Si+1Si+2...Si+n-1Si+n)=H(Si+1Si+2...S(2i+1+n)/2)*(prime^k)+H(S(2i+1+n)/2+1...Si+n-1Si+n);其中prime为选定的素数,选择10^9+7可以过,k为S(2i+1+n)/2+1...Si+n-1Si+n的长度,即k=(i+n)
- ((2i+1+n)/2+1) +1;用上述方程,线段树父亲结点hash值由孩子hash值来维护,即可在O(hash)=O(logN)的复杂度内查询任意一子串的hash值。

这种字符串hash的方法理论上有风险,但有很大的概率不发成冲突。

Complexity

Time Complexity: O(Q*logN*logN)

Memory Complexity: O(4*N)

Source

Codeforces gym Hello 2015 Div1 E

Code

Codeforces gym Hello 2015 Div1 E From My Github

时间: 01-09

Codeforces gym Hello 2015 Div1 E的相关文章

Codeforces gym Hello 2015 Div1 B and Div2 D

Codeforces gym 100571 problem D Problem 给一个有向图G<V,E>和源点S,边的属性有长度L和颜色C,即E=<L,C>.进行Q次询问,每次给定一个点X,输出S到X的最短路的长度(不存在则输出 -1).但要求S到X的路径中相邻两条边颜色不一样. Limits Time Limit(ms): 1000 Memory Limit(MB): 256 |V|, |E|: [1, 10^5] X, S: [1, |V| ] L: [1, 10^9] |C|

Codeforces gym Hello 2015 Div1 C and Div2 E

Codeforces gym 100570 problem C Codeforces gym 100571 problem E Problem 给一个N行M列的矩阵Ma,进行Q次(Q<=10)查询,每次给定一个K,问有多少子矩阵,满足最大值max - 最小值min <=K. Limits Time Limit(ms): 8000 Memory Limit(MB): 512 N, M: [1, 400] Q: [1, 10] Ma(i, j), K: [1, 10^9] Solution (Th

Codeforces gym Hello 2015 Div2 B

Codeforces gym 100571 problem B Problem 设函数F(x),F(1)与F(2)已知,且当 i>=3,F(i)=a*F(i-2)+b*F(i-1).再给一个长度为N的数列A,进行Q次如下操作:每次给一个区间[L, R],对于每个k(L=<k<=R),将A[k]=A[k]+F[k-L+1].最后输出数列A(mod 10^9+7). Limits Time Limit(ms): 1000 Memory Limit(MB): 256 N, Q: [1, 10^

【模拟】ECNA 2015 I What&#39;s on the Grille? (Codeforces GYM 100825)

题目链接: http://codeforces.com/gym/100825 题目大意: 栅栏密码.给定N(N<=10),密钥为一个N*N的矩阵,'.'代表空格可以看到,'X'代表被遮挡,还有密文字符串S,长度为N*N 每次将这个矩阵顺时针旋转90°,把矩阵中空格对应的位置按照从上到下从左到右的顺序依次填充上密文字符,求最终这个密文字符能否填满N*N的矩阵,能按顺序输出得到的答案,不能输出"invalid grille" 题目思路: [模拟] 直接模拟即可.旋转的坐标公式很好推.

Codeforces Gym - 101147J Whistle&#39;s New Car

Discription Statements Whistle has bought a new car, which has an infinite fuel tank capacity. He discovered an irregular country since it has n cities and there are exactly n?-?1roads between them, of course, all cities are connected. He is so much

Codeforces Gym 101174 A Within Arm&#39;s Reach 贪心 手臂

#include<iostream> #include<stdio.h> #include <string.h> #include <algorithm> #include <vector> #include <math.h> using namespace std; #define LL long long const int maxn=25; double a[maxn],l[maxn],r[maxn]; double ex,ey

【宽搜】ECNA 2015 D Rings (Codeforces GYM 100825)

题目链接: http://codeforces.com/gym/100825 题目大意: 给你一张N*N(N<=100)的图表示一个树桩,'T'为年轮,'.'为空,求每个'T'属于哪一圈年轮,空的为'.',如果最内圈<10,每个格子用两位表示,否则用三位,不足的用'.'补足. 题目思路: [宽搜] 初始所有点标记为INF,先将图上所有的'.'标记为0,边缘如果有'T'记为1,并把'.'和边缘所有的点加入队列,接下来一个一个上下左右扩展并更新答案,没进队的进队.最后输出. 1 // 2 //by

Codeforces Gym 100269 Dwarf Tower (最短路)

题目连接: http://codeforces.com/gym/100269/attachments Description Little Vasya is playing a new game named "Dwarf Tower". In this game there are n different items,which you can put on your dwarf character. Items are numbered from 1 to n. Vasya want

CodeForces Gym 101063C 二进制压缩

http://codeforces.com/gym/101063/problem/C 给n个人,m样物品,每个人可以从物品中选择几样.两人选择物品的交集元素个数比上并集元素个数如果大于某个比例即可将两人配对.求配对数. n的范围是1e5,直接比较所有人的选择会TLE,应该将所有选择物品的情况用二进制压缩,m最大是10,情况数目小于2048,可以接受.注意配对总数范围应为long long. #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> i