http://poj.org/problem?id=2887
题意:给出一个字符串,还有n个询问,第一种询问是给出一个位置p和字符c,要在位置p的前面插入c(如果p超过字符串长度,自动插在最后),第二种询问是给出一个位置p,查找第p个位置的字符(p保证合法)。
思路:暴力分块。一开始建成块之后,每次插入就在每个块的字符串插入字符,因为询问最多只有2000个,所以就算极端情况也不会超时。
注意:sz和cnt其中一个要向上取整。用string类会超时。
1 #include <cstring> 2 #include <iostream> 3 #include <cstdio> 4 #include <string> 5 #include <cmath> 6 using namespace std; 7 char s[1010][5010]; 8 char str[1000010]; 9 int n, block[1010], sz, cnt; 10 11 void Build() { 12 sz = sqrt(n); 13 cnt = (n + sz - 1) / sz; // 记得向上取整, 因为这WA了一次 14 for(int i = 0; i < n; i++) s[i / sz + 1][block[i / sz + 1]++] = str[i]; 15 } 16 17 void Insert(char c, int p) { 18 int i; 19 for(i = 1; i <= cnt; i++) { 20 if(p - block[i] <= 0) break; 21 p -= block[i]; 22 } 23 if(i == cnt + 1) { s[cnt][block[cnt]++] = c; return ; } 24 block[i]++; 25 int len = strlen(s[i]); 26 for(int j = len - 1; j >= p - 1; j--) s[i][j+1] = s[i][j]; 27 s[i][p-1] = c; 28 } 29 30 void Query(int p) { 31 int i; 32 for(i = 1; i <= cnt; i++) { 33 if(p - block[i] <= 0) break; 34 p -= block[i]; 35 } 36 printf("%c ", s[i][p-1]); 37 } 38 39 int main() { 40 scanf("%s", str); n = strlen(str); 41 int q; scanf("%d", &q); 42 Build(); 43 while(q--) { 44 char op[3], c[3]; int num; 45 scanf("%s", op); 46 if(op[0] == 'I') { 47 scanf("%s%d", c, &num); 48 Insert(c[0], num); 49 } else { 50 scanf("%d", &num); 51 Query(num); 52 } 53 } 54 return 0; 55 }