Znzryb's Blog

CF-1073-E. Comparable Permutations（单调性的变化）

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

题目大意

任务目标

已知一个隐藏的长度为 $n$ 的排列 $p$ 。你需要找到一个字典序最小的排列 $q$ ，使得 $q$ 满足以下两个条件：

$q > p$ （ $q$ 的字典序大于 $p$ ）
$rev(q) > rev(p)$ （ $q$ 翻转后的字典序大于 $p$ 翻转后的字典序）

注意： $q$ 必须是由 $p$ 中的元素重新排列得到的。你不需要直接输出 $q$ ，而是输出一个下标排列 $r$ ( $1 \le r_i \le n$ )，使得 $q_i = p_{r_i}$ 。如果不存在满足条件的 $q$ ，输出 $-1$ 。

2. 交互规则

你可以进行询问，格式为 ? i j，查询 $p_i < p_j$ 是否成立。
如果 $p_i < p_j$ ，交互库返回 $1$ ；否则返回 $0$ 。
每个测试点最多允许询问 $3n$ 次。
交互库是非自适应的（隐藏排列 $p$ 在交互开始前已确定）。

3. 样例解释

样例 1： $p = [5, 4, 2, 3, 1]$
- 满足条件的最小 $q$ 为 $[5, 4, 3, 1, 2]$ 。
- 验证： $q$ 比 $p$ 字典序大； $rev(q) = [2, 1, 3, 4, 5]$ ， $rev(p) = [1, 3, 2, 4, 5]$ ，显然 $rev(q) > rev(p)$ 。
- 输出 $r = [1, 2, 4, 5, 3]$ ，因为 $p_1=5, p_2=4, p_4=3, p_5=1, p_3=2$ 。
样例 2： $p = [3, 1, 2, 4]$
- 不存在同时满足 $q > p$ 且 $rev(q) > rev(p)$ 的排列 $q$ ，故输出 $-1$ 。

4. 数据范围

$t \le 1000$ ， $n \le 2 \cdot 10^4$ ，所有测试用例的 $n$ 之和不超过 $2 \cdot 10^4$ 。
时间限制 2 秒，内存限制 256 MB。

思路讲解

一开始看这道题目，不能看出来像下面这张图的解法，但是我们会误以为这个情况的一些其他性质比较重要，但是最重要的是单调性的变化，因为没有单调性的变化意味着没有这个答案。

因此，这道题目关键点在于这个单调性的变化（即未发生单调性变化下操作是没有意义的，一定会违反题设条件），我们先来看这个情况，不难发现，在单调性变化之后执行交换与这个反转操作最好。

那么如果先下降呢？经过对拍验证以及这个推理，如果先下降再上升，是无法构造出答案的。原因：设在当前点，你需要构造 $q$ ，以满足题设条件。因此，你要提高 $q$ 的字典序，那么必须要在后面的点当中选一个比当前点高的（最优的是恰好高的），但是这样一来，就会导致 $\text{rev}(q)$ 的字典序下降（这个是无法挽救的，因为目前的更换的当前点处于上升序列，处于上升序列的其他点比当前点低，处于下降序列的其他点比当前点低），导致无法满足题设条件。

因此先下降，再上升的话，必须要再找一个下降。

然后，交换好以后，就想办法把这个上升序列插入到这个下降序列当中（有序插入，保持单调下降性），随便你用什么办法。

然后为了减少提问个数，我们使用了记忆化，就是问过的，就不再问了（注意问了 a b 的话，b a 也不要再问了）。

感觉这道题目难度主要还是在这个调试，代码和细节上。

AC代码

AC
https://codeforces.com/contest/2191/submission/359093232

源代码

/**
 * Problem: E. Comparable Permutations
 * Contest: Codeforces Round 1073 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2191/problem/E
 * Created: 2026-01-21 22:46:09
 * 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;

/*
 *
 */
#ifdef LOCAL
#include "E_grader.h"
Grader grader;
#endif

