| 题目名称 | 1049. [Citric S2] 天空中的繁星 |
|---|---|
| 输入输出 | stara.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-08-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：14， 提交：52， 通过率：26.92% | ||||
 sk_code |
100 | 0.837 s | 7.19 MiB | C++ |
 安呐一条小咸鱼。 |
100 | 1.377 s | 3.23 MiB | C++ |
|
安呐一条小咸鱼。 |
100 | 1.393 s | 2.91 MiB | C++ |
 liu_runda |
100 | 1.446 s | 2.23 MiB | C++ |
 ONCE AGAIN |
100 | 1.457 s | 1.37 MiB | C++ |
|
liu_runda |
100 | 1.478 s | 1.99 MiB | C++ |
 wangyucheng |
100 | 1.527 s | 4.43 MiB | C++ |
|
wangyucheng |
100 | 1.542 s | 4.43 MiB | C++ |
|
sk_code |
100 | 2.259 s | 10.58 MiB | C++ |
|
sk_code |
100 | 2.334 s | 1.77 MiB | C++ |
| 关于 天空中的繁星 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这题好难想QAQ
安呐一条小咸鱼。
2016-10-12 08:14
1楼
| ||||
【题目背景】
第二届『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开关。