B. 细节博弈

$\hspace{15pt}$ 知识点：博弈论（对称博弈）、贪心、字符串。

$\hspace{15pt}$ 预估难度：1200。

题解

解题思路

不难发现，如果Alice无法一次将所有的的元素变成A，那么无论接下来怎么操作，Bob都可以镜像防守，将Alice的操作还原回去，使得Alice操作无效化。

过程实现

我们可以 $O(n)$ 遍历一下字符串，找到最左边的字符 B 和最右边的字符 B，记录为 $L$ 和 $R$ 。
计算两个 B 的最远距离是否超过 $k$ ，如果没超过，说明 Alice 能够一次把字符串变成全部由 A 组成的字符串，Alice 胜利；否则 Bob 胜利。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t = 1;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        string a;
        cin >> a;
        int l = 0, r = 0;
        for (int i = 0; i < a.size(); i++) {
            if (a[i] == 'B') {
                l = i;
                break;
            }
        }
        for (int i = (int)(a.size()) - 1; i >= 0; i--) {
            if (a[i] == 'B') {
                r = i;
                break;
            }
        }
        cout << (r - l + 1 <= k ? "Alice" : "Bob") << '\n';
    }
    return 0;
}

C. 超级蜗牛

$\hspace{15pt}$ 知识点：二分查找、模拟。

$\hspace{15pt}$ 预估难度：1400。

题解

题目大意

$\hspace{15pt}$ 有一只蜗牛他会按照奇数天数上爬偶数天数下滑的模式在无限高的墙上进行活动，你需要对 $m$ 次询问进行回答，每次询问给出一个高度 $x$ 回答需要爬到这个高度的最小天数。

思路

$\hspace{15pt}$ 观察题目发现，蜗牛进行的周期性攀爬，所以我们可以用前缀和预处理一个周期，对于每一天记录这一天结束时的所在高度，并额外记录这个周期蜗牛每次刷新最高高度的位置以及此时的天数。接下来对每次询问进行分类讨论：

$\hspace{23pt}\bullet\,$ 第一种情况为询问值 $x$ 不超过一次周期的最高值（注意，最高值不是周期结束时的高度），说明在第一个周期即可达到这个高度 $x$ ，我们只需要在上述额外记录状态中简单二分高度对应的最小天数即可。

$\hspace{23pt}\bullet\,$ 第二种情况为询问值 $x$ 大于一次周期的最高值，并且一次周期结束的位置变化量为正数（即一次周期后的高度大于周期前的高度），我们需要先简单算出需要多少个完整周期，设需要完整周期 $y$ 周期，那么 $y$ 是满足式子 $y \times$ 周期位置变化量 $\leqq x$ 的最大值，简单算出 $y$ 之后按照第一种情况二分剩余高度所需天数即可。

$\hspace{23pt}\bullet\,$ 第三种情况为询问值 $x$ 大于一次周期的最高值，并且一次周期结束的位置变化量为非正数，此时一个周期过后蜗牛高度无法上升即永远我无法达到询问高度，输出 $-1$ 。

算法即时间复杂度解析

$\hspace{15pt}$ 前缀和、二分查找、分类讨论、预处理算法

$\hspace{15pt}$ 时间复杂度：前缀和预处理为 $O(n)$ 时间复杂度，单次查找需要 $O(logn)$ 时间复杂度，整体时间复杂度为 $O(nlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while (T--){
        int n,m;
        cin>>n>>m;
        vector<ll> a(2*n+1);
        vector<pair<ll,ll>> b;
        for (int i=1;i<=2*n;i++) {
            cin>>a[i];
            a[i]=a[i-1]+a[i]*(i%2==1?1:-1);
            if (b.empty()||b.back().first<a[i]) b.push_back({a[i],i});
        }
        while(m--){
            ll x;
            cin>>x;
            ll y=x-b.back().first;
            ll z=0;
            if (y>0){
                if (a[2*n]<=0){
                    cout<<-1<<'\n';
                    continue;
                }
                ll xx=(y/a[2*n]+(y%a[2*n]!=0));
                x-=xx*a[2*n];
                z+=xx*2*n;
            }
            ll l=0,r=b.size()-1,mid;
            while(l!=r){
                mid=l+r>>1;
                if (b[mid].first>=x) r=mid;
                else l=mid+1;
            }
            cout<<b[l].second+z<<'\n';
        }
    }
}

D. 遥控器

$\hspace{15pt}$ 知识点：dfs，预处理，前缀和，组合数学。

$\hspace{15pt}$ 预估难度：1600。

题解

题意

$\hspace{15pt}$ 这道题的核心是计算在给定操作下能够产生的不同排列的总数：统计有多少个排列 $\pi$ ，满足其支撑集 $S(\pi)$ 构成树上的一条链。

