雪花雪花雪花

思路

会哈希吗？

用哈希记录每个雪花的特征，便于比对相同的雪花。

将66片雪花的值的积与和相加 再%\%一个质数，这样的话相同66片雪花的值必然会得出同一个结果，然后我们再进行比对。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=100010;
const int mod=99991;
int n,top;
int s[tt][6],head[tt],x[tt];

int f(int *p){
    int sum=0,cnt=1;
    for(int i=0;i<6;i++){
        sum=(sum+p[i])%mod;
        cnt=(long long)cnt*p[i]%mod;
    }
    return (sum+cnt)%mod;
}

bool solve(int *x,int *y){
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            bool flag=1;
            for(int k=0;k<6;k++){
                if(x[((i+k)%6)]!=y[((j+k)%6)]){
                    flag=0;
                }
            }
            if(flag==1){
                return true;
            }
            flag=1;
            for(int k=0;k<6;k++){
                if(x[((i+k)%6)]!=y[((j-k+6)%6)]){
                    flag=0;
                }
            }
            if(flag==1){
                return true;
            }
        }
    }
    return false;
}

bool check(int *a){
    int h=f(a);
    for(int i=head[h];i!=0;i=x[i]){
        if(solve(s[i],a)==1){
            return true;
        }
    }
    top++;
    memcpy(s[top],a,6*sizeof(int));
    x[top]=head[h];
    head[h]=top;
    return false;
}

int main(){
	cin >>n;
    for(int i=1;i<=n;i++){
        int a[20];
        for(int j=0;j<6;j++){
            cin >>a[j];
        }
        if(check(a)==1){
            cout <<"Twin snowflakes found.";
            return 0;
        }
    }
    cout <<"No two snowflakes are alike.";
	return 0;
}

兔子与兔子

思路

可以使用质数作为进制数，这样可以更加避免哈希冲突。

然后我们将所求划分为一个子问题，即在区间中子串的哈希值是否相等。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=1e6+10;
int f[tt];
int h[tt];

int solve(int l,int r){
    return (h[r]-h[l-1]*f[r-l+1]);
}

int main(){
	string s;
	cin >>s;
	s=" "+s;
	f[0]=1;
	for(int i=1;i<s.size();i++){
		h[i]=h[i-1]*131+s[i];
		f[i]=f[i-1]*131;
	}
	int m;
	cin >>m;
	while(m--){
		int l1,r1,l2,r2;
		cin >>l1>>r1>>l2>>r2;
		if(solve(l1,r1)==solve(l2,r2)){
			cout <<"Yes"<<endl;
		}else{
			cout <<"No"<<endl;
		}
	}
	return 0;
}

回文子串的最大长度

思路

我们可以算出一个前缀和，再算出一个后缀和，然后就可以知道，正字符串和一个反字符串。

字符串的哈希值就是这个区间的哈希值和。

算完之后，我们当前就只需要枚举一个midmid中间点，因为所有回文串都是有一个中间点，或者中间区间。

然后二分分别寻找这个字符串长度即可。

代码

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;

const int tt=1e6+10;
char s[tt];
ull f1[tt],f2[tt];
ull p[tt];

ull h1(int i,int j){
	return f1[j]-f1[i-1]*p[j-i+1];
}

ull h2(int i,int j){
	return f2[i]-f2[j+1]*p[j-i+1];
}

int main(){
	p[0]=1;
	for(int i=1;i<=tt-1;i++){
		p[i]=p[i-1]*131;
	}
	int t=0;
	while(++t){
		int ans=0;
		scanf("%s",s+1);
		int len=strlen(s+1);
		if(len==3&&s[1]=='E'&&s[2]=='N'&&s[3]=='D') return 0;
		cout <<"Case "<<t<<": ";
		f2[len+1]=0;
		for(int i=1;i<=len;i++){
			f1[i]=f1[i-1]*131+(s[i]-'a'+1);
		}
		for(int i=len;i>=1;i--){
			f2[i]=f2[i+1]*131+(s[i]-'a'+1);
		}
		for(int i=1;i<=len;i++){
			int l=0,r=min(i-1,len-i);
			while(l<r){
				int mid=(l+r+1)>>1;
				if(h1(i-mid,i-1)==h2(i+1,i+mid)){
					l=mid;
				}else{
					r=mid-1;
				}
			}
			ans=max(l<<1|1,ans);
			l=0,r=min(i-1,len-i+1);
			while(l<r){
				int mid=(l+r+1)>>1;
				if(h1(i-mid,i-1)==h2(i,i+mid-1)){
					l=mid;
				}else{
					r=mid-1;
				}
			}
			ans=max(l<<1,ans);
		}
		cout <<ans<<endl;
	}
	return 0;
}

