传送门：carpet

题意

有一个n*m的地毯，aij表示地毯每格的元素，bij表示地毯每格的价格，要求选取一块价格最大值最小的地毯，并且这块地毯无限铺开之后，原地毯是其子矩阵。

题解

先找到这个矩阵的最小循环节子矩阵，求一下每行的循环节长度用map记录，取出现次数为m并且循环节长度最小的；每列也求一下循环节长度用map记录，取出现次数为m并且循环节长度最小的；这样就得到了最小的循环节子矩阵。然后问题就变成了求一个p*q的子矩阵最大值的最小值，可以参考这个题 Fake Maxpooling （求得是k*k子矩阵的最大值的和）稍加修改变成求p*q子矩阵的最大值的最小值就好了。这里用到单调队列，先横着算一下每个长度为p的区间的最大值记录下来，然后再把记录下来的数组竖着同样算一下长度为q的区间，将每次求到的最大值取最小值。

ps：谨记像这种横着求一遍竖着求一遍的一定不能求第二遍的时候直接copy第一遍的代码改，会把自己坑死的！！！不要手懒！！！

代码

1 #include
2 #define ll long long
3 using namespace std;
4
5 const int maxn=1e6+10;
6 int nt1[maxn];
7 int nt2[maxn];
8 string s[maxn];
9 unordered_map mp;
10 deque dq;
11 int val[maxn],v[maxn];
12
13 void getnt1(string s)
14 {
15 int i=0,j=-1;
16 nt1[0]=-1;
17 while(i>n>>m;
41 for(int i=0;i>s[i];
42 for(int i=0;i>v[i*m+j];
45 }
46 }
47
48 int pp=m,qq=n;
49 for(int i=0;i<n;i++){
50 getnt1(s[i]);
51 int p=nt1[m];
52 while(p!=-1){
53 mp[m-p]++;
54 if(mp[m-p]==n) pp=min(pp,m-p);
55 p=nt1[p];
56 }
57 }
58 mp.clear();
59 for(int i=0;i<m;i++){
60 string t;
61 for(int j=0;j<n;j++){
62 t+=s[j][i];
63 }
64 getnt2(t);
65 int p=nt2[n];
66 while(p!=-1){
67 mp[n-p]++;
68 if(mp[n-p]==m) qq=min(qq,n-p);
69 p=nt2[p];
70 }
71 }
72
73 int ans=1e9;
74 for(int i=0;i<n;i++){
75 while(dq.size()) dq.pop_back();
76 for(int j=0;j<pp-1;j++){
77 while(dq.size()&&v[i*m+dq.back()]<=v[i*m+j]) dq.pop_back();
78 dq.push_back(j);
79 }
80 for(int j=pp-1;j<m;j++){
81 while(dq.size()&&dq.front()+pp<=j) dq.pop_front();
82 while(dq.size()&&v[i*m+dq.back()]<=v[i*m+j]) dq.pop_back();
83 dq.push_back(j);
84 val[i*m+j]=v[i*m+dq.front()];
85 }
86 }
87 for(int i=pp-1;i<m;i++){
88 while(dq.size()) dq.pop_back();
89 for(int j=0;j<qq-1;j++){
90 while(dq.size()&&val[dq.back()*m+i]<=val[j*m+i]) dq.pop_back();
91 dq.push_back(j);
92 }
93 for(int j=qq-1;j<n;j++){
94 while(dq.size()&&dq.front()+qq<=j) dq.pop_front();
95 while(dq.size()&&val[dq.back()*m+i]<=val[j*m+i]) dq.pop_back();
96 dq.push_back(j);
97 ans=min(ans,val[dq.front()*m+i]);
98 }
99 }
100 ll res=(ll)ans*(ll)(pp+1)*(ll)(qq+1);
101 cout<<res<<endl;
102 return 0;
103 }