Znzryb's Blog

2025_ICPC_NERC_Northern_Eurasia_Finals——D. Doorway（扫描线的本质就是遍历一个出一个）（扫描线特别适合处理区间重合相关问题）

Posted on 2026-02-09 Edited on 2026-03-14

题目大意

题目总结：D. Doorway

说白了就是告诉你滑动门两边的墙壁，告诉你从左到右的滑动门的这个长度。然后有好几层的这样子的子的滑动门系统问你这样子的系统能够张开的最大口子长度是多少。

问题描述

在一个多层滑动门系统中，共有 $n$ 层。每一层可以看作一个水平区间，由左侧墙壁 $x_{i,1}$ 和右侧墙壁 $x_{i,2}$ 限定。每一层包含若干扇固定长度的滑动门，门可以在该层的墙壁范围内自由左右滑动，但不能相互重叠，也不能越过墙壁。

目标

寻找一个最大的开口（Opening）。开口定义为一个水平区间，使得在所有层中，该区间内的任何位置都没有任何门或墙壁遮挡。你需要通过调整每一层门的位置，使得这个公共开口的长度最大化。

输入格式

第一行：层数 $n$ ( $1 \le n \le 10^5$ )。
接下来的 $n$ 行，每行描述一层：
- 三个整数：门数量 $k_i$ 、左墙坐标 $x_{i,1}$ 、右墙坐标 $x_{i,2}$ ( $0 \le x_{i,1} < x_{i,2} \le 10^9$ )。
- $k_i$ 个整数：该层从左到右每扇门的长度 $l_{i,j}$ 。
数据保证 $\sum k_i \le 3 \cdot 10^5$ 。

输出格式

一个整数，表示通过移动门所能达到的最大公共开口长度。

样例解释

样例 1

输入：
- 第 1 层：墙在 $[2, 11]$ ，门长 3 和 2。
- 第 2 层：墙在 $[4, 12]$ ，门长 1, 1 和 2。
逻辑：
所有层的共同墙壁限制区间为 $[\max(x_{i,1}), \min(x_{i,2})]$ ，即 $[4, 11]$ ，长度为 7。
- 在第 1 层中，如果将长为 3 的门推到最左，长为 2 的门推到最右，中间会留出空隙。
- 在第 2 层中，通过合理分配门的位置，可以使得在 $[4, 11]$ 这个范围内，所有层共同暴露出的最大空白区间长度为 4。

样例 2

输入：
- 第 1 层：墙在 $[0, 7]$ ，门长 2 和 4（总长 6，空隙 1）。
- 第 2 层：墙在 $[4, 9]$ ，门长 4（总长 4，空隙 1）。
逻辑：
第一层有效范围 $[0, 7]$ ，第二层有效范围 $[4, 9]$ ，它们的交集是 $[4, 7]$ ，长度仅为 3。由于两层中都存在长度大于或等于交集长度的门或门组限制，无法在所有层中腾出一个完全没有遮挡的公共区间。
输出： 0

注意

这个示例展示了第一个例子的解决方案。墙壁填充黑色，门填充各种灰色，开口是白色。当每层的第一个门向左移动，其余的门向右移动时，我们得到了最大的开口为4。

思路讲解

还是一样的思路啊，就是当你发现你只知道起始位置的时候，你会发现计算这个东西啊，其实不是很容易。

当然，我们上面所指的起始位置，其实是指的总体的起始位置。考虑到，虽然说总体的起始位置，知道总体的起始位置，然后我们去进行一个这个操作，它其实也是需要 $O(N)$ 吧。

那我们曾经提及过非常多次，当我们发现采用总体的想法碰壁的时候，我们应该怎么样？我们应该采用更加细颗粒度的东西，是不是？因此我们可以采用每一个起始位置，就是每一个滑窗系统的起始位置，去解决以及考虑这个问题。

AI 的模拟

这道题维护的是：每层的"gap 右端点"，一共 $N$ 个值。
具体来说，multiset 里始终有 $N$ 个数，第 $i$ 层占一个位置，表示"在当前扫描位置下，第 $i$ 层的空隙最远能延伸到哪里"。
我画一下扫描过程，用样例来说明。

样例模拟

1
2
3

2
2 2 11 3 2
3 4 12 1 1 2

层 1： $x_1=2$ ， $x_2=11$ ，门 $=[3,2]$ ， $w=4$ 。gap-start 候选： $2, 5, 7$ ，对应 rightend： $6, 9, 11$ 。
层 2： $x_1=4$ ， $x_2=12$ ，门 $=[1,1,2]$ ， $w=4$ 。gap-start 候选： $4, 5, 6, 8$ ，对应 rightend： $8, 9, 10, 12$ 。
所有事件排序：

扫到 $g$	属于哪层	新 rightend	multiset 状态	$\min - g$
$2$	层1	$6$	$\{6, -\infty\}$	层2还没激活
$4$	层2	$8$	$\{6, 8\}$	$6-4=2$
$5$	层1	$9$	$\{9, 8\}$	$8-5=3$
$5$	层2	$9$	$\{9, 9\}$	$9-5=\mathbf{4}$
$6$	层2	$10$	$\{9, 10\}$	$9-6=3$
$7$	层1	$11$	$\{11, 10\}$	$10-7=3$
$8$	层2	$12$	$\{11, 12\}$	$11-8=3$
答案 = $4$ ，在 $g=5$ 时取到。
multiset 里的含义：在扫描位置 $g=5$ 时，层 1 的空隙最远能到 $9$ ，层 2 的空隙最远能到 $9$ 。取最小值 $9$ ，opening = $9 - 5 = 4$ 。
所以维护的东西就是这 $N$ 个"每层能延伸到多远"的值，用 multiset 随时拿最小值。

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）
为什么这道题目你需要去塞一个负无穷呢？是这样子的，这个是因为啊，我们另外一道题目就是这个 brick work 是处理这个不相交问题，但这道题目我们处理的是相交问题。不相交问题你自然是还没有启用的区间，你自然是不用往里面去塞的。但是集合相交问题，还没有启用的集合，需要往里塞一个未启用值，就是未生效值。因为它都没启用，它肯定是不相交的对吧，为了避免这种情况影响我们的最终判断，我们需要往里面塞一个未启用值？

