测试得分:100
更正情况:T1 0% T3 50%
测试时的想法、为啥没写出来:
考试一开始,就看了所有的题,T1T3没想法,T2刚开始看觉得好像是DP,仔细一看发现似乎是贪心进阶。于是就。。。用贪心写了出来,然后。。。似乎就A了。
T1。。。坦白说,一直都没想法。
T3。。想试着找找规律、、把表打出来了没把规律找出来QAQ
心得:1)A题的感觉不是一般的酸爽。
分析:T1:这题我弃疗
T2:首先假装倍增一下,因为我们要处理的是一个环,但是贪心的话似乎把它复制一下合成一条大线段比较好做。
题目要求在给出的线段中最多能选出的不相交的线段数,所以我们可以在读入的时候做一下小处理:如果右端点小于左端点,那么右端点应该加上n,这大概就是伪倍长QAQ。所以把右端点sort完后第一条线段就是最短的。将这条线段的左端点加上n就是上限了,下限初始为这条线段的右端点,然后继续枚举右端点贪心,并要记得更新下限。这样下来就是最优解了。
出题人说这是乱搞,可我觉得不是啊QAQ
T3:打表
类似的题目:T1:我。。。原谅我见识少。。
T2:Begin1349
T3:上一句的上一句话好不好QAQ