编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

这种水题居然交了4次...前2次理解错了题，第3次把i打成了j，最可恨的是即使打错了还是把样例过掉了，囧！哎！老了...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

方向对了就很快了！

简单的贪心

这题……

N^2就能过……

Wsxhwyy

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

把包含有其他区间的区间删掉。

然后对于排序后的每个区间，尽量选取靠右的数做z的元素。（贪心。）

我开始还以为求的是 满足条件的不同集合z共有多少个……后来发现是求得z元素个数……

= = 先看一道原题：

给定N个区间，用最少的线段覆盖这N个区间。

是不是跟这道题很像？

因此我们得出算法：

先按右端点排序，然后从第一条线段开始，每一次切右端点（至于能切几个要看标志数组里剩下多少个点），看能覆盖掉多少个点（即i+1~n这几个线段中每个线段能被覆盖多少点）。用一个标志数组记录每一条线段剩余多少个点（一开始都为2），在循环的时候，遇到剩余0的线段就不再考虑。

以前见过z∩[ai，bi]>=1的用贪心。 >=2的也用贪心一样。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

这个贪心还是比较简单的

排序后贪心就ok了

orz楼上大牛

呵呵，改回来了~~~感谢管理员

其实那个Guest就是fengyi。。。第一个一遍AC的那个

nlogn

先乱搞，把两两之间有包含关系的线段中留下较小的那个线段(排序一次，扫描两次);

把省下的按坐端点从小到大排序，每次贪心的填线段最左边的两个点，扫描一便。

我的做法：

实际上就是贪心

1、先将它们的起始时间升序排序。

2、让i从0-n-1扫描，再将j循环找到一个重合区间使得a[j].start>区间的最小end，然后讨论

3、a)若区间的最大start=最小end，先将i~(j-1)之间的区间的used++，子集的元素个数++，若used[i]

HAH
这么猛?
FROM VIJOS GUEST\`

From Vijos Guest 这是亮点

纪念下

虽然没过

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案正确... 728ms

├ 测试数据 05：答案正确... 150ms

├ 测试数据 06：答案错误...程序输出比正确答案长

├ 测试数据 07：答案错误...程序输出比正确答案长

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：55 有效耗时：878ms

我搞定了 按右标记QSORT

再从后向前插就可以了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

地板....