HASH 字符串 KMP 进制hash 最小表示法 trie树

雪花雪花

有N片雪花，每片雪花由六个角组成，每个角都有长度。
第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6。
因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。
例如ai,1,ai,2,…,ai,6和ai,2,ai,3,…,ai,6，ai,1就是形状相同的雪花。
ai,1,ai,2,…,ai,6和ai,6,ai,5,…,ai,1也是形状相同的雪花。
我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。
求这N片雪花中是否存在两片形状相同的雪花。
输入格式
第一行输入一个整数N，代表雪花的数量。
接下来N行，每行描述一片雪花。
每行包含6个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。
同行数值之间，用空格隔开。
输出格式
如果不存在两片形状相同的雪花，则输出：
No two snowflakes are alike.
如果存在两片形状相同的雪花，则输出：
Twin snowflakes found.
数据范围
1≤n≤100000,
0≤ai,j<10000000
输入样例：
2
1 2 3 4 5 6
4 3 2 1 6 5
输出样例：
Twin snowflakes found.

虽然说是hash表过的题 但是这里我写一个 最小表示过的代码

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 1e6 + 5 ;
const double pi = acos(-1.0);
const int mod = 991 ;
int s[300],ss[300];
int ge(int s[]) {
	int len = 6;
	for(int i=1; i<=len; i++) s[i+len]=s[i];
	int i=1,j=2,k;
	while(i<=len&&j<=len) {
		for(k=0; k<len&&s[i+k]==s[j+k]; k++);
		if(k==len) break;
		if(s[k+i]>s[j+k]) {
			i=i+1+k;
			if(i==j) i++;
		} else {
			j=j+1+k;
			if(j==i) j++;
		}
	}
	int pos=min(i,j);
	return pos;
}

set<int> mp;

signed main() {
	int n;
	cin>>n;
	while(n--) {
		for(int i=1; i<=6; i++) {
			cin>>s[i];
		}
		for(int i=1; i<=6; i++) ss[7-i]=s[i];
		int hash = 0;
		int k1=ge(s);
		for(int i=0; i<6; i++) {
			hash=hash*mod+s[k1+i];
		}
		int k2=ge(ss);
		int hash2=0;
		for(int i=0; i<6; i++) {
			hash2=hash2*mod+ss[k2+i];
		}
		if(mp.find(min(hash,hash2))!=mp.end()) {
			cout<<"Twin snowflakes found."<<endl;
			return 0;
		}
		mp.insert(min(hash,hash2));
	}
	cout<<"No two snowflakes are alike."<<endl;
	return 0;
}

进制hash
快速找 字符串内部连续串是否存在 一样

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int unsigned long long

const int maxn = 1e6 + 5 ;
const double pi = acos(-1.0);
const int mod = 131;

char str[maxn];
int p[maxn],f[maxn];
int n;

signed main() {
	scanf("%s",str+1);
	int len = strlen(str+1);
	p[0]=1;
	for(int i=1; i<=len; i++) {
		f[i]=f[i-1]*131+(str[i]-'a'+1);
		p[i]=p[i-1]*mod;
	}
	cin>>n;
	while(n--) {
		int l,r,x,y;
		cin>>x>>y>>l>>r;
		if(f[y]-f[x-1]*p[y-x+1]==f[r]-f[l-1]*p[r-l+1]) {
			cout<<"Yes"<<endl;
		} else cout<<"No"<<endl;
	}
	return 0;
}

马拉车 KMP 板子不讲

Trie

前缀统计

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 1e6+5;

int trie[maxn][30],tot=1;
int ens[maxn];

void ins(char str[]){
	int len=strlen(str),p=1;
	for(int k=0;k<len;k++){
		int ch=str[k]-'a';
		if(trie[p][ch]==0) trie[p][ch]=++tot;
		p=trie[p][ch]; 
	}
	ens[p]++;
}

int serach(char str[]){
	int res=0;
	int len=strlen(str),p=1;
	for(int k=0;k<len;k++){
		int ch=str[k]-'a';
		if(trie[p][ch]==0) break;
		p=trie[p][ch];
		if(ens[p]) res+=ens[p];
	}
	return res;
}

signed main() {
	fastio;
	int n,m;
	cin>>n>>m;
	char s[maxn];
	for(int i=1;i<=n;i++){
		cin>>s;
		ins(s);
	}
// cin>>m;
	while(m--){
		int ans=0;
		cin>>s;
		ans+=serach(s);
		cout<<ans<<endl;
	}
	return 0;
}

最大异或对

在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数N。
第二行输入N个整数A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
输入样例：
3
1 2 3
输出样例：
3

第一次完全没有想到这跟trie有关系 orz
PS 这里一定要高位往低位取贪心 先拿高位 比低位贪

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 4e6+5;

int trie[maxn][5],tot=1;

void ins(int s){
	int p=1;
	for(int k=0;k<=31;k++){
	// int ch = ((1<<k)&s?1:0);
		int ch=s>>k&1;
		if(trie[p][ch]==0) trie[p][ch]=++tot;
		p=trie[p][ch]; 
	}
}

int serach(int s){
	int res=0;
	int p=1;
	for(int k=0;k<=31;k++){
	// int ch=((1<<k)&s);
		int ch=s>>k&1;
		if(trie[p][!ch]){
			p=trie[p][!ch];
			res+=(1<<k);
		}
		else{
			p=trie[p][ch];
		}
	}
	return res;
}

int a[maxn];

signed main() {
	fastio;
	int n,m;
	cin>>n;
	int s;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ins(a[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,serach(a[i]));
	}
	cout<<ans<<endl;
	return 0;
}

最长异或值路径
树上 2点之间路径的最大异或值
无根树转有根树 记录每个点到跟路径异或值 重复部分刚好是2次 被消掉
如上找最大异或值就好

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
//#define int long long

const int maxn = 4e6+5;

int trie[maxn][5],tot=1;

int cnt,head[maxn];
int nxt[maxn<<1],to[maxn<<1],dis[maxn<<1];

void ade(int a,int b,int c) {
	to[++cnt]=b;
	dis[cnt]=c;
	nxt[cnt]=head[a];
	head[a]=cnt;
}
int fa[maxn];

void dfs(int x,int pre,int sum) {
	fa[x]=sum;
	for(int i=head[x]; i; i=nxt[i]) {
		if(to[i]==pre) continue;	
		dfs(to[i],x,sum^dis[i]);
	}	
}

void ins(int s) {
	int p=1;
	for(int k=31; k>=0; k--) {
		int ch=s>>k&1;
		if(trie[p][ch]==0) trie[p][ch]=++tot;
		p=trie[p][ch];
	}
}

int serach(int s) {
	int res=0;
	int p=1;
	for(int k=31; k>=0; k--) {
		int ch=s>>k&1;
		if(trie[p][!ch]) {
			p=trie[p][!ch];
			res+=(1<<k);
		} else {
			p=trie[p][ch];
		}
	}
	return res;
}

int a[maxn];

signed main() {
	fastio;
	int n,m;
	cin>>n;
	int st,ed,d;
	for(int i=1;i<n;i++){
		cin>>st>>ed>>d;
		st++,ed++;
		ade(st,ed,d),ade(ed,st,d);
	}
	dfs(1,-1,0);
	for(int i=1;i<=n;i++){
		ins(fa[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,serach(fa[i]));
	}
	cout<<ans<<endl;
	return 0;
}