WA #2 求调
查看原帖
WA #2 求调
421987
lizihan250楼主2025/7/31 21:39

如题,代码如下所示。

大致的思路是,用字典树维护,对于每个节点,尝试求出在它这里进行 Tab 操作会跳到哪里(不妨称为“跳转坐标”)。具体的,对于每个节点,若它是一个指令的结尾或它的多个子节点上传跳转坐标,则该点的跳转坐标为自己;否则,“跳转坐标”记为其子节点的“跳转坐标”。

看了一眼发现自己会做直接开做,没想到调了 1.5h 还是调不出来。在这里还是告诫各位选手要懂得取舍,不然只会让自己陷入分数与心态的双重两难境地。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=100000,Maxm=5000000,Maxlen=1000000,Maxp=26;
int n,m,cnt=0;
string s,nw;
struct node
{
    int nt,fa,p;
    bool tag;
    int suf[Maxp+2];
}nums[Maxlen+10];
void dfs(int u)
{
    int res=0;
    for(int i=0;i<Maxp;i++)
    {
        if(nums[u].suf[i]==0) continue;
        dfs(nums[u].suf[i]);
        if(res==0) res=nums[nums[u].suf[i]].nt;
        else res=u;
    }
    if(nums[u].tag) res=u;
    nums[u].nt=res;
    return;
}
void check(int u,string txt)
{
    cout<<u<<" "<<txt<<":"<<endl;
    cout<<nums[u].nt<<" "<<nums[u].fa<<" "<<nums[u].p<<" "<<nums[u].tag<<endl;
    /*for(int i=0;i<Maxp;i++)
        if(nums[u].suf[i]!=0) cout<<char(i+'a')<<" "<<nums[u].suf[i]<<endl;*/
    for(int i=0;i<Maxp;i++)
        if(nums[u].suf[i]!=0) check(nums[u].suf[i],txt+char(i+'a'));
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        int ptr=0;
        for(char c:s)
        {
            if(nums[ptr].suf[c-'a']!=0) ptr=nums[ptr].suf[c-'a'];
            else
            {
                cnt++;
                nums[ptr].suf[c-'a']=cnt;
                nums[cnt].fa=ptr;
                ptr=cnt;
            }
        }
        nums[ptr].tag=true;
        nums[ptr].p=i;
    }
    dfs(0);
    //check(0,"");
    cin>>s;
    int ptr=0,over=0;
    for(char c:s)
    {
        if('a'<=c&&c<='z')
        {
            if(over>0||nums[ptr].suf[c-'a']==0) over++;
            else ptr=nums[ptr].suf[c-'a'];
        }
        else if(c=='B')
        {
            if(over>0) over--;
            else if(ptr!=0) ptr=nums[ptr].fa;
        }
        else if(c=='T') {if(over==0) ptr=nums[ptr].nt;}
        else
        {
            if(over==0&&nums[ptr].tag) cout<<nums[ptr].p<<" ";
            else cout<<-1<<" ";
            ptr=over=0;
        }
        //cout<<ptr<<" "<<over<<endl;
    }
    return 0;
}
2025/7/31 21:39
加载中...