本文主要是介绍POJ 2887：Big String ← 块状链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目来源】
http://poj.org/problem?id=2887
【题目描述】
You are given a string and supposed to do some string manipulations.
【输入格式】
The first line of the input contains the initial string. You can assume that it is non-empty and its length does not exceed 1,000,000.
The second line contains the number of manipulation commands N (0 < N ≤ 2,000). The following N lines describe a command each. The commands are in one of the two formats below:
（1）I ch p: Insert a character ch before the p-th character of the current string. If p is larger than the length of the string, the character is appended to the end of the string.
（2）Q p: Query the p-th character of the current string. The input ensures that the p-th character exists.
All characters in the input are digits or lowercase letters of the English alphabet.
【输出格式】
For each Q command output one line containing only the single character queried.
【输入样例】
ab
7
Q 1
I c 2
I d 4
I e 2
Q 5
I f 1
Q 3
【输出样例】
a
d
e
【算法分析】
● 顾名思义，块状链表=分块+链表，或者理解为用链表串起来的分块。根据对分块最优性的思思，n 个数据分为 sqrt(n) 块，每块 sqrt(n) 个数据。
● 块状链表结合了数组与链表的优势，优化了计算复杂度。
● POJ 不支持万能头文件 #include <bits/stdc++.h>。
● 针对错误提示 error C2668: 'sqrt' : ambiguous call to overloaded function 的解决方法，就是将代码 sz=sqrt(n); 中的 n 进行强制类型转换，修改为 sz=sqrt((double)n); 即可。
【算法代码一】
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;const int maxn=1e6+5;
const int maxm=1e3+5;
char str[maxn];
int block[maxm];
char ch[maxm][5*maxm];
int n,sz,cnt;void build() {sz=sqrt((double)n);cnt=(n+sz-1)/sz; //向上取整for(int i=0; i<n; i++) {ch[i/sz+1][block[i/sz+1]++]=str[i];}
}void insert(char c, int p) {int i;for(i=1; i<=cnt; i++) {if(p-block[i]<=0) break;p-=block[i];}if(i==cnt+1) {ch[cnt][block[cnt]++]=c;return ;}block[i]++;int len=strlen(ch[i]);for(int j=len-1; j>=p-1; j--) ch[i][j+1]=ch[i][j];ch[i][p-1]=c;
}void query(int p) {int i;for(i=1; i<=cnt; i++) {if(p-block[i]<=0) break;p-=block[i];}cout<<ch[i][p-1]<<endl;
}int main() {cin>>str;n=strlen(str);int T;cin>>T;build();while(T--) {char op, c;int num;cin>>op;if(op=='I') {cin>>c>>num;insert(c, num);} else {cin>>num;query(num);}}return 0;
}/*
in:
ab
7
Q 1
I c 2
I d 4
I e 2
Q 5
I f 1
Q 3out:
a
d
e
*/
【算法代码二】
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;const int maxn=1e6+5;
const int maxm=1e3+5;
char str[maxn];
int block[maxm];
char ch[maxm][5*maxm];
int n,sz,cnt;void build() {sz=sqrt((double)n);cnt=(n+sz-1)/sz; //向上取整for(int i=0; i<n; i++) {ch[i/sz+1][block[i/sz+1]++]=str[i];}
}void insert(char c, int p) {int i;for(i=1; i<=cnt; i++) {if(p-block[i]<=0) break;p-=block[i];}if(i==cnt+1) {ch[cnt][block[cnt]++]=c;return ;}block[i]++;int len=strlen(ch[i]);for(int j=len-1; j>=p-1; j--) ch[i][j+1]=ch[i][j];ch[i][p-1]=c;
}void query(int p) {int i;for(i=1; i<=cnt; i++) {if(p-block[i]<=0) break;p-=block[i];}printf("%c\n", ch[i][p-1]);
}int main() {scanf("%s", str);n=strlen(str);int T;scanf("%d", &T);build();while(T--) {char op[3], c[3];int num;scanf("%s", op);if(op[0]=='I') {scanf("%s %d", c, &num);insert(c[0], num);} else {scanf("%d", &num);query(num);}}return 0;
}/*
in:
ab
7
Q 1
I c 2
I d 4
I e 2
Q 5
I f 1
Q 3out:
a
d
e
*/
【参考文献】
https://www.cnblogs.com/fightfordream/p/6565816.html
https://blog.csdn.net/hnjzsyjyj/article/details/138955263
https://oi-wiki.org/ds/block-list/
https://www.cnblogs.com/nancheng58/p/10068136.html
这篇关于POJ 2887：Big String ← 块状链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