思路

$\hspace{15pt}$ 首先，分析操作的本质。在一条祖先-后代路径P上，选择偶数个点 $b_1, \dots, b_m$ 并依次进行交换 $(a_{b_{2i-1}}, a_{b_{2i}})$ ，这个操作等价于对路径P上的点的对应值施加一个由 $m/2$ 次对换构成的排列。因为我们可以任意选择点（允许重复），并且可以构造任意长度的偶数序列，所以我们可以实现任意次数的对换。这等价于我们可以在路径P上的点集 $S_P$ 上施加任意的排列（对称群 $S_{|S_P|}$ ）。

$\hspace{15pt}$ 接下来，我们需要计算所有可能的排列总数。一个操作由一对祖先-后代节点 $(x, y)$ 确定一条路径 $P_{x,y}$ 。所有可生成的排列，是作用在所有这些路径 $S_{x,y}$ 上的排列的集合的并集。

$\hspace{15pt}$ 观察路径的结构：对于任意一个节点 $v$ 和它的一个祖先 $u$ ，路径 $P_{u,v}$ 上的点集 $S_{u,v}$ 是根到 $v$ 的路径 $S_{1,v}$ 上的点集的子集。因此，在 $S_{u,v}$ 上的任意排列都可以看作是 $S_{1,v}$ 上的一个排列（它保持 $S_{1,v} \setminus S_{u,v}$ 中的元素不变）。这意味着，对于一个固定的节点 $v$ ，所有以 $v$ 为后代节点的路径所能生成的排列集合，它们的并集就等于在最长路径 $S_{1,v}$ 上进行排列所能生成的集合。

$\hspace{15pt}$ 因此，问题转化为计算 $\left| \bigcup_{v=2}^{n} \text{Sym}(S_{1,v}) \right|$ ，其中 $\text{Sym}(S)$ 表示在点集 $S$ 上的所有排列构成的集合。

$\hspace{15pt}$ 直接计算这个并集的大小很困难，可以转换思路。一个排列 $\pi$ 是可生成的，当且仅当它所移动的点的集合 $M(\pi) = \{i \mid \pi(i) \leqq i\}$ 是某个根路径 $S_{1,v}$ 的子集。一个集合 $M$ 是某个 $S_{1,v}$ 的子集，当且仅当 $M$ 中所有点都在同一条从根出发的路径上，即 $M$ 中任意两点都具有祖先-后代关系。

$\hspace{15pt}$ 我们统计所有满足这个条件的排列。总数等于 $1$ (不操作) 加上所有非恒等排列的数量。

$\hspace{15pt}$ 一个非恒等排列由其移动的点的集合 $M$ 唯一地确定了其贡献（ $D_{|M|}$ 个排列，即 $|M|$ 个元素的错排数）。

$\hspace{15pt}$ 我们可以根据一个集合 $M$ 中深度最大的节点 $u$ 来对所有合法的 $M$ 进行分类计数。每个合法的 $M$ 都有唯一一个深度最大的节点。

$\hspace{15pt}$ 对于一个节点 $u$ ，其深度为 $d_u$ ，它作为最深节点的合法集合 $M$ 必须满足 $M \subseteq S_{1,u}$ 。若 $|M|=k$ ，则 $M$ 由 $u$ 和从 $u$ 的 $d_u-1$ 个真祖先中选出的 $k-1$ 个节点构成。这样的集合有 $\binom{d_u-1}{k-1}$ 个。

$\hspace{15pt}$ 因此，节点 $u$ 的贡献是 $\sum_{k=2}^{d_u} \binom{d_u-1}{k-1} D_k$ 。

$\hspace{15pt}$ 令 $F(d) = \sum_{k=2}^{d} \binom{d-1}{k-1} D_k$ 。通过一系列组合恒等式和错排的递推公式 $D_k = k D_{k-1} + (-1)^k$ ，可以推导出 $F(d)$ 的递推式： $F(d) = (d-1)F(d-1) + (d-1)!$ 。解得 $F(d) = (d-1)(d-1)!$ 。

$\hspace{15pt}$ 最终答案为 $1 + \sum_{u=1}^{n} F(d_u) = 1 + \sum_{u=1}^{n} (d_u-1)(d_u-1)!$ 。

