集训记录

P4823

贪心按 $a+b$ 从小到大排序，小的先走，正确性反证得到：

• 设有两个人 $i$ 和 $j$，且 $a_i+b_i>a_j+b_j$，且两人出去的顺序为 $i\to j$，也就是高的在上面。
• 那么，现在交换两个人，按照反证的假设如果原来 $i$ 和 $j$ 都能出去，那么现在只有 $i$ 能出去，且根据题意，其一定能出去；
• 若 $j$ 现在都出不去，那么由于 $j$ 比 $i$ 高，那么在不交换前，两人基准位置相同，更矮的 $i$ 一定出不去。矛盾，得证。

转化为选 $i$ 踮脚或逃的背包。$f_{i,j}$ 表示前 $i$ 个人总高度为 $j$ 最多逃多少人。注意到 $j$ 可能很大，考虑把结果和状态换一下，$f_{i,j}$ 表示前 $i$ 个人，逃 $j$ 个能搭起来的最大高度。

$$f_0\coloneqq \sum_{i=1}^{n}a_i\\ f_{j}=f_{j-1}-a_i\ (f_{j-1}+b_i\geq h)$$

模拟赛 T2

给定一棵树，求一个删边的构造，使得任意删除新的图中的一条边图仍然联通。

[证明]

设叶子 $m$ 个，则答案数 $\lceil \dfrac{m}{2}\rceil$。

按 dfn 对叶子节点编号，则每次删的边构造可以为 $i\to i+\lfloor\dfrac{m}{2}\rfloor$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

bitset<N> leaf;
vector<int> dfn;
void dfs(int u, int fa) {
    if (leaf[u]) dfn.push_back(u);
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
}
int main() {
    n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int m = 0;
    for (int i = 1; i <= n; i++) {
        if (e[i].size() == 1) {
            leaf[i] = 1;
            m++;
        }
    }
    dfs(1, 0);
    cout << ((m + 1) >> 1) << '\n';
    for (int i = 0; i <= (m >> 1) - 1; i++) {
        cout << dfn[i] << " " << dfn[i + (m >> 1)] << '\n';
    }
    if (m & 1) {
        cout << dfn.front() << " " << dfn.back() << '\n';
    }
    return 0;
}

CF1251D

二分枚举中位数，考虑贪心地 check。将要求转化为一段段区间，对于一个区间 $i$，有三种情况：中位数大于/小于区间或在区间内。

• 对于前两种情况，一定不会产生中位数，为了省钱选下界；
• 对于第三种情况，因为此时剩余数量已经确定，故对于一半的数选中位数，另外全选下界。选下界的这一半为了省钱，在下界相对小的区间选。

check 过程中判一下如果前两种情况的数量大于中位数一定不合法即可。