// 返回 1 为严格小于，返回 0 是 ≥
int query_is_a_lt_b(int a,int b,map<pair<int,int>,int> &memo) {
    if (a==b) return 1;
    if (memo.contains({a,b})) {
        return memo[{a,b}];
    }
    int res;
#ifdef LOCAL
    res = grader.query_is_a_lt_b(a,b);
#else
    cout<<"? "<<a<<" "<< b<<endl;
    cin>>res;
#endif
    memo[{a,b}]=res;
    memo[{b,a}]=res^1;
    return res;
}
int query_is_a_gt_b(int a,int b,map<pair<int,int>,int> &memo) {
    if (memo.contains({a,b})) {
        return !memo[{a,b}];
    }
    int res;
#ifdef LOCAL
    res=grader.query_is_a_lt_b(a,b);
#else
    cout<<"? "<<a<<" "<< b<<endl;
    cin>>res;
#endif
    memo[{a,b}]=res;
    memo[{b,a}]=res^1;
    return !res;
}
void out_ans(bool have_ans,const vector<ll> &perm,ll N) {
#ifdef LOCAL
    grader.out_ans(have_ans,perm,N);
    return;
#endif
    if (!have_ans) {
        cout<<"! "<<-1<<endl;
        return;
    }
    cout<<"! ";
    for (int i=1;i<=N;++i) {
        cout<<perm[i]<<" ";
    }
    cout<<endl;
}


void Solve() {
    ll N;
    cin >> N;
#ifdef LOCAL
    grader=Grader(N);
#endif

    map<pair<int,int>,int> memo;
    // 我们先来找一下最大的 i
    ll big_i=0;
    for (int i=N-1;i>=1;--i) {
        int is_a_small_b=query_is_a_lt_b(i,i+1,memo);
        if (is_a_small_b) {
            big_i=i;
            break;
        }
    }
    vector<ll> perm(N+2);
    for (int i=1;i<=N;++i) {
        perm[i]=i;
    }
    if (big_i==0) {
        out_ans(false,perm,N);
        return;
    }
    // 如果说 big_i 后有这个周旋的空间，那就很好了
    if (big_i!=N-1) {
        // 二分查找第一个比 i 大的 j
        ll j_1st_gt_i=0;
        // 6 5 4
        ll bsl=big_i+1,bsr=N;
        auto check=[&](ll idx) {
            int res=query_is_a_lt_b(big_i,idx,memo);
            return res;
        };
        while (bsl<bsr) {
            ll mid=(bsl+bsr+1)>>1;
            if (check(mid)) {
                bsl=mid;
            }else {
                bsr=mid-1;
            }
        }
        j_1st_gt_i=bsl;
        swap(perm[j_1st_gt_i],perm[big_i]);
        reverse(perm.begin()+big_i+1,perm.begin()+N+1);
        out_ans(true,perm,N);
    }else {
        // 我们要找到这个第二个下降出现（4 5 6这样子）
        ll end_of_down=big_i;
        ll sec_down_start=0;
        for (int i=big_i-1;i>=1;--i) {
            if (query_is_a_lt_b(i,i+1,memo)) {
                if (end_of_down-i>1) {
                    sec_down_start=i;
                    break;
                }
                end_of_down=i;
            }
        }
        if (sec_down_start==0) {
            // 不开始第二次下降等于不对
            out_ans(false,perm,N);
            return;
        }
        auto check_bs=[&](ll i) {
            return query_is_a_gt_b(i,sec_down_start,memo);
        };
        auto range1=views::iota(sec_down_start+1,end_of_down);
        auto it1=ranges::partition_point(range1,check_bs);
        auto range2=views::iota(end_of_down,N+1)|views::reverse;
        auto it2=ranges::partition_point(range2,check_bs);

        it1=ranges::prev(it1);

        ll to_be_select=*it1;
        if (it2!=range2.begin()) {
            it2=ranges::prev(it2);
            if (query_is_a_lt_b(*it2,*it1,memo)) {
                to_be_select=*it2;
            }
        }
        swap(perm[to_be_select],perm[sec_down_start]);
        vector after_sec_down_ls(perm.begin()+end_of_down,perm.begin()+N+1);
        ll idx=-1;
        auto check=[&](ll pos) {
            if (idx==-1) {
                if (query_is_a_lt_b(pos,after_sec_down_ls[idx+1],memo)) {
                    return true;
                }
                return false;
            }
            if (idx>=after_sec_down_ls.size()) {
                --idx;
                return true;
            }
            if (idx+1>=after_sec_down_ls.size()) {
                if (query_is_a_lt_b(after_sec_down_ls[idx],pos,memo)) {
                    return true;
                }
                return false;
            }
            if (query_is_a_lt_b(after_sec_down_ls[idx],pos,memo) &&
                query_is_a_lt_b(pos,after_sec_down_ls[idx+1],memo)) {
                return true;
            }
            return false;
        };

        for (int i=end_of_down-1;i>sec_down_start;--i) {
             ll pos=perm[i];
            while (!check(pos)) {
                ++idx;
            }
            after_sec_down_ls.insert(after_sec_down_ls.begin()+idx+1,pos);
        }
        for (int i=sec_down_start+1;i<=N;++i) {
            perm[i]=after_sec_down_ls[i-sec_down_start-1];
        }
        out_ans(true,perm,N);
    }
}

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

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

