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\times
C的字符迷宫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 条评论