Znzryb's Blog

2026牛客暑期多校 8——H-It's Magic, Not a Trick!（这是魔法，不是戏法！）

Posted on 2026-08-12 Edited on 2026-08-14

题目大意

这是魔法，不是戏法！(It’s Magic, Not a Trick!)

时间限制：C/C++/Rust/Pascal 2 秒，其他语言 4 秒
空间限制：C/C++/Rust/Pascal 1024 MB，其他语言 2048 MB

“呃……真麻烦，不过真正的魔法师是不会放弃的。”

自称"超高校级的魔法师"的梦野秘密子在自己面前摆了一排共 $n$ 个附魔护符。第 $i$ 个护符最初蕴含 $a_i$ 单位魔力，且每个 $a_i$ 都是正整数。最近她研读了一本积满灰尘的古老魔导书，破译出了一个以极为特殊的方式操纵魔力的咒语。

每施放一次咒语，她必须严格按顺序执行以下两步：

注魔：选择任意一个护符，向其中注入恰好 $1$ 单位自身的魔力，使该护符的魔力增加 $1$ 。
释放：选择任意一个在注魔完成之后魔力至少为 $x$ 的护符，爆发出耀眼的光芒，从该护符中消耗恰好 $x$ 单位魔力，使其魔力减少 $x$ 。两步可以选择同一个护符，也可以选择不同的护符，咒语在这一点上是灵活的。

但有一条关键限制：如果注魔完成之后不存在魔力至少为 $x$ 的护符，则释放无法进行。此时整个咒语直接失效，什么都不会发生，她试图注魔的那个护符的魔力也保持不变。

只要每一次尝试都能成功、且所有护符的魔力始终保持非负，秘密子就可以任意多次地施放这个咒语。她好奇自己法术的极限：通过选择每次注魔与释放的位置，所有护符剩余魔力之和最小可能是多少？

比起自己算术，她更想去睡一觉，于是她向你——她可靠的助手——求助。由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果。

每个测试点包含多组测试数据。

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试数据的组数。接下来是各组测试数据的描述。

每组测试数据的第一行包含两个整数 $n$ 和 $x$ （ $1 \le n \le 2 \cdot 10^5$ ， $1 \le x \le 10^9$ ）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le 10^{18}$ ）。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

对于每组测试数据，输出一个整数——所有护符剩余魔力之和的最小可能值对 $998244353$ 取模的结果。

1
2
3

3
0
6

第一组数据： $x = 3$ ，所有护符魔力均为 $1$ 。无论向哪个护符注魔，注魔后魔力最大也只有 $2 < 3$ ，无法进行释放，因此秘密子一次咒语也无法施放，剩余魔力之和为 $1 + 1 + 1 = 3$ 。

第二组数据：只有一个护符，魔力为 $3$ ， $x = 4$ 。对该护符注魔得到 $4$ ，再对它自身释放，魔力变为 $0$ 。此后无法继续施放，答案为 $0$ 。

第三组数据： $x = 10$ ，初始魔力为 $[30, 8, 7, 6]$ 。可以按如下方式施放 $5$ 次咒语：

次数	注魔对象	释放对象	操作后的魔力序列
1	第 $2$ 个（ $8 \to 9$ ）	第 $1$ 个（ $30 \to 20$ ）	$[20, 9, 7, 6]$
2	第 $2$ 个（ $9 \to 10$ ）	第 $1$ 个（ $20 \to 10$ ）	$[10, 10, 7, 6]$
3	第 $3$ 个（ $7 \to 8$ ）	第 $1$ 个（ $10 \to 0$ ）	$[0, 10, 8, 6]$
4	第 $3$ 个（ $8 \to 9$ ）	第 $2$ 个（ $10 \to 0$ ）	$[0, 0, 9, 6]$
5	第 $3$ 个（ $9 \to 10$ ）	第 $3$ 个（ $10 \to 0$ ）	$[0, 0, 0, 6]$

此时剩余魔力之和为 $6$ ，且无法再继续施放咒语，因此答案为 $6$ 。

思路讲解

初始放电次数：

// ---------------- 3. 提取“免费放电次数” = “初始注入预算” ----------------
// cnt：光靠已有能量就能完成的放电次数 sum(a_i / x)。
// 这 cnt 次施法各自附带的那个 +1 可以任意投放，所以 cnt 同时就是可支配的预算。
// 取模后 a[i] 只保留余数 r_i ∈ [0, x-1]。
i128 cnt = 0;
for (int i = 0; i < n; i++)
{
    cnt += a[i] / x;
    a[i] %= x;
}

