Znzryb's Blog
0%

Posted on Edited on

题目大意

问题描述:

  • 给定一棵有 n 个顶点的有根树,根节点为 1,所有顶点初始为白色

  • 定义 $d_i $ 为根节点到第 i 个顶点的距离

操作规则:

  • 每次操作可以选择一个白色顶点的子集 S

  • S 中的任意两个节点必须满足:

    • 不通过边相连(不相邻)
    • 到根节点的距离不相同(不在同一层)

  • 将 S 中的所有顶点涂成黑色

目标:

  • 求将整棵树全部涂成黑色所需的最少操作次数

数据范围:

  • 测试用例数 t: 1 ≤ t ≤ 10⁴

  • 顶点数 n: 2 ≤ n ≤ 2×10⁵

  • 所有测试用例的 n 之和不超过 2×10⁵

版本说明:

  • 这是简化版本,只需要输出最少操作次数

  • 困难版本(D2)需要输出具体的操作方案

启示：当我们发现一道题目需要猜结论，但是我们没啥思路的时候，不妨先猜下界，然后想办法不断提升这个下界（特别是对于这种个数推断与猜测）。

思路讲解

easy version，我们想要搞一个这个 dp，但是就出现这个问题了，因为和别的子树的交互，删除，没有考虑到，这个是树上 dp 的弱点，要么想办法在这个转移/合并的时候解决这个问题，要么就换做法。

发现这个 easy version 过题比较多，那么就要想到，可能就是猜结论了，不过直接猜出来比较难，我们可以先猜猜下界。首先，设 tit_i 为第 ii 层的节点个数，那么 ans≥max(t1,⋯ ,tn)ans≥\text{max}(t_1,\cdots,t_n) 是肯定的，不过，如果说 ii 层的这个所有节点都共用一个根节点，这个时候还需要对 ti+1t_i+1 取 max 值。（这个就是 easy 版本的结论）

那么 hard 版本就相当于构造性证明这个结论。

不过，想办法构造比较困难，我们不如交给随机化算法。即，我们的这个构造实际上可以看作为给这个节点涂颜色，要求节点颜色种类不能超过 ansans，并且和父节点颜色不同。我们仅仅只是使用一个这个 holeColorholeColor 的贪心进行一个瞎搞。

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
for (int i=1;i<=mx_dep;++i) {
    while (true) {
        shuffle(all(dep_node_mtx[i]),rng);
        ll holeColor=-1;
        ll cur_color=1;
        for (auto u:dep_node_mtx[i]) {
            if (holeColor!=-1 && holeColor!=color[parent[u]]) {
                color[u]=holeColor;
                holeColor=-1;
                continue;
            }
            if (cur_color!=color[parent[u]]) {
                color[u]=cur_color;
                cur_color++;
            }else {
                holeColor=cur_color;
                cur_color++;
                color[u]=cur_color;
                cur_color++;
            }
        }
        if (cur_color<=ans+1) {
            break;
        }
    }
}

AC代码

AC
https://codeforces.com/contest/2183/submission/358257705

心路历程（WA，TLE，MLE……）

走了一些弯路，做这种图论的题目，还是需要更有整体意识

顺序会影响结果的原因很朴素：这段构造是“局部贪心”，它不会为后面的点“预留”某个关键编号。

同一层里每个点只禁用 1 个编号（父亲的 du[parent]），但“哪个点拿走哪个编号”是有讲究的；你现在这套贪心只维护 一个洞 g，一旦把洞用在了“本来很灵活的点”身上，就可能把后面那个“更挑剔的点”逼到只能用更大的编号，最后 > ans 失败。

我用一个最小反例把它讲清楚（这就是“为什么顺序影响结果”的精髓）：

反例：明明有解，但某个顺序会让贪心爆掉

设这一层有 3 个点 (A,B,C)，D1 算出来最优 (K=ans=3)。

它们父亲的编号分别是：

  • (du[parent(A)] = 1) ⇒ (A) 不能用 1

  • (du[parent(B)] = 2) ⇒ (B) 不能用 2

  • (du[parent©] = 3) ⇒ © 不能用 3

显然存在合法分配（且都在 1…3 内）：

du[A]=2, du[B]=3, du[C]=1du[A]=2,\ du[B]=3,\ du[C]=1

都互不相同，也都避开了父亲的编号。

但你的贪心在顺序 A→B→C 时会失败

你的规则（对应代码）是：

  • t：按 1,2,3… 递增发新编号

  • 如果当前点禁用 t，就“跳过”它：把 t 存到洞 g，然后给它 t+1

  • 若 g 存在且当前点不禁用 g，就先把洞 g 填给它

现在按顺序 A, B, C 跑：

处理 A（禁 1）

  • t=1，但 A 禁 1 ⇒ 产生洞 g=1，t 再加到 2

  • 给 A：du[A]=2