$\hspace{15pt}$ 时间复杂度：预计算阶乘 $O(N_{max})$ ，每组数据 $O(N)$ 建图和 $O(N)$ 计算深度和 $O(N)$ 累加答案。总复杂度为 $O(N_{max} + \sum N)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll A[200005];
int main() {
    int T;
    cin>>T;
    A[0]=1;
    for (int i=1;i<=200000;i++) A[i]=A[i-1]*i%mod;
    while(T--) {
        int n;
        cin>>n;
        vector<vector<ll>> e(n+1);
        vector<ll> h(n+1);
        for (int i=1;i<n;i++){
            ll x,y;
            cin>>x>>y;
            e[x].push_back(y);
            e[y].push_back(x);
        }
        h[1]=1;
        ll ans=0;
        auto dfs = [&](auto dfs,ll x,ll fa,ll y)->void{
            if (h[x]>=2){
                y=(y+A[h[x]]-2*A[h[x]-1]+A[h[x]-2]+3*mod)%mod;
                ans=(ans+y)%mod;
                
            }
            for (auto u:e[x]){
                if (u==fa) continue;
                h[u]=h[x]+1;
                dfs(dfs,u,x,y);
            }
        };
        dfs(dfs,1,0,0);
        cout<<(ans+1)%mod<<(char)(10);
    }
}

</details>

E. 超大无向连通图-1

$\hspace{15pt}$ 知识点：单调栈，构造，思维，贪心。

$\hspace{15pt}$ 预估难度：1800。

题解

题目大意

$\hspace{15pt}$ 题目需要你在数组 $a$ 的限制内构造个数组 $b$ 使得由这两个数组按照：对于任意一对下标 $1 \leqq i < j \leqq n$ ，若同时满足 $b_i > b_j$ ，则在节点 $i$ 与节点 $j$ 之间连一条无向边，且这条边的长度为 $a_j$ ，这样的连边方式使得 $n$ 个结点构成的图是无向连通图并最大化所有边之和。

思路

$\hspace{15pt}$ 观察题目，发现边长与数组 $a$ 有直接关系，而 $a_i$ 的取值范围为 $[-n,n]$ ，容易看出我们需要尽可能多利用 $a_i \geqq 0$ 的情况，尽可能不利用 $a_i<0$ 的情况。

$\hspace{15pt}$ 因为每对下标 $1\leqq i<j \leqq n$ 都独立影响一条边，所以我们容易想到当 $a_j \geqq 0$ 时，将 $i$ 与所有的 $1\sim i-1$ 都进行建边来最大程度的利用 $a_i$ 做出的贡献即只需要 $b_j<min(b_1,b_2,\dots,b_{j-1})$ 。

$\hspace{15pt}$ 接下来考虑 $a_i<0$ 的情况，如果存在一个下标 $j>i$ 并且 $a_j \geqq 0$ ，此时按照上面的思路就会链接 $i$ 与 $j$ 此时就保证连通性问题了，即这种情况不需要在额外加边；反之情况，因需要保证连通性问题，这些下标一定要至少建立一个边，为了最小化消耗损耗，对于点 $i$ 去寻找满足 $j>i$ 的最大 $a_j$ 比较 $a_i$ 与 $a_j$ 选择最大值进行连接即可，另外注意全为负数时根据算法不同可能需要额外讨论。

$\hspace{15pt}$ 因题目没有限制 $b$ 的的大小所以我们只需要考虑上述情况并不需要考虑具体 $b$ 的值， $b$ 的构造方案有无数种。

算法及时间复杂度

$\hspace{15pt}$ 贪心，思维，构造，前缀和（单调栈）。在 $O(n)$ 的时间复杂度完成（即题解思路）。

One More Thing

$\hspace{15pt}$ by the way，本题还有一种神秘写法（李超线段树优化dp），简单说一下。

$\hspace{15pt}$ 题目中节点 $j$ 与左侧 $k_j$ 个节点连边，等价于覆盖区间 $[j-k_j, j-1]$ 。图连通的充要条件是：所有节点的覆盖区间并集必须完全覆盖 $[1, n-1]$ 。我们可以将连通性转化为区间覆盖问题。

$\hspace{15pt}$ 设 $dp[x]$ 为覆盖后缀区间 $[x, n-1]$ 所需的最小代价。当前起点是 $x$ ，我们必须选择一个右侧的节点 $j$ ( $j > x$ )，让它向左延伸覆盖到 $x$ 。为了覆盖 $[x, j-1]$ ，节点 $j$ 需要延伸长度 $j-x$ ，产生的代价为 $|a_j| \times (j-x)$ ，剩下的后缀 $[j, n-1]$ 则由子问题 $dp[j]$ 解决。

$dp[x] = \min_{j > x} \{ \underbrace{|a_j| \cdot (j - x)}{\text{当前覆盖代价}} + \underbrace{dp[j]}{\text{剩余代价}} \}$

