2016年1月8日 星期五

[HOJ 164][POI 18 Stage 1]森森砍你的臉

HOJ生病惹QQ,因此我在這裡做了題目備份,請參考~

這題我用O(N^3)的做法,然後過了OAO
總之,記錄每一點往右和往下最多連續幾個1,然後枚舉正方形的左上角,接著枚舉邊長,正方形存在答案就+1
最後幾筆1200ms左右,時限1500ms...
後來有寫出O(N^2logN)的作法

code:


#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
int N,DOWN[1000][1000],RIGHT[1000][1000];
char GRID[1000][1000];
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)
    {
        char &c=GRID[i][j];
        do{c=getchar();}while(c!='0'&&c!='1');
    }
    for(int i=N-1;i>=0;i--)for(int j=N-1;j>=0;j--)
    {
        if(GRID[i][j]=='0')DOWN[i][j]=RIGHT[i][j]=0;
        else DOWN[i][j]=(i==N-1?1:DOWN[i+1][j]+1),RIGHT[i][j]=(j==N-1?1:RIGHT[i][j+1]+1);
    }
    int ans=0;
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)
    {
        int mxlen=min(DOWN[i][j],RIGHT[i][j]);
        for(int len=1;len<=mxlen;len++)if(DOWN[i][j+len-1]>=len&&RIGHT[i+len-1][j]>=len)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原