处理 B（禁 2）

  • 此时 g=1，而 B 的父亲编号是 2，不等于 1 ⇒ 贪心立刻把洞填掉

  • 给 B：du[B]=1，洞清空

处理 C（禁 3）

  • 现在已用掉 {2,1}，t 会走到 3

  • 但 C 禁 3 ⇒ 贪心只能跳过 3，给它 4

  • 得到 du[C]=4 > ans(=3) ⇒ 这层构造失败，重来

所以你看到的现象就是：同样的一层，同样的 K，有的顺序一把过，有的顺序必炸。

Posted on Edited on

题目大意

背景

有 n 个基地排成一条线，第 k 个基地是主基地(home base)。初始时主基地有 1 个士兵。

规则

每天按顺序发生以下事件:

  1. 选择一个基地 i 和该基地中任意数量的士兵(可以是 0 或全部)，命令这些士兵向左移动到基地 i-1 或向右移动到基地 i+1(所有士兵必须同方向移动，且不能移出边界)

  2. 然后，一个新士兵出现在主基地 k(这个新士兵不受当天命令影响)

目标

给定:

  • n: 基地总数

  • m: 天数

  • k: 主基地位置

如果一个基地至少有 1 个士兵，则称其为"加固基地"(fortified)。求第 m 天结束时最多能有多少个加固基地。

输入输出

输入: 多组测试数据，每组包含三个整数 n, m, k (1≤k≤n≤10⁵, 1≤m≤10⁹)

输出: 每组数据输出第 m 天结束时最多能加固的基地数量

限制

  • 1 ≤ t ≤ 10⁴ (测试用例数)

  • 1 ≤ k ≤ n ≤ 10⁵

  • 1 ≤ m ≤ 10⁹

  • 所有测试用例的 n 之和不超过 2×10⁵

https://generals.io/ 应该是从这个游戏获取的灵感。

思路讲解

其实就是贪心，不过我们一开始写的贪心代码太屎山了，过不去，我重构了一下，写成了一个二分答案的代码，一次就过了。

那么二分答案，我们已经知道了这个需要占据 occupiedoccupied 个位置了，还有什么变量是不确定的吗？当然是有的，就是左边要占据多少个位置（needlneedl），右边要占据多少个位置（needrneedr）。 不过为了方便期间，我们定义左边为空比较少的（remlreml），右边为空比较多的（remrremr），即 remr>remlremr>reml。使用以下式子计算出 needlneedl 和 needrneedr：

reml×2<occupied:needl←reml,needr←occupied−needlothers:needl←occupied2,needr←occupied−needlreml\times2<occupied:needl\gets reml,needr\gets occupied-needl\\ \text{others}:needl\gets\frac{occupied}{2},needr\gets occupied-needl

那么，我们已经知道了 needlneedl 和 needrneedr，那我们知道，最好的走法就是先走 needrneedr，然后再走 needlneedl，由于 needr≥needlneedr≥needl，我们可以保证走左边的时候出兵点有足够的兵。因此，总的消耗为：

consume←needl+needr+(needr−1)consume\gets needl+needr+(needr-1)

那么最后 consumeconsume 和 mm 比较一下就好了，那么 check 函数写出来了，整个二分答案就没有难点了。

⚠️注意：我们对传入的参数 occupiedoccupied 减了 1，因为出兵点是自动占领的嘛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
auto check=[&](ll occupied) {
    if (occupied>N) return false;
    occupied--;
    ll reml=max(0ll,K-1),remr=max(0ll,N-K);
    if (reml>remr) {
        swap(reml,remr);
    }
    ll needl=0,needr=0;
    if (reml*2<occupied) {
        needl=reml;
        needr=occupied-reml;
    }else {
        needl=occupied/2;
        needr=occupied-needl;
    }
    ll consume=needl+needr*2-1;
    if (consume>M) {
        return false;
    }
    return true;
};

AC代码

AC
https://codeforces.com/contest/2183/submission/358159596

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

问题描述

给定长度为 n 的数组 a 和整数 k。需要执行 n−k+1 次操作:

  • 每次操作选择一个长度为 k 的窗口,该窗口的 MEX 值在所有大小为 k 的窗口中最大

  • 从这个窗口中删除任意一个元素

  • 重复以上过程直到数组长度变为 k−1

目标: 最大化最终剩余元素的 MEX 值

关键概念

MEX (最小排除值): 集合中未出现的最小非负整数

例如: MEX([1,2,0,1,3,0]) 中窗口 [1,2,0] 的 MEX 是 3

输入输出

输入:

  • 第一行: 测试用例数量 t (1≤t≤10⁴)

  • 每个测试用例第一行: n 和 k (2≤k≤n≤2×10⁵2≤k≤n≤2×10⁵)

  • 每个测试用例第二行: n 个整数 a₁,a₂,...,aₙa₁,a₂,...,aₙ (0≤aᵢ≤n)

