BZOJ 1140 POI2009 KOD 編碼 DFS

BZOJ 1140 POI2009 KOD 編碼 DFS

題目大意：給定一棵二進制編碼樹，保證每個節點要麼有2個兒子，要麼沒有兒子，每個葉節點代表一個字符，求有多少字符滿足即使前面被刪掉一個前綴，只要這個字符的編碼沒有被破壞，就可以保證後面的編碼都解讀正確

先說下這個做法是可以被卡的……

首先我們可以發現這樣的字符滿足【編碼樹上根節點+任意一個後綴+一些完整的子串+這個字符的轉移都能到達一個葉節點】

然後打幾個標記爆搜就行了……

然而這樣做的復雜度是∑sizei的，當二叉樹很平衡的時候復雜度是O(nlogn)，親測可以卡到O(n2)

我覺得那個搜索可以用後綴自動機來優化一下……然而我太弱了
這個就交給後人吧233

啟示錄：
未來的人們啊= =
當你們看到這篇題解的時候，我應該還活著= =
希望你們能夠找到這道題的線性做法= =
233333……

#include 
#include 
#include 
#include 
#define M 1200100
using namespace std;
int n,tot;
int son[M][2];
char s[3003003];
int stack[M],top;
int a[M];
bool v1[M],v2[M],not_ans[M];
void DFS1(int p1,int p2)
{
    if(!son[p2][0])
    {
        if(!v1[p1])
            v1[p1]=true,stack[++top]=p1;
        return ;
    }
    if(!son[p1][0])
        return ;
    DFS1(son[p1][0],son[p2][0]);
    DFS1(son[p1][1],son[p2][1]);
}
void DFS2(int p1,int p2)
{
    if(!son[p2][0])
    {
        if(!v2[p1])
            v2[p1]=true,p2=1;
        else
            return ;
    }
    if(!son[p1][0])
    {
        if(p2!=1)
            not_ans[p1]=true;
        if(!v1[p2])
            v1[p2]=true,DFS2(1,p2);
        return ;
    }
    DFS2(son[p1][0],son[p2][0]);
    DFS2(son[p1][1],son[p2][1]);
}
int main()
{
    int i;
    cin>>n;
    scanf("%s",s+1);
    stack[++top]=++tot;
    for(i=1;i<=n;i++)
    {
        switch(s[i])
        {
            case '0':
                son[stack[top]][0]=++tot;
                stack[++top]=tot;
                break;
            case '1':
                son[stack[top]][1]=++tot;
                stack[++top]=tot;
                break;
            case 'X':
                a[++a[0]]=stack[top];
                break;
            case 'B':
                stack[top--]=0;
                break;
        }
    }

    /*
    for(i=1;i<=tot;i++)
        if(son[i][0])
        {
            printf("%d %d %d\n",i,son[i][0],0);
            printf("%d %d %d\n",i,son[i][1],1);
        }
    */

    for(i=2;i<=tot;i++)
        DFS1(1,i);
    while(top)
        DFS2(1,stack[top--]);
    for(i=1;i<=a[0];i++)
        if(!not_ans[a[i]])
            stack[++top]=i;
    cout<