$\hspace{15pt}$ 由于这是一个经典的 $1D/1D$ 动态规划问题，且转移方程符合直线形式，我们可以使用李超线段树 (Li Chao Tree) 来维护这些直线，并在 $O(\log N)$ 时间内查询最小 $y$ 值。

参考代码

<details style="border: 1px solid #ddd; border-radius: 8px; padding: 5px 12px; margin: 3px 0; width: 100%; box-sizing: border-box;">

参考代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<ll> a(n+1);
        int f=0;
        for (int i=1;i<=n;i++){
            cin>>a[i];
            if (a[i]>=0) f=i;
        }
        ll ans=0;
        for (int i=1;i<=n;i++){
            if (a[i]>=0) ans+=a[i]*(i-1);
        }
        vector<ll> stk;
        for (int i=f+1;i<=n;i++){
            while(!stk.empty()&&a[stk.back()]<=a[i]) stk.pop_back();
            stk.push_back(i);
        }
        for (int i=1;i<stk.size();i++){
            ans+=a[stk[i]]*(stk[i]-stk[i-1]);
        }
        if (!stk.empty())ans+=a[stk[0]]*(stk[0]-(f+(f==0)));
        cout<<ans<<'\n';
    }
}

F. 小s的逆序对

$\hspace{15pt}$ 知识点：线段树，扫描线，推公式。

$\hspace{15pt}$ 预估难度：2200。

题解

题意

$\hspace{15pt}$ 给定数组 $a$ ，你最多进行一次操作：选一个位置 $p$ ，把 $a_p$ 取出后插入到任意位置（可到首尾），其余元素相对顺序不变；定义逆序对为满足 $i<j$ 且 $a_i>a_j$ 的有序对数量（相等不计），求最小可能的逆序对数量。

思路

$\hspace{15pt}$ 记原逆序对为 $I_0$ 。移动某个位置 $p$ 的元素时，除该元素外，其余元素相对顺序不变，所以它们之间的逆序对不变；变化只来自该元素与其它元素的配对。

$\hspace{15pt}$ 设 $old(p)$ 为该元素在原数组中参与的逆序对数，即“左边比它大的个数”加“右边比它小的个数”，则把它移走会让答案变为 $I_0-old(p)+new(p)$ ，其中 $new(p)$ 是它插入到某个位置后与其它元素产生的新逆序对数；因此只要对每个 $p$ 求最小 $new(p)$ ，取最小增量 $\min_p(new(p)-old(p))$ ，答案为 $I_0+\min_p(new(p)-old(p))$ 。

$\hspace{15pt}$ 用坐标压缩后两次树状数组即可在 $O(n\log n)$ 求出所有 $old(p)$ 以及 $I_0$ 。

$\hspace{15pt}$ 关键是如何对某个值 $r$ 快速求“插入任意位置的最小新贡献”。若把该元素插入在前缀长度为 $k$ 的位置之后，则 $new(r,k)=\#\{i\le k:a_i>r\}+\#\{i>k:a_i<r\}$ 。把右边那项改写为全局小于 $r$ 的数量 $TotalLess(r)$ 减去前缀中小于 $r$ 的数量，可得 $new(r,k)=TotalLess(r)+D_r(k)$ ，其中 $D_r(k)=PrefGreater(r,k)-PrefLess(r,k)$ 。所以 $\min_k new(r,k)=TotalLess(r)+\min_k D_r(k)$ 。

$\hspace{15pt}$ 代码按 $r$ 从小到大扫描，用线段树维护整条 $D_r(k)$ （对后缀区间做加法、查询全局最小）。从 $r$ 变到 $r+1$ 时，只需要把值为 $r$ 和 $r+1$ 的出现位置对应的后缀区间各减 1，即可把 $D_r$ 更新成 $D_{r+1}$ ，从而得到每个 $r$ 的 $\min_k D_r(k)$ ，进而得到每个值的最优 $bestNew[r]=\min_k new(r,k)$ 。

$\hspace{15pt}$ 最后枚举位置 $p$ ，取 $bestNew[a_p]-old(p)$ 的最小值即可。

复杂度

$\hspace{15pt}$ 坐标压缩 $O(n\log n)$ ，两次树状数组 $O(n\log n)$ ，线段树按值扫描总计 $O((n+m)\log n)$ ，总体 $O(n\log n)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

int a[200000];
map<int, int> mp;
vector<int> v[200000];
int tre[200001], N;