/*
1



_______________[ Stress test, testcase 3 INPUT ]_______________
1
5
2 3 5 1 4

_______________[ Stress test, testcase 3 OUTPUT]_______________
WA
hide perm: 2 3 5 1 4
ans_ls: 2 4 1 3 5
ans_rec: 2 3 5 4 1


WA
hide perm: 8 1 9 3 5 4 2 6 7
ans_ls: 8 1 9 4 2 3 5 6 7
ans_rec: 8 1 9 4 6 7 2 3 5

WA
hide perm: 2 3 1 4 5
ans_ls: 3 1 2 4 5
ans_rec: 3 4 5 1 2

*/

暴力 grader.h 实现（函数式交互）

//
// Created by zz y on 2026/1/20.
//

#ifndef E_GRADER_H
#define E_GRADER_H
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Grader {
    vector<ll> perm_ls;
    ll N;
    // vector<ll> num_pos_ls;
    vector<ll> ans_ls;
    ll cnt_query=0;
    bool is_a_gt_b(const vector<ll> &a,const vector<ll> &b) const {
        for (int i=1;i<=N;++i) {
            if (a[i]<b[i]) {
                return false;
            }else if (a[i]>b[i]) {
                return true;
            }
        }
        return false;
    }

    bool check() {
        vector<ll> ans_ls_rev=ans_ls;
        vector<ll> perm_ls_rev=perm_ls;
        reverse(perm_ls_rev.begin()+1,perm_ls_rev.begin()+N+1);
        reverse(ans_ls_rev.begin()+1,ans_ls_rev.begin()+N+1);
        return is_a_gt_b(ans_ls,perm_ls) && is_a_gt_b(ans_ls_rev,perm_ls_rev);
    }
    bool exist_ans=false;
    explicit Grader(ll N):N(N) {
        perm_ls.resize(N+2);
        for (int i=1;i<=N;++i) {
            cin>>perm_ls[i];
        }
        // shuffle(perm_ls.begin()+1,perm_ls.begin()+N+1,rng);
        // for (int i=1;i<=N;++i) {
        //     ll num=perm_ls[i];
        //     num_pos_ls[num]=i;
        // }
        ans_ls=perm_ls;
        sort(ans_ls.begin()+1,ans_ls.begin()+N+1);
        do {
            if (check()) {
                exist_ans=true;
                break;
            }
        }while (next_permutation(ans_ls.begin()+1,ans_ls.begin()+N+1));
    }
    Grader()=default;
    int query_is_a_lt_b(int a,int b) {
        // if (a==b) return 1;
        if (a<=0 || a>N || b<=0 || b>N) {
            cout<<"a b over [1,N] "<< a << " "<< b<<"\n";
        }
        ++cnt_query;
        if (cnt_query>3*N) {
            cout<<"over 3*N queries"<<"\n";
        }
        return perm_ls[a]<perm_ls[b];
    }

    void out_ans(bool have_ans,const vector<ll> &perm,ll N) {
        vector<ll> ans_rec(N+2);
        for (int i=1;i<=N;++i) {
            ans_rec[i]=perm_ls[perm[i]];
        }
        auto print_error=[&]() {
            cout<<"WA\n";
            cout<<"exist_ans: "<<exist_ans<<"\n";
            cout<<"hide perm: ";
            for (int j=1;j<=N;++j) {
                cout<<perm_ls[j]<<" ";
            }
            cout<<"\n";
            cout<<"ans_ls: ";
            for (int j=1;j<=N;++j) {
                cout<<ans_ls[j]<<" ";
            }
            cout<<"\n";
            cout<<"ans_rec: ";
            for (int j=1;j<=N;++j) {
                cout<<ans_rec[j]<<" ";
            }
            cout<<"\n";
        };
        if (exist_ans!=have_ans) {
            print_error();
            return;
        }
        if (!exist_ans && exist_ans==have_ans) {
            cout<<"AC\n";
            return;
        }

        for (int i=1;i<=N;++i) {
            if (ans_rec[i]!=ans_ls[i]) {
                print_error();
                return;
            }
        }
        cout<<"AC\n";
    }
};