multiset<ll> ri_st;
// vector<Event> event_ls;
vector<ll> i_ri_ls(N + 2);
map<ll, vector<Event> > x1_idx_x2_mtx;
for (int i = 1; i <= N; ++i) {
    ll sum = accumulate(all(door_mtx[i]), 0ll);
    auto [x1,x2] = wall_pos[i];
    x2 -= sum;
    // 在没有碰到自己的左端点之前，这个滑动系统不应该贡献任何的这个有效的右端点。
    ri_st.insert(-INF);
    i_ri_ls[i] = -INF;
    x1_idx_x2_mtx[x1].push_back({i, x2});
    for (auto v: door_mtx[i]) {
        x1 += v;
        x2 += v;
        x1_idx_x2_mtx[x1].push_back({i, x2});
    }
}
ll ans = 0;
for (auto &[x1,vec]: x1_idx_x2_mtx) {
    for (auto &[id,x2]: vec) {
        ri_st.erase(ri_st.find(i_ri_ls[id]));
        ri_st.insert(x2);
        i_ri_ls[id] = x2;
    }
    ans = max(ans, *ri_st.begin() - x1);
}

AC代码

AC
https://codeforces.com/contest/2181/submission/362349671

源代码

/**
 * Problem: D. Doorway
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2181/problem/D
 * Created: 2026-02-11 00:56:58
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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";
#include <iostream>

#define debug1d(a) do { \
std::cerr << #a << " = ["; \
bool first = true; \
for (const auto &x : a) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} while (0)

#define debug2d(a) do { \
std::cerr << #a << " = [\n"; \
for (const auto &row : a) { \
std::cerr << "  ["; \
bool first = true; \
for (const auto &x : row) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} \
std::cerr << "]\n"; \
} while (0)

#define debug3d(a) do { \
std::cerr << #a << " = [\n"; \
for (const auto &mat : a) { \
std::cerr << "  [\n"; \
for (const auto &row : mat) { \
std::cerr << "    ["; \
bool first = true; \
for (const auto &x : row) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} \
std::cerr << "  ]\n"; \
} \
std::cerr << "]\n"; \
} while (0)
#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 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, testcase;

/*
 *
 */
struct Wall_pos {
    ll x1, x2;
};

struct Event {
    ll idx/*,x1*/, x2;
    // bool operator<(const Event &o) const {
    //     if (x1!=o.x1) return x1<o.x1;
    //     return idx<o.idx;
    // }
};

void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll> > door_mtx(N + 2);
    vector<Wall_pos> wall_pos(N + 2);
    ll mxx1 = 0, mnx2 = INF;
    for (int i = 1; i <= N; ++i) {
        ll K, x1, x2;
        cin >> K >> x1 >> x2;
        wall_pos[i] = {x1, x2};
        mxx1 = max(mxx1, x1);
        mnx2 = min(mnx2, x2);
        door_mtx[i].resize(K);
        for (auto &v: door_mtx[i]) {
            cin >> v;
        }
    }
    multiset<ll> ri_st;
    // vector<Event> event_ls;
    vector<ll> i_ri_ls(N + 2);
    map<ll, vector<Event> > x1_idx_x2_mtx;
    for (int i = 1; i <= N; ++i) {
        ll sum = accumulate(all(door_mtx[i]), 0ll);
        auto [x1,x2] = wall_pos[i];
        x2 -= sum;
        // 在没有碰到自己的左端点之前，这个滑动系统不应该贡献任何的这个有效的右端点。
        ri_st.insert(-INF);
        i_ri_ls[i] = -INF;
        x1_idx_x2_mtx[x1].push_back({i, x2});
        for (auto v: door_mtx[i]) {
            x1 += v;
            x2 += v;
            x1_idx_x2_mtx[x1].push_back({i, x2});
        }
    }
    ll ans = 0;
    for (auto &[x1,vec]: x1_idx_x2_mtx) {
        for (auto &[id,x2]: vec) {
            ri_st.erase(ri_st.find(i_ri_ls[id]));
            ri_st.insert(x2);
            i_ri_ls[id] = x2;
        }
        ans = max(ans, *ri_st.begin() - x1);
    }
// #ifdef LOCAL
//     debug2d(x1_idx_x2_mtx);
// #endif
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
    Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2181/submission/362349671

*/

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

AI 提示

好，我来认真讲一下这道 Doorway 的扫描线，以及和 Brickwork 的对比。

Doorway 扫描线的精妙之处

这道题的扫描线，最精妙的地方有三层递进：

第一层：观察到 gap 宽度是定值

每层的门总长是固定的，墙的区间也是固定的，所以每层的空隙宽度 $w_i = x_2 - x_1 - \sum l_j$ 是一个常数。不管你怎么滑动门，空隙的大小不变，变的只是空隙的位置。
这意味着原问题从"怎么安排门"变成了"从每层选一个空隙位置，使得所有层的空隙的交集最大"。

