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] \times n\)，显然可以找到第一关键字。
- 在确定第一关键字\(x\)后，第二关键字\(y\)的出现次数为\(cnt[x] \times 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 \ne t_j, i \ne 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\)即可。
代码