for (int i = 0; i < n; i++)
{
    // 把这个符从 r_i 抬到 x 需要 x - r_i 点，
    // 其中 1 点由“放它自己的那次施法的注入”免费提供，
    // 其实这个减少了题目难度，因为可以直接融入进 cost 里面，不用再单独拿出来算啊
    // 所以真正要从预算里掏的是 x - r_i - 1 点。
    // 特别地，r_i == x - 1 时代价为 0：即使预算为空也能白嫖一次施法。
    i128 cost = x - a[i] - 1;

    if (cost <= cnt)
    {
        cnt -= cost; // 花掉预算
        a[i] = 0;    // 这个符被打到 0
        round++;     // 多出一次成功施法
    }
    // 由于 a 已降序 → cost 单调不减，而 cnt 单调不增，
    // 因此一旦买不起，后面全都买不起，这里其实可以直接 break。
}

// ---------------- 5. 用剩余预算反复“复用零符” ----------------
  // 重新降序排序：被买下的都变成 0 了，排完之后 a[0] 是剩下的最大余数。
  // a[0] == 0 表示所有符都已归零。
  sort(all(a), greater<>());
 
  if (a[0] == 0) // a[0] == 0 表示所有符都已归零。
  {
    // 下面就是计算朴素情况啊
      // 全零之后想再多施一次法，只能挑一个 0 号符：
      // 从预算掏 x-1 点把它填到 x-1，再靠本次施法自带的 +1 补满 x 然后放电。
      // 所以此后每一次施法的净代价固定为 x - 1，能买几次就买几次。
      if (cnt >= x - 1)
      {
          i128 d = cnt / (x - 1);
          cnt -= (x - 1) * d;
          round += d;
      }
      // 注：若 a[0] != 0，说明它没被买下，即 x - a[0] - 1 > cnt，
      // 而 x - a[0] - 1 <= x - 2 < x - 1，故必有 cnt < x - 1，
      // 这个分支本来也会得到 d = 0 —— 判断是冗余的，保留只为语义清晰。
  }

// ---------------- 6. 输出 S - (x-1) * R ----------------
// round 最大约 1e23，(x-1) % MOD < 1e9，乘积约 1e32，仍在 i128 范围内。
// 先减可能变负，故 +MOD 再取模。
cout << (sum - (x - 1) % MOD * round % MOD + MOD) % MOD << "\n";

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84457244

源代码（队友的 AC 提交）

// teamname: Gospel_rock
// Acmer: 鵗曦(xixii_)
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128_t;
constexpr const ll INF = 1e18, MOD = 998244353;
constexpr const ld EPS = 1e-7;
// #define int long long
#define all(x) x.begin(), x.end()
#define debug1d(a)                            \
    cerr << #a << " = [";                     \
    for (int i = 0; i < (int)(a).size(); i++) \
        cerr << (i ? ", " : "") << (a)[i];    \
    cerr << "]\n";
#define debug2d(a)                                   \
    cerr << #a << " = [\n";                          \
    for (int i = 0; i < (int)(a).size(); i++)        \
    {                                                \
        cerr << "  [";                               \
        for (int j = 0; j < (int)(a[i]).size(); j++) \
            cerr << (j ? ", " : "") << a[i][j];      \
        cerr << "]\n";                               \
    }                                                \
    cerr << "]\n";
#define debug(x) cerr << "[" << #x << "] = " << (x) << "\n"
static int last_res;

ostream &operator<<(ostream &os, __int128_t x)
{
    if (x < 0)
        os << '-', x = -x;
    if (x > 9)
        os << x / 10;
    return os << (char)('0' + x % 10);
}

