[POI 2023/2024 R1] Zapobiegliwy student
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目背景
译自 XXXI Olimpiada Informatyczna - I etap Zapobiegliwy student。
题目描述
考虑如下的一个简单问题:
你有 个线段在数轴上,你要选出尽量多的线段,使它们两两不交。
我知道你一定会做,但你需要解决这个:
你有 个线段在数轴上,你要选出尽量多的线段对 ,即最大化 。
满足 个要求:
- 两两不交。
- 两两不交。
- 两两不交。
- 两两不交。
其中 , 与 不能相同。
输入格式
第一行一个正整数 。
接下来 行每行两个正整数 ,表示一个线段的两个端点。
两个线段 不交当且仅当 或 。
输出格式
第一行一个正整数 。
接下来 行,每行两个正整数 ,表示一对线段的编号。
8
1 5
3 10
4 8
9 12
11 16
14 15
20 22
15 21
3
1 3
4 6
8 7
见附件
见附件
见附件
见附件
提示
如果你的第一行正确但是方案不对(可以不输出方案,此时不要有换行),你能得到 的分数。
如果你的方案合法并且第一行和答案相差不超过 ,你能得到 的分数。
子任务编号 | 限制 | 分值 |
---|---|---|
1 | 40 | |
2 | 60 |
周四下午训练
- Status
- Done
- Rule
- IOI
- Problem
- 5
- Start at
- 2025-2-20 8:00
- End at
- 2025-2-20 17:00
- Duration
- 9 hour(s)
- Host
- Partic.
- 6