codeforces #346 div 2 B. Qualifying Contest (排序)

题目链接
题意:给出选手个数n,下面n行每个选手的信息“名字 区域编号 分数”.保证每个区域至少两个选手。问每个区域能否唯一确定一支二人的队伍(尽可能选分数高的,当要选的人里有分数相同的则不能确定。
思路:排序啊。。。然后搞啊。。结果发现思路没缕清。。。在某一个区域中,决定是否能唯一确定队伍的是第二个人和第三个人的成绩,和第一个人无关。
特殊处理一个区域只有两个人参加的,这种情况肯定能唯一确定队伍。
妈蛋,这种傻逼题卡了一个小时。。。。

codeforces 137 C. History (sorting,贪心)

题目链接
题意:给出n个时间的开始和截止时间,保证没有两个时间的开始或者截止时间相同,问有多少个时间被包含在其他事件中。即aj < ai and bi < bj. 思路:没有两个事件的时间相同很关键。 那么我们可以直接按照开始时间为关键字排序,然后结束时间取之前发生了的(可能还没发生完)时间的结束时间的最大值即可。

codeforces 612 D. The Union of k-Segments

http://codeforces.com/contest/612/problem/D

题意:给出n个线段信息,每个线段以l,r的形式给出。给定k。要求从作到右给出至少有k个线段覆盖的区间的信息。并使得区间数目尽可能少。

思路:很经典的一类问题…又想起了当年在tyvj上海洋兄给我的那个把线段比喻成公路,把两个端点比喻成收费站的比喻了。做法是把所有点的信息按照从小到大排序,并且记录点的类型信息,如果点相同,那么我们规定入口处的优先级高。用pair来搞的话。。可以把入口的type规定成-1,出口规定成1.然后从最左边的点开始扫,遇到-1的点厚度+1,遇到1的点厚度-1.当厚度为k的时候记录区间信息。