istream &operator>>(istream &is, __int128_t &x)
{
    string s;
    if (!(is >> s))
        return is;

    x = 0;
    size_t i = 0;
    bool neg = false;

    if (s[0] == '-')
    {
        neg = true;
        i = 1;
    }
    else if (s[0] == '+')
    {
        i = 1;
    }

    for (; i < s.size(); i++)
        x = x * 10 + (s[i] - '0');

    if (neg)
        x = -x;

    return is;
}
void solve()
{
    ll n, x;
    cin >> n >> x;
    vector<i128> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    i128 cnt = 0;
    i128 sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = (sum + a[i]) % MOD;
    }
    if (x == 1)
    {
        cout << sum << "\n";
        return;
    }
    for (int i = 0; i < n; i++)
    {
        cnt += a[i] / x;
        a[i] %= x;
    }
    i128 round = cnt;
    sort(all(a), greater<>());
    for (int i = 0; i < n; i++)
    {
        i128 cost = x - a[i] - 1;
        if (cost <= cnt)
        {
            cnt -= cost;
            a[i] = 0;
            round++;
        }
    }
    sort(all(a), greater<>());
    if (a[0] == 0)
    {
        if (cnt >= x - 1)
        {
            i128  d = cnt /(x - 1);
            cnt -= (x - 1) * d;
            round += d;
        }

    }
    cout << (sum - (x - 1) % MOD * round % MOD + MOD) % MOD << "\n";
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

AI 注释队友代码版

// teamname: Gospel_rock
// Acmer: 鵗曦(xixii_)
//
// 题目：2026 牛客暑期多校 8 - H. It's Magic, Not a Trick!
//
// ============================ 题意 ============================
// n 个符，第 i 个初始能量 a_i（正整数）。一次“施法”必须按顺序做两步：
//   1) 注入：任选一个符 +1；
//   2) 放电：任选一个此刻能量 >= x 的符 -x（可以就是刚才注入的那个）。
// 若注入后不存在能量 >= x 的符，则整次施法失败（什么都不发生）。
// 问：任意安排注入/放电位置，最终总能量的最小值是多少（对 998244353 取模）。
//
// ============================ 思路 ============================
// 【第 0 步】一次成功的施法让总能量恰好减少 (x - 1)，与注入到哪、从哪放电无关。
//   设最多能成功施法 R 次，则答案 = S - (x-1) * R，其中 S = sum(a_i)。
//   所以整题只需最大化 R。
//
// 【第 1 步】记账模型。R 次施法 = R 个 “+1” 的注入 + R 次放电。
//   把放电归属到具体的符：符 i 收到 b_i 点注入、被放电 d_i 次，则要求
//       a_i + b_i >= x * d_i，且 sum(b_i) = sum(d_i) = R。
//   即：注入总量本身就等于施法次数——这是一个“自举”的预算系统。
//
// 【第 2 步】免费的部分。cnt0 = sum(a_i / x) 次放电不用任何额外注入就能完成。
//   而这 cnt0 次施法各自附带的那个 “+1” 可以随便扔到任何地方，
//   所以 cnt0 同时是我们可自由调度的【注入预算】。
//   把 a_i 取模，余数 r_i = a_i % x ∈ [0, x-1]。
//
// 【第 3 步】价目表。想让余数为 r 的符多放一次电，需要把它从 r 抬到 x，共 x - r 点。
//   其中最后 1 点由【放它自己的那次施法的注入】提供（注入和放电是同一次施法的两步，
//   且允许作用于同一个符），所以真正从预算里掏的是：
//       第一次把某个符打到 0：净代价 x - r_i - 1
//       之后在同一个（已经是 0 的）符上再放一次电：净代价 x - 0 - 1 = x - 1
//   由于 x - r_i - 1 <= x - 1 恒成立，所有“第一次”都不比任何“第二次”贵。
//   每笔购买的收益都恰好是 “+1 次施法”，收益相同就只看价格 → 按代价升序贪心即最优，
//   而代价升序 <=> 余数降序，所以把余数从大到小排序后依次买即可。
//
// 【第 4 步】顺序可行性。预算的物理含义是“还剩几次可以立刻执行的放电”。
//   每花 1 点预算就真的执行一次施法：放电落在某个能量 >= x 的符上（还有预算就说明存在），
//   注入则定向浇到正在攒的目标符上。攒到 x-1 后，下一次施法直接把目标符注入到 x 并放电，
//   这一次不消耗预算，正好对应记账里“免费的那一发”。故计数与真实操作序列一一对应。
//
// 复杂度：O(n log n) / 组，瓶颈是排序。
// ==============================================================

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ordered_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128_t;

constexpr const ll INF = 1e18, MOD = 998244353;
constexpr const ld EPS = 1e-7;

// #define int long long
#define all(x) x.begin(), x.end()

// ------------------------- 调试宏（比赛模板，与算法无关） -------------------------
#define debug1d(a)                            \
    cerr << #a << " = [";                     \
    for (int i = 0; i < (int)(a).size(); i++) \
        cerr << (i ? ", " : "") << (a)[i];    \
    cerr << "]\n";