int lowbit(int x) {
    return x - (x & (x - 1));
}
void add(int p, int vl) {
    for (; p <= N; p += lowbit(p)) tre[p] += vl;
}
int qsum(int p) {
    int vl = 0;
    for (; p > 0; p -= lowbit(p)) vl += tre[p];
    return vl;
}
void clr() {
    int i;
    for (i = 0; i <= N; i++) tre[i] = 0;
}
int vmx[1 << 19], lazy[1 << 19];
void gen(int t, int dep) {
    vmx[t] = 0;
    lazy[t] = 0;
    if (dep == 0) return;
    gen(t * 2 + 1, dep - 1);
    gen(t * 2 + 2, dep - 1);
}
void pushdown(int t) {
    int l = t * 2 + 1, r = t * 2 + 2;
    vmx[l] += lazy[t];
    lazy[l] += lazy[t];
    vmx[r] += lazy[t];
    lazy[r] += lazy[t];
    lazy[t] = 0;
}
void add(int t, int dep, int l, int r, int vl) {
    if (l == 0 && r == (1 << dep)) {
        vmx[t] += vl;
        lazy[t] += vl;
        return;
    }
    pushdown(t);
    int x = (1 << (dep - 1));
    if (l < x) {
        if (r <= x)
            add(t * 2 + 1, dep - 1, l, r, vl);
        else {
            add(t * 2 + 1, dep - 1, l, x, vl);
            add(t * 2 + 2, dep - 1, 0, r - x, vl);
        }
    } else
        add(t * 2 + 2, dep - 1, l - x, r - x, vl);
    vmx[t] = max(vmx[t * 2 + 1], vmx[t * 2 + 2]);
}
int qmax(int t, int dep, int l, int r) {
    if (l == 0 && r == (1 << dep)) return vmx[t];
    pushdown(t);
    int x = (1 << (dep - 1));
    if (l < x) {
        if (r <= x) return qmax(t * 2 + 1, dep - 1, l, r);
        return max(qmax(t * 2 + 1, dep - 1, l, x), qmax(t * 2 + 2, dep - 1, 0, r - x));
    }
    return qmax(t * 2 + 2, dep - 1, l - x, r - x);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T, n, i, j, c, tdep, ans1;
    map<int, int>::iterator it;
    long long ans0;
    for (cin >> T; T > 0; T--) {
        cin >> n;
        for (i = 0; i < n; i++) {
            cin >> a[i];
            mp[a[i]] = 0;
        }
        c = 0;
        for (it = mp.begin(); it != mp.end(); it++) {
            (*it).second = c;
            c++;
        }
        for (i = 0; i < n; i++) a[i] = mp[a[i]];
        mp.clear();
        N = c;
        ans0 = 0;
        for (i = n - 1; i > -1; i--) {
            ans0 += qsum(a[i]);
            add(a[i] + 1, 1);
        }
        clr();
        for (tdep = 0; (1 << tdep) < n + 1; tdep++);
        gen(0, tdep);
        for (i = 0; i < n; i++) add(0, tdep, i + 1, n + 1, -1);
        for (i = 0; i < n; i++) v[a[i]].push_back(i);
        ans1 = 0;
        for (i = 0; i < c; i++) {
            for (j = 0; j < v[i].size(); j++) add(0, tdep, v[i][j] + 1, n + 1, 1);
            for (j = 0; j < v[i].size(); j++) {
                ans1 = max(ans1, qmax(0, tdep, v[i][j] + 1, n + 1) - qmax(0, tdep, v[i][j] + 1, v[i][j] + 2));
                ans1 = max(ans1, qmax(0, tdep, 0, v[i][j] + 1) - qmax(0, tdep, v[i][j], v[i][j] + 1));
            }
            for (j = 0; j < v[i].size(); j++) add(0, tdep, v[i][j] + 1, n + 1, 1);
        }
        cout << ans0 - ans1 << '\n';
        for (i = 0; i < c; i++) v[i].clear();
    }
    return 0;
}

G. Block Game2.0

$\hspace{15pt}$ 知识点：构造、贪心、模拟。

$\hspace{15pt}$ 预估难度：2500。

题解

题意

$\hspace{15pt}$ 给定 $2$ 行 $n$ 列的矩阵，和一个万能数字 $k$ ，每次操作选择一行，把 $k$ 插入这一行的头，同时所有数字后移，最后一列的数字被挤出来成为新的 $k$ 。

$\hspace{15pt}$ 构造一个不超过 $4n+4$ 的操作序列，最大化操作结束后矩阵第一列上两个数字 $+k$ 的值。（不必最小化操作次数。）

思路

$\hspace{15pt}$ 贪心地，我们发现因为 $n+1$ 次操作之内就能让一行矩阵的所有数字都充当一次头部元素，而两行矩阵也不过 $2\times (n+1)$ 次操作，题目给了 $4\times (n+1)$ 次操作。因此我们不妨大胆假设：这些操作必然能使得 $2n+1$ 个数字中的前三大位于我们要求的位置。

