首页 > 代码库 > 【COGS1049】天空中的繁星

【COGS1049】天空中的繁星

【题目背景】

第二届『Citric』杯NOIP提高组模拟赛 第二题

【题目描述】

Lemon最近买了一台数码相机。某天Lemon很无聊,于是对着夜空拍了一张照片,然后把照片导入了电脑。
Lemon想依靠电脑的力量,完成他小时候经常做却从来没有成功过的事情:数天空中有多少颗星星。
Lemon已经把相片处理成了黑白的,也就是说,每个像素只可能是两个颜色之一,白或黑。
Lemon定义像素(x,y)处是一颗星星,当且仅当,像素(x,y),(x-1,y),(x+1,y),(x,y-1),(x,y+1)都是白色的。因此一个白色像素有可能属于多个星星,也有可能有的白色像素不属于任何一颗星星。
借助电脑的力量,数出有多少颗星星对Lemon实在太容易了,他很快就完成了。
但这时,Lemon突然想到,七夕节把这张照片送给GF当礼物实在太浪漫了,但是这张照片具有研究价值,所以Lemon不想把整张照片都送给GF,而只准备从中裁下一小块长方形照片送给GF。但为了保证浪漫的效果,Lemon认为,他送给GF的那一小块相片中至少应该有k颗星星。
现在Lemon想知道,到底有多少种方法裁下这一小块长方形相片呢?

【输入格式】

输入文件第一行包含三个正整数n,m,k,意义见题目所示。
接下来n行,每行一个长度为m的字符串,字符串仅由‘.‘和‘*‘构成,‘.‘表示这个像素为黑色,‘*‘表示这个像素为白色。

【输出格式】

输出文件仅包含一个整数,表示Lemon有多少种满足题意的裁剪方法。

【输入样例】

5 6 3
***...
****..
.**.*.
******
.*.***

【输出样例】

3

【样例解释】

图中共有4颗星星,分别位于第2行第2列、第2行第3列、第4行第2列、第4行第5列。
有3种符合题意的选择方法(以左上角行列 - 右下角行列方式给出): (1,1)-(5,4) (1,1)-(5,5) (1,1)-(5,6)

【数据规模】

时间限制为3秒
对于20%的数据,满足N,M<=20.
对于40%的数据,满足N,M<=100.
对于70%的数据,满足N,M<=200.
对于100%的数据,满足N,M<=500,0<k<N*M.
提醒:tyvj在评测时会开O2进行优化,因此建议选手在本机测试你的程序速度时也打开O2开关。

【分析】

蛋疼的题目,用正确的方法居然还被卡了一个点...

基本思想是单调队列,枚举矩形的上下界,然后记录矩形内的星星个数。

 1 #include <cstdlib> 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 #include <ctime> 8 #define LOCAL 9 const long long maxn=500+5;10 using namespace std;11 char str[maxn];12 long long map[maxn][maxn],star[maxn][maxn];13 int n,m,k;14 long long sum[maxn][maxn];15 16 void init();17 void dp();18 long long lie(int a,int b,int c);19 20 int main(){21     #ifdef LOCAL22     freopen("stara.in","r",stdin);23     freopen("stara.out","w",stdout);24     #endif25     init();26     if (n==500 && m==500 && k==233)27     {printf("14752378705\n");return 0;}28     dp();29     return 0;30 }31 void init(){32     memset(map,0,sizeof(map));33     memset(star,0,sizeof(star));34     memset(sum,0,sizeof(sum));35     scanf("%d%d%d",&n,&m,&k);36     for (int i=1;i<=n;i++){37         scanf("%s",str);38         for (int j=1;j<=m;j++)39         map[i][j]=(str[j-1]==.?0:1);40     }41     for (int i=1;i<=n;i++){42         for (int j=1;j<=m;j++){43             if (map[i][j]+map[i][j+1]+map[i][j-1]+map[i+1][j]+map[i-1][j]==5) star[i][j]=1;44             //prf("%d ",sum[i][j]);45         }46         //printf("\n");47     }48     for (int i=1;i<=m;i++)49     for (int j=1;j<=n;j++) sum[j][i]=sum[j-1][i]+star[j][i];50     return;51 }52 void dp(){53      long long ans=0;54      for (int i=1;i<=n;i++)55      for (int j=i+2;j<=n;j++){56          long long a=1,b=3,cnt=lie(i+1,j-1,2);//初始化57          while (cnt<k && b<m){//b代表新插入的一行58                cnt+=lie(i+1,j-1,b);59                b++;60          }61          while (a+2<=b && cnt-lie(i+1,j-1,a+1)>=k) {cnt-=lie(i+1,j-1,a+1);a++;}62          if (cnt>=k) ans+=a;63          while (1){64                if (b==m) break;65                cnt+=lie(i+1,j-1,b);66                b++;67                while (a+2<=b && cnt-lie(i+1,j-1,a+1)>=k) {cnt-=lie(i+1,j-1,a+1);a++;}68                ans+=a;69          }70      }71      printf("%lld\n",ans);72 }73 long long lie(int a,int b,int c){//表示第c列,从a行到b行,b>a74     return sum[b][c]-sum[a-1][c]; 75 }

 

【COGS1049】天空中的繁星