carpet

C++(g++ 7.5.0) 解法, 执行用时: 451ms, 内存消耗: 156968K, 提交时间: 2023-08-04 10:25:20

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long

using namespace std;


const int N=1e6+10;
const int mod=1061067769;
const int P=13331;

int n,m;

int row[N];//行哈希值
int col[N];//列哈希值

int kmp(int a[N],int sz) {
	vector<int>ne(sz+1);
	for(int i=2,j=0; i<=sz; i++) {
		while(j&&a[j+1]!=a[i])j=ne[j];
		if(a[j+1]==a[i])j++;
		ne[i]=j;
	}
	return sz-ne[sz];
}

signed main() {
	ios;
	cin>>n>>m;

	vector<vector<int>> a(n + 1, vector<int>(m + 1)), b = a;

	vector<string>g(n);
	for(int i=0; i<n; i++)cin>>g[i];
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++)cin>>a[i][j];
	}
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			row[i+1]=(row[i+1]*P+g[i][j])%mod;
		}
	}
	for(int j=0; j<m; j++) {
		for(int i=0; i<n; i++) {
			col[j+1]=(col[j+1]*P+g[i][j])%mod;
		}
	}

	int r=kmp(row,n),c=kmp(col,m);

	
	
	for(int i=1;i<=n;i++){
		deque<int>q;
		for(int j=1;j<=m;j++){
			while(q.size()&&j-q.front()>=c)q.pop_front();
			while(q.size()&&a[i][q.back()]<=a[i][j])q.pop_back();
			q.push_back(j);
			b[i][j]=a[i][q.front()];
		}
	}
	int res=LLONG_MAX;
	for(int j=1;j<=m;j++){
		deque<int>q;
		for(int i=1;i<=n;i++){
			while(q.size()&&i-q.front()>=r)q.pop_front();
			while(q.size()&&b[q.back()][j]<=b[i][j])q.pop_back();
			q.push_back(i);
			if(i>=r&&j>=c)res=min(res,b[q.front()][j]);
		}
	}
	
	
	
	cout<<res*(r+1)*(c+1)<<"\n";
}

C++11(clang++ 3.9) 解法, 执行用时: 439ms, 内存消耗: 130696K, 提交时间: 2018-07-23 21:24:50

#include<vector>
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
const int N=1e6+7;
string s[N],str;
char tmp[N];
vector<string>V;
vector<int>G[N];
ll r[N],c[N];
int f[N];
ll h(string s){
	ll res=0;
	for(int i=0;s[i];++i) res=res*233+s[i];
	return res;
}
int kmp(ll s[],int n){
	f[1]=0;
	for(int i=2;i<=n;++i){
		int j=f[i-1];
		while(j&&s[i]!=s[j+1]) j=f[j];
		if(s[i]==s[j+1]) ++j;
		f[i]=j;
	}
	return n-f[n];
}
int a[N],v[N]; 
int main(){
	int n,m,R=0,C=0,p,q;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) {
		scanf("%s",tmp);
		r[++R]=h(tmp);
		V.push_back(tmp);
	}
	for(int i=0;i<m;++i) {
		str="";
		for(int j=0;j<n;++j) str+=V[j][i];
		c[++C]=h(str);
	}
	p=kmp(r,n),q=kmp(c,m);
	for(int i=1;i<=n;++i) {
		int head=1,tail=0;
		for(int j=1;j<=m;++j) {
		    scanf("%d",&v[j]);
		    if(head<=tail&&j-a[head]>=q) ++head;
		    while(head<=tail&&v[a[tail]]<=v[j]) --tail;
		    a[++tail]=j;
		    if(j>=q) G[i].push_back(v[a[head]]);
		}
	}
	int ans=1e9+7;
	for(int i=0;i<m-q+1;++i) {
		int head=1,tail=0;
		for(int j=1;j<=n;++j) {
			if(head<=tail&&j-a[head]>=p) ++head;
		    while(head<=tail&&G[a[tail]][i]<=G[j][i]) --tail;
		    a[++tail]=j;
		    if(j>=p) ans=min(ans,G[a[head]][i]);
		}
	}
	printf("%lld\n",1LL*(p+1)*(q+1)*ans);
}

C++14(g++5.4) 解法, 执行用时: 238ms, 内存消耗: 17392K, 提交时间: 2018-07-22 15:48:04

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define mo 1000000007
#define INF (0x3f3f3f3f)
inline void rd(int &x){
	static char c; x=0;
	while (c=getchar(),c<48);
	do x=(x<<3)+(x<<1)+(c^48);
	while (c=getchar(),c>=48);
}
char s[N];
int row[N],col[N],fail[N];
inline int KMP(int *a,int n){
	fail[0]=fail[1]=0;
	int i,j;
	for (i=1,j=0;i<n;i++){
		while (j>0 && a[i]!=a[j]){
			j=fail[j];
		}
		if (a[i]==a[j]){
			j++;
		}
		fail[i+1]=j;
	}
	return n-fail[n];
}
int A[N],Mx[N],G[N];
#define ID(x,y) (((x)-1)*m+y)
int main(){
	int n,m,i,j;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++){
		scanf("%s",s+1);
		for (j=1;j<=m;j++){
			row[i]=(233LL*row[i]+s[j])%mo;
			col[j]=(233LL*col[j]+s[j])%mo;
		}
	}
	int Tx=KMP(row+1,n),Ty=KMP(col+1,m);
	int L,R;
	for (i=1;i<=n;i++){
		L=1,R=0;
		for (j=1;j<=m;j++){
			rd(A[ID(i,j)]);
			while (L<=R && A[ID(i,G[R])]<=A[ID(i,j)]){
				R--;
			}
			if (L<=R && G[L]==j-Ty){
				L++;
			}
			G[++R]=j;
			Mx[ID(i,j)]=A[ID(i,G[L])];
		}
	}
	int Ans=INF;
	for (j=Ty;j<=m;j++){
		L=1,R=0;
		for (i=1;i<=n;i++){
			while (L<=R && Mx[ID(G[R],j)]<=Mx[ID(i,j)]){
				R--;
			}
			if (L<=R && G[L]==i-Tx){
				L++;
			}
			G[++R]=i;
			if (i>=Tx){
				Ans=min(Ans,Mx[ID(G[L],j)]);
			}
		}
	}
	printf("%lld\n",1LL*(Tx+1)*(Ty+1)*Ans);
	return 0;
}

详情