$\hspace{15pt}$ 因此接下来我们尝试来构造这样一种方案。

$\hspace{15pt}$ 首先考虑，整个过程需要从头插入元素和从尾部删除元素，因此我们可以用两个 $deque$ 来维护这个矩阵的两行。

$\hspace{15pt}$ 方便起见，我们不妨先将这前三大标记为 $1$ ，其余数字均标记为 $0$ 。这样一来，问题转化成了构造这个操作序列，使得最终矩阵第一列的两个数字都是 $1$ ，且 $k=1$ 。

$\hspace{15pt}$ 接下来，下文中的矩阵变成了 $A$ 和 $B$ 这两个 $deque$ 维护的两个 $01$ 序列。其中 $A, B$ 分别代表第一行和第二行。

$\hspace{15pt}$ 接下来，为了方便分类讨论，我们不妨令这三个 $1$ 都在矩阵中，也就是令 $k=0$ ，即如果 $k$ 是前三大中的值，我们就预先操作几次让 $k$ 不在前三大中。（这一步，在下面的代码中直接先操作令 $k$ 成为了所有数字中的最小值，这样在 $01$ 矩阵的视角下，就必然满足 $k=0$ 了。）

$\hspace{15pt}$ 进行完这一步后，我们就可以按第一行中的 $1$ 分类讨论，但在此之前我们为了简化代码，可以先钦定 $A$ 中的 1 比 $B$ 更多，这里只需要在 $A$ 更少时将 $A,B$ 进行交换，同时把标记是否交换过的 $change$ 置为 $true$ 。

$\hspace{15pt}$ 那么此时 $A$ 中的 $1$ 个数必然不小于 $2$ 。（因为此时 $k$ 是所有数的 $\min$ ，因此必然 $k=0$ ）：

$\hspace{15pt}$ 接下来，我们先不着急分类讨论，先考虑这样一件事：

$\hspace{15pt}$ 我们对一行考虑，什么时候一次操作能使得操作结束后，这一行的第一个数字和 $k$ 都等于 $1$ ，我们会发现实际上当且仅当在这行数字中有两个相邻的 $1$ 。

$\hspace{15pt}$ 因为实际上只考虑一行数字和 $k$ 的话，实际上操作相当于将这个长度为 $n+1$ 的序列**（ $k$ 本质上就是第 $n+1$ 个数字）**循环右移，而 $k$ 和第一个数字在这个循环中是相邻的位置关系。

$\hspace{15pt}$ 有了这个发现，我们就可以考虑无脑构造，使得在某行中存在两个相邻的 $1$ ，这样一来，后面对这一行做不超过 $n$ 次操作，就能使得这一行满足条件。

$\hspace{15pt}$ 而此时我们发现，我们已经钦定了 $A$ 中的 $1$ 更多，而显然 $A$ 中的元素我们并不方便去修改顺序，因此我们可以暴力地对 $A$ 操作，碰到 $0$ 就塞入 $A$ ，而碰到 $1$ 就塞入 $B$ ，直至给 $B$ 中塞入两个 $1$ ，则此时这两个 $1$ 必然位于 $B$ 的前两个位置。

$\hspace{15pt}$ 则此时，就只有三种比较简单的情况了：

${\hspace{20pt}}_\texttt{1.}\,$ 三个 $1$ 全在 $B$ 中。

${\hspace{20pt}}_\texttt{2.}\,$ 两个 $1$ 在 $B$ 中，而第三个 $1$ 在 $k$ 上。

${\hspace{20pt}}_\texttt{3.}\,$ 两个 $1$ 在 $B$ 中，而第三个 $1$ 在 $A$ 中。

$\hspace{15pt}$ 此时我们会发现，无论是哪种情况，我们总能转化成第二种情况。

${\hspace{20pt}}_\texttt{1.}\,$ 如果全在 $B$ 中，则我们就无脑对 $B$ 操作，直到碰到最靠后的那个 $1$ ，此时这个 $1$ 就被放在了 $k$ 中。

${\hspace{20pt}}_\texttt{2.}\,$ 如果有一个 $1$ 在 $A$ 中，则我们就无脑对 $A$ 操作，直到碰到那个 $1$ ，此时这个 $1$ 也被放入了 $k$ 。

$\hspace{15pt}$ （不难发现，上面这一步不超过 $n$ 次操作就能使得 $k=1$ ，同时另外两个 $1$ 恰好位于 $B$ 中的某两个相邻的位置。）

$\hspace{15pt}$ 接下来，局面已经变成了： $k=1$ ，且 $B$ 中存在两个相邻的 $1$ 。

$\hspace{15pt}$ 那么问题几乎已经解决了，我们直接把这个 $k$ 塞入 $A$ 中，此时 $A$ 就符合条件了（仅操作一次。）