#define debug2d(a)                                   \
    cerr << #a << " = [\n";                          \
    for (int i = 0; i < (int)(a).size(); i++)        \
    {                                                \
        cerr << "  [";                               \
        for (int j = 0; j < (int)(a[i]).size(); j++) \
            cerr << (j ? ", " : "") << a[i][j];      \
        cerr << "]\n";                               \
    }                                                \
    cerr << "]\n";

#define debug(x) cerr << "[" << #x << "] = " << (x) << "\n"

static int last_res;

// ------------------------- __int128 的输入输出重载 -------------------------
// a_i <= 1e18 用 long long 够用，但中间量 cnt / round 可能达到 1e23 量级，
// 因此整份代码统一用 i128 存能量，这里补上流运算符。
ostream &operator<<(ostream &os, __int128_t x)
{
    if (x < 0)
        os << '-', x = -x;
    if (x > 9)
        os << x / 10;
    return os << (char)('0' + x % 10);
}

istream &operator>>(istream &is, __int128_t &x)
{
    string s;
    if (!(is >> s))
        return is;

    x = 0;
    size_t i = 0;
    bool neg = false;

    if (s[0] == '-')
    {
        neg = true;
        i = 1;
    }
    else if (s[0] == '+')
    {
        i = 1;
    }

    for (; i < s.size(); i++)
        x = x * 10 + (s[i] - '0');

    if (neg)
        x = -x;

    return is;
}

void solve()
{
    ll n, x;
    cin >> n >> x;

    vector<i128> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    // ---------------- 1. 先把初始总能量 S 在取模意义下算出来 ----------------
    // 注意必须在修改 a 之前算，因为后面 a 会被取模成余数。
    // 最终答案 = S - (x - 1) * R (mod 998244353)。
    i128 sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = (sum + a[i]) % MOD;
    }

    // ---------------- 2. 特判 x == 1 ----------------
    // 每次施法 = +1 再 -1，总能量恒定不变，做多少次都没有收益（x - 1 = 0）。
    // 同时也避免了后面除以 (x - 1) 时的除零。
    if (x == 1)
    {
        cout << sum << "\n";
        return;
    }

    // ---------------- 3. 提取“免费放电次数” = “初始注入预算” ----------------
    // cnt：光靠已有能量就能完成的放电次数 sum(a_i / x)。
    // 这 cnt 次施法各自附带的那个 +1 可以任意投放，所以 cnt 同时就是可支配的预算。
    // 取模后 a[i] 只保留余数 r_i ∈ [0, x-1]。
    i128 cnt = 0;
    for (int i = 0; i < n; i++)
    {
        cnt += a[i] / x;
        a[i] %= x;
    }

    // round：累计的施法总次数 R，初值就是这些白拿的放电。
    i128 round = cnt;

    // ---------------- 4. 贪心买“第一次”：把余数大的符优先打到 0 ----------------
    // 余数越大 → 补到 x 需要的注入越少 → 代价越低，所以按余数降序处理。
    sort(all(a), greater<>());

    for (int i = 0; i < n; i++)
    {
        // 把这个符从 r_i 抬到 x 需要 x - r_i 点，
        // 其中 1 点由“放它自己的那次施法的注入”免费提供，
        // 所以真正要从预算里掏的是 x - r_i - 1 点。
        // 特别地，r_i == x - 1 时代价为 0：即使预算为空也能白嫖一次施法。
        i128 cost = x - a[i] - 1;

        if (cost <= cnt)
        {
            cnt -= cost; // 花掉预算
            a[i] = 0;    // 这个符被打到 0
            round++;     // 多出一次成功施法
        }
        // 由于 a 已降序 → cost 单调不减，而 cnt 单调不增，
        // 因此一旦买不起，后面全都买不起，这里其实可以直接 break。
    }

    // ---------------- 5. 用剩余预算反复“复用零符” ----------------
    // 重新降序排序：被买下的都变成 0 了，排完之后 a[0] 是剩下的最大余数。
    // a[0] == 0 表示所有符都已归零。
    sort(all(a), greater<>());

    if (a[0] == 0)
    {
        // 全零之后想再多施一次法，只能挑一个 0 号符：
        // 从预算掏 x-1 点把它填到 x-1，再靠本次施法自带的 +1 补满 x 然后放电。
        // 所以此后每一次施法的净代价固定为 x - 1，能买几次就买几次。
        if (cnt >= x - 1)
        {
            i128 d = cnt / (x - 1);
            cnt -= (x - 1) * d;
            round += d;
        }
        // 注：若 a[0] != 0，说明它没被买下，即 x - a[0] - 1 > cnt，
        // 而 x - a[0] - 1 <= x - 2 < x - 1，故必有 cnt < x - 1，
        // 这个分支本来也会得到 d = 0 —— 判断是冗余的，保留只为语义清晰。
    }

    // ---------------- 6. 输出 S - (x-1) * R ----------------
    // round 最大约 1e23，(x-1) % MOD < 1e9，乘积约 1e32，仍在 i128 范围内。
    // 先减可能变负，故 +MOD 再取模。
    cout << (sum - (x - 1) % MOD * round % MOD + MOD) % MOD << "\n";
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    int t = 1;
    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

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

