1507: [NOI2003]Editor(块状链表)
2024-10-15 20:42:05
1507: [NOI2003]Editor
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 4157 Solved: 1677
[Submit][Status][Discuss]
Description
Input
输入文件editor.in的第一行是指令条数t,以下是需要执行的t个操作。其中: 为了使输入文件便于阅读,Insert操作的字符串中可能会插入一些回车符,请忽略掉它们(如果难以理解这句话,可以参考样例)。 除了回车符之外,输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。 这里我们有如下假定: MOVE操作不超过50000个,INSERT和DELETE操作的总个数不超过4000,PREV和NEXT操作的总个数不超过200000。 所有INSERT插入的字符数之和不超过2M(1M=1024*1024),正确的输出文件长度不超过3M字节。 DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。 输入文件没有错误。 对C++选手的提示:经测试,最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。
Output
输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。
Sample Input
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 15
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 15
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
Sample Output
.\/.
abcde^_^f.\/.ghijklmno
abcde^_^f.\/.ghijklmno
code
#include<cstdio>
#include<cstring> const int MAXL = ;
const int Block_size = ;
const int Block_num = ;
int Number[Block_num],Tot;
int nxt[Block_num],siz[Block_num];
char data[Block_num][Block_size];
char str[MAXL],s[]; void Init() {
for (int i=; i<Block_num; ++i)
Number[i] = i;
Tot = ;
nxt[] = -;siz[] = ;
}
int Getnum() {
return Number[Tot++];
}
void Delnum(int x) {
Number[--Tot] = x;
}
int find(int &pos) {
int k = ;
while (k != - && pos > siz[k]) {
pos -= siz[k];
k = nxt[k];
}
return k;
}
void Madenews(int cur,int news,int num,char str[]) {
if (news!=-) {
nxt[news] = nxt[cur];
siz[news] = num;
memcpy(data[news],str,num);
}
nxt[cur] = news;
}
void split(int cur,int pos) {
if (cur==- || pos==siz[cur]) return ;
int news = Getnum();
Madenews(cur,news,siz[cur]-pos,data[cur]+pos);
siz[cur] = pos;
}
void Merge(int x,int y) {
memcpy(data[x]+siz[x],data[y],siz[y]);
siz[x] += siz[y];
nxt[x] = nxt[y];
Delnum(y);
}
void Maintain() {
int cur = ;
while (cur != -) {
int p = nxt[cur];
while (p != - && siz[cur] + siz[p] <= Block_size) {
Merge(cur,p);
p = nxt[cur];
}
cur = nxt[cur];
}
}
void Insert(int pos,int num,char str[]) {
int cur = find(pos);
split(cur,pos);
int cnt = ;
while (cnt + Block_size <= num) {
int news = Getnum();
Madenews(cur,news,Block_size,str+cnt);
cur = news;
cnt += Block_size;
}
if (num - cnt) {
int news = Getnum();
Madenews(cur,news,num-cnt,str+cnt);
}
Maintain();
}
void Erase(int pos,int num) {
int cur = find(pos);
split(cur,pos);
int p = nxt[cur];
while (p != - && num > siz[p]) {
num -= siz[p];
p = nxt[p];
}
split(p,num);
p = nxt[p];
for (int i=nxt[cur]; i!=p; i=nxt[cur]) {
nxt[cur] = nxt[i];
Delnum(i);
}
Maintain();
}
void Getdata(int pos,int num,char str[]) {
int cur = find(pos);
int cnt = siz[cur] - pos;
if (num < cnt) cnt = num;
memcpy(str,data[cur]+pos,cnt);
int tmp = nxt[cur];
while (tmp!=- && cnt+siz[tmp] <= num) {
memcpy(str+cnt,data[tmp],siz[tmp]);
cnt += siz[tmp];
tmp = nxt[tmp];
}
if (num - cnt && tmp != -)
memcpy(str+cnt,data[tmp],num-cnt);
str[num] = '\0';
}
int main() {
Init();
int Nowpos = ,opt,num;
scanf("%d",&opt);
while (opt) {
opt--;
scanf("%s",s);
if (s[]=='M') scanf("%d",&Nowpos);
else if (s[]=='I') {
scanf("%d",&num);
for (int i=; i<num; ++i) {
scanf("%c",&str[i]);
if (str[i]< || str[i]>) --i;
}
Insert(Nowpos,num,str);
}
else if (s[]=='D') {
scanf("%d",&num);
Erase(Nowpos,num);
}
else if (s[]=='G') {
scanf("%d",&num);
Getdata(Nowpos,num,str);
printf("%s\n",str);
}
else if (s[]=='P') --Nowpos;
else ++Nowpos;
}
return ;
}
最新文章
- For Freedom —— 代理篇
- myeclipse2014
- php的字符串处理函数
- 一个利用sed和awk处理文本的小栗子
- UVa 12304 (6个二维几何问题合集) 2D Geometry 110 in 1!
- windows8安装xna4.0不能开发Xbox和PC端游戏的解决办法
- Delphi中的THashTable
- Brew install for mac
- JavaSE学习总结第05天_Java语言基础1
- 数据仓库搭建——Inmon与Kimball
- 获取JSON对象的属性名称
- zTree:一个依靠 jQuery 实现的多功能 “树插件”
- 实战一个职业技术学校。 by:hack某某
- echarts的axisLabel的文字内容过长的解决办法
- session持久化到sqlserver
- 【已解决】在 Visual Studio 中设置 JavaScript/TypeScript 的断点 脚本出现自动中断错误
- java concurrent 中ExecutorService和CompletionService简单区别
- PHP 如何获取二维数组中某个key的集合(高性能查找)
- Java学习-1
- Shell检查程序是否正常,并显示出程序启动时间、执行时间
热门文章
- css hack 浏览器携带自身特有的属性 (二)
- 织梦DEDECMS会员中心发布文章修改提示"数据校验不对,程序返回"
- RSA_new()初始化和RSA_free()释放RSA结构体后依然会有内存泄漏(转)
- Outlook 2016 自动发送/接收无法正常工作
- 使用jmeter测试数据库性能
- 转 winfrom如何通过http来进行通信,并且通过传递json格式的数据可接受json格式的数据
- hiho一下 第四十四周 博弈游戏&#183;Nim游戏(直接公式解)
- 洛谷 P2895 [USACO08FEB]流星雨Meteor Shower
- ACM博弈论基础
- 字符编码:BSTR