Codeforces Round #111 (Div. 2)
C. Find Pair
题意
- 给(N(N le 10^5))个数，在所有(N^2)对数中求第(K(K le N^2))对数。
- 排序按照pair比较，first为第一关键字，second第二关键字。
思路
- 统计(cnt[x])为值(x)出现的次数。
- 第一关键字为(x)的对数为(cnt[x] imes n)，显然可以找到第一关键字。
- 在确定第一关键字(x)后，第二关键字(y)的出现次数为(cnt[x] imes cnt[y])，通过前缀和就可以求出第二关键字。
代码
D. Edges in MST
题意
- 一张带边权的无向图，有(N(N le 10^5))个点，(M(M le 10^5))条边。
- 对于每条边，判定在最小生成树的状态：在任一最小生成树中(any)、在一种最小生成树中(at least one)、不在任一最小生成树中(none)。
思路
- 按边权从小到大做，边权相同的一起考虑。
- 边权较小的边形成的连通块缩点，考虑当前权值的边：
- 若当前的边会与边权小的边构成环，说明这条边显然不在任一生成树中。
- 若当前的某些边构成环，说明这些边只会在一种生成树中，否则割边会在任一生成树中。
代码
E. Buses and People
题意
- 给(N(N le 10^5))个区间([s_i, f_i])及权值(t_i), (s_i, f_i, t_i le 10^9)，保证(t_i e t_j, i e j)
- 给(M(M le 10^5))个区间([l_i, r_i])和权值(b_i)。
- 对于(M)的区间，找到最小的(t_j)的编号(j)，使得(b_i le t_j)且(s_j le l_i, r_i le f_j)。
思路
- 若(s_j le 1_i)，则相当于在([b_i, max{t}])中找到第一个(f_j ge r_i)。
- 因为每个(t_j)均不相同，则用线段树维护对于区间([t_i,t_j])的最大(f)值。
- 对于每个(b_i)，二分(t)即可。
代码