2026牛客暑期多校 8——Problem F. Tree Shifts Her

Posted on 2026-08-12 Edited on 2026-08-14

题目大意

世界树的裂隙

时间限制：C/C++/Rust/Pascal 4 秒，其他语言 8 秒
空间限制：C/C++/Rust/Pascal 1024 MB，其他语言 2048 MB
Special Judge，64bit IO Format: %lld

在月球上，篝一直研究着一份浩繁的可能性集合。她用一种极度压缩的语言讲述自己的发现：寥寥数语所承载的信息，就足以压垮一个普通人的心智。

孝太郎不愿认输，一次次动用自己加速思维的能力去追赶她的讲解。这样的尝试失败了太多次，于是篝决定在继续讲下去之前，先测一测他的反应速度。当然，"把话说得简单些"从来不在她的选项之内。

这一次，篝取出了一棵有 $n$ 个顶点的世界树，顶点编号为 $1$ 到 $n$ 。这棵树是无向、无权的。

每次询问给出两个顶点 $u$ 和 $v$ 。篝会暂时删去 $u$ 到 $v$ 的唯一简单路径上的所有边，此时世界树会分裂成若干个连通块，构成一个森林。

一个连通块的直径定义为其中任意两点之间距离的最大值，其中距离指两点间路径上的边数。特别地，只含一个顶点的连通块，其直径为 $0$ 。

对于每次询问，孝太郎需要求出所有连通块直径之和。

各次询问相互独立：每次询问结束后，所有被删去的边都会恢复原状，然后才进行下一次询问。特别地，若 $u = v$ ，则该路径上不含任何边，世界树保持不变。

第一行包含两个整数 $n$ 和 $q$ （ $1 \le n, q \le 2 \cdot 10^5$ ）。

接下来 $n - 1$ 行，每行两个整数 $a_i$ 和 $b_i$ （ $1 \le a_i, b_i \le n$ ），表示顶点 $a_i$ 与 $b_i$ 之间有一条无向边。保证这些边构成一棵树。

接下来 $q$ 行，每行两个整数 $u_i$ 和 $v_i$ （ $1 \le u_i, v_i \le n$ ），表示一次询问。

对于每次询问，输出一行一个整数，表示删去对应路径上的边之后，所有连通块的直径之和。

样例中的树形态如下：边集为 $\{(1,2),(2,3),(3,4),(3,5),(5,6),(5,7)\}$ 。

询问 $1$ ： $u = 1, v = 4$ 。路径为 $1 \to 2 \to 3 \to 4$ ，删去边 $(1,2),(2,3),(3,4)$ 。剩余连通块为 $\{1\}$ 、 $\{2\}$ 、 $\{4\}$ 、 $\{3,5,6,7\}$ ，直径分别为 $0, 0, 0, 2$ ，总和为 $2$ 。
询问 $2$ ： $u = 6, v = 7$ 。路径为 $6 \to 5 \to 7$ ，删去边 $(5,6),(5,7)$ 。剩余连通块为 $\{6\}$ 、 $\{7\}$ 、 $\{1,2,3,4,5\}$ ，直径分别为 $0, 0, 3$ （如 $1$ 与 $4$ 之间），总和为 $3$ 。
询问 $3$ ： $u = 3, v = 3$ 。路径不含任何边，整棵树保持不变，其直径为 $4$ （如 $1$ 与 $6$ 之间），总和为 $4$ 。
询问 $4$ ： $u = 2, v = 5$ 。路径为 $2 \to 3 \to 5$ ，删去边 $(2,3),(3,5)$ 。剩余连通块为 $\{1,2\}$ 、 $\{3,4\}$ 、 $\{5,6,7\}$ ，直径分别为 $1, 1, 2$ ，总和为 $4$ 。
询问 $5$ ： $u = 1, v = 7$ 。路径为 $1 \to 2 \to 3 \to 5 \to 7$ ，删去边 $(1,2),(2,3),(3,5),(5,7)$ 。剩余连通块为 $\{1\}$ 、 $\{2\}$ 、 $\{3,4\}$ 、 $\{5,6\}$ 、 $\{7\}$ ，直径分别为 $0, 0, 1, 1, 0$ ，总和为 $2$ 。

