BZOJ 2241 SDOI2011 打地鼠 線性篩+二階差分
首先聲明：此題不滿足二分條件，一切寫二分的題解均為誤解 請注意辨明！
題目大意：給定一個m*n的洞穴矩陣，每個洞穴裡面有若干地鼠，我們需要選定一個r*c的錘子進行擊打，每次擊打必須保證r*c的范圍內所有洞穴均有地鼠，且每次擊打只會打掉每個洞穴恰好一只地鼠，求最小擊打次數
m,n<=100
考慮一個1*8的洞穴，當我們把錘子設作1*4時可以完成擊打，而1*3不能 故不滿足單調性，二分不正確
但是一個性質是確定的：假設我們選定一個3*4的錘子可以完成擊打，那麼我們選定一個3*2的錘子也一定能完成擊打
那麼反過來，當我們選擇一個3*2的錘子無法完成擊打時，那麼3*4的錘子一定無法完成擊打
說白了這題是一個偏是積性函數
於是這題我們選擇線性篩進行篩選 若r相同時c1無法完成擊打，那麼c1*p也無法完成擊打
驗證的話 首先選定錘子時打的方案是一定的，於是我們貪心，從左上至右下依次擊打，每個位置擊打的次數等於擊打區域左上角洞穴的當前地鼠數量，當擊打後任意洞穴地鼠數量不為零
然後驗證的時候強行模擬是O( (mn)^2 )樹套樹可以變成O( mn*logm*logn )
但是這道題有修改而沒有查詢(每次查詢節點時前面必須為零) 故我們選擇O(1)修改O(n^2)查詢的二階差分
向左向上進行兩次差分 然後每次修改如圖
擊打後整個區域都為零則可以完成擊打
此外這題O(n^4)暴力都能過 而且只比正解慢了四毫秒 就連O(n^6)的暴力加點剪枝都過了0.0 什麼情況究竟
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHByZSBjbGFzcz0="brush:java;">#include
#include
#include
#include
#define M 110
using namespace std;
int m,n,cnt,a[M][M],map[M][M],sum,ans=0x7f7f7f7f;
const int prime[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97},tot=25;
int not_able[2][M];
bool Judge(int x,int y)
{
int i,j;
if( sum%(x*y) )
return 0;
memcpy(map,a,sizeof a);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(map[i][j]<0)
return 0;
if(i<=m-x+1&&j<=n-y+1)
{
int num=map[i][j];
map[i][j]-=num;
map[i+x][j]+=num;
map[i][j+y]+=num;
map[i+x][j+y]-=num;
}
if(map[i][j]>0)
return 0;
}
}
ans=min(ans,sum/x/y);
return 1;
}
bool Linear_Shaker(int num,bool flag,int Time)
{
int i,j;
bool re=0;
for(i=1;i<=(flag?n:m);i++)
{
if(not_able[flag][i]!=Time)
{
if(flag)
not_able[flag][i]=(Judge(num,i)?0:Time);
else
not_able[flag][i]=(Linear_Shaker(i,1,++cnt)?0:Time);
}
if(not_able[flag][i]!=Time)
re=1;
if(i^1)
for(j=1;j<=tot&&i*prime[j]<=(flag?n:m);j++)
{
if(not_able[flag][i]==Time||not_able[flag][prime[j]]==Time)
not_able[flag][i*prime[j]]=Time;
if(i%prime[j]==0)
break;
}
}
return re;
}
int main()
{
int i,j;
cin>>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]),sum+=a[i][j];
for(i=m;i;i--)
for(j=n;j;j--)
a[i][j]-=a[i-1][j];
for(i=m;i;i--)
for(j=n;j;j--)
a[i][j]-=a[i][j-1];
Linear_Shaker(0,0,++cnt);
cout<
