題目描述

Alice得到了一張由n×m個(gè)黑白像素點(diǎn)組成的圖片，她想要壓縮這張圖片。壓縮圖片的過程如下：
1.首先，選擇一個(gè)正整數(shù)k(k>1)，將圖片劃分成若干個(gè)k×k的小塊。如果n,m不能被k整除，用白色像素點(diǎn)在圖片的右邊或下面補(bǔ)全，使補(bǔ)全成n,m都能被k整除。
2.由于壓縮時(shí)每個(gè)k×k的小塊必須顏色一致(即全黑或者全白)，所以需要先改變某些像素點(diǎn)的顏色，然后再進(jìn)行壓縮。

在Alice可以自由的選擇任意一個(gè)大于1的正整數(shù)k作為小塊的邊長的情況下，請(qǐng)你告訴Alice，她至少需要改變多少個(gè)像素點(diǎn)的顏色。

?

輸入

輸入的第一行包含兩個(gè)由空格隔開的正整數(shù)n,m(2≤n,m≤1000)，表示圖片的尺寸。
接下來n行，每行包含一個(gè)長度為m的”01”串，表示Alice得到的那張圖片。”0”表示一個(gè)白色像素點(diǎn)，”1”表示一個(gè)黑色像素點(diǎn)。

?

輸出

輸出一個(gè)整數(shù)，表示Alice要壓縮她的圖片至少需要改變顏色的像素點(diǎn)的個(gè)數(shù)。

樣例輸入?

3 5 00100 10110 11001

樣例輸出?

5

提示

選擇k=2，圖片被補(bǔ)全為，如下：
001000
101100
110010
000000
為使每個(gè)2×2的小塊顏色一致，改變顏色為，如下：
001100
001100
000000
000000
可以發(fā)現(xiàn)這是所有情況中改變顏色的像素點(diǎn)數(shù)最少的，改變了5個(gè)像素點(diǎn)的顏色(答案為5的改色方案不止這一種)。

---

題目大意：給出一個(gè)n*m的01矩陣，我們可以隨意取一個(gè)k值，滿足

整個(gè)n*m的矩陣可以分割為數(shù)個(gè)相鄰的，大小為k*k的小矩陣，邊界多余的部分若無法構(gòu)成k*k，則用0補(bǔ)齊

要求每個(gè)k*k小矩陣中的數(shù)字相同：

全部為0

全部為1

問在上述兩個(gè)約束條件下，我們最少需要改變多少個(gè)數(shù)字

題目分析：這個(gè)題目的題意還是比較容易理解的，現(xiàn)在就在于該如何實(shí)現(xiàn)了，因?yàn)榍耙惶焱砩显谂？妥龅搅艘粋€(gè)比較類似的二維前綴和的題目，所以讀完這個(gè)題之后第一反應(yīng)就是觀察一下能否用二維前綴和輔助求解，答案肯定是可以的，所以我們就可以直接維護(hù)一個(gè)二維前綴和，然后從小到大枚舉k，每次更新最終答案就可以了

對(duì)了需要注意一下，因?yàn)檫@個(gè)題目涉及到了邊界補(bǔ)零的問題，所以我們的初始矩陣不能恰好開到1e3*1e3，肯定會(huì)RE的，因?yàn)槲覀兠杜e的k最大值是min(n,m)，所以按理來說矩陣開到2e3*2e3，然后每次維護(hù)2*n*2*m的大小就足夠用了

其實(shí)一開始用二維前綴和還是蠻擔(dān)心會(huì)超時(shí)的，因?yàn)榧由蟽?nèi)層枚舉的k，總的時(shí)間復(fù)雜度到了n*n*n，題目中的n是1e3，那么放到這個(gè)題目中就是1e9，肯定必超時(shí)，但有一個(gè)細(xì)節(jié)需要注意一下，因?yàn)殡S著k的增大，x和y枚舉的次數(shù)就會(huì)和k成反比，也就是說當(dāng)k達(dá)到一定大小的時(shí)候，x和y的枚舉次數(shù)就會(huì)遠(yuǎn)遠(yuǎn)小于n，雖然這種情況下時(shí)間復(fù)雜度我也不太會(huì)算，但肯定無法到達(dá)1e9的程度，起碼1e7或1e8評(píng)測機(jī)還是頂?shù)米〉?/p>

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e3+100;LL maze[N][N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)//讀數(shù)據(jù)for(int j=1;j<=m;j++)scanf("%1lld",&maze[i][j]);for(int i=1;i<=n*2;i++)//維護(hù)二維前綴和for(int j=1;j<=m*2;j++)maze[i][j]+=maze[i-1][j]+maze[i][j-1]-maze[i-1][j-1];LL ans=inf;//初始化答案為無窮大for(int k=2;k<=min(m,n);k++)//枚舉k{LL sum=0;//記錄一下當(dāng)前k的情況下的答案for(int i=k;i<=2*n;i+=k)for(int j=k;j<=2*m;j+=k){LL c=maze[i][j]-maze[i-k][j]-maze[i][j-k]+maze[i-k][j-k];sum+=min(llabs(c-1LL*k*k),c);//這里我們選取全部轉(zhuǎn)換為當(dāng)前1或者0中的較小值}ans=min(ans,sum);//實(shí)時(shí)更新答案}cout<<ans<<endl;return 0; }

?

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的中石油训练赛 - Block(二维前缀和+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。