Znzryb's Blog

Hello 2026——C. War Strategy（二分答案可以减小实现难度）

Posted on 2026-01-16 Edited on 2026-04-06

题目大意

背景

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

规则

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

选择一个基地 i 和该基地中任意数量的士兵(可以是 0 或全部)，命令这些士兵向左移动到基地 i-1 或向右移动到基地 i+1(所有士兵必须同方向移动，且不能移出边界)
然后，一个新士兵出现在主基地 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/ 应该是从这个游戏获取的灵感。

思路讲解

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

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

reml\times2<occupied:needl\gets reml,needr\gets occupied-needl\\ \text{others}:needl\gets\frac{occupied}{2},needr\gets occupied-needl

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

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

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

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

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

源代码

/**
 * Problem: C. War Strategy
 * Contest: Hello 2026
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2183/problem/C
 * Created: 2026-01-17 10:38:08
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N,M,K;
    cin >> N >> M >> K;
    ll bsl=1,bsr=N;
    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;
    };
    while (bsl<bsr) {
        ll mid=(bsl+bsr+1)>>1;
        if (check(mid)) {
            bsl=mid;
        }else {
            bsr=mid-1;
        }
    }
    cout<<bsl<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

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

*/

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

Hello 2026——B. Yet Another MEX Problem（由鸽巢原理导出决策根本无关紧要）

Posted on 2026-01-16 Edited on 2026-04-06

题目大意

问题描述

给定长度为 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⁵$ )
每个测试用例第二行: n 个整数 $a₁,a₂,...,aₙ$ (0≤aᵢ≤n)

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

思路讲解

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

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

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

AC代码

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

源代码

/**
 * Problem: B. Yet Another MEX Problem
 * Contest: Hello 2026
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2183/problem/B
 * Created: 2026-01-16 11:23:30
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    set<ll> st;
    for (int i=0;i<N+2;++i) {
        st.insert(i);
    }
    for (int i=0;i<N;++i) {
        cin>>A[i];
        st.erase(A[i]);
    }
    ll mex=*st.begin();
    cout<<min(mex,K-1)<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}

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

*/

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

Hello 2026——A. Binary Array Game（01 串的首尾很重要，博弈论很少轮次最优）

Posted on 2026-01-16 Edited on 2026-04-06

题目大意

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

游戏规则:

两人在一个长度为 n 的数组上进行游戏,数组只包含 0 和 1
Alice 先手,双方轮流操作
每次操作选择区间 [l, r],将该区间替换为单个数字 $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”(大小写不敏感)

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

思路讲解

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

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

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

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

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

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

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

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

源代码

