社区讨论

玄学错误全 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 条回复,欢迎继续交流。

正在加载回复...