#endif //E_GRADER_H

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

CF-1073-D2. Sub-RBS (Hard Version)（注意虚拟节点可能的操作特判）（括号序列 dp 的状态设计）

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

题目大意

1. 核心定义

括号序列比较 (“Better Than”)：
对于两个括号序列 $a$ 和 $b$ ，满足以下条件之一则称 $a$ 比 $b$ “更好”：
1. $b$ 是 $a$ 的前缀，且 $a \neq b$ 。
2. 在第一个不相同的字符位置 $i$ ， $a_i = '('$ 且 $b_i = ')'$ 。
序列 $t$ 的得分 (Score)：
1. 如果 $t$ 不是正则括号序列 (RBS)，得分为 $0$ 。
2. 如果 $t$ 是 RBS，查找其所有的正则括号子序列 $r$ 。如果存在某些 $r$ 满足 $r$ 比 $t$ “更好”，则得分为这些 $r$ 中长度 $|r|$ 的最大值。
3. 若不存在这样的 $r$ ，得分为 $0$ 。

2. 任务要求

给定一个长度为 $n$ ( $1 \le n \le 100$ ) 的括号序列 $s$ ，求 $s$ 的所有非空子序列的得分之和，结果对 $998244353$ 取模。

3. 样例解释

样例 2：s = ()()()
考虑其中一个子序列 $t = "()()()"$ ：
- 它是一个 RBS。
- 它有一个子序列 $r = "(())"$ （取原序列第 1, 3, 4, 6 位）。
- 比较 $t$ 和 $r$ ：第一位都是 (，第二位 $t_2 = ')'$ 而 $r_2 = '('$ 。根据定义， $r$ 比 $t$ 更好。
- $r$ 的长度为 $4$ ，经校验这是最长的更好子序列，故该子序列 $t$ 得分为 $4$ 。
- 其他子序列得分均为 $0$ ，总和为 $4$ 。
样例 3：****s = (())()
- 对于子序列 $t = "(())()"$ ，虽然它是 RBS，但无法找到比它“更好”的 RBS 子序列。
- 例如，要在某位置 $i$ 更好，必须 $t_i = ')'$ 且 $r_i = '('$ ，但在该位置之前， $t$ 已经用完了所有的 ( 匹配了前面的 )，无法构造出更优的正则子序列。
- 因此总和为 $0$ 。

思路讲解

首先，D1 当中，我们发现一个规律，就是只要 $s$ 串只要是有答案的，其答案就是 $|s|-2$ ，那么其有答案的条件是第一个 $)$ 出现的位置后，又至少出现了出现了两个 $($ 。

我们可以定义一个如下状态：

⚠️注意：这里的长度，个数，指的是合法方案个数及其合法方案的总（后缀）长度，这样子定义是为了方便记忆化搜索。

总体上的记忆化搜索过程可以描述为这样：

\begin{aligned} & res \gets (0,0) \\ & \text{if } unbalance = 0 \land state = 3: res \gets (1,1) \\ & lres \gets \text{dfs}(idx, unbalance, state) \\ & \text{if } idx \neq 0: lres_{\text{len}} \gets lres_{\text{len}} + lres_{\text{num}} \\ & res \gets res + lres\end{aligned}

那么之所以不在 $idx=0$ 的时候进行这个操作，是因为 0 是虚拟节点，没有实际字符。

auto dfs=[&](auto && self,int idx,int unbalance,int state) -> Len_num{
    if (unbalance<0) {
        return {0,0};
    }
    if (vis[idx][unbalance][state]) {
        return dp[idx][unbalance][state];
    }
    vis[idx][unbalance][state]=true;
    // assert(idx<=N);
    Len_num res={0,0};
    if (unbalance==0 && state==3) {
        // 相当于只选这个 s【idx】的时候
        res={1,1};
    }
    for (int i=idx+1;i<=N;++i) {
        Len_num lres;
        if (s[i]==')') {
            lres=self(self,i,unbalance-1,max(1,state));
        }else {
            int to_state;
            if (state==0) to_state=0;
            else to_state=min(3,state+1);
            lres=self(self,i,unbalance+1,to_state);
        }
        res+=lres;
        // 0 是一个虚拟节点，不会增加这个 res 长度
        if (lres.len!=0 && idx!=0) {
            // 这里给所有的方案增加一个长度，即选了
            res.len+=lres.num;
        }
        res%=mod;
    }
    dp[idx][unbalance][state]=res;
    return res;
};
Len_num res=dfs(dfs,0,0,0);

AC代码

AC
https://codeforces.com/contest/2191/submission/358546432

源代码

/**
 * Problem: D2. Sub-RBS (Hard Version)
 * Contest: Codeforces Round 1073 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2191/problem/D2
 * Created: 2026-01-18 01:00: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;

/*
 *
 */
struct Len_num {
    ll len,num;
    void operator+=(const Len_num &o) {
        len+=o.len;
        num+=o.num;
    }
    void operator%=(const ll a) {
        len%=a;
        num%=a;
    }
};
void Solve() {
    ll N;
    cin >> N;
    string s;
    cin>>s;
    s.insert(s.begin(),'#');
    // dp 里面存的是合法方案数
    vector dp(N+2,vector(N+2,vector<Len_num>(4)));
    vector vis(N+2,vector(N+2,vector<char>(4)));
    auto dfs=[&](auto && self,int idx,int unbalance,int state) -> Len_num{
        if (unbalance<0) {
            return {0,0};
        }
        if (vis[idx][unbalance][state]) {
            return dp[idx][unbalance][state];
        }
        vis[idx][unbalance][state]=true;
        // assert(idx<=N);
        Len_num res={0,0};
        if (unbalance==0 && state==3) {
            // 相当于只选这个 s【idx】的时候
            res={1,1};
        }
        for (int i=idx+1;i<=N;++i) {
            Len_num lres;
            if (s[i]==')') {
                lres=self(self,i,unbalance-1,max(1,state));
            }else {
                int to_state;
                if (state==0) to_state=0;
                else to_state=min(3,state+1);
                lres=self(self,i,unbalance+1,to_state);
            }
            res+=lres;
            // 0 是一个虚拟节点，不会增加这个 res 长度
            if (lres.len!=0 && idx!=0) {
                res.len+=lres.num;
            }
            res%=mod;
        }
        dp[idx][unbalance][state]=res;
        return res;
    };
    Len_num res=dfs(dfs,0,0,0);
    ll ans=res.len-res.num*2;
    ans%=mod;
    if (ans<0) {
        ans+=mod;
    }
    cout<<ans<<"\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/2191/submission/358546432

1
1
(

1
6
()()()

*/

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

res\gets \{0,0\}\\ unbalance=0 \text{ and } state=3:res\gets \{1,1\} \\ lres\gets \text{dfs}(idx,unbalance,state)\\ idx≠0:lres.len\gets lres.len+lres.num\\ res\gets res+lres

CF-1073-C. Sorting Game（考虑和终态不一样的点）

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

题目大意

Alice 和 Bob 在长度为 n 的二进制字符串 s(仅包含字符 0 和 1)上进行博弈游戏。Alice 先手,双方轮流操作。

游戏规则:

每回合,玩家选择一个索引序列 i₁, i₂, …, iₘ(严格递增),使得这些位置的字符形成非增序列(s[i₁] ≥ s[i₂] ≥ … ≥ s[iₘ])
然后将这些位置的字符重新排列为非减序列(先放所有 0,再放所有 1)
有效移动必须严格改变字符串(即选中的字符中至少有一个 0 和一个 1)
无法进行有效移动的玩家输掉游戏

任务:

假设双方都采用最优策略,判断谁会获胜
如果 Alice 获胜,输出她的一个获胜首步移动(索引序列)

输入格式:

多组测试数据,第一行包含测试数据组数 t(1 ≤ t ≤ 10⁴)
每组数据:第一行为字符串长度 n(1 ≤ n ≤ 2×10⁵),第二行为二进制字符串 s
保证所有测试用例的 n 之和不超过 2×10⁵

输出格式:

如果 Bob 获胜,输出 “Bob”
如果 Alice 获胜,输出三行:第一行 “Alice”,第二行整数 m(选中的索引数量),第三行 m 个递增的索引

样例说明:

样例 1(000):字符串已经有序,无法进行任何有效移动,Bob 直接获胜
样例 3(10):Alice 可以选择位置 [1,2],将字符串变为 01,之后 Bob 无法移动,Alice 获胜

思路讲解

其实我们会发现，只需要一次操作即可解决这个问题。

AC代码

https://codeforces.com/contest/2191/submission/358351618

源代码

/**
 * Problem: C. Sorting Game
 * Contest: Codeforces Round 1073 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2191/problem/C#
 * Created: 2026-01-18 00:37:57
 * 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;
    string s;
    cin>>s;
    string sorted_str=s;
    sort(all(sorted_str));
    vector<ll> op_ls;
    for (int i=0;i<N;++i) {
        if (sorted_str[i]!=s[i]) {
            op_ls.push_back(i);
        }
    }
    if (op_ls.empty()) {
        cout<<"Bob\n";
        return;
    }
    cout<<"Alice\n";
    cout<<SZ(op_ls)<<"\n";
    for (auto pos:op_ls) {
        cout<<pos+1<<" ";
    }
    cout<<"\n";
}

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

/*

*/

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

Hello 2026——D2. Tree Coloring (Hard Version)（随机化算法可以分层实现）（猜测答案时，可以先猜测一个下界然后尝试不断提升）

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

题目大意

问题描述:

给定一棵有 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 过题比较多，那么就要想到，可能就是猜结论了，不过直接猜出来比较难，我们可以先猜猜下界。首先，设 $t_i$ 为第 $i$ 层的节点个数，那么 $ans≥\text{max}(t_1,\cdots,t_n)$ 是肯定的，不过，如果说 $i$ 层的这个所有节点都共用一个根节点，这个时候还需要对 $t_i+1$ 取 max 值。（这个就是 easy 版本的结论）

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

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

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代码

/**
 * Problem: D1. Tree Coloring (Easy Version)
 * Contest: Hello 2026
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2183/problem/D1
 * Created: 2026-01-17 19:53:19
 * 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<ll>> dep_node_mtx(N+2);
    vector<set<ll>> dep_fa_mtx(N+2);
    ll mx_dep=0;
    auto dfs=[&](auto && self,ll u,ll p,ll dep) -> void {
        dep_node_mtx[dep].push_back(u);
        dep_fa_mtx[dep].insert(p);
        mx_dep=max(mx_dep,dep);
        for (auto to:g[u]) {
            if (to==p) {
                continue;
            }
            self(self,to,u,dep+1);
        }
    };
    dfs(dfs,1,-1,1);
    ll ans=0;
    for (int i=1;i<=mx_dep;++i) {
        ll ti=SZ(dep_node_mtx[i]);
        if (dep_fa_mtx[i].size()<=1) {
            ans=max(ans,ti+1);
        }else {
            ans=max(ans,ti);
        }
    }
    cout<<ans<<"\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/358257705

/**
 * Problem: D2. Tree Coloring (Hard Version)
 * Contest: Hello 2026
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2183/problem/D2
 * Created: 2026-01-17 20:14:41
 * 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;

/*
 *
 */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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<ll>> dep_node_mtx(N+2);
    vector<set<ll>> dep_fa_mtx(N+2);
    vector<ll> parent(N+2);
    ll mx_dep=0;
    auto dfs=[&](auto && self,ll u,ll p,ll dep) -> void {
        parent[u]=p;
        dep_node_mtx[dep].push_back(u);
        dep_fa_mtx[dep].insert(p);
        mx_dep=max(mx_dep,dep);
        for (auto to:g[u]) {
            if (to==p) {
                continue;
            }
            self(self,to,u,dep+1);
        }
    };
    dfs(dfs,1,0,1);
    ll ans=0;
    vector<ll> color(N+2);
    for (int i=1;i<=mx_dep;++i) {
        ll ti=SZ(dep_node_mtx[i]);
        if (dep_fa_mtx[i].size()<=1) {
            ans=max(ans,ti+1);
        }else {
            ans=max(ans,ti);
        }
    }
    vector<vector<ll>> op_mtx(ans+2);
    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;
            }
        }
    }
    cout<<ans<<"\n";
    for (int i=1;i<=N;++i) {
        op_mtx[color[i]].push_back(i);
    }
    for (int i=1;i<=ans;++i) {
        cout<<SZ(op_mtx[i])<<" ";
        for (auto u:op_mtx[i]) {
            cout<<u<<" ";
        }
        cout<<"\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/358257705

*/

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

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

源代码

/**
 * Problem: D1. Tree Coloring (Easy Version)
 * Contest: Hello 2026
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2183/problem/D1
 * Created: 2026-01-17 15:49:35
 * 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;

/*
 *
 */
// struct Dep_node {
//     ll dep,node;
// };
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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);
    }
    for (int i=1;i<=N;++i) {
        sort(all(g[i]));
    }

    vector<vector<ll>> dep_node_mtx(N+2);
    ll mx_dep=0;
    auto dfs=[&](auto && self,ll u,ll p,ll dep) -> void {
        dep_node_mtx[dep].push_back(u);
        mx_dep=max(mx_dep,dep);
        for (auto to:g[u]) {
            if (to==p) {
                continue;
            }
            self(self,to,u,dep+1);
        }
    };
    dfs(dfs,1,-1,1);
    // 我们每次都先选这个入度最大的点，因此我们先对这个入度大的点进行这个排序
    for (int i=1;i<=N;++i) {
        shuffle(all(dep_node_mtx[i]),rng);
        stable_sort(all(dep_node_mtx[i]),[&](const ll &a,const ll &b) {
            return SZ(g[a])<SZ(g[b]);
        });
    }
    ll processed_node=0;
    auto check_is_connect=[&](ll u,ll v) {
        if (binary_search(all(g[u]),v)) {
            return true;
        }
        return false;
    };
    ll ans=0;
    while (processed_node<N) {
        vector<ll> del_node_ls;
        for (int i=1;i<=mx_dep;++i) {
            if (dep_node_mtx[i].empty()) {
                continue;
            }
            ll u=0;
            if (!del_node_ls.empty()) u=del_node_ls.back();
            for (int j=SZ(dep_node_mtx[i])-1;j>=0;--j) {
                ll v=dep_node_mtx[i][j];
                if (!check_is_connect(v,u)) {
                    dep_node_mtx[i].erase(dep_node_mtx[i].begin()+j);
                    del_node_ls.push_back(v);
                    break;
                }
            }
        }
        ++ans;
        processed_node+=SZ(del_node_ls);
    }
    cout<<ans<<"\n";
}

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

/*

*/

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

同一层里每个点只禁用 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

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

$du[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，有的顺序一把过，有的顺序必炸。

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

*/