题目名称 3970. 贪吃蛇
输入输出 hunger.in/out
难度等级 ★★★☆
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试数据 10
题目来源 Gravatarsyzhaoss 于2024-05-06加入
开放分组 全部用户
提交状态
分类标签
二分答案 线段树
分享题解
通过:3, 提交:4, 通过率:75%
Gravatar喵喵喵 100 0.569 s 6.87 MiB C++
Gravatar 100 1.254 s 6.87 MiB C++
GravatarAeeE5x 100 1.273 s 6.87 MiB C++
Gravatarchenbp 0 0.307 s 0.97 MiB C++
关于 贪吃蛇 的近10条评论(全部评论)

3970. 贪吃蛇

★★★☆   输入文件:hunger.in   输出文件:hunger.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

一条饥肠辘辘的贪吃蛇来到了一个资源丰富的小岛,它发现地上有很多排果子(一排可能有一个或者很多个果子),前后左右的果子对仗整齐。

果子阵旁有一块牌匾,上面写着果子拿取规则:

“来到此处的幸运儿,拿取果子时,可以选择一次拿走一排所有的果子,也可以选择放着这一排果子不拿。但若这一排的某一个或某几个果子与已经拿走过的果子的列数重合,那么这一排的果子将无法拿取”。

由于贪吃蛇非常贪吃,它想尽可能的多吃到一些果子,请你帮它计算最多能拿走多少个果子?

【输入格式】

第一行,一个整数 $N$,表示有 $N$ 排果子。

接下来 $N$ 行,每行两个正整数 $l、r$,用一个空格隔开。表示在 $[l,r] $之间有一排果子。

贪吃蛇可以选择拿走这一排果子,或者放着这一排果子不管。但如果这一排果子中的某一个或某几个的列数与它已经拿走过的果子的列数重合,那么她就无法拿走这一排果子。

【输出格式】

一行一个整数。表示贪吃蛇最多能拿走多少个果子。

【样例1输入】

3
1 3
7 8
3 4

【样例1输出】

5

【样例2输入】

5
99 100
88 100
78 101
130 180
68 141

【样例2输出】

75

【样例3】

样例下载

【数据规模与约定】

对于 $100\%$ 的测试数据,$\space 1 \le l \le r \le 10^{18}$ 。

【来源】

2024年校际联合邀请赛 入门组-第1场 Task4