2018湖南省队集训(九日游)6.22总结

测试得分: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

 
点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s