输出: 一个非负整数,表示可能的最大 MEX 值

思路讲解

哈哈，当你发现一道理应很简单的题目有这个比较复杂的决策的时候，这个时候需要想的是，这个决策是不是根本无关紧要？

哈哈，为什么决策根本无关紧要呢？因为答案肯定是 ≤k−1≤k-1 的，因此我们需要的数字是 0～k−20～k-2，不过我们选择的区间长度是 kk，因此如果区间里面数字全是 [0,k−2][0,k-2]，那必然有重复数字，删除重复的自然是不会对答案产生影响。如果有数字超过这个范围，那删除也更加没有影响。

因此其实最后的这个结果就是原数组 mex 值和 k−1k-1 中的最小值，

AC代码

AC
https://codeforces.com/contest/2183/submission/358042015

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

这道题是 Alice 和 Bob 的博弈游戏题。

游戏规则:

  • 两人在一个长度为 n 的数组上进行游戏,数组只包含 0 和 1

  • Alice 先手,双方轮流操作

  • 每次操作选择区间 [l, r],将该区间替换为单个数字 1−min(al,...,ar)1 - min(a_l, ..., a_r)

  • 如果区间全是 1,则替换为 0;否则替换为 1

  • 游戏持续到数组只剩一个数字为止

获胜条件:

  • 如果最终剩下的数字是 0,Alice 获胜

  • 否则 Bob 获胜

输入格式:

  • 第一行:测试用例数 t (1 ≤ t ≤ 100)

  • 每个测试用例第一行:数组长度 n (3 ≤ n ≤ 100)

  • 每个测试用例第二行:n 个整数 a_i (0 ≤ a_i ≤ 1)

输出格式:

  • 对于每个测试用例,输出 “Alice” 或 “Bob”(大小写不敏感)

要求: 判断在双方最优策略下谁会获胜

思路讲解

这种题目一般是这样的，看起来这个操作非常复杂，但是实际上是只需要很少轮次的最优操作，就可以得出答案。`

首先，如果整个序列都是11，Alice 就可以通过对整个序列进行操作立即获胜。

注意最后一次操作必须涉及至少一个a1a_1或ana_n。我们根据a1a_1和ana_n的值进行讨论：

如果a1=1a_1 = 1，那么Alice 可以直接在区间[2,n][2,n]上操作以获胜，因为a2∼na_{2 \sim n}必须包含至少一个00。

如果an=1a_n = 1，那么Alice 可以直接在区间[1,n−1][1,n-1]上操作以获胜，因为a1∼n−1a_{1 \sim n-1}必须包含至少一个00。

如果a1=0a_1 = 0且an=0a_n = 0，那么在整个序列上进行操作肯定会导致Alice 失败。这意味着Alice 不能同时操作a1a_1和ana_n。因此，在Alice 操作后，序列aa中仍然至少会有一个00。Bob 然后可以在整个序列上操作以获胜。因此，在这种情况下，Bob 获胜。（这么讲有点奇怪，其实就是，你无论第一次你怎么操作，第二次 Bob 都可以直接掀桌子，得到 1）

时间复杂度：O(∑n)O(\sum n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    // 全 1 的情况
    if (find(all(A),0)==A.end()) {
        cout<<"Alice\n";
        return;
    }
    // 只要首尾有一个是 1
    if (A.front() || A.back()) {
        cout<<"Alice\n";
        return;
    }
    // 首尾都为 0
    cout<<"Bob\n";
}

AC代码

AC

https://codeforces.com/contest/2183/submission/358031419

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

有 n 个块，编号从 1 到 n，每个块上有一个初始整数 a_i。

对于一个连续段 [l, r]，如果整数 d (0 ≤ d ≤ r - l) 满足 min(al,al+1,...,al+d)=dmin(a_l, a_{l+1}, ..., a_{l+d}) = d，则称 d 为 nasty 数字。

一个段的 nastiness 定义为该段中 nasty 数字的数量。

需要处理 q 个操作：

  • **操作 1：**将第 i 个块上的数字修改为 x

  • **操作 2：**查询段 [l, r] 的 nastiness

对于每个操作 2，输出对应段的 nastiness 值。

思路讲解

我们发现一件事情，令 $mn\gets min(a_l, a_{l+1}, …, a_{l+d}) ，，d\uparrow，，mn\downarrow$，他们两个的这个单调关系是相反的，我们却要求的是 mn=dmn=d 的这个情况的数量，由于 dd 是严格递增的，mnmn 是非严格递减的，这两者显然最多只有一个交点。

那么现在这个问题就来到了，我们实际上就是求一个区间中是否有这个 dd 值嘛，显然，这个可以使用二分解决，只要我们有一个数据结构可以支持这个 RMQ 和这个单点修改即可，可以使用我们的树状数组。

AC代码

AC
https://codeforces.com/contest/2184/submission/358028437

心路历程（WA，TLE，MLE……）