后缀数组

思路

如果前xx个字符串可以匹配，则前yy个字符串也可以匹配；如果前xx个字符串不可以匹配，则前yy个字符串也不可以匹配。可以通过二分来寻找最大的xx，配合哈希，可以做到O(logn)O(logn)的时间复杂度。这样，就可以把排序优化到O(nlog2n)O(nlog^2n)的时间复杂度了，符合要求。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef unsigned long long ull;

const int tt=3e5+10;
const int base=131;

int sa[tt];
ull p[tt],h[tt];
string s;
int len=0;

ull get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}

int solve(int a,int b){
	int l=-1,r=min(len-a+1,len-b+1)+1;
	while(l+1<r){
		int mid=l+r>>1;
		if(get(a,a+mid-1)==get(b,b+mid-1)){
			l=mid;
		}else{
			r=mid;
		}
	}
	return l;
}

bool cmp(int a,int b){
	int res=solve(a,b);
	return s[a+res]<s[b+res];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >>s;
	len=s.size(); 
	s=" "+s;
	p[0]=1;
	for(int i=1;i<=len;i++){
		sa[i]=i;
		p[i]=p[i-1]*base;
		h[i]=h[i-1]*base+s[i];
	}
	sort(sa+1,sa+1+len,cmp);
	for(int i=1;i<=len;i++){
		cout <<sa[i]-1<<" ";
	}
	cout <<endl;
	for(int i=1;i<=len;i++){
		cout <<solve(sa[i],sa[i-1])<<" ";
	}
	return 0;
}

矩阵

思路

我们将n∗mn*m的矩形中所有大小为a∗ba*b的矩形哈希一下并放到哈希表中，然后给出矩阵后，直接O(1)O(1)查找就可以了

先求出每一行前缀的hashhash，然后固定矩阵的一边长度bb，求出长度为bb的边的hashhash值，然后从这一行向下延伸aa行，求出这aa行对应的长度为bb的hashhash值。

当长度大于a后，就将最上面一行删去，始终保持大小为a∗ba*b的矩阵。这样就可以求矩阵的hashhash。

代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int tt=1010,p=131;
ull h[tt][tt],base[tt*tt];
char c[tt];

ull get(ull hash_n[],int l,int r){
    return hash_n[r]-hash_n[l-1]*base[r-l+1];
}

int main(){
	int n,m,a,b;
	cin >>n>>m>>a>>b;
    base[0]=1;
    for(int i=1;i<=n*m;i++){
    	base[i]=base[i-1]*p;
	}
    for(int i=1;i<=n;i++){
        scanf("%s",c+1);
        for(int j=1;j<=m;j++){
        	h[i][j]=h[i][j-1]*p+c[j]-'0';
		}
    }
    unordered_set<ull> s;
    for(int i=b;i<=m;i++){
        ull x=0;
        int l=i-b+1,r=i;
        for(int j=1;j<=n;j++){
            x=x*base[b]+get(h[j],l,r);
            if(j>a){
            	x-=get(h[j-a],l,r)*base[a*b];
			}
            if(j>=a){
                s.insert(x);
            }
        }
    }
    int q;
    cin >>q;
    while(q--){
        ull x=0;
        for(int i=0;i<a;i++){
            scanf("%s",c);
            for(int j=0;j<b;j++){
                x=x*p+c[j]-'0';
            }
        }
        if(s.count(x)) cout <<"1"<<endl;
        else cout <<"0"<<endl;
    }
	return 0;
}

树形地铁系统

待更新……

谢谢

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 22ms
  4. Powered by Hydro v5.0.0-beta.13 Community