| 题目名称 | 797. [APIO2012] 守卫 |
|---|---|
| 输入输出 | guard.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 43 |
| 题目来源 |
 王者自由
于2012-05-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：49， 通过率：0% | ||||
 TA |
6 | 0.011 s | 0.31 MiB | C++ |
 Hyoi_ctime |
6 | 0.014 s | 0.31 MiB | C++ |
 Owaski |
4 | 0.722 s | 23.21 MiB | C++ |
 流云天辉 |
4 | 0.758 s | 5.65 MiB | C++ |
 lazycal |
4 | 0.845 s | 3.28 MiB | C++ |
 noip |
2 | 0.707 s | 0.70 MiB | C++ |
 frontier |
2 | 0.801 s | 2.94 MiB | C++ |
 apt |
2 | 0.930 s | 3.98 MiB | Pascal |
 kleinercubs |
2 | 1.024 s | 2.96 MiB | C++ |
 xiyuedong |
2 | 1.054 s | 49.90 MiB | C++ |
| 关于 守卫 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
@cstdio 这题数据错了吧。
TA
2015-07-06 22:05
3楼
| ||||
|
忘了打输入输出文件也能上榜。。。
 Dissolute丶Tokgo
2015-04-30 16:06
2楼
| ||||
|
数据好强QAQ
 ztx
2015-04-29 19:44
1楼
| ||||
-
【问题描述】
APIO王国正被忍者攻击！忍者非常厉害，因为他们在进攻的时候可以躲在
阴影里面使得其他人看不到他们。整个王国除了国王居住的APIO城堡以外都已
经被占领了。在城堡前，有N个灌木丛，从1到N编号，有K个忍者躲在恰好
K个灌木丛后面。APIO城堡里有M个守卫。守卫i监视着编号从Ai到Bi 的连续
的一段灌木丛。每个守卫都向国王报告在他所监视范围内是否有忍者出现。作为
国王的仆人，你需要告诉国王，基于守卫的报告，哪些灌木丛后面一定躲着一个
忍者，即对于任何和守卫报告不矛盾的忍者排列方式，在这个灌木丛后面都躲着
一个忍者。
你需要写一个程序来输出所有的这些灌木丛的编号。
【数据范围】
1 ≤ N ≤ 100,000 灌木的数量；
1 ≤ K ≤ N 忍者数；
0 ≤ M < 100,000 守卫数。
对于10%的数据，N ≤ 20， M ≤ 100；
对于50%的数据，N ≤ 1000， M ≤ 1000。
【输入格式】
从标准输入读入数据。
第一行包含三个用空格分隔的整数N, K, M，N是灌木丛的个数，K是忍者
的个数，M是守卫的个数。
接下来M行，每行描述一个守卫的信息。其中的第i行包含三个整数Ai, Bi,
Ci，表示第i个守卫的监视范围是从Ai 到Bi（Ai ≤ Bi）。Ci 是0或者1，若是0表
示范围内没有看到忍者，1表示范围内有至少一个忍者。
输入数据保证至少存在一种忍者排列方式满足所有条件。
【输出格式】
输出到标准输出。
若存在灌木丛，在其后面一定躲着忍者，则将这些一定躲着忍者的灌木丛按
照编号从小到大的顺序依次输出，每个一行。即若有X个这样的灌木丛，则需
要输出X行。若不存在，则输出一行一个“-1”，不包含引号。
【样例输入1】
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1
【样例输出1】
3
5
【样例说明1】
在这个样例中，有两种可能的安排方式：1，3，5或者2，3，5。即3和5
后面必然躲着一个忍者。
考虑第一个灌木丛，存在一种安排方案使得它的后面躲着忍者，但也存在一
种安排方案使得它后面没有躲忍者，因此不应该输出1。同理，不应该输出2。
【样例输入2】
5 1 1
1 5 1
【样例输出2】
-1
【样例说明2】
在这个样例中，没有灌木丛后面一定躲着忍者。