| 题目名称 | 2345. [HZOI 2015]QAQ的棋盘 |
|---|---|
| 输入输出 | chessboard.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 assassain
于2016-06-15加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：5， 提交：17， 通过率：29.41% | ||||
 stdafx.h |
100 | 1.403 s | 5.63 MiB | C++ |
 _Horizon |
100 | 1.628 s | 2.53 MiB | C++ |
 assassain |
100 | 1.894 s | 61.86 MiB | C++ |
 Sky_miner |
100 | 1.971 s | 4.49 MiB | C++ |
 Stu.yxr |
100 | 2.992 s | 26.45 MiB | C++ |
|
Sky_miner |
90 | 2.481 s | 3.59 MiB | C++ |
|
stdafx.h |
70 | 3.157 s | 3.19 MiB | C++ |
|
_Horizon |
70 | 3.701 s | 2.70 MiB | C++ |
|
stdafx.h |
70 | 3.710 s | 1.74 MiB | C++ |
|
stdafx.h |
40 | 6.011 s | 0.67 MiB | C++ |
| 关于 QAQ的棋盘 的近10条评论(全部评论) |
|---|
【题目描述】
QAQ有一个n*m的棋盘，有些格子不能放置棋子，放在一行或一列的棋子会相互攻击（也就是一行，一列最多放一个棋子）。
求在满足放置尽量多的棋子的前提下，哪些位置一定要放置棋子。
【输入格式】
多组测试数据。
每组数据第一行三个正整数 n, m，K 表示棋盘大小，和能放置棋子的点的个数
接下来K行，每行两个正整数，x，y 表示一个格子的位置
【输出格式】
见样例
【样例输入】
3 3 4
1 2
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2
【样例输出】
Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.
【提示】
1 <= n, m <= 5000, K <= n*m && K <= 40000
【来源】
hdu