思路讲解

AC代码

源代码

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

2023 Abakoda Long Contest——C. Canonizing Cannonade（封圣炮响）

Posted on 2026-08-10

题目大意

题目描述

Bob 正在为学校的一场模拟战斗设计队形，参与者扮演潘普洛纳战役中的士兵。

一个队形是一个 $r \times c$ 的网格，其中恰好有 $m$ 个格子里站着士兵。敌方每消耗一发炮弹，可以进行如下操作：

选择某一行或某一列，消灭该行或该列中的所有士兵。

定义一个队形的韧性为消灭其中所有士兵所需的最少炮弹数。

给定 $r, c, m, k$ ，请构造出任意一个韧性恰好等于 $k$ 的队形，或者报告无解。你需要回答同一个文件中的 $T$ 组测试数据。

输入格式

第一行包含一个整数 $T$ ，表示测试数据的组数。

接下来是每组测试数据的描述，每组数据占一行，包含四个用空格分隔的整数 $r, c, m, k$ 。

输出格式

对于每组测试数据，若无解，输出一行 NO；否则输出一行 YES。

若输出 YES，则接下来还需输出一个 $r \times c$ 的网格，即输出 $r$ 行，每行包含一个长度为 $c$ 的字符串。网格中只能包含字符 . 和 #，分别表示空地和站有士兵的格子；注意其中恰好应有 $m$ 个字符为 #。

若存在多组可行解，输出任意一组均可。

数据范围与评分

对所有子任务：

0 \leq T \leq 1500,\quad 1 \leq r, c \leq 25,\quad 1 \leq m \leq rc,\quad 1 \leq k \leq 10^9

子任务	分值	限制
1	$\mathbf{40}$	$m = k$
2	$\mathbf{30}$	$m = 2k$
3	$\mathbf{20}$	$m = 3$
4	$\mathbf{10}$	无额外限制

样例

1
2
3

2
7 8 11 4
9 6 2 10

YES
........
...#....
#..#...#
#....#.#
...##.#.
........
...#....
NO

对于第一组数据，可以验证所有士兵能够用 $4$ 次操作被清除：选择从上往下的第三、四、五行，以及从左往右的第四列。同时可以说明无法用 $3$ 次操作完成，因此该队形的韧性为 $4$ 。

对于第二组数据，无法构造出满足要求的队形。

思路讲解

AC代码

源代码

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

ABC-470-E - Concentration （翻牌配对）

Posted on 2026-08-10

题目大意

翻牌配对

时限 2000 ms，内存 1024 MB。

给定整数 $N, L$ 以及 $N$ 个两两不同的整数 $A_1, A_2, \dots, A_N$ 。

桌上共有 $2N$ 张牌，每个数值 $A_i$ 恰好写在其中两张牌的正面上，牌的背面没有任何信息。

初始时把所有牌随机洗乱后背面朝上摆放。等价地说：设 $B$ 是把序列 $(A_1, A_1, A_2, A_2, \dots, A_N, A_N)$ 均匀随机打乱后得到的长度为 $2N$ 的序列，则第 $i$ 张牌正面的数字为 $B_i$ 。

玩家知道所有的 $A_i$ ，但最初不知道任何 $B_i$ 。一旦某张牌 $i$ 被翻开，玩家就会永久记住 $B_i$ 的值。

游戏开始时，生命值为 $L$ ，得分为 $0$ ，尚未被移除的牌的下标集合为 $S = \{1, 2, \dots, 2N\}$ 。玩家在任何时刻都知道当前的生命值、得分和集合 $S$ 。

重复执行以下步骤，直到生命值变为 $0$ 或者 $S$ 为空：