第二层：最优 st 必在 gap-start 处（这个说白了傻子都知道，所谓的gap start就是每层都有K种选择，纯纯是傻逼。）

opening 的左端点 st 如果确定了，那每层的最优策略就是：把空隙尽量往右推（把尽可能多的门放到 st 左边），这样右端点 $\text{rightend}_i(\text{st})$ 最大。
关键性质：在两个相邻的 gap-start 之间，所有层的 rightend 都不变，但 st 在递增，所以 $\min(\text{rightend}_i) - \text{st}$ 严格递减。
结论：最优 st 必然是某层的某个 gap-start 位置。候选点总共就 $\sum(k_i + 1)$ 个。

第三层：扫描线 + multiset 做到 O(sum_k * log n)

如果对每个候选 st 暴力算所有层的 rightend，复杂度是 $O(\sum k_i \times n)$ ，太慢。
精妙之处：把所有候选 st 排序后从左到右扫描，每次只有一层的 rightend 发生变化（就是当前 gap-start 所属的那一层）。用 multiset 维护所有层的 rightend， $O(\log n)$ 就能查到全局最小值。
这和 Brickwork 里的扫描线"每次只有一个矩形进入/离开 activates 集合"是同一个道理。

和 Brickwork 的对比

	Brickwork（砖墙）	Doorway（门）
消除的维度	扫描 x 坐标，把 2D 矩形重叠问题变成 1D 区间重叠问题	扫描 gap-start 位置，把"多层选位置求交集最大"变成"逐步更新单层 rightend"
事件类型	矩形左边进入（op=1）、右边离开（op=0）	gap-start 出现（更新该层的 rightend）
维护的集合	`set<pair<ll,ll>>` 维护当前所有激活的 y 区间，保证互不重叠	`multiset<ll>` 维护每层当前的 rightend，追踪全局最小值
每次事件的操作	插入时检查前驱/后继是否重叠；删除时直接 erase	更新一层的 rightend（erase 旧值 + insert 新值），查 `*begin()`
核心不变量	activates 中所有区间互不重叠	multiset 中恰好 N 个值，每层一个
判定条件	每次插入都不和邻居重叠 → yes	`*begin() - g` 的最大值就是答案

相同点

都是把高维问题降到一维：Brickwork 把 2D 重叠检测降到 1D 区间检测；Doorway 把"多层 gap 位置选择"降到一维扫描。
每次事件只影响一个元素：Brickwork 每次只有一个区间进/出；Doorway 每次只有一层的 rightend 变化。这是扫描线高效的根本原因。
都依赖有序集合：利用 set/multiset 的 $O(\log n)$ 操作来维护全局信息。

不同点

目标不同：Brickwork 是判定问题（有没有重叠）；Doorway 是最优化问题（最大 opening）。
集合语义不同：Brickwork 的 activates 存的是当前活跃的区间，需要保证互不重叠，所以只需查前驱后继；Doorway 的 multiset 存的是每层一个标量值（rightend），需要的是全局最小值，所以用 begin()。
事件的对称性：Brickwork 有"进入"和"离开"两种事件，是对称的；Doorway 只有一种事件（gap-start），每层的 rightend 只增不减，没有"离开"。

错误的代码（然后采用类似于懒更新的策略。但是呢，要记住一件事情啊，**懒更新**，你不能把更加优秀的东西塞入**这个你的集合里面**）

/**
 * Problem: D. Doorway
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2181/problem/D
 * Created: 2026-02-10 17:09:28
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 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 debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\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 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,testcase;

/*
 *
 */
