題目鏈接：點擊查看

題目大意：給出一個數組 a 和數組 b 只由 0 和 1 構成，構造出矩陣 maze[ x?][ y?] = a[ x ] * b[ y ]，顯然maze矩陣同樣只由 0 和 1 構成，現在要求面積為 k 的子矩陣中，有多少個全部為 1?

題目分析：再次感覺難度大于 C 題的一道 B 題。?？疾斓姆矫婧芫C合，不知道如何分類，就暫且分為思維吧，首先排除n*m*n*m的暴力，接下來一步一步考慮，因為面積為 k 的子矩陣，換一種說法，假設子矩陣的大小為 x * y ，則必須滿足 x * y == k 的子矩陣才可能滿足條件，所以不難想到要對面積 k 進行因數分解，sqrt( k )的時間復雜度預處理出 k 的所有因數作為子矩陣的長和寬，對于每一對可行的長和寬 ( x , y ) 來說，都需要計算其貢獻，接下來說的內容可能有點抽象，后面我會舉例子說明的?，F在的問題轉換為了，給出指定大小的子矩陣 ( x , y ) ，如何計算出其出現次數，通過觀察樣例給出的矩陣可以發現，假設某個子矩陣的左上角端點為( x1 , y1 )，右下角端點為( x2 , y2 )，若該子矩陣想要全部為 1 的話，那么數組 a[ x1 ] ~ a[ x2 ] 以及 b[ y1 ] ~ b[ y2 ] 的這兩段連續區間內必須全部為 1 才行，這樣就可以將數組 a 以及數組 b 轉換為連續的 1 儲存了，比如數組 a 原本為 1011011101 ，那么轉換后就變為了 1,2,3,1 了，我們記為 aa 數組和 bb 數組，這樣轉換后有什么用呢？剩下的其實就可以排列組合計算答案了，還是以大小為( x , y )的子矩陣為例，我們遍歷一遍 aa 數組，可以對大小為 x * y 的子矩陣做出貢獻，那么必須滿足連續的行數大于等于 x 才行，通過平移可以知道，貢獻就是 aa[ i ] - x + 1 了，遍歷一遍數組aa后，可以計算出有多少種行可以做出貢獻，同理遍歷一遍 bb 數組后計算出有多少列可以做出貢獻，相乘就是總貢獻了

下面舉一個例子，就拿樣例為例，a 數組為 1 0 1，轉換為 aa 數組也就變成了 1,1

b 數組為 1 1 1，轉換為 bb 數組也就變成了 3

以大小為 ( 1 , 2 ) 的子矩陣為例，我們需要在 aa 數組中找到有多少個連續的行滿足 aa[ i ] >= 1，顯然有兩個

接下來需要在 bb 數組中找到有多少個連續的列，滿足 bb[ i ] >= 2 ，因為 bb 數組只有一個元素，且其值為 3 ，那么對列的貢獻也就是 2 了，因為可以這樣選：（選橙色的列）

1 1 1

也可以這樣選：

1 1 1

綜上，對于子矩陣 ( 1 , 2 ) 的貢獻為 2 * 2 = 4

總時間復雜度為 sqrt( n * m )*( n + m )，我用了unordered_map稍加優化，而且sqrt(n*m)應該也不會拉滿，所以評測機給出的反饋是十分不錯的

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=4e4+100;int a[N],b[N];vector<pair<int,int>>node;void init(int k) {for(int i=1;i*i<=k;i++){if(k%i==0){node.push_back(make_pair(i,k/i));if(i!=k/i)node.push_back(make_pair(k/i,i));}} }unordered_map<int,int>A,B;void solve(int a[],int n,unordered_map<int,int>& mp) {int pos=1,cnt=0;while(pos<=n){while(a[pos]){pos++;cnt++;}if(cnt){mp[cnt]++;cnt=0;}pos++;} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m,k;scanf("%d%d%d",&n,&m,&k);init(k);for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=1;i<=m;i++)scanf("%d",b+i);solve(a,n,A);//預處理出aa數組和bb數組，存放在unordered_map中solve(b,m,B);LL ans=0;for(int k=0;k<node.size();k++)//遍歷每對因子{int x=node[k].first,y=node[k].second;LL xx=0,yy=0;for(auto it:A)//行貢獻if(it.first>=x)xx+=it.second*(it.first-x+1);for(auto it:B)//列貢獻if(it.first>=y)yy+=it.second*(it.first-y+1);ans+=xx*yy;//累加貢獻}printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1323B Count Subrectangles(思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。