玩家根据当前已知信息，从 $S$ 中选择一张牌 $i$ 并翻开，获知 $B_i$ 。
玩家根据当前已知信息（包括刚获知的 $B_i$ ），从 $S \setminus \{i\}$ 中选择一张牌 $j$ 并翻开，获知 $B_j$ 。
若 $B_i = B_j$ ，则把 $i, j$ 从 $S$ 中移除，并把得分增加 $B_i$ 。
若 $B_i \neq B_j$ ，则把这两张牌翻回背面，并把生命值减少 $1$ 。

玩家以最大化最终得分的期望值为目标采取最优策略。请求出游戏结束时的期望得分。

输入从标准输入按以下格式给出：

第一行两个整数 $N$ 和 $L$ 。

第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$ 。

输出一行一个实数，表示最优策略下游戏结束时的期望得分。答案与标准答案的绝对误差或相对误差不超过 $10^{-5}$ 即视为正确。

$1 \leq N \leq 200$
$1 \leq L \leq 200$
$1 \leq A_1 < A_2 < \dots < A_N \leq 10^5$
所有输入值均为整数。

1
2

3 2
1 2 3

1	3.8666666667

游戏可能按如下方式进行。为了区分这六张牌，分别称它们为 A、B、C、D、E、F。

游戏以生命值 $2$ 、得分 $0$ 开始。

翻开卡牌 A，上面写着 $3$ 。
翻开卡牌 B，上面写着 $2$ 。
因为数字不同，把两张牌翻回背面，生命值减少 $1$ ，变为 $1$ 。

翻开卡牌 C，上面写着 $3$ 。
翻开卡牌 A，上面写着 $3$ 。
因为数字相同，把这两张牌移出桌面，得分增加 $3$ ，变为 $3$ 。

翻开卡牌 D，上面写着 $1$ 。
翻开卡牌 E，上面写着 $2$ 。
因为数字不同，把两张牌翻回背面，生命值减少 $1$ ，变为 $0$ 。

生命值变为 $0$ ，游戏结束，最终得分为 $3$ 。

注意，在上述过程中刚翻开卡牌 C 之后，玩家可以利用「卡牌 C 正面写着 $3$ 」这一信息，选择翻开另一张已经知道写着 $3$ 的卡牌 A。

1 2	5 2 2 3 5 7 101

1	17.8560846561

1 2	20 10 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

1	770.7122293087

思路讲解

AC代码

源代码

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

ABC-470-D - Inverse and Swap

Posted on 2026-08-10

题目大意

D - Inverse and Swap

时间限制：2 秒 / 内存限制：1024 MiB

分值： $400$ 分

给定一个 $(1, \dots, N)$ 的排列 $P = (P_1, \dots, P_N)$ 。

请依次处理 $Q$ 个询问，询问有以下两种：

