15北京网络赛 B题
题目描述：
题目2 : Mission Impossible 6
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
Perhaps you've watched the highly regarded movie series, Mission Impossible, spanning from its debut in 1996 through its fourth installment. Now, Mission Impossible 5 is screening in China. Mr. Tom Cruise, a seasoned actor and now also delving into programming studies through my MOOC course, in hopes of scoring top grades, wanted me to reveal the plot of Mission Impossible 6 by compelling him to share his knowledge about this upcoming film.
In “Mission Impossible 6”, 埃登·霍特冒险去坏老板的房间安装一个小摄像头以偷看坏老板在电脑上工作的内容。不幸的是，在搬动桌子获取更多阳光后，在之后 埃登无法通过摄像头看到电脑屏幕；幸运的是他能看到键盘输入的内容。因此 埃登想通过观察坏老板键盘输入的内容来了解他在电脑上写了什么工作——这个工作既不刺激又不危险——所以对于埃登来说真的难以实现——这也是为什么汤姆·克鲁斯想要学习编程的原因
To simplified the problem, we assume that Bad Boss is editing a one line document, and the document consists of only lowercase letters. At first, there are nothing in the text editor window except a caret blinking at the left-most position (the starting position of the line). When Bad Boss input a lowercase letter, the letter appears at the right side of the caret, and then the caret moves to the right side of the letter just inputted. The text editor can switch between “insert mode” and “overwrite mode”. When it’s in “overwrite mode”, the newly inputted letter will overwrite the letter which is on the right of the caret(if there is one). If it’s in “insert mode”, the newly inputted letter will be inserted before the letter which is originally on the right of the caret.
Additionally, Bad Boss is capable of performing certain operations through the input of uppercase letters, as mentioned below.
'L' : Shifts the caret to the left by one character. If the caret is already at the beginning of the line, no movement occurs.
A rightward shift operation 'R' shifts the caret to move one letter to its right. When reaching or being positioned at the end of a line segment, it signifies that there are no more letters to its immediate right, so this operation does not advance or execute.
'S': 切换在'overWrite模式'与'inser模式'之间. 开始时处于'inser模式'状态.
‘D’: Remove a letter that is on the right side of the caret. When the caret is at the end of the line, no action occurs. Additionally, operation 'D' has another effect detailed in operation 'C'.
Delete a letter that is adjacent to the caret. If there is no character before the caret, nothing will be deleted.
对应键盘上的' C '键的功能是执行复制操作到剪贴板中。最初状态下，在剪贴板中没有任何内容，并且编辑器中的' 复制状态'字段被设置为' NOTHING '。当按下' C '键时：
If the copy status was "NOTHING", the copy status will become "START", and its current position will be recorded as "copy position 1".
When the copy status is set to "START," it will be reset to "NOTHING." The portion of text between the current caret position and the saved "copy position 1" will then be copied into the clipboard. If there was existing content in the clipboard, it will be overwritten. If both positions are identical, the clipboard contents will be cleared.
Please pay attention to the following: When the copy status is set to "START", unless any letter other than 'L', 'R', or 'D' is typed, the copy status will immediately transition to "NOTHING" without affecting the currently selected character, which functions as per its designated role. Specifically, if a 'D' key is pressed while the copy status is "START", it will cause an immediate transition to "NOTHING", resulting in the deletion of all characters located between the current cursor position and "copy position 1".
‘V’: 将内容复制到剪贴板右侧并粘贴到光标所在位置的右侧。若剪贴板中无内容，则操作无效；在插入模式下会将粘贴内容插入当前光标位置之后；若处于覆盖模式且剪贴板中有k个字符，则前k个字符将被覆盖；若右侧字符数量少于k，则所有右侧字符也将被替换为剪贴板中的相应字符；完成粘贴操作后光标将移动至最后一个粘贴字符右侧。
The 该文本行的内容将始终保持在M个字母以内. 如果这些输入将导致内容超过M个字母，则必须予以忽略. 当复制粘贴时, 您要么复制所有内容到剪贴板中, 要么因文字长度限制而不进行任何复制操作.
输入
The initial line of the input represents an integer T (where T ≤ 20), signifying that there are T test cases. The subsequent lines come after, and each of these lines contains a test case.
For each test case:
An integer M (where 0 ≤ M ≤ 10,000) is defined as representing the text length constraint. This parameter characterizes the inputs made by a so-called bad boss in each test case. The letter count for each test case cannot exceed 10,000.
输出
For each test case, output the result that Bad Boss obtains. If the result is absent, output “NOTHING”.
样例输入
8；
八；
五；
十五；
十位数为一五；
二十位为一五七七；
二十位为一五七七；
三十位为一三二二二二四四零零零零零零四四四四四四九九九九九九九九九九；
二十位为一三二二二二六六六六六六七七七七七七八八八八八八一；
二十位为一三二二二二六六六六六六七七七seven seven seven seven seven seven seven seven seven seven seven sevenseven eight eight eight eight eight oneoneoneoneoneoneoneone;
三十位为一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一;
十位数为十
样例输出
abe
abkjc
axz
abcdxkuyz
abcdekfekfgg
abcdeekfg
abcdedeabkz
NOTHING
题解：
模拟题,用链表来模拟就好.注意链表的操作和一些奇怪的要求.
重点：
主代码手啊…你一定要练习代码的实现水平!!
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctype.h>
#include <limits.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#define CLR(a) memset(a, 0, sizeof(a))
#define REP(i, a, b) for(int i = a;i < b;i++)
#define REP_D(i, a, b) for(int i = a;i <= b;i++)
typedef long long ll;
using namespace std;
const int maxn = 1e6 + 100;
struct node
{
char c;
int pre, nex;
node(char _c = '0', int _pre = 0, int _nex = 0)
{
c = _c;
pre = _pre;
nex = _nex;
}
};
node a[maxn];
int tot, M, cnt;
// modol 0 is insert, 1 is replace; sta 0 is nothing, 1 is start;
int modol, sta, oldPos, nowPos;
char clipbord[maxn];
int clipbordN;
int newNode(char _c = '0')
{
if(tot!=0)
cnt++;
a[tot].pre = -1;//新添加的node一定要搞成-1
a[tot].nex = -1;
a[tot].c = _c;
tot++;
return tot-1;
}
int findNext(int l, int r)//找l后面是否有r
{
int now = l;
while(now != -1)
{
if(now == r)
return 1;
now = a[now].nex;
}
return 0;
}
void del(int pos)//把pos删掉,同时记得cnt-1,删的时候会影响3个点,注意********
{
cnt--;
int pre = a[pos].pre;
int nex = a[pos].nex;
if(pre!=-1)
a[pre].nex = nex;
if(nex!=-1)
a[nex].pre = pre;
}
void del(int oldpos, int nowpos)//删一堆点,注意方向.和涉及到的相邻的点
{
if(!findNext(oldpos, nowpos))
swap(oldpos, nowpos);
if(oldpos==nowpos)
return;
int tmppos = oldpos;
oldpos = a[oldpos].nex;
int now = oldpos;
while(1)
{
cnt--;
if(now == nowpos)
break;
now = a[now].nex;
}
int pre = a[oldpos].pre;
int nex = a[nowpos].nex;
if(pre!=-1)
a[pre].nex = nex;
if(nex!=-1)
a[nex].pre = pre;
}
void lMove()//移动光标
{
if(a[nowPos].pre != -1)
nowPos = a[nowPos].pre;
}
void rMove()
{
if(a[nowPos].nex != -1)
nowPos = a[nowPos].nex;
}
void switc()
{
modol = 1-modol;
sta = 0;
}
void dDelete()//题目中的删
{
if(sta == 0)
{
if(a[nowPos].nex != -1)
{
del(a[nowPos].nex);
}
}
else
{
sta = 0;
del(oldPos, nowPos);
}
}
void bDelete()
{
int tmppos = a[nowPos].pre;
if(nowPos!=0)
{
del(nowPos);
nowPos = tmppos;
}
sta = 0;
}
void touchC()
{
if(sta == 0)
{
sta = 1;
oldPos = nowPos;
}
else
{
sta = 0;
int nowoldpos = oldPos, nownowpos = nowPos;
if(findNext(nowoldpos, nownowpos)==0)//找到
swap(nowoldpos, nownowpos);
clipbordN = 0;//拷贝
if(nowoldpos==nownowpos)
return;
nowoldpos = a[nowoldpos].nex;
while(1)
{
clipbord[clipbordN] = a[nowoldpos].c;
clipbordN++;
if(nowoldpos==nownowpos)
break;
nowoldpos = a[nowoldpos].nex;
}
}
}
int addNode(int now, char c, int modol)//添加节一共会涉及到三个节点,注意注意**************
{
if(modol==0||a[now].nex==-1)
{
int id = newNode(c);
int nownex = a[now].nex;
if(nownex!=-1)
a[nownex].pre = id;
a[id].nex = a[now].nex;
a[id].pre = now;
a[now].nex = id;
now = id;
}
else
{
now = a[now].nex;
a[now].c = c;
}
return now;
}
void in(char c)
{
sta = 0;
if(modol==0 || a[nowPos].nex == -1)
{
if(cnt+1<=M)
nowPos = addNode(nowPos, c, 0);
}
else
{
nowPos = addNode(nowPos, c, 1);
}
}
void paste()
{
sta = 0;
if(modol==0)
{
if(cnt+clipbordN<=M)
{
for(int i = 0; i<clipbordN; i++)
{
nowPos = addNode(nowPos, clipbord[i], 0);
}
}
}
else
{
int tmp = 0, tmpnow = a[nowPos].nex;
while(tmpnow!=-1)
{
tmp++;
tmpnow = a[tmpnow].nex;
}
if(cnt+clipbordN-tmp<=M)
{
for(int i = 0; i<clipbordN; i++)
{
nowPos = addNode(nowPos, clipbord[i], 1);
}
}
}
}
char str[maxn];
void solve()
{
tot = 0;
nowPos = newNode();
modol = 0;
sta = 0;
clipbordN = 0;
cnt = 0;
int n = strlen(str);
for(int i = 0; i<n; i++)
{
if(str[i] >= 'a' && str[i] <= 'z')
in(str[i]);
if(str[i] == 'L')
lMove();
if(str[i] == 'R')
rMove();
if(str[i] == 'S')
switc();
if(str[i] == 'D')
dDelete();
if(str[i] == 'B')
bDelete();
if(str[i] == 'C')
touchC();
if(str[i] == 'V')
paste();
// printf("------------i is %d-----------\n", i);
// int now = a[0].nex;
// while(now!=-1)
// {
// putchar(a[now].c);
// now = a[now].nex;
// }
// printf("\n");
// printf("now is %c\n", a[nowPos].c);
}
if(a[0].nex==-1)
printf("NOTHING\n");
else
{
int now = a[0].nex;
while(now!=-1)
{
putchar(a[now].c);
now = a[now].nex;
}
printf("\n");
}
}
int main()
{
//freopen("3Cin.txt", "r", stdin);
//freopen("3Cout.txt", "w", stdout);
int ncase;
scanf("%d", &ncase);
while(ncase--)
{
scanf("%d %s", &M, str);
solve();
}
return 0;
}