struct Wall_pos {
    ll x1,x2;
};
// struct Event {
//     ll st,ed;
//     // 这里要使用 Auto 的自动推导类型。
//     auto operator<=>(const Event&) const = default;
// };
void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll>> door_mtx(N+2);
    vector<Wall_pos> wall_pos(N+2);
    ll mxx1=0,mnx2=INF;
    for (int i=1;i<=N;++i) {
        ll K,x1,x2;
        cin>>K>>x1>>x2;
        wall_pos[i]={x1,x2};
        mxx1=max(mxx1,x1);
        mnx2=min(mnx2,x2);
        door_mtx[i].resize(K);
        for (auto &v:door_mtx[i]) {
            cin>>v;
        }
    }
    // vector<Event> event_ls;
    map<ll,vector<ll>> event_mtx;
    multiset<ll> ed_st;
    for (int i=1;i<=N;++i) {
        // vector<ll> suf_sum(SZ(door_mtx[i]));
        // partial_sum(door_mtx[i].rbegin(),door_mtx[i].rend(),suf_sum.rbegin());
        // suf_sum.push_back(0);
        ll sum=accumulate(all(door_mtx[i]),0ll);
        auto [x1,x2]=wall_pos[i];
        // event_ls.push_back({x1,x2-sum});
        event_mtx[x1].push_back(x2-sum);
        ed_st.insert(x2-sum);
        ed_st.insert(x2);
        x2-=sum;
        for (auto v:door_mtx[i]) {
            x1+=v;
            x2+=v;
            // event_ls.push_back({x1,x2});
            event_mtx[x1].push_back(x2);
            ed_st.insert(x2);
        }
    }
    ll ans=0;
    for (auto it=event_mtx.begin();it!=event_mtx.end();++it) {
        for (auto ed:it->second) {
            auto it_erase=ed_st.find(ed);
            if (it_erase!=ed_st.end()) {
                ed_st.erase(it_erase);
            }
        }
        if (it->first<mxx1) {
            continue;
        }
        auto nex_it=next(it);
        if (nex_it==event_mtx.end()) {
            continue;
        }
        ll lans=*ed_st.begin()-(nex_it->first);
        ans=max(ans,lans);
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/

for (int i = 1; i <= N; ++i) {
    ll sum = accumulate(all(door_mtx[i]), 0ll);
    auto [x1,x2] = wall_pos[i];
    x2 -= sum;
    // 在没有碰到自己的左端点之前，这个滑动系统不应该贡献任何的这个有效的右端点。
    ri_st.insert(-INF);
    i_ri_ls[i] = -INF;
    x1_idx_x2_mtx[x1].push_back({i, x2});
    for (auto v: door_mtx[i]) {
        x1 += v;
        x2 += v;
        x1_idx_x2_mtx[x1].push_back({i, x2});
    }
}

2025_ICPC_NERC_Northern_Eurasia_Finals——F. Fragmented Nim（先碰到弹性堆的那一方，一定赢了，因为他不仅可以制造陷阱，还可以逼迫对手进入陷阱）

Posted on 2026-02-09 Edited on 2026-02-11

题目大意

经典的Nim游戏规则如下。有 $n$ 堆石头，第 $i$ 堆最初包含 $a_i$ 个石头。Alice和Bob轮流进行; Alice先行动。在他们的轮次中，玩家选择任意非空堆并从中移除任意正数个石头。拿到最后一块石头的玩家获胜。

在玩了很多Nim游戏之后，Alice和Bob决定稍微改变规则。在这一变体中，轮到的玩家不选择堆 — — 他们的对手为他们选择！然而，玩家仍然可以决定从那堆中移除多少石头。

Alice仍然先手。在Alice的轮次中，Bob选择任意非空堆，然后Alice从中移除任意正数个石头。同样地，在Bob的轮次中，Alice选择任意非空堆，然后Bob从中移除任意正数个石头。

对于给定的石头堆配置，确定如果两名玩家都遵循最佳策略，谁将获胜。

思路讲解

这种题目是这样子的，先碰到弹性堆的那一方，一定赢了。先碰到弹性堆的那一方一定赢了，这个是因为你不仅可以制造陷阱，还可以逼迫对手进入陷阱，这个是最厉害的地方。

全是 1 的情况（ $bigs = 0$ ）：每回合只能取 1 颗，总共 $n$ 回合，奇数轮 Alice 赢，偶数轮 Bob 赢——即 $n$ 为奇则 Alice 胜。
存在 $>1$ 的堆时（ $bigs \geq 1$ ）：当一个玩家被指向一个大堆（ $a_i > 1$ ），他可以选择"全取"（消灭堆）或"留 1"（变成 size-1 堆）。这意味着他能自由控制对手下一步面对的 $ones$ 的奇偶性——因此被指向大堆的人必赢。
既然指向大堆 = 给对方胜利，所以"选堆方"（chooser）一定会优先把对手指向 size=1 的堆。双方轮流消耗 size-1 堆，直到 size-1 堆耗尽，最终被迫指向大堆的那一方就输了。
消耗 $ones$ 个 size-1 堆需要 $ones$ 轮。若 $ones$ 为偶数，Alice 仍是 mover，获得大堆 → Alice 赢；若 $ones$ 为奇数，Bob 是 mover → Bob 赢。

在变体 Nim 的纯弹性子游戏里，当前玩家必胜，本质上靠的是一个两步连招：

第一步（你是操作者）：对手把你指到某个弹性堆，你把它削成 1。你制造了一个"陷阱"。

第二步（你变成了选堆方）：下一回合，角色互换——你来选堆，对手来操作。你把对手指向那个你刚造出来的大小为 1 的堆。对手被迫吃掉它，白白浪费一个回合。

净效果：两个回合过去了，一个弹性堆被消灭，又轮到你了。你从 $f$ 个弹性堆的先手，变成了 $f-1$ 个弹性堆的先手。循环往复，直到只剩最后一个弹性堆，你直接清空获胜。

这个连招之所以成立，是因为操作者和选堆方的角色每回合交替。你当操作者时布下陷阱，下一回合你当选堆方时把对手推进陷阱。

AC代码

AC
https://codeforces.com/contest/2181/submission/362136313

源代码

/**
 * Problem: F. Fragmented Nim
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2181/problem/F
 * Created: 2026-02-09 21:02:52
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 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 debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\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 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,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll cnt1=0;
    for (int i=0;i<N;++i) {
        cin>>A[i];
        if (A[i]==1) {
            ++cnt1;
        }
    }
    if (cnt1==N) {
        if (N&1) {
            cout<<"Alice\n";
        }else {
            cout<<"Bob\n";
        }
        return;
    }
    if (cnt1%2==0) {
        cout<<"Alice\n";
    }else {
        cout<<"Bob\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2181/submission/362136313

*/

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

AI 提示

[1 tool called]
好的，让我来分析这道 Fragmented Nim 变体博弈问题。
先读一下你的代码模板，然后我来推导策略。
这道题的关键在于理解"选堆权"和"取石权"分离后博弈结构的变化。让我推导一下：
核心推导：

全是 1 的情况（ $bigs = 0$ ）：每回合只能取 1 颗，总共 $n$ 回合，奇数轮 Alice 赢，偶数轮 Bob 赢——即 $n$ 为奇则 Alice 胜。
存在 $>1$ 的堆时（ $bigs \geq 1$ ）：当一个玩家被指向一个大堆（ $a_i > 1$ ），他可以选择"全取"（消灭堆）或"留 1"（变成 size-1 堆）。这意味着他能自由控制对手下一步面对的 $ones$ 的奇偶性——因此被指向大堆的人必赢。
既然指向大堆 = 给对方胜利，所以"选堆方"（chooser）一定会优先把对手指向 size=1 的堆。双方轮流消耗 size-1 堆，直到 size-1 堆耗尽，最终被迫指向大堆的那一方就输了。
消耗 $ones$ 个 size-1 堆需要 $ones$ 轮。若 $ones$ 为偶数，Alice 仍是 mover，获得大堆 → Alice 赢；若 $ones$ 为奇数，Bob 是 mover → Bob 赢。
结论：

全是 1 → Alice 赢当且仅当 $n$ 为奇
存在 $>1$ 的堆 → Alice 赢当且仅当 size=1 的堆数量为偶数
验证样例：
[1,2,3]：有大堆， $ones=1$ （奇）→ Bob ✓
[1]：全是 1， $n=1$ （奇）→ Alice ✓
[10,3,4,7,4]：有大堆， $ones=0$ （偶）→ Alice ✓
[1 tool called]

AI 提示 2

你这个问题问得好——“到底是什么结构性原因，让碰到弹性堆的人必赢？” 以及 “为什么同样的事在经典 Nim 里不成立？”

核心原因：两步连招

在变体 Nim 的纯弹性子游戏里，当前玩家必胜，本质上靠的是一个两步连招：
第一步（你是操作者）：对手把你指到某个弹性堆，你把它削成 1。你制造了一个"陷阱"。
第二步（你变成了选堆方）：下一回合，角色互换——你来选堆，对手来操作。你把对手指向那个你刚造出来的大小为 1 的堆。对手被迫吃掉它，白白浪费一个回合。
净效果：两个回合过去了，一个弹性堆被消灭，又轮到你了。你从 $f$ 个弹性堆的先手，变成了 $f-1$ 个弹性堆的先手。循环往复，直到只剩最后一个弹性堆，你直接清空获胜。
这个连招之所以成立，是因为操作者和选堆方的角色每回合交替。你当操作者时布下陷阱，下一回合你当选堆方时把对手推进陷阱。

为什么经典 Nim 里这招不灵

经典 Nim 里，你自己选堆、自己操作。你可以执行第一步——把某堆削成 1。但第二步断了：

下一回合，对手自己选堆。对手凭什么要去碰你造出来的那个大小为 1 的堆？对手直接无视它，去操作别的堆。
你造了陷阱，但你没有能力把对手推进去。对手有完全的选择自由。
具体看 $[2, 2]$ 的经典 Nim：

先手把 pile 1 削成 1： $[1, 2]$ 。
后手不碰 pile 1，去把 pile 2 也削成 1： $[1, 1]$ 。
对称局面，先手吃一个，后手吃最后一个，后手赢。
先手的"陷阱"完全被后手绕过了。而在变体 Nim 里， $[2, 2]$ 先手赢，就是因为先手削成 $[1, 2]$ 后，选堆权在先手手里，先手直接把后手按到那个 1 上。

所以真正的区别是什么

	变体 Nim	经典 Nim
操作者能布陷阱吗？	能（削成 1）	能（削成 1）
下一回合能把对手推进陷阱吗？	能（你变成选堆方）	不能（对手自己选堆）
两步连招成立吗？	成立	不成立
决定性的差异不在于"谁碰到弹性堆"，而在于：布陷阱之后，你有没有能力强制对手踩进去。
变体 Nim 里有这个能力（角色交替赋予的），经典 Nim 里没有（双方完全自由选择）。这就是为什么变体 Nim 的弹性子游戏退化成了简单的奇偶计数，而经典 Nim 退化不了——经典 Nim 里没有"强制"机制，信息是完全对称的，所以需要 XOR 这种更精细的不变量来刻画胜负。

2025_ICPC_NERC_Northern_Eurasia_Finals——M. Medical Parity

Posted on 2026-02-09 Edited on 2026-02-12

题目大意

题目总结：M. Medical Parity

问题描述

给定两个长度为 $n$ 的二进制字符串 $x'$ （测试结果串）和 $y'$ （奇偶校验控制串）。

在理想情况下，字符串 $y$ 与 $x$ 必须满足以下关系：

对于每一个位置 $i$ （ $1 \le i \le n$ ）， $y_i$ 是字符串 $x$ 前 $i$ 个字符中 ‘1’ 的数量对 2 取模的结果。

即： $y_i = (\sum_{j=1}^{i} x_j) \pmod 2$ 。

这意味着：

如果 $x$ 的前 $i$ 个字符中有奇数个 ‘1’，则 $y_i = 1$ 。
如果 $x$ 的前 $i$ 个字符中有偶数个 ‘1’，则 $y_i = 0$ .

由于记录数据时可能存在错误，输入的 $x'$ 和 $y'$ 可能不满足上述规则。你需要通过翻转最少数量的位（将 ‘0’ 变 ‘1’ 或将 ‘1’ 变 ‘0’），使得修改后的 $y$ 成为修改后的 $x$ 的合法奇偶校验控制串。翻转操作可以在 $x'$ 或 $y'$ 的任意位置进行。

输出要求

输出使 $y$ 成为 $x$ 的合法奇偶校验串所需的最少总翻转次数。

样例解释

样例 1
输入： $x'=11101, y'=10110$
根据 $x'$ 计算合法的校验串 $y$ ：
- $i=1$ : $x$ 前 1 位有 1 个 ‘1’（奇数）， $y_1=1$
- $i=2$ : $x$ 前 2 位有 2 个 ‘1’（偶数）， $y_2=0$
- $i=3$ : $x$ 前 3 位有 3 个 ‘1’（奇数）， $y_3=1$
- $i=4$ : $x$ 前 4 位有 3 个 ‘1’（奇数）， $y_4=1$
- $i=5$ : $x$ 前 5 位有 4 个 ‘1’（偶数）， $y_5=0$
  计算得 $y=10110$ ，与给定的 $y'$ 完全一致。
  结论： 翻转次数为 0。
样例 2
输入： $x'=11101, y'=10010$
根据 $x'$ 计算出的合法 $y$ 应为 $10110$ （见样例 1）。
对比给定的 $y'=10010$ ，只有第 3 位不同（ $y_3$ 应为 1，给定为 0）。
结论： 只需翻转 $y'$ 的第 3 位，总翻转次数为 1。
样例 3
输入： $x'=01100, y'=10110$
若要达成合法状态，一种最少翻转方案是：
1. 翻转 $x'$ 的第 1 位，使其变为 $11100$ 。
2. 此时合法的 $y$ 应为 $10111$ 。
3. 对比原 $y'=10110$ ，只需再翻转 $y'$ 的最后一位（第 5 位）。
  结论： 总共翻转了 2 次（ $x'$ 一次， $y'$ 一次）。

思路讲解

$y_i = c_i \bmod 2$ ，其中 $c_i$ 是 $x$ 前 $i$ 个字符中 1 的个数。注意到 $y_i \oplus y_{i-1} = x_i$ （定义 $y_0 = 0$ ）。也就是说， $x$ 完全由 $y$ 决定（反之亦然）。所以你实际上只需要确定一个最终的 $y$ （或 $x$ ），另一个就自动确定了。

（其实只要观察到了红字的这个约束，红字的这个东西，那么剩下来这个DP啊就非常容易了。）

vector<array<ll,2>> dp(N+2,{INF,INF});
dp[0][0]=0;
for (int i=1;i<=N;++i) {
    dp[i][1]=(Y[i]!=1)+min(dp[i-1][0]+(X[i]!=1),dp[i-1][1]+(X[i]!=0));
    dp[i][0]=(Y[i]!=0)+min(dp[i-1][0]+(X[i]!=0),dp[i-1][1]+(X[i]!=1));
}

AC代码

AC
https://codeforces.com/contest/2181/submission/362133326

源代码

/**
 * Problem: B. Battle of Arrays
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2181/problem/B
 * Created: 2026-02-09 20:45:55
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 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 debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\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 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,testcase;

/*
 *
 */

void Solve() {
    string sx,sy;
    cin>>sx>>sy;
    ll N=sx.size();
    vector<ll> X(N+2),Y(N+2);
    sx.insert(sx.begin(),'#');
    sy.insert(sy.begin(),'#');
    ll cnt=0;
    vector<ll> presum(N+2);
    bool ok=true;
    for (int i=1;i<=N;++i) {
        cnt+=sx[i]-'0';
        X[i]=sx[i]-'0';
        Y[i]=sy[i]-'0';
        presum[i]=cnt;
        if (presum[i]%2!=Y[i]) {
            ok=false;
        }
    }
    if (ok) {
        cout<<0<<"\n";
        return;
    }
    vector<array<ll,2>> dp(N+2,{INF,INF});
    dp[0][0]=0;
    for (int i=1;i<=N;++i) {
        dp[i][1]=(Y[i]!=1)+min(dp[i-1][0]+(X[i]!=1),dp[i-1][1]+(X[i]!=0));
        dp[i][0]=(Y[i]!=0)+min(dp[i-1][0]+(X[i]!=0),dp[i-1][1]+(X[i]!=1));
    }
    debug2d(dp);
    cout<<min(dp[N][0],dp[N][1])<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2181/submission/362133326

*/

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

AI 的提示

[1 tool called]
好的，你在 VP，我给你一些递进的提示，你可以根据需要看多少：
提示 1：观察 $y$ 和 $x$ 的关系
$y_i = c_i \bmod 2$ ，其中 $c_i$ 是 $x$ 前 $i$ 个字符中 1 的个数。注意到 $y_i \oplus y_{i-1} = x_i$ （定义 $y_0 = 0$ ）。也就是说， $x$ 完全由 $y$ 决定（反之亦然）。所以你实际上只需要确定一个最终的 $y$ （或 $x$ ），另一个就自动确定了。
提示 2：代价的刻画
假设你选定了最终的 $y$ ，那么 $x$ 就确定了（ $x_i = y_i \oplus y_{i-1}$ ）。翻转的总代价就是：

\sum_{i=1}^{n} [x_i \neq x'i] + \sum{i=1}^{n} [y_i \neq y'_i]

把 $x_i = y_i \oplus y_{i-1}$ 代入后，每个位置的代价只取决于 $y_{i-1}$ 和 $y_i$ 。试着把它写成关于相邻 $y$ 值的函数。
提示 3：DP 的思路
既然每一位的代价只依赖 $y_{i-1}$ 和 $y_i$ ，你可以用一个很简单的 DP：设 $dp_{i,v}$ 表示确定了 $y_1, y_2, \dots, y_i$ 且 $y_i = v$ （ $v \in \{0, 1\}$ ）时的最小总代价。转移时枚举 $y_i$ 的取值，计算当前位在 $x$ 和 $y$ 上分别需要翻转多少位即可。
这个 DP 是 $O(n)$ 的，完全够用。
祝 VP 顺利！

CF-1078-D. Table Cut（绷不住了，真是贪心了，贪了）

Posted on 2026-02-09 Edited on 2026-02-10

题目大意

给定一个大小为 $n \times m$ 的表格，其中每个单元格包含 $0$ 或 $1$ 。任务是通过一条从左上角到右下角的切割线将其分成两部分。切割线只能向右或向下走。

设 $a$ 为切割后表格一部分中的1的数量， $b$ 为表格另一部分中的1的数量。目标是最大化 $a \cdot b$ 的值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10^4$ )。随后是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ( $1 \leq n, m \leq 3 \cdot 10^{5}$ , $2 \leq n \cdot m \leq 3 \cdot 10^{5}$ ) — 表中的行数和列数。

接下来的 $n$ 行中，每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数对应值为 $a_{i, j}$ ( $0 \leq a_{i, j} \leq 1$ )。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $3 \cdot 10^{5}$ 。

输出

对于每个测试用例，在输出数据的第一行输出一个数字 - 乘积的最大值。

在第二行，输出一个由 $n$ 个字符 ‘D’ 和 $m$ 个字符 ‘R’ 组成的字符串，表示下一次切割的方向，其中 ‘D’ 表示向下切割，而 ‘R’ 表示向右切割。

30
RDRDRDRDDR
20
DRRDRDDDR
4
DRDRD

注意

这些图片展示了第一个和第二个测试用例的正确切割方式，从而实现产品的最大价值。

思路讲解

绷不住了，我想了半天的DP解法，结果和我讲，其实这道题目根本不用DP，就贪心啊，然后这个答案总归是最大的，就是把它尽量均匀的切分成两半，总是可以的。

就是形如上图这样子切分，可以证明啊，其实也不用证明了。你直接感觉你就知道把它们尽量均匀的切分成两半是非常可行的，是完全可行的。

    for (int x=1;x<=N;++x) {
        ll to_sum=sum+pre_sum[x][M];
// #ifdef LOCAL
//         debug(to_sum);
//         debug(sum);
// #endif
        if (to_sum>=half && !is_in) {
            ll bpy=1;
            is_in=true;
            for (ll y=M;y>=1;--y) {
                sum+=maze[x][y];
                if (sum==half) {
                    bpy=y;
                    break;
                }
            }
            for (int y=1;y<bpy;++y) {
                ans.push_back('R');
            }
            ans.push_back('D');
            for (int y=bpy;y<=M;++y) {
                ans.push_back('R');
            }
        }else {
            ans.push_back('D');
        }
        sum=to_sum;
    }

AC代码

https://codeforces.com/contest/2194/submission/362089758

源代码

/**
 * Problem: D. Table Cut
 * Contest: Codeforces Round 1078 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2194/problem/D
 * Created: 2026-02-09 14:03:01
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 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 debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\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 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,testcase;

/*
 *
 */

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<int>> maze(N+2,vector<int>(M+2));
    vector<vector<ll>> pre_sum(N+2,vector<ll>(M+2));
    ll sum1=0;
    for (int x=1;x<=N;++x) {
        for (int y=1;y<=M;++y) {
            cin>>maze[x][y];
            sum1+=maze[x][y];
        }
    }
    string ans;
    for (int x=1;x<=N;++x) {
        partial_sum(all(maze[x]),pre_sum[x].begin());
    }
    ll sum=0,half=sum1/2;
    bool is_in=false;
    for (int x=1;x<=N;++x) {
        ll to_sum=sum+pre_sum[x][M];
// #ifdef LOCAL
//         debug(to_sum);
//         debug(sum);
// #endif
        if (to_sum>=half && !is_in) {
            ll bpy=1;
            is_in=true;
            for (ll y=M;y>=1;--y) {
                sum+=maze[x][y];
                if (sum==half) {
                    bpy=y;
                    break;
                }
            }
            for (int y=1;y<bpy;++y) {
                ans.push_back('R');
            }
            ans.push_back('D');
            for (int y=bpy;y<=M;++y) {
                ans.push_back('R');
            }
        }else {
            ans.push_back('D');
        }
        sum=to_sum;
    }
    ll a=sum1/2,b=sum1-a;
    cout<<a*b<<"\n";
    cout<<ans<<"\n";
#ifdef LOCAL    // 校验器
    if (count(all(ans),'D')==N && count(all(ans),'R')==M) {

    }else {
        cout<<"WA\n";
        return;
    }
    ll col=0,row=0;
    ll a_num=0,b_num=0;
    for (auto ch:ans) {
        if (ch=='R') {
            ++col;
        }else {
            row++;
            a_num+=pre_sum[row][col];
            b_num+=pre_sum[row][M]-pre_sum[row][col];
        }
    }
    if (a_num*b_num==a*b) {

    }else {
        cout<<"WA\n";
    }
#endif

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2194/submission/362089758

DRDRRD

1
3 2
1 0
0 1
1 1

_______________[ Stress test, testcase 16 INPUT ]_______________
1
1 4
0 0 0 1

_______________[ Stress test, testcase 16 OUTPUT]_______________
0
DRRRRR
WA

*/

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

CF-1078-C. Secret message

Posted on 2026-02-08 Edited on 2026-02-12

题目大意

题目总结：秘密信息 (Secret message)

给定 $k$ 条长度均为 $n$ 的字符串（纸条）。你需要构造一个长度为 $n$ 的目标字符串 $S$ ，满足以下要求：

字符来源限制：对于 $S$ 中的每一个位置 $i$ （ $0 \le i < n$ ），该位置的字符必须是 $k$ 条纸条中第 $i$ 个位置出现的某一个字符。
最小化信息度：字符串 $S$ 的“信息度” $d$ 必须尽可能小。
- 信息度 $d$ 的定义：最小的正整数 $d$ ，使得 $S$ 可以由一个长度为 $d$ 的字符串 $t$ 连续重复多次构成（即 $S = t + t + \dots + t$ ）。这意味着 $d$ 必须是 $n$ 的约数。

样例解释

样例 1

输入： $n=3, k=2$ ，纸条为 abc 和 baa

位置 0 可选字符：{a, b}
位置 1 可选字符：{b, a}
位置 2 可选字符：{c, a}
目标：尝试最小信息度 $d=1$ （即 $S$ 是由同一个字符重复 3 次）。
检查：若 $S = \text{"aaa"}$ ，第 0 位 ‘a’（在第一条纸条）、第 1 位 ‘a’（在第二条纸条）、第 2 位 ‘a’（在第二条纸条）均存在。因此 $d=1$ 可行。
输出：aaa

样例 2

输入： $n=9, k=2$ ，纸条为 iiinnnfff 和 nnfiffinn

尝试 $d=1$ ：无法找到一个字符在所有 9 个位置都出现。
尝试 $d=3$ ：寻找长度为 3 的字符串 $t$ ，使得 $S = t + t + t$ 满足条件。
检查：若 $t = \text{"inf"}$ ，则 $S = \text{"infinfinf"}$ 。
- 第 0, 3, 6 位：‘i’ 分别在纸条 1, 2, 2 中出现。
- 第 1, 4, 7 位：‘n’ 分别在纸条 1, 1, 1 中出现。
- 第 2, 5, 8 位：‘f’ 分别在纸条 2, 1, 2 中出现。
输出：infinfinf

样例 3

输入： $n=4, k=2$ ，纸条为 acbd 和 bdac

尝试 $d=1$ ：不满足。
尝试 $d=2$ ：寻找长度为 2 的字符串 $t$ ，使得 $S = t + t$ 满足条件。
检查：若 $t = \text{"ac"}$ ，则 $S = \text{"acac"}$ 。
- 位置 0 (‘a’)：在第一条。
- 位置 1 (‘c’)：在第二条。
- 位置 2 (‘a’)：在第二条。
- 位置 3 (‘c’)：在第一条。
输出：acac

思路讲解

其实说白了这道题目就是想让你找一个字符串，一个字符串集的这个最小循环子串。啊，也就是找其最小循环节，但是其最小循环节呢是严格的这个最小循环节长度（即题目中的信息度），就是它不能够呃就是它不能够比如说呃roate，不能够呃循环移动的那种循环节，它是比较严格的那种循环节。

auto check=[&](ll len,bool gen_ans=false) -> bool {
  // 先生成一个长度为 len 的，每一位他能够所选的这个字符的集合(可以使用 Vector 套 bitset 表示.)。
    vector<vector<int>> bi=gen_bi(0,len);
    // 然后这里是不断的生成，就是继续生成这样子的集合，进行与运算的操作。
    for (ll i=len;i<N;i+=len) {
        bi=fac_and(bi,gen_bi(i,len));
    }
    for (int i=0;i<len;++i) {
        bool ok=false;
        for (int j=0;j<26;++j) {
            if (bi[i][j]) {
                if (gen_ans) {
                    ans.push_back('a'+j);
                }
                ok=true;
                break;
            }
        }
        if (!ok) {
            return false;
        }
    }
    if (gen_ans) {
        string back_up=ans;
        for (int i=2;i<=N/len;++i) {
            ans+=back_up;
        }
    }
    return true;
};

AC代码

https://codeforces.com/contest/2194/submission/361977470

源代码

/**
 * Problem: C. Secret message
 * Contest: Codeforces Round 1078 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2194/problem/C
 * Created: 2026-02-08 17:13:24
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 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,testcase;

/*
 *
 */

void Solve() {
    ll N,K;
    cin >> N >> K;
    vector<string> A(K);
    vector<vector<int>> i_ch_has(N,vector<int>(26));
    for (int i=0;i<K;++i) {
        cin>>A[i];
        for (int j=0;j<N;++j) {
            i_ch_has[j][A[i][j]-'a']=1;
        }
    }
    vector<ll> factor_n;
    for (int i=1;i<=N;++i) {
        if (N%i==0) {
            factor_n.push_back(i);
        }
    }
    string ans;
    auto gen_bi=[&](ll idx,ll len) -> vector<vector<int>> {
        vector<vector<int>> res(len,vector<int>(26));
        for (ll i=idx;i<idx+len;++i) {
            for (int j=0;j<26;++j) {
                res[i-idx][j]|=i_ch_has[i][j];
            }
        }
        return res;
    };
    auto fac_and=[](vector<vector<int>> a, const vector<vector<int>> &b)->vector<vector<int>>  {
        for (int i=0;i<a.size();++i) {
            for (int j=0;j<a[i].size();++j) {
                a[i][j]&=b[i][j];
            }
        }
        return a;
    };
    auto check=[&](ll len,bool gen_ans=false) -> bool {
        vector<vector<int>> bi=gen_bi(0,len);
        for (ll i=len;i<N;i+=len) {
            bi=fac_and(bi,gen_bi(i,len));
        }
        for (int i=0;i<len;++i) {
            bool ok=false;
            for (int j=0;j<26;++j) {
                if (bi[i][j]) {
                    if (gen_ans) {
                        ans.push_back('a'+j);
                    }
                    ok=true;
                    break;
                }
            }
            if (!ok) {
                return false;
            }
        }
        if (gen_ans) {
            string back_up=ans;
            for (int i=2;i<=N/len;++i) {
                ans+=back_up;
            }
        }
        return true;
    };
    for (auto fac:factor_n) {
        if (check(fac)) {
            check(fac,true);
            break;
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
1
9 2
iiinnnfff
nnfiffinn

*/