感谢的分享

题意：给你一个n*m的矩阵，每个格子有自己的颜色和权值，现在要你选择一个子矩阵，假设子矩阵的大小是p*q的，子矩阵选择的条件是，将子矩阵无限的平移复制粘贴，原来的n*m的矩阵是复制粘贴之后矩阵的子矩阵，选择子矩阵有一个花费，花费是原矩阵所有的大小为p*q的子矩阵中选择一个最大值x，花费就是x*p*q。n*m<=1e6。

做法：将此题分成两步来考虑，首先我们要找到我们的p*q的子矩阵，该子矩阵一定是原矩阵的一个循环节，不然复制粘贴之后无法构成原矩阵，我们要找最小的循环节，这样可以在后面一步中保证花费最小。之后就是线性时间复杂度内找到所有p*q矩阵中的最小值。

第一步，找循环节。利用KMP算法。首先我们应该知道的是：假设字符串的长度是l，那么最小的循环节的大小就是len-next[len] ，除此以外还有len-next[next[len]]，等等，于是我们对于每一行每一列都将有可能的循环节大小都统计出来，当出现的次数是n(或者m)的时候一定是可以的，于是这样就找到了循环节的大小。

第二步，在大小n*m的矩阵中p*q的子矩阵中最大值最小，于是我们有限队列预处理一下就好了，先预处理出来每一行连续的q个的最大值，再找到连续的p行中最大值的最大。

代码如下：

#include
     
      using namespace std;const int maxn = 1e6+100;vector
      
       tmp;struct KMPer{    int next[maxn];    int len;    void clear()    {        len = 0;        next[0] = next[1] = 0;    }    void NEXT(char ss[])    {//        cout<
       
        <
        
          s;vector
         
          
            > a;vector
           
            
              >maxVal;int cnt1[maxn],cnt2[maxn];int n,m;char S[maxn];pair
             
               pq[maxn];int l,r;int main(){#ifdef ONLINE_JUDGE ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);#endif while( cin>>n>>m ) { ///-------------------初始化-------------- memset(cnt1, 0, sizeof(cnt1)); memset(cnt2, 0, sizeof(cnt2)); s.resize(n+1); maxVal.resize(n+1); a.resize(n+1); ///--------------输入--------------- for (int i=1; i<=n; i++) { cin>>s[i]; a[i].resize(m+1); maxVal[i].resize(m+1); } for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { cin>>a[i][j]; } } ///________________横向寻找每一行的 循环节大小--------------- kmper.clear(); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { S[j] = s[i][j-1]; } S[m+1] = '\0';// cout<
              
               <
               
                =1; i--) { if(cnt1[i]==n) q = i; //横向循环节的大小是q if(cnt2[i]==m) p = i; //纵向循环节的大小是p }// printf("%d...%d...\n" , p , q); ///------在一个大小n*m的矩阵中找到大小为p*q的子矩阵中最大值最小------ for (int i=1; i<=n; i++) { l = 0,r=0; for (int j=1; j<=m; j++) { while (r>l&&pq[l].second<=j-q)l++; while (r>l&&pq[r-1].first<=a[i][j])r--; pq[r++] = {a[i][j],j}; if (j>=q) { maxVal[i][j-q+1] = pq[l].first; } } } int ans = 0x3f3f3f3f; for (int j=1; j<=m-q+1; j++) { l=r=0; for (int i=1; i<=n; i++) { while (r>l&&pq[l].second<=i-p)l++; while (r>l&&pq[r-1].first<=maxVal[i][j])r--; pq[r++] = {maxVal[i][j],i}; if (i>=p) { ans = min(ans,pq[l].first); } } } cout<<1LL*(p+1)*(q+1)*ans<