$\hspace{15pt}$ 接着再对 $B$ 进行无脑地操作，直至 $k=1$ ，此时由于原先 $B$ 中的两个 $1$ 处于相邻的位置，因此第二个 $1$ 必然位于 $B$ 的末尾，因此再进行一次操作，就可以直接让： $B$ 的头部元素为 $1$ ，同时 $k=1$ 。

$\hspace{15pt}$ 到此我们就构造了一个合法的解，我们来计算一下操作次数。

${\hspace{20pt}}_\texttt{1.}\,$ 首先我们调整了 $k$ ，使得 $k$ 取到了全局的 $min$ 。（这一步不超过 $n+1$ 次。）

${\hspace{20pt}}_\texttt{2.}\,$ 接着我们将 $A$ 中的两个 $1$ 塞入了 $B$ 中相邻的位置。（这一步不超过 $n$ 次。）

${\hspace{20pt}}_\texttt{3.}\,$ 接着我们进行了分类讨论，这里最坏的一种类是，我们需要把 $A$ 中剩下的那个 $1$ 调整到 $k$ 里，（这一步最多 $n+1$ 次操作。）

${\hspace{20pt}}_\texttt{4.}\,$ 最后，我们首先进行了一次操作把 $k$ 摁进了 $A$ 中，让 $A$ 合法（这一步 $1$ 次。）

${\hspace{20pt}}_\texttt{5.}\,$ 接着我们无脑地对 $B$ 操作，将 $B$ 中的那两个相邻的 $1$ 调整成合法的位置。（这一步不超过 $n$ 次。）

$\hspace{15pt}$ 因此我们只需要最多 $4n+3$ 次操作，必然可以达到这个最优的局面，而题目给了 $4n+4$ 次，显然是够用的。

$\hspace{15pt}$ Bonus：实际上，极限的操作次数在 $3n+3$ 次。

