牛客16638，一道比较经典的KMP题目

carpet

题目传送门

题目大意

给出一个 $n * m$ 的字符矩阵，每个位置有一个 $cost$ ，找出这个矩阵的最小循环子矩阵 $p$ 行 $q$ 列，即最小二维循环周期，之后再找出每一个这样大小的子矩阵的 $cost$ 的最大值，再取最小值为 $A$ ，输出 $A*(p+1)*(q+1)$ 即可。

思路

分三步，首先要求出字符矩阵的最小循环子矩阵的行数和列数，之后再对每一个这样大小的子矩阵的 $max{cost}$ 进行求 $min$ ，最后，输出答案即可。

1. 针对第一步，我们采用KMP算法。

   我们求出每一行的 $p[i]$ 值，之后利用 $p[i]$ 值将每一行的所有循环节长度(即周期)求出来，用 map 记录每个周期的出现次数，遍历完每一行之后，找出 map 中记录的出现了 m 次的周期的最小值，即为最小循环子矩阵的列数 $q$ 。

   $p$ 的求法和 $q$ 一样，对每一列进行同样的操作即可。

2. 针对第二步，我们采用优先队列优化的滑动窗口。

   考虑到数据量较大，我们要首先对每一列进行滑动窗口的操作，记录下第 $i$ 行第 $j$ 列的 $max{cost[i-p+1 … i][j]}$ 。以此来优化矩阵的滑动窗口操作，变成了线性。

   之后，我们对每一个 $p$ 行 $q$ 列的子矩阵进行求解，遍历每一行，每次可直接调用上一步求出的值，即可求出 $A$ 。

3. 输出答案 $A*(p+1)*(q+1)$ ，注意这个结果是可能超过 int 的范围的。

代码

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<iostream>
#include<unordered_set>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Inf 0x3f3f3f3f
//#define int long long
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef pair<P,int> PP;
const int MAXX=1000005;
const double eps=0.0000001;

int n,m,p[MAXX];

void lgetpmt(const vector<vector<char> >& a,int k){
	for(int i=1,j=0;i<m;++i){
		while(j>0&&a[k][i+1]!=a[k][j+1])
			j=p[j];
		if(a[k][i+1]==a[k][j+1])
			++j;
		p[i+1]=j;
	}
}
void tgetpmt(const vector<vector<char> >& a,int k){
	for(int i=1,j=0;i<n;++i){
		while(j>0&&a[i+1][k]!=a[j+1][k])
			j=p[j];
		if(a[i+1][k]==a[j+1][k])
			++j;
		p[i+1]=j;
	}
}

inline void solve_it(){
	scanf("%d%d",&n,&m);
	vector<vector<char> > a(n+2,vector<char>(m+2));
	vector<vector<int> > c(n+2,vector<int>(m+2));
	for(int i=1;i<=n;++i){
		getchar();
		for(int j=1;j<=m;++j)
			scanf("%c",&a[i][j]);
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			scanf("%d",&c[i][j]);
	
	map<int,int> left,top;
	int l=m,t=n;
	for(int i=1;i<=n;++i){
		lgetpmt(a,i);
		int jj=p[m];
		while(jj!=0){
			++left[m-jj];
			if(left[m-jj]==n) l=min(l,m-jj);
			jj=p[jj];
		}
	}
	for(int i=1;i<=m;++i){
		tgetpmt(a,i);
		int jj=p[n];
		while(jj!=0){
			++top[n-jj];
			if(top[n-jj]==m) t=min(t,n-jj);
			jj=p[jj];
		}
	}
	
//	printf("*%d %d\n",t,l);//t行l列  1 2
	
	priority_queue<P> pq;
	vector<vector<int> > topmax(n+2,vector<int>(m+2));
	for(int j=1;j<=m;++j){
		while(!pq.empty())
			pq.pop();
		
		for(int i=1;i<=t;++i)
			pq.emplace(c[i][j],i);
		topmax[t][j]=pq.top().first;
		
		for(int i=t+1;i<=n;++i){
			pq.emplace(c[i][j],i);
			while(pq.top().second<=i-t)
				pq.pop();
			topmax[i][j]=pq.top().first;
		}
	}
	
	int ans=Inf;
	for(int i=t;i<=n;++i){
		while(!pq.empty())
			pq.pop();
		
		for(int j=1;j<=l;++j)
			pq.emplace(topmax[i][j],j);
		ans=min(ans,pq.top().first);
		
		for(int j=l+1;j<=m;++j){
			pq.emplace(topmax[i][j],j);
			while(pq.top().second<=j-l)
				pq.pop();
			ans=min(ans,pq.top().first);
		}
	}
	
//	printf("*%d\n",ans);//
	printf("%lld\n",((LL)ans)*((LL)(l+1))*((LL)(t+1)));
}

signed main(){
//	LL T;scanf("%lld",&T);
//	while(T--)
		solve_it();
	
	return 0;
}

总结

感觉这道题涉及了很多内容，可以当作一道比较经典的应用KMP进行求解的题目了。

前面因为所有循环节的求法写错了，导致调了半天一直调不出来，要牢记。

所有循环节的求法

int jj=p[n];
while(jj!=0){
    ans.emplace_back(n-jj);//这里的 n-jj 均为循环节，ans记录所有循环节
    jj=p[jj];
}