F. Dr. Evil Underscores CF1285D 字典树

题意:输入n个整数,求一个整数X,使得它与这些整数的最大异或值最小。输出这个最小值。
输入:第一行n,第二行n个整数。所有整数<=2^{31}-1
输出:答案,一个整数。
分析:把所有整数分解成30位二进制数,从左至右,看成一个字符串,插入Trie树,然后开始dfs求答案。树高为30层,当搜索到某一层,只有0或1时,那么X在这一层的二进制数也是0或1,即对答案的贡献为0;若该层0和1都有,那么就是说,不论X在这里的二进制数是0还是1,最终答案这里肯定是1,那么选01两边最小的一个答案就行了。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 3e6+5;
int Trie[maxn][2];
int cnt = 0;
void insert(int n);
int dfs(int cur,int root);
int read();
int main(){
    int n,temp;
    //cin>>n;
    //scanf ("%d",&n);
    n = read();
    while (n--){
        //cin >> temp;
        //scanf ("%d",&temp);
        temp = read();
        insert(temp);
    }
    cout << dfs(30,0);
    return 0;
}
int dfs(int cur,int root){
    if (cur==0) return 0;
    if (!Trie[root][0]) return dfs(cur-1,Trie[root][1]);
    if (!Trie[root][1]) return dfs(cur-1,Trie[root][0]);
    return (1<<(cur-1))+min(dfs(cur-1,Trie[root][0]),dfs(cur-1,Trie[root][1]));
}

void insert(int n){
    int temp,root = 0;
    for (int i=30;i>=1;i--){
        temp = (n>>(i-1)) & 1;
        if (!Trie[root][temp])  Trie[root][temp] = ++cnt;
        root = Trie[root][temp];
    }
    return;
}
int read(){
    int f=1,x=0;char ch = getchar();
    while (ch<'0' || ch>'9')  {if (ch=='-')   f=-1;ch = getchar();}
    while (ch>='0' && ch<='9')  {x = 10*x+ch-'0';ch = getchar();}
    return x*f;
}

也就10w个数据,但把cin换成scanf的话,,能快200ms,搞不懂cf。
用快读的还可以比scanf再快上一点。

I. Word Puzzles POJ1204 AC自动机

题意:给定一个L\timesC的字符迷宫word puzzles,然后给出W个模板串,求这些模板串在puzzles中出现的位置以及方向。方向有1~8这8个方向,1为钟表的12点种方向,剩下的按顺时针依次。。
输入
第一行:三个整数 L C W
接下来L行输入迷宫,每行一个长为C的字符串
最后W行,每行一个模板串
输出
对每个模板串,输出三个参数:第一个字符在迷宫中的横纵坐标,方向。横纵坐标大小从0开始而不是1。

构建AC自动机,先把迷宫存下来,然后把模板串插入到Trie树,构建AC自动机,注意维护每个结点对应第几个模板串。然后再8个方向依次扫描迷宫,扫描到了就记录一下答案,最后输出。细节挺多。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1005,maxn = 1e6+5;
typedef struct AC_Auto{
    int Trie[maxn][27],fail[maxn],cnt;
    int val[maxn],ans[maxn][3];              //val[i]表示i结点对应的是哪个模板串,ans[i]存第i个模板串的答案
    char Orien[maxn];        //表示第i个模板串的方向,也算答案的一部分
    int len[maxn];        //每个模板串的长度
    AC_Auto(){
        cnt = 0;
    }
    void insert(char *s,int len,int j);
    void build();
    void query(int orien,int x,int y);  //orien为方向,x y为起点
}AC;
int L,C,W;
char s[N][N],t[maxn];
AC ac;
int main(){
    scanf ("%d %d %d",&L,&C,&W);
    for (int i=1;i<=L;i++)
        scanf ("%s",s[i]+1);
    for (int i=1;i<=W;i++){
        scanf ("%s",t+1);
        ac.len[i] = strlen(t+1);
        ac.insert(t,ac.len[i],i);
    }
    ac.build();
    for (int j=1;j<=C;j++)  ac.query(4,1,j),ac.query(5,1,j),ac.query(6,1,j),ac.query(1,L,j),ac.query(2,L,j),ac.query(8,L,j);
    for (int i=1;i<=L;i++)  ac.query(2,i,1),ac.query(3,i,1),ac.query(4,i,1),ac.query(6,i,C),ac.query(7,i,C),ac.query(8,i,C);
    for (int i=1;i<=W;i++)  printf ("%d %d %c\n",ac.ans[i][1],ac.ans[i][2],ac.Orien[i]);
    return 0;
}

void AC::query(int orien,int x,int y){            //query以(x,y)开头的,方向为orien的字符串
    int flag1,flag2;
    switch (orien){                //这里是一个方向的小技巧,要记住
        case 1:flag1 = -1,flag2 = 0;break;
        case 2:flag1 = -1,flag2 = 1;break;
        case 3:flag1 = 0,flag2 = 1;break;
        case 4:flag1 = 1,flag2 = 1;break;
        case 5:flag1 = 1,flag2 = 0;break;
        case 6:flag1 = 1,flag2 = -1;break;
        case 7:flag1 = 0,flag2 = -1;break;
        case 8:flag1 = -1,flag2 = -1;break;
    }
    int root = 0,temp;
    for (int i=x,j=y;i>=1 && i<=L && j>=1 &&  j<=C;i+=flag1,j+=flag2){
        temp = root = Trie[root][s[i][j]-'A'+1];
        while (temp){
            if (val[temp] && !ans[val[temp]][0])     //记录答案这里是有点麻烦的,因为扫描到模板串后,可能是扫描到了第一个字符,也可能是最后一个,依方向而定。
                  ans[val[temp]][0] = 1,ans[val[temp]][1] = i-1-len[val[temp]]*flag1+flag1,ans[val[temp]][2] = j-1-len[val[temp]]*flag2+flag2,Orien[val[temp]] = orien+'A'-1;
            temp = fail[temp];
        }
    }
    return;
}

void AC::insert(char *s,int len,int j){
    int root = 0;
    for (int i=1;i<=len;i++){
        if (!Trie[root][s[i]-'A'+1])    Trie[root][s[i]-'A'+1] = ++cnt;
        root = Trie[root][s[i]-'A'+1];
    }
    val[root] = j;                                    //终结点标记!
    return;
}
void AC::build(){
    queue<int> q;
    int temp;
    for (int i=1;i<=26;i++) if (Trie[0][i]) q.push(Trie[0][i]);
    while (!q.empty()){
        temp = q.front();   q.pop();
        for (int i=1;i<=26;i++){
            if (Trie[temp][i]){
                fail[Trie[temp][i]] = Trie[fail[temp]][i];
                q.push(Trie[temp][i]);
            }else
                Trie[temp][i] = Trie[fail[temp]][i];
        }
    }
    return;
}

0 条评论

发表评论

邮箱地址不会被公开。