$\hspace{15pt}$ 细节见代码：（当然，最后别忘记判断 $change$ ，要把 $A,B$ 交换回去，相当于把最后那一部分的操作数的 $1,2$ 互换。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val, r, c;

    bool operator>(const Node& n) const {
        return val > n.val;
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    deque<int> A, B;
    int mx = -1e9;
    int mn1 = 1e9, mn2 = 1e9;
    int c1 = 0, c2 = 0;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        mx = max(mx, x);
        if (x <= mn1) {
            mn1 = x;
            c1 = n - i + 1;
        }
        A.emplace_back(x);
    }
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        mx = max(mx, x);
        if (x <= mn2) {
            mn2 = x;
            c2 = n - i + 1;
        }
        B.emplace_back(x);
    }
    if (n == 1) {
        cout << 0 << endl;
        return ;
    }

    string pre; // 把 k 调到最小值
    if (mn1 < mn2) { // A 的 min 更小
        while (c1--) {
            pre += '1';
            A.emplace_front(k);
            k = A.back();
            A.pop_back();
        }
    } else {
        while (c2--) {
            pre += '2';
            B.emplace_front(k);
            k = B.back();
            B.pop_back();
        }
    }

    vector<Node> v;
    for (int i = 0; i < n; i++) v.push_back({A[i], 1, i});
    for (int i = 0; i < n; i++) v.push_back({B[i], 2, i});
    sort(v.begin(), v.end(), greater<>()); // 前三大标记成1，其余0
    k = 0;
    for (int i = 0; i < 3; i++) {
        auto [val, r, c] = v[i];
        if (r == 1) {
            A[c] = 1;
        } else {
            B[c] = 1;
        }
    }
    for (int i = 3; i < n * 2; i++) {
        auto [val, r, c] = v[i];
        if (r == 1) {
            A[c] = 0;
        } else {
            B[c] = 0;
        }
    }
    int mx_cnt1 = (v[0].r == 1) + (v[1].r == 1) + (v[2].r ==
                  1); // 第一行的最大值个数

    bool change = 0;
    if (mx_cnt1 <= 1) { // 让A的更多
        swap(A, B);
        change = 1;
    }

    // 把A的两个大的扔到B里
    string ans;
    int cnt1 = 0;
    while (cnt1 < 2) {
        if (k == 1) {
            B.emplace_front(k);
            k = B.back();
            B.pop_back();
            ans += '2';
            cnt1++;
        } else {
            A.emplace_front(k);
            k = A.back();
            A.pop_back();
            ans += '1';
        }
    }
    int haveA = -1;
    if (k == 1) {
        haveA = 1;
    }
    for (int i = 0; i < n; i++) {
        if (A[i] == 1) {
            haveA = n - i + 1;
            break;
        }
    }
    if (haveA == -1) { // 0 3
        while (k != 1) { // 把B里多的那最后一个1拿出来给k
            B.emplace_front(k);
            k = B.back();
            B.pop_back();
            ans += '2';
        }
        haveA = 1;
    }
    while (haveA--) {
        A.emplace_front(k);
        k = A.back();
        A.pop_back();
        ans += '1';
    }
    while (!(B.front() == 1 && k == 1)) {
        B.emplace_front(k);
        k = B.back();
        B.pop_back();
        ans += '2';
    }

    if (change) {
        for (auto& c : ans) {
            if (c == '1') {
                c++;
            } else {
                c--;
            }
        }
    }
    pre += ans;
    cout << pre.size() << '\n' << pre << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_ --) {
        solve();
    }
    return 0;
}#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val, r, c;

    bool operator>(const Node& n) const {
        return val > n.val;
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    deque<int> A, B;
    int mx = -1e9;
    int mn1 = 1e9, mn2 = 1e9;
    int c1 = 0, c2 = 0;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        mx = max(mx, x);
        if (x <= mn1) {
            mn1 = x;
            c1 = n - i + 1;
        }
        A.emplace_back(x);
    }
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        mx = max(mx, x);
        if (x <= mn2) {
            mn2 = x;
            c2 = n - i + 1;
        }
        B.emplace_back(x);
    }
    if (n == 1) {
        cout << 0 << endl;
        return ;
    }

    string pre; // 把 k 调到最小值
    if (mn1 < mn2) { // A 的 min 更小
        while (c1--) {
            pre += '1';
            A.emplace_front(k);
            k = A.back();
            A.pop_back();
        }
    } else {
        while (c2--) {
            pre += '2';
            B.emplace_front(k);
            k = B.back();
            B.pop_back();
        }
    }

    vector<Node> v;
    for (int i = 0; i < n; i++) v.push_back({A[i], 1, i});
    for (int i = 0; i < n; i++) v.push_back({B[i], 2, i});
    sort(v.begin(), v.end(), greater<>()); // 前三大标记成1，其余0
    k = 0;
    for (int i = 0; i < 3; i++) {
        auto [val, r, c] = v[i];
        if (r == 1) {
            A[c] = 1;
        } else {
            B[c] = 1;
        }
    }
    for (int i = 3; i < n * 2; i++) {
        auto [val, r, c] = v[i];
        if (r == 1) {
            A[c] = 0;
        } else {
            B[c] = 0;
        }
    }
    int mx_cnt1 = (v[0].r == 1) + (v[1].r == 1) + (v[2].r ==
                  1); // 第一行的最大值个数

    bool change = 0;
    if (mx_cnt1 <= 1) { // 让A的更多
        swap(A, B);
        change = 1;
    }

    // 把A的两个大的扔到B里
    string ans;
    int cnt1 = 0;
    while (cnt1 < 2) {
        if (k == 1) {
            B.emplace_front(k);
            k = B.back();
            B.pop_back();
            ans += '2';
            cnt1++;
        } else {
            A.emplace_front(k);
            k = A.back();
            A.pop_back();
            ans += '1';
        }
    }
    int haveA = -1;
    if (k == 1) {
        haveA = 1;
    }
    for (int i = 0; i < n; i++) {
        if (A[i] == 1) {
            haveA = n - i + 1;
            break;
        }
    }
    if (haveA == -1) { // 0 3
        while (k != 1) { // 把B里多的那最后一个1拿出来给k
            B.emplace_front(k);
            k = B.back();
            B.pop_back();
            ans += '2';
        }
        haveA = 1;
    }
    while (haveA--) {
        A.emplace_front(k);
        k = A.back();
        A.pop_back();
        ans += '1';
    }
    while (!(B.front() == 1 && k == 1)) {
        B.emplace_front(k);
        k = B.back();
        B.pop_back();
        ans += '2';
    }

    if (change) {
        for (auto& c : ans) {
            if (c == '1') {
                c++;
            } else {
                c--;
            }
        }
    }
    pre += ans;
    cout << pre.size() << '\n' << pre << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_ --) {
        solve();
    }
    return 0;
}

2025WPC竞赛题解

B. 细节博弈

题解

解题思路

过程实现

参考代码

C. 超级蜗牛

题解

题目大意

思路

算法即时间复杂度解析

参考代码

D. 遥控器

题解

题意

思路

参考代码

E. 超大无向连通图-1

题解

题目大意

思路

算法及时间复杂度

One More Thing

参考代码

F. 小s的逆序对

题解

题意

思路

复杂度

参考代码

G. Block Game2.0

题解

题意

思路

参考代码