【ACM-ICPC 2018 沈阳赛区网络预赛 I】Lattice's basics in digital electronics

【题解】

每个单词的前缀都不同。
不能更明示了...
裸的字典树。
模拟一下。输出一下就ojbk了。

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x)

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int NN = 10000;

const int SI = 10;

const int N = 2e5;

int ch[NN+10][2],flag[NN+10];

int tot,m,n;

char si[SI+10];

char s[N+10];

int result[N*4+10],cur;

void ins(int ci){

    int len = strlen(si);

    int now = 1;

    for (int i = 0;i < len;i++){

        if (ch[now][si[i]-'0']==0){

            ch[now][si[i]-'0'] = ++tot;

        }

        now = ch[now][si[i]-'0'];

    }

    flag[now] = ci;

}

void cl(char key){

    cur++;

    int num = 0;

    if (key>='a' && key<='z'){

        key = key-'a'+'A';

    }

    if (key>='A' && key<='Z'){

        num+=key-'A'+10;

    }else num = key-'0';

    for (int i = cur+3;i>=cur;i--){

        result[i] = num&1;

        num/=2;

    }

    cur = cur+3;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

	int T;

    cin >> T;

    while (T--){

        memset(ch,0,sizeof ch);

        memset(flag,255,sizeof flag);

        tot = 1;

        cin >> m >> n;

        for (int i = 1;i <= n;i++){

            int ci;

            cin >> ci >> si;

            ins(ci);

        }

        cin >> s;

        int len = strlen(s);

        cur = 0;

        for (int i = 0;i < len;i++) cl(s[i]);

        int now = 1;

        for (int i = 1;i <= cur;){

            if (i+8>cur) break;

            int cnt = 0;

            for (int j = i;j <= i+7;j++)

                if (result[j]==1) cnt++;

            int odd = result[i+8];

            odd=1-odd;

            if ((cnt&1)==(odd&1)){

                for (int j = 1;j <= 8;j++){

                    result[now+j-1]=result[i+j-1];

                }

                now = now + 8;

            }

            i = i+9;

        }

        int index = 1;

        for (int i = 1;i <= m;i++){

            int now = 1;

            for (int j = index;;j++){

                now = ch[now][result[j]];

                if (flag[now]!=-1) {

                    index = j+1;

                    char key = flag[now];

                    cout<<key;

                    break;

                }

            }

        }

        cout<<endl;

    }

	return 0;

}

巴特西

【ACM-ICPC 2018 沈阳赛区网络预赛 I】Lattice's basics in digital electronics

最新文章

热门文章