社区讨论
玄学错误全 WA 求调
P4008[NOI2003] 文本编辑器参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @m4cne7hw
- 此快照首次捕获于
- 2024/12/06 19:13 去年
- 此快照最后确认于
- 2025/11/04 13:16 4 个月前
rt.
CPP#include <bits/stdc++.h>
#define pii pair<int , int>
using namespace std;
const int blo = 2005 , N = 20000005;
int T , pool[blo << 2] , cnt = 0 , curpos;
pii cur;
char ans[N];
int read()
{
int f = 1 , res = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
res = res * 10 + ch - '0';
ch = getchar();
}
return f * res;
}
inline char read(char& x){x=getchar();while(x<'!') x=getchar();return x;}
inline string read(string& x){char ch;x.clear();read(ch);while(ch>='!') x+=ch,ch=getchar();return x;}
struct node
{
int siz , nxt;
char val[blo << 1];
};
node g[blo << 2];
int tot = 0;
int newnode() {return pool[cnt++];}
void del(int x) {pool[--cnt] = x;}
void add(int x , int y , int num , char c[])
{
if(y != -1)
{
g[y].nxt = g[x].nxt;
g[y].siz = num;
memcpy(g[y].val , c , num);
}
g[x].nxt = y;
}
void merge(int x , int y)
{
memcpy(g[x].val + g[x].siz , g[y].val , g[y].siz);
g[x].siz += g[y].siz;
g[x].nxt = g[y].nxt;
del(y);
}
pii find(pii pos)
{
int now = pos.first , sum = pos.second;
while(g[now].siz < sum)
{
sum -= g[now].siz;
now = g[now].nxt;
}
return {now , sum};
}
void split(pii pos)
{
pos = find(pos);
int now = pos.first , num = pos.second;
if(now == -1 || num == g[now].siz) return;
add(now , newnode() , g[now].siz - num , g[now].val + num);
g[now].siz = num;
}
void insert(int len , char s[])
{
cur = find(cur);
split(cur);
int now = cur.first;
int sum = 0 , ne = -1 , st = now;
while(sum + blo <= len)
{
ne = newnode();
add(now , ne , blo , s + sum);
sum += blo;
now = ne;
}
if(sum < len)
{
ne = newnode();
add(now , ne , len - sum , s + sum);
}
if(ne != -1 && g[now].siz + g[ne].siz < blo ) merge(now , ne) , ne = g[now].nxt;
if(g[st].siz + g[g[st].nxt].siz < blo && g[st].nxt != -1) merge(st , g[st].nxt);
}
void era(int len)
{
cur = find(cur);
split(cur);
pii p = find({g[cur.first].nxt , len});
split(p);
for(int i = g[cur.first].nxt ; i != g[p.first].nxt ; i = g[i].nxt) del(i);
g[cur.first].nxt = g[p.first].nxt;
while(g[cur.first].siz + g[g[cur.first].nxt].siz < blo && g[cur.first].nxt != -1) merge(cur.first , g[cur.first].nxt);
}
void getstr(int len)
{
cur = find(cur);
int now = cur.first , num = cur.second , sum = g[now].siz - num;
if(len < sum) sum = len;
memcpy(ans , g[now].val + num , sum);
int ne = g[now].nxt;
while(now != -1 && len >= sum + g[ne].siz)
{
memcpy(ans + sum , g[ne].val , g[ne].siz);
sum += g[ne].siz , ne = g[ne].nxt;
}
if(sum < len)
{
memcpy(ans + sum , g[ne].val , len - sum);
}
ans[len] = '\0';
cout << ans << '\n';
}
int main()
{
for(int i = 1 ; i < blo << 2 ; i++) pool[i] = i;
cnt = 1; g[0].siz = 0 , g[0].nxt = -1;
T = read();
while(T-->0)
{
string op;
read(op);
if(op == "Move")
{
curpos = read();
cur = {0 , curpos};
}
else if(op == "Insert")
{
int n;
n = read();
while((ans[0] = getchar()) == ' ');
for(int i = 1 ; i < n ; i++)
{
ans[i] = getchar();
if(ans[i] < 32) i--;
}
insert(n , ans);
}
else if(op == "Delete")
{
int n;
n = read();
era(n);
}
else if(op == "Get")
{
int n;
n = read();
getstr(n);
}
else if(op == "Prev")
{
cur = {0 , --curpos};
}
else
{
cur = {0 , ++curpos};
}
}
return 0;
}
实在做不出来看了眼题解,内存池比较像qwq
回复
共 3 条回复,欢迎继续交流。
正在加载回复...