2018icpc 沈阳网络赛 I Lattice's basics in digital electronics【哈夫曼编码】

#include <bits/stdc++.h>
using namespace std;
const int maxn=4e6+50;
char s[300][20];
char info[maxn];
int bin[maxn];
int fial[maxn];
int idx=0;
int M,N,Q;
int cnt=0;
int tot;
struct node
{
    int l,r,vis;
    char ch;
    void init()
    {
        l=-1;
        r=-1;
        vis=0;
    }
}tree[maxn];
void change()
{
    for(int i=0;i<N;i++)
    {
        char k = info[i];
        int t = 0;
        if(k>='A'&&k<='F')  t = 10+ k-'A';
        else if(k>='a'&&k<='f')  t = 10+ k-'a';
        else t = k-'0';
        for(int j=3;j>=0;j--)
        {
            int num = i*4+j;
            int q=t%2;
            t = t/2;
            bin[num]= q;
        }
    }
    /*for(int i=0;i<N*4;i++)
    {
        printf("%d ",bin[i]);
        if((i+1)%9==0)cout<<endl;
    }
    cout<<endl;*/
    int cnt1,cnt2;
    for(int i=0;i<4*N;i+=9)
    {
        //cout<<i<<" "<<endl;
        if(i+9>4*N)break;
        //cout<<i<<endl;
        cnt1=0;
        cnt2=0;
        for(int j=0;j<8;j++)
        {
            int p = i+j;
            fial[idx++]=bin[p];
            if(bin[p]%2) cnt1++;
            else cnt2++;
        }
        if(bin[i+8]==1&&(cnt1%2))
            idx-=8;
        if(bin[i+8]==0&&!(cnt1%2))
            idx-=8;
        //cout<<i<<" "<<idx<<" "<<endl;
    }
    /*for(int i=0;i<idx;i++)
    {
        printf("%d ",fial[i]);
        if((i+1)%8==0) printf("\n");
    }*/

}
void add(char ch[],char k)
{
    int len =strlen(ch);
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(ch[i]=='0')
        {
            int next=tree[now].l;
            if(next==-1)
            {
                next=++tot;
                tree[next].init();
                tree[now].l=next;
            }
            now=next;
        }
        if(ch[i]=='1')
        {
            int next = tree[now].r;
            if(next==-1)
            {
                next=++tot;
                tree[next].init();
                tree[now].r =next;
            }
            now = next;
        }
    }
    tree[now].ch = k;tree[now].vis = 1;
}
void decode()
{
    int now=0;
    for(int i=0;i<idx;i++)
    {
        if(cnt>=Q)break;

        if(fial[i]==1)
        {
            if( tree[now].r==-1&&(cnt<Q))
            {
                cnt++;
                printf("%c",tree[now].ch);now=0;
                i-=1;
            }
            else now = tree[now].r;
        }
        else if(fial[i]==0)
        {
            if(tree[now].l==-1&&(cnt<Q))
            {
                cnt++;
                printf("%c",tree[now].ch);now=0;
                i-=1;
            }
            else now = tree[now].l;
            }
    }
    if(now)
    {
        if(tree[now].vis)
        printf("%c",tree[now].ch);
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        tot=0;
        tree[0].init();
        idx=0;
        cnt=0;
        memset(bin,0,sizeof(bin));
        memset(fial,0,sizeof(fial));
        scanf("%d%d",&Q,&M);
        for(int i=1;i<=M;i++)
        {
            int x;
            scanf("%d",&x);
            char t=x;
            //printf("%c\n",t);
            scanf("%s",&s[x]);
            add(s[x],t);
        }
        scanf("%s",info);
        N=strlen(info);
        change();
        decode();
        printf("\n");
    }
    return 0;
}