BZOJ2241 [SDOI2011]打地鼠

2014.12.17 16:08 Wed| 1 visits oi_2015| 2015_刷题日常| Text

首先声明:此题不满足二分条件,一切写二分的题解均为误解 请注意辨明!

……

说白了这题是一个积性函数

……

故我们选择O(1)修改O(n^2)查询的二阶差分

——PoPoQQQ

Solution

又见水题!

这道题据说要用线性筛+二阶差分。orz大神的做法。

确实不满足二分性质,但是我会枚举 233

额,代码还是挺带有美感的哈……运行起来只需要64ms。不服?删掉主函数中的if判断,只需要2000+ms……真是干(sang)得(xin)漂(bing)亮(kuang)。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 105

int n,m,sum,a[N][N],t[N][N],ans=0x7fffffff;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void check(int x,int y)
{
    memcpy(t,a,sizeof t);
    for(int now,i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if((now=t[i][j])>0){
                if(i+x-1<=m&&j+y-1<=n)
                    for(int k=0;k<x;k++)
                        for(int l=0;l<y;l++)
                            t[i+k][j+l]-=now;
                else return;
            }
            else if(now<0) return;
    ans=min(ans,sum/(x*y));
}

int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            sum+=a[i][j]=read();
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(sum%(i*j)==0&&sum/(i*j)<ans)
                check(i,j);
    cout<<ans<<endl;
}