/**
 * Problem: A. Binary Array Game
 * Contest: Hello 2026
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2183/problem/A
 * Created: 2026-01-16 10:40:44
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    if (find(all(A),0)==A.end()) {
        cout<<"Alice\n";
        return;
    }
    if (A.front() || A.back()) {
        cout<<"Alice\n";
        return;
    }
    cout<<"Bob\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

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

CF-1072-G. Nastiness of Segments

Posted on 2026-01-15 Edited on 2026-04-06

题目大意

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

对于一个连续段 [l, r]，如果整数 d (0 ≤ d ≤ r - l) 满足 $min(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=d$ 的这个情况的数量，由于 $d$ 是严格递增的， $mn$ 是非严格递减的，这两者显然最多只有一个交点。

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

AC代码

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

源代码

/**
 * Problem: G. Nastiness of Segments
 * Contest: Codeforces Round 1072 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2184/problem/G
 * Created: 2026-01-16 09:39:42
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
// by Gospel_rock znzryb
// 参考了（抄了）OIwiki
// https://www.luogu.com.cn/record/228807838 ST表模版题（max）
// https://www.luogu.com.cn/record/228809172 打乱了插入顺序，和上面是同一道
struct RMQ{
    const ll dummy=INF;
    ll n;vector<ll> tr;vector<ll> origin;
    inline ll lowbit(const ll &x){
        return x&-x;
    }
private:
    ll op(const ll &a,const ll &b){
        return min(a,b);
    }
public:
    RMQ(ll n){
        this->n=n+2;
       tr.resize(n+5,INF),origin.resize(n+5);
    }
    ll query(ll l,ll r){
        ll res=dummy;
        while (r>=l) {
            res=op(origin[r],res);
            r--;
            for(;r-lowbit(r)>=l;r-=lowbit(r)){
                res=op(res, tr[r]);
            }
        }
        return res;
    }
    void upd(ll p,ll x){    // 其实不是增加
        origin[p]=x;
        for(int i=p;i<=n;i+=lowbit(i)){
            tr[i]=origin[i];
            for(int j=1;j<lowbit(i);j<<=1){
                tr[i]=op(tr[i],tr[i-j]);
            }
        }
    }
};
void Solve() {
    ll N,Q;
    cin >> N >> Q;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    RMQ tr(N);
    for (int i=1;i<=N;++i) {
        tr.upd(i,A[i]);
    }
    for (int _=1;_<=Q;++_) {
        ll op;
        cin>>op;
        if (op==1) {
            ll pos,x;
            cin>>pos>>x;
            tr.upd(pos,x);
        }else {
            ll l,r;
            cin>>l>>r;
            ll bsl=0,bsr=r-l;
            auto check=[&](ll x) {
                ll mn=tr.query(l,l+x);
                if (mn>x) {
                    return 0;
                }
                if (mn==x) return 1;
                return 2;
            };
            while (bsl<bsr) {
                ll mid=(bsl+bsr)>>1;
                if (check(mid)) {
                    bsr=mid;
                }else {
                    bsl=mid+1;
                }
            }
            if (check(bsl)==1) {
                cout<<1<<"\n";
            }else {
                cout<<0<<"\n";
            }
        }
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

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

CF-1072-F. Cherry Tree（不要忘记 dp，特别是子问题相互重叠之时）

Posted on 2026-01-15 Edited on 2026-04-06

题目大意

给定一棵有 n 个顶点的有根树,根节点为 1。每个叶子节点上都有一个樱桃。

你需要通过"摇动"顶点来收集所有樱桃。摇动顶点 v 时,所有作为 v 后代的叶子节点上的樱桃都会掉落。每个叶子的樱桃只能掉落一次,否则树会损坏。

关键限制:摇动的顶点数量必须是 3 的倍数。

问题:是否可能在满足上述条件下收集所有樱桃?

输入格式:

第一行:测试用例数 t (1 ≤ t ≤ 10⁴)
每个测试用例:第一行为 n (2 ≤ n ≤ 2×10⁵),接下来 n-1 行描述树的边

**输出格式:**对每个测试用例输出 “YES” 或 “NO”

思路讲解

当你发现一个问题的子结构之间互相重叠覆盖，其中还涉及这个决策的时候，这个时候，你就要想，是不是 dp 了。

树上 dp，定义状态为 $dp_{u,i}$ ，指的是以 $u$ 为根的子树中，是否可以凑出来为这个 $i\ (0,1,2)$ 的这个 3 的余数。

接着问题就来到了如何转移？我们不妨定义， $to$ 为转移过来的子节点，四个你可以理解为 bitset 的东西，长度为 3， $bi$ 为目前的状态，若 $dp_{to,0}$ 为 true，那么 $bi1$ 就是这个 $bi$ 向前循环移动的结果，否则 $bi1$ 为全 0。同理，我们可以定义出 $bi0$ ， $bi2$ 。最终经过这个 $to$ 节点的转移后， $bi\gets bi0 \lor bi1 \lor bi2$ 。（当然，第一个 $to$ 节点转移过来的话，为了初值确定， $bi\gets dp_{to}$ ）

最后，令 $bi_1\gets \text{true}$ （因为我们始终可以选择子树根节点，来解决这个问题），接着 $dp_u\gets bi$ 。

为什么要这么转移？我们会发现，就是说如果子树只有一个唯一的位移的话，是不是只是让这个状态进行一个位移？那么其实只有一个位移是没什么大用的，但是如果有两种位移？三种位移？这几种位移之间如何组合？那么答案就昭然若揭了。

AC代码

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

源代码

/**
 * Problem: F. Cherry Tree
 * Contest: Codeforces Round 1072 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2184/problem/F
 * Created: 2026-01-15 14:06:26
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll>> g(N+2);
    for (int i=1;i<=N-1;++i) {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<vector<int>> dp(N+2,vector<int>(3));
    auto dfs=[&](auto && self,ll u,ll p) -> void {
        vector<int> bi(3);
        // 循环左移
        auto left_move=[&](ll x) {
            vector<int> res(3);
            for (int i=0;i<3;++i) {
                res[(i+x)%3]=bi[i];
            }
            return res;
        };
        auto fun_or=[&](vector<int> a,vector<int> b) {
            for (int i=0;i<3;++i) {
                a[i]|=b[i];
            }
            return a;
        };
        int cnt =  0;

        for (auto v:g[u]) {
            if (v==p) continue;
            self(self,v,u);
            if (cnt ==  0) {
                bi=dp[v];
                cnt++;
                continue;
            }
            vector<int> bi1(3),bi2(3),bi0(3);
            if (dp[v][0]) {
                bi0=left_move(0);
            }
            if (dp[v][1]) {
                bi1=left_move(1);
            }
            if (dp[v][2]) {
                bi2=left_move(2);
            }
            bi=fun_or(bi0,fun_or(bi1,bi2));
        }
        bi[1]=1;
        dp[u]=bi;
    };
    dfs(dfs,1,0);

    cout << (dp[1][0] ? "YES\n":"NO\n");
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2184/submission/357994744

*/