1 x y：交换 $P_x$ 与 $P_y$ 的值。
2：构造满足以下条件的 $(1, \dots, N)$ 的排列 $P' = (P'_1, \dots, P'_N)$ ，并将 $P_1, \dots, P_N$ 的值分别替换为 $P'_1, \dots, P'_N$ 。（可以证明满足条件的 $P'$ 唯一存在。）
- 对每个满足 $1 \leq i \leq N$ 的整数 $i$ ，都有 $P_{P'_i} = i$ 。

请输出处理完所有询问后 $P_1, \dots, P_N$ 的值。

输入从标准输入给出，格式如下：

N Q
P_1 P_2 ⋯ P_N
query_1
⋮
query_Q

其中 $\mathrm{query}_q$ 表示第 $q$ 个询问，以下面两种格式之一给出：

1 x y

将处理完所有询问后 $P_1, \dots, P_N$ 的值以空格分隔，输出在一行中。

$2 \leq N \leq 5 \times 10^5$
$1 \leq Q \leq 5 \times 10^5$
$(P_1, \dots, P_N)$ 是 $(1, \dots, N)$ 的排列
对于类型 $1$ 的询问， $1 \leq x < y \leq N$
输入中的所有值均为整数

输入

输出

4 5 2 1 3

说明

每个询问处理完成时， $P_1, \dots, P_N$ 的值如下：

处理完第 $1$ 个询问时， $P = (2,5,3,1,4)$
处理完第 $2$ 个询问时， $P = (4,1,3,5,2)$
处理完第 $3$ 个询问时， $P = (4,3,1,5,2)$
处理完第 $4$ 个询问时， $P = (4,3,5,1,2)$
处理完第 $5$ 个询问时， $P = (4,5,2,1,3)$

输入

7 4
3 7 5 6 4 2 1
2
2
2
2

输出

1	3 7 5 6 4 2 1

说明

本样例中的 $4$ 个询问均为类型 $2$ ，处理完成后 $P$ 与初始时相同。

输入

10 8
7 3 2 4 8 5 10 9 1 6
2
1 4 10
1 6 9
2
1 9 10
1 3 10
2
1 4 6

输出

1	3 10 2 8 6 7 1 5 9 4

说明

本样例包含两种询问混合出现的情况，请按照询问给出的顺序依次处理。

思路讲解

那么实际上，排列就是位置和值的对应关系啊，至于箭头的方向和哪边是位置，哪边是值，这个其实不是特别重要啊，用一个变量 f 维护一下即可啊。

那么这个叫什么交换操作就只是需要修改一下这个对应关系即可啊，这个就非常简单，你可以理解为我们就是一个无向图啊，然后最后再进行定向即可啊。

当然，还是要注意一下值和位置当前的对应关系啊。

存储的时候，S 和 T都可以看成是一个只有一条出边的有向图邻接表啊，那么实际上，我们存储的就是这个无向图啊。因为无向图就是一条边有两个方向的有向图嘛。

int mp[2][500005];

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

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> mp[0][i];        // 位置 i —— 值 mp[0][i]
        mp[1][mp[0][i]] = i;    // 同一条边，从值那一侧再记一遍
    }

    int f = 0;                  // 定向标记

    while (q--) {
        int op;
        cin >> op;

        if (op == 2) {
            f ^= 1;             // 换个方向读，O(1)
            continue;
        }

        int x, y;
        cin >> x >> y;

        int *S = mp[f];         // 当前的"位置侧"
        int *T = mp[f ^ 1];     // 对侧

        int u = S[x], v = S[y]; // 原来 x—u、y—v 两条边

        // 拆掉 x—u、y—v，重连成 x—v、y—u
        // 用 tie + make_tuple 一次性赋值：右边先整体求值，
        // 天然避开"先改哪个、后改哪个"的顺序陷阱
        tie(S[x], S[y], T[u], T[v]) = make_tuple(v, u, y, x);
    }

    // 最后按 f 定向，输出对应的那一侧
    const int *R = mp[f];
    for (int i = 1; i <= n; i++)
        cout << R[i] << " \n"[i == n];

    return 0;
}

AC代码

https://atcoder.jp/contests/abc470/submissions/78275932

AI 代码

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

/* ------------------------------------------------------------------
   模型：排列 = 位置集 与 值集 之间的完美匹配（无向）
     mp[0][i] : 从"位置侧"看，位置 i 连到哪个值
     mp[1][v] : 从"值侧"看，值 v 连到哪个位置
     两者存的是同一个匹配，只是从两侧各记一遍邻接。

   f = 当前把哪一侧当作"位置"来读（即定向）
     f = 0 -> 真正的 P 就是 mp[0]
     f = 1 -> 真正的 P 是 mp[1]（相当于整体取了逆）

   操作 2：只改定向，f ^= 1，不动任何数据
   操作 1：在当前"位置侧" S 上把 x,y 两条边的另一端对调，
           同时在对侧 T 上把这两个端点的记录改回来，共 4 个格子
   ------------------------------------------------------------------ */

int mp[2][500005];

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

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> mp[0][i];        // 位置 i —— 值 mp[0][i]
        mp[1][mp[0][i]] = i;    // 同一条边，从值那一侧再记一遍
    }

    int f = 0;                  // 定向标记

    while (q--) {
        int op;
        cin >> op;

        if (op == 2) {
            f ^= 1;             // 换个方向读，O(1)
            continue;
        }

        int x, y;
        cin >> x >> y;

        int *S = mp[f];         // 当前的"位置侧"
        int *T = mp[f ^ 1];     // 对侧

        int u = S[x], v = S[y]; // 原来 x—u、y—v 两条边

        // 拆掉 x—u、y—v，重连成 x—v、y—u
        // 用 tie + make_tuple 一次性赋值：右边先整体求值，
        // 天然避开"先改哪个、后改哪个"的顺序陷阱
        tie(S[x], S[y], T[u], T[v]) = make_tuple(v, u, y, x);
    }

    // 最后按 f 定向，输出对应的那一侧
    const int *R = mp[f];
    for (int i = 1; i <= n; i++)
        cout << R[i] << " \n"[i == n];

    return 0;
}

源代码