编程知识 购物 网址 新闻 笑话 | 软件 日历 阅读 图书馆 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
   -> C++ -> BZOJ1269: [AHOI2006]文本编辑器editor -> 正文阅读

[C++]BZOJ1269: [AHOI2006]文本编辑器editor

1269: [AHOI2006]文本编辑器editor Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4671  Solved: 1801
[Submit][Status][Discuss] Description
这些日子,可可不和卡卡一起玩了,原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗?为了明确任务目标,可可对“文本编辑器”做了一个抽象的定义: 
 
 文本:由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内,也就是说,这些字符均为可见字符或空格。光标:在一段文本中用于指示位置的标记,可以位于文本的第一个字符之前,文本的最后一个字符之后或文本的某两个相邻字符之间。文本编辑器:为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空,我们就说这个文本编辑器是空的。 编写一个程序:? 建立一个空的文本编辑器。? 从输入文件中读入一些操作指令并执行。? 对所有执行过的GET操作,将指定的内容写入输出文件。
Input
输入文件中第一行是指令条数N,以下是需要执行的N个操作。除了回车符之外,输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。
Output
依次对应输入文件中每条GET指令的输出,不得有任何多余的字符。
Sample Input
10
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
editor
Move 0
Get
Move 11
Rotate 4
Get
Sample Output
B
t
HINT
对输入数据我们有如下假定:? MOVE操作不超过50 000个,INSERT、DELETE和ROTATE操作作的总个数不超过6 000,GET操作不超过20 000个,PREV和NEXT操作的总个数不超过20 000。? 所有INSERT插入的字符数之和不超过2M(1M=1 024*1 024)。? DELETE操作、ROTATE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作不会把光标移动到非法位置。? 输入文件没有错误。
Source
鸣谢seter重新制作数据
[Submit][Status][Discuss]
HOME Back
MDZZ块状链表好恶心。。
也没啥好讲的,就是个大暴力
不过网上好像没多少资料
有空整理一下吧

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 using namespace std;
  7 const int MAXN=2000000+10;
  8 const int BlockSize=3000 + 100,BlockNum=3000 + 10;
  9 int Cur=0,head,tot;
 10 char str[MAXN];
 11 struct Block
 12 {
 13     int size,nxt;
 14     bool rev;
 15     char a[BlockSize];
 16     void Clear()
 17     {
 18         size=0;nxt=-1,rev=0;
 19     }
 20 }B[BlockNum];
 21 queue<int>q;//鐢ㄤ竴涓槦鍒楁潵缁存姢褰撳墠鏈夊摢浜涘潡
 22 int NewNode()
 23 {
 24     int t=q.front();q.pop();
 25     B[t].Clear();
 26     return t;
 27 }
 28 inline void Pre()
 29 {
 30     while(q.size()!=0)    q.pop();
 31     for(int i=0;i<BlockNum;i++) q.push(i);
 32     head = NewNode();
 33 }
 34 void Find(int &idx,int &cur)
 35 {
 36     while(idx!=-1&&cur>B[idx].size) cur-=B[idx].size,idx=B[idx].nxt;
 37 }
 38 void Pushdown(int idx)
 39 {
 40     if(B[idx].rev) 
 41     {
 42     //    for(int i=0;i<B[idx].size;i++)
 43     //        cout<<B[idx].a[i];cout<<endl;
 44         reverse(B[idx].a,B[idx].a+B[idx].size);
 45     //    for(int i=0;i<B[idx].size;i++)
 46     //        cout<<B[idx].a[i];cout<<endl;
 47         B[idx].rev=0;
 48     }
 49         
 50 }
 51 inline void Split(int idx,int cur)
 52 {
 53     if(idx==-1||cur==B[idx].size)    return ;
 54     Pushdown(idx);
 55     int tot=NewNode();
 56     memcpy(B[tot].a,B[idx].a+cur,sizeof(char) * (B[idx].size-cur) );
 57     B[tot].size=B[idx].size-cur;
 58     B[idx].size=cur;
 59     B[tot].nxt=B[idx].nxt;
 60     B[idx].nxt=tot;
 61 }
 62 void Delet(int idx)
 63 {
 64     q.push(idx);
 65 }
 66 void Merge(int idx)
 67 {
 68     for(int i=idx;i!=-1;i=B[i].nxt)
 69         for(int j=B[i].nxt;j!=-1;j=B[j].nxt)
 70         {
 71             if(B[i].size+B[j].size<=BlockSize)
 72             {
 73                 Pushdown(i);
 74                 Pushdown(j);
 75                 memcpy(B[i].a+B[i].size,B[j].a,sizeof(char) * B[j].size);
 76                 B[i].size+=B[j].size;B[i].nxt=B[j].nxt;
 77                 Delet(j);
 78             }
 79             else break;
 80         }
 81 }
 82 inline void Insert(int cur,int x,char *str)
 83 {
 84     int idx=head;
 85     Find(idx,cur);
 86     Split(idx,cur);
 87     int i=0;//宸茬粡鍔犲叆鐨勪釜鏁?
 88     while(i<x)
 89     {
 90         int Limit=min(BlockSize,x-i);
 91         int tot=NewNode();
 92         memcpy(B[tot].a,str+i,sizeof(char) * Limit);
 93         B[tot].size=Limit;
 94         B[tot].nxt=B[idx].nxt;
 95         B[idx].nxt=tot;
 96         idx=B[idx].nxt;
 97         i+=Limit;
 98     }
 99     Merge(head);
100 }
101 void Print(int cur)
102 {
103     int idx=head;
104     Find(idx,cur);
105     if(cur==B[idx].size) idx=B[idx].nxt,cur=0;
106     Pushdown(idx);
107     printf("%c\n",B[idx].a[cur]);
108 }
109 void Rever(int l,int r)
110 {
111     int idx=head;
112     Find(idx,l);
113     Split(idx,l);
114     int Start=idx,StartNxt=B[idx].nxt;
115     idx=head;
116     Find(idx,r);
117     Split(idx,r);
118     int EndNxt=B[idx].nxt;
119     int Tmp[BlockNum],cnt=0;
120     for(int i=StartNxt;i!=EndNxt;i=B[i].nxt)
121         B[i].rev^=1,Tmp[++cnt]=i;
122     Tmp[++cnt]=Start;Tmp[0]=EndNxt;
123     for(int i=cnt;i>=1;i--)
124         B[Tmp[i]].nxt=Tmp[i-1];
125     Merge(head);
126 }
127 void Dele(int l,int r)
128 {
129     int idx=head;
130     Find(idx,l);
131     Split(idx,l);
132     int Start=idx,StartNxt=B[idx].nxt;
133     idx=head;
134     Find(idx,r);
135     Split(idx,r);
136     int EndNxt=B[idx].nxt;
137     for(int i=StartNxt;i!=EndNxt;i=B[i].nxt)    Delet(i);
138     B[Start].nxt=EndNxt;
139     Merge(head);
140 }
141 int main()  
142 {
143     #ifdef WIN32
144     freopen("a.in","r",stdin);
145     #else
146     #endif
147     int N;scanf("%d",&N);
148     char opt[20];
149     Pre();
150     while(N--)
151     {
152         scanf("%s",opt);
153         if(opt[0]=='M') 
154             scanf("%d",&Cur);
155         else if(opt[0]=='I')
156         {
157             int len;
158             scanf("%d", &len);
159             int i = 0;
160             while(i < len) {char ch = getchar();if(ch >= 32 && ch <= 126) str[i++] = ch;}
161             str[i++] = '\0';
162             Insert(Cur,len,str);
163         }
164         else if(opt[0]=='D')
165         {
166             int x;
167             scanf("%d",&x);
168             Dele(Cur,Cur+x);
169         }
170         else if(opt[0]=='R')
171         {
172             int x;
173             scanf("%d",&x);
174             Rever(Cur,x+Cur);
175         }
176         else if(opt[0]=='G')    
177             Print(Cur);
178         else if(opt[0]=='P')    Cur--;
179         else if(opt[0]=='N')    Cur++;
180     }
181     return 0;
182 }

  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
POJ 2987 Firing
树的重心
第一章 作业7.
【左神算法课】超经典:求两单向链表交点(
上一篇文章      下一篇文章      查看所有文章
加:2017-12-09 23:28:03  更:2017-12-09 23:28:12 
 
360图书馆 软件开发资料 购物精选 新闻资讯 Chinese Culture 三丰软件 开发 中国文化 阅读网 日历 万年历 2019年12日历
2019-12-8 18:35:29
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程知识