Znzryb's Blog

如何开大栈空间

Posted on 2026-03-29 Edited on 2026-04-06

杭电 OJ 暂不支持调整栈空间大小。如果使用 G++ 提交代码，并且代码中含有递归，递归层数较深，会返回 Runtime Error (STACK_OVERFLOW)。添加如下代码可以开大栈空间：

int main() {
    int size(256<<20);  // 256M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    // 关同步流代码
    // 主程序代码
    exit(0); // 一定要添加这一条，不然会返回 Runtime Error (ACCESS_VIOLATION)
}

2026 杭电春季联赛 2——1002-庭扫落樱（二分图最大匹配）（最小边覆盖和最大匹配之间的关系）

Posted on 2026-03-29 Edited on 2026-04-06

题目大意

题目描述

给定二维平面第一象限上的 $n$ 个弹幕发射器。第 $i$ 个发射器位于坐标 $(x_i, y_i)$ ，并向四个方向之一发射一条射线（激光）：

$d_i = 0$ ：向上发射
$d_i = 1$ ：向右发射
$d_i = 2$ ：向下发射
$d_i = 3$ ：向左发射

射线的照明路径包含发射器本身所在的位置。题目保证任意两个发射器不会同时在对方的照明路径上。

现在可以在平面上放置障碍物（允许放置在发射器所在的坐标上），只要障碍物位于某条射线上，就能阻挡该射线的照射。求最少需要放置多少个障碍物，才能使得所有 $n$ 个发射器的照射路径上都至少包含一个障碍物。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 100$ ），表示测试用例的数量。

每个测试用例第一行包含一个整数 $n$ （ $1 \le n \le 300$ ），表示发射器的数量。
接下来 $n$ 行，每行包含三个整数 $x_i, y_i, d_i$ （ $1 \le x_i, y_i \le 10^9$ ， $d_i \in \{0, 1, 2, 3\}$ ），表示发射器的坐标与发射方向。

保证所有测试用例中 $n$ 的总和不超过 $3000$ 。

输出格式

对于每个测试用例，输出一行一个整数，表示最少需要放置的障碍物数量。

样例输入

样例输出

1
2

3
1

样例解释

在第一个测试用例中，有 $6$ 个发射器。一种最优方案是放置 $3$ 个障碍物，具体位置如下：

在坐标 $(5, 7)$ 处放置一个障碍物：该点覆盖了第 $1$ 束（从 $(5,5)$ 向上）、第 $2$ 束（从 $(3,7)$ 向右）以及第 $5$ 束（从 $(5,2)$ 向上）激光。
在坐标 $(9, 1)$ 处放置一个障碍物：该点覆盖了第 $3$ 束（从 $(9,9)$ 向下）以及第 $4$ 束（从 $(9,1)$ 向左）激光。
在坐标 $(-2025, 20)$ 处放置一个障碍物：该点覆盖了第 $6$ 束（从 $(1,20)$ 向左）激光。

该方案共使用了 $3$ 个障碍物，且可以证明不存在比 $3$ 更少的放置方案。

思路讲解

一种错误的图论建模方式是把激光当作左边的点，把这个障碍物当成右边的点，但是这样子建图是做不出来这道题目的，因为我们不是要让激光和障碍物一一匹配，这个非常容易就能做到。

P3386 【模板】二分图最大匹配

那么要做这道题目，最重要的就是我们要把障碍物看成连边，左边的点指的是这个方向为上下的点，右边的点指的是这个方向为左右的点。

void Solve() {
    ll N;
    cin >> N;
    vector<X_y_d> xyd_ls(N);
    for (int i = 0; i < N; ++i) {
        cin >> xyd_ls[i].x >> xyd_ls[i].y >> xyd_ls[i].d;
    }
    xyd_ls = unique_xyd_ls(xyd_ls);
    auto g = build_graph(xyd_ls);
    Bi_graph_matcher matcher(g,SZ(xyd_ls));
    ll mx_match = matcher.mx_match();
    ll ans = (SZ(xyd_ls) - 2 * mx_match) + mx_match;
    cout << ans << "\n";
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=18859

源代码

// teamname: Gospel_rock
/**
 * Problem: 庭扫落樱
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1198&pid=1002
 * Created: 2026-03-29 18:54:03
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>

#include <utility>
#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 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 X_y_d {
    ll x;
    ll y;
    ll d;
};

struct X_y {
    ll x;
    ll y;

    bool operator<(const X_y &o) const {
        if (x != o.x) return x < o.x;
        return y < o.y;
    }
};

bool is_two_laser_intersect(X_y_d a, X_y_d b) {
    if ((a.d==0 || a.d==2) && (b.d==1 || b.d==3)) {
        X_y node = {a.x, b.y};
        if (a.d == 0) {
            if (node.y < a.y) {
                return false;
            }
        }
        if (a.d == 2) {
            if (node.y > a.y) {
                return false;
            }
        }
        if (b.d == 1) {
            if (node.x < b.x) {
                return false;
            }
        }
        if (b.d == 3) {
            if (node.x > b.x) {
                return false;
            }
        }
        return true;
    }else {
        return false;
    }
}

auto unique_xyd_ls_detail(const vector<X_y_d> &xyd_ls, ll offset) {
    vector<X_y_d> res;
    res.reserve(SZ(xyd_ls));
    map<ll, ll> mp1, mp3;
    for (auto [x,y,d]: xyd_ls) {
        if (offset) {
            swap(x, y);
        }
        if (d == 0 + offset) {
            if (!mp1.contains(x)) {
                mp1[x] = y;
            } else {
                mp1[x] = max(mp1[x], y);
            }
        } else if (d == 2 + offset) {
            if (!mp3.contains(x)) {
                mp3[x] = y;
            } else {
                mp3[x] = min(mp3[x], y);
            }
        }
    }
    for (auto [x_,y_]: mp1) {
        auto [x,y] = make_tuple(x_, y_);
        if (offset) swap(x, y);
        res.push_back({x, y, 0 + offset});
    }
    for (auto [x_,y_]: mp3) {
        auto [x,y] = make_tuple(x_, y_);
        if (offset) swap(x, y);
        res.push_back({x, y, 2 + offset});
    }
    return res;
}

auto unique_xyd_ls(const vector<X_y_d> &xyd_ls) {
    auto res1 = unique_xyd_ls_detail(xyd_ls, 0);
    auto res2 = unique_xyd_ls_detail(xyd_ls, 1);
    res1.insert(res1.end(), res2.begin(), res2.end());
#ifdef LOCAL
    cerr << "xyd_ls:\n";
    for (int i = 0; i < SZ(xyd_ls); ++i) {
        cerr << xyd_ls[i].x << " " << xyd_ls[i].y << " " << xyd_ls[i].d << "\n";
    }
#endif
    return res1;
}


// 注意，二分图构建的是有向图
auto build_graph(const vector<X_y_d> &xyd_ls) {
    ll idx = SZ(xyd_ls);
    map<X_y, ll> mp;
    vector<vector<ll> > g(SZ(xyd_ls) + 2);
    for (int i = 0; i < SZ(xyd_ls); ++i) {
        for (int j = i + 1; j < SZ(xyd_ls); ++j) {
            if (xyd_ls[i].d == 0 || xyd_ls[i].d == 2) {
                auto flag = is_two_laser_intersect(xyd_ls[i], xyd_ls[j]);
                if (!flag) {
                    continue;
                }
                g[i].push_back(j);
            }
        }
    }
    // #ifdef LOCAL
    //     debug2d(g);
    // #endif
    return g;
}

struct Bi_graph_matcher {
    vector<vector<ll> > g;
    vector<char> vis;
    vector<ll> match;
    ll left_cnt;

    Bi_graph_matcher(vector<vector<ll> > _g, ll _left_cnt) : g(std::move(_g)), vis(SZ(g) + 2), match(SZ(g) + 2, -1),
                                                             left_cnt(_left_cnt) {
    }

    bool find(ll u) {
        for (auto to: g[u]) {
            if (vis[to]) {
                continue;
            }
            vis[to] = true;
            // 如果 v 还没有匹配，或者 v 原本匹配的人能找到新的匹配（腾出位置）
            if (match[to] == -1 || find(match[to])) {
                match[to] = u;
                return true;
            }
        }
        return false;
    }

    ll mx_match() {
        ll ans = 0;
        for (int i = 0; i <= left_cnt; ++i) {
            vis.assign(SZ(g) + 2, 0);
            if (find(i)) {
                ++ans;
            }
        }
        return ans;
    }
};


void Solve() {
    ll N;
    cin >> N;
    vector<X_y_d> xyd_ls(N);
    for (int i = 0; i < N; ++i) {
        cin >> xyd_ls[i].x >> xyd_ls[i].y >> xyd_ls[i].d;
    }
    xyd_ls = unique_xyd_ls(xyd_ls);
    auto g = build_graph(xyd_ls);
    Bi_graph_matcher matcher(g,SZ(xyd_ls));
    ll mx_match = matcher.mx_match();
    ll ans = (SZ(xyd_ls) - 2 * mx_match) + mx_match;
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
    // auto start = std::chrono::high_resolution_clock::now();
#endif
    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();

    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=18859


pair<bool, X_y> intersect_two_laser(X_y_d a, X_y_d b) {
    // pair<bool,  > res;
    if (a.d == b.d) return {false, {}};
    if (a.d == 0 && b.d == 2) return {false, {}};
    if (a.d == 1 && b.d == 3) return {false, {}};
    if ((a.d==0 && b.d==1)) {

    }
    X_y node = {a.x, b.y};
    if (a.d == 0) {
        if (node.y < a.y) {
            return {false, {}};
        }
    }
    if (a.d == 2) {
        if (node.y > a.y) {
            return {false, {}};
        }
    }
    if (a.d == 1) {
        if (node.x < a.x) {
            return {false, {}};
        }
    }
    if (a.d == 3) {
        if (node.x > a.x) {
            return {false, {}};
        }
    }
    return {true, node};
}

// 注意，二分图构建的是有向图
auto build_graph(const vector<X_y_d> &xyd_ls) {
    ll idx = SZ(xyd_ls);
    map<X_y, ll> mp;
    vector<vector<ll> > g(SZ(xyd_ls) + 2);
    g.reserve(4 * SZ(xyd_ls));
    for (int i = 0; i < SZ(xyd_ls); ++i) {
        X_y xy = {xyd_ls[i].x, xyd_ls[i].y};
        ll node;
        if (mp.contains(xy)) {
            node = mp[xy];
        } else {
            ++idx;
            g.push_back({});
            node = idx;
            mp[xy] = idx;
        }
        g[i].push_back(node);
        // g[node].push_back(i);
    }
    for (int i = 0; i < SZ(xyd_ls); ++i) {
        for (int j = i + 1; j < SZ(xyd_ls); ++j) {
            auto [flag,xy] = intersect_two_laser(xyd_ls[i], xyd_ls[j]);
            if (!flag) {
                continue;
            }
            ll node;
            if (mp.contains(xy)) {
                node = mp[xy];
            } else {
                ++idx;
                g.push_back({});
                node = idx;
                mp[xy] = idx;
            }
            g[i].push_back(node);
            g[j].push_back(node);
            // g[node].push_back(i);
            // g[node].push_back(j);
        }
    }
#ifdef LOCAL
    debug2d(g);
#endif
    return g;
}
*/

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

最好显式忽略这个其他情况：

使用 offset 进行 swap，最后也要 swap 回来。

将哨兵值设置为 -1，可以避免 0-based 造成问题。

Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)——CF-2211-B. Mickey Mouse Constructive

Posted on 2026-03-29 Edited on 2026-04-06

题目大意

题目描述

给定一个数组 $a$ ，定义 $f(a)$ 为将 $a$ 划分成一个或多个连续子数组的方案数，需满足以下条件：

每个元素恰好属于一个子数组。
所有子数组的元素和都相等。

例如，对于 $a=[1,1]$ ， $f(a)=2$ ，因为有两种合法的划分方案：

$[1,1]$ ，此时唯一的子数组和为 $2$ 。
$[1]+[1]$ ，此时两个子数组和均为 $1$ 。

给定两个整数 $x$ 和 $y$ 。你需要构造一个长度为 $x+y$ 的数组 $a$ ，其中包含 $x$ 个 $1$ 和 $y$ 个 $-1$ 。
你需要求出在所有合法的数组 $a$ 中， $f(a)$ 的最小值，并将该最小值对 $676767677$ 取模后输出。同时，你需要输出一个能达到该最小值的数组构造方案。

注意：你需要最小化的是 $f(a)$ 本身，然后将这个最小值对 $676767677$ 取模，而不是去最小化 $f(a) \bmod 676767677$ 的结果。

输入格式

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ )，表示测试用例的数量。

接下来每个测试用例包含一行，包含两个整数 $x$ 和 $y$ ( $0 \le x, y \le 2 \cdot 10^5$ )，保证 $x+y \ge 1$ 。

保证所有测试用例中 $x$ 的总和与 $y$ 的总和均不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出两行：
第一行输出 $f(a)$ 的最小值对 $676767677$ 取模的结果。
第二行输出一个达到该最小值的数组 $a$ 的元素（用空格分隔）。

样例输入

样例输出

2
1 1
1
1 -1
1
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1
2
-1 -1 -1 1

样例解释

在第一个测试用例中， $x=2$ 且 $y=0$ 。唯一可能的数组是 $a=[1,1]$ ，正如题目描述中所解释的，此时 $f(a)=2$ 。

在第二个测试用例中， $x=1$ 且 $y=1$ 。一个能使 $f(a)$ 最小化的合法数组是 $a=[1,-1]$ 。此时 $f(a)=1$ ，因为唯一能使所有子数组和相等的划分方式就是不进行任何分割（即 $[[1,-1]]$ ，子数组和为 $0$ ）。

思路讲解

void Solve() {
    ll X, Y;
    cin >> X >> Y;
    vector<ll> A(X + Y + 2);
    for (int i = 1; i <= X; ++i) {
        // cout << 1 << " ";
        A[i] = 1;
    }
    for (int i = 1; i <= Y; ++i) {
        // cout << -1 << " ";
        A[i + X] = -1;
    }
    ll s = llabs(X - Y);
    ll ans = 1;
    // 这里要采用求约数个数的方法
    if (s != 0) {
        ans = 0;
        for (ll d = 1; d * d <= s; ++d) {
            if (s % d == 0) {
                ++ans;
                if (d * d != s) ++ans;
            }
        }
    }
    cout << ans << "\n";
    for (int i = 1; i <= X + Y; ++i) {
        cout << A[i] << " ";
    }
    cout << "\n";
    // mod
}

AC代码

https://codeforces.com/contest/2211/submission/368623804

源代码

// teamname: Gospel_rock
/**
 * Problem: B. Mickey Mouse Constructive
 * Contest: Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2211/problem/B
 * Created: 2026-03-28 22:48:14
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * 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 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 = 676767677;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

void Solve() {
    ll X, Y;
    cin >> X >> Y;
    vector<ll> A(X + Y + 2);
    for (int i = 1; i <= X; ++i) {
        // cout << 1 << " ";
        A[i] = 1;
    }
    for (int i = 1; i <= Y; ++i) {
        // cout << -1 << " ";
        A[i + X] = -1;
    }
//     ll N = X + Y;
//     ll sum = X - Y;
//     ll cur = 0;
//     ll ans = 0;
//     for (int i = 1; i <= N; ++i) {
//         cur += A[i];
//         ll rem = sum - cur;
// #ifdef LOCAL
//         debug(cur);
//         debug(rem);
//         cend;
// #endif
//         if (cur == 0) {
//             // assert(0);
//             if (cur == rem) {
//                 ++ans;
//                 ans %= mod;
//             }
//             continue;
//         }
//         if ((rem * cur) >= 0 && rem % cur == 0) {
//             ++ans;
//             ans %= mod;
//         }
//     }
    ll s = llabs(X - Y);
    ll ans = 1;
    if (s != 0) {
        ans = 0;
        for (ll d = 1; d * d <= s; ++d) {
            if (s % d == 0) {
                ++ans;
                if (d * d != s) ++ans;
            }
        }
    }
    cout << ans << "\n";
    for (int i = 1; i <= X + Y; ++i) {
        cout << A[i] << " ";
    }
    cout << "\n";
    // mod
}

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;
}

/*



// if (Y != 0) {
    //     ll N = X + Y;
    //     ll sum = X;
    //     ll ans = 1;
    //     for (ll i = 1; i <= Y; ++i) {
    //         sum--;
    //         ll rem = Y - i;
    //         if (sum < 0) {
    //             if (rem % abs(sum) == 0 && rem != 0) {
    //                 ans++;
    //                 ans %= mod;
    //             }
    //         }
    //     }
    //     cout << ans << "\n";
    // } else {
    //     ll ans = 1;
    //     ll sum = 0;
    //     for (ll i = 1; i <= X; ++i) {
    //         sum++;
    //         ll rem = X - i;
    //         if (rem % abs(sum) == 0 && rem != 0) {
    //             ans++;
    //             ans %= mod;
    //         }
    //     }
    //     cout << ans << "\n";
    // }
*/

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

Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)——CF-2211-C2. Equal Multisets (Hard Version)（注意对子串变化的注意，虽然这个还是很容易注意到的）

Posted on 2026-03-28 Edited on 2026-04-06

题目大意

题目描述
给定一个长度为 $n$ 的数组 $a$ 和一个参数 $k$ 。如果一个数组 $b$ 满足以下条件，则称其为“很酷的”：
对于从 $k$ 到 $n$ 的每个下标 $i$ ，子数组 $[a_{i-k+1}, a_{i-k+2}, \dots, a_i]$ 都是子数组 $[b_{i-k+1}, b_{i-k+2}, \dots, b_i]$ 的重新排列（即两个长度为 $k$ 的滑动窗口构成的多重集相同）。

现在给定数组 $a$ 和数组 $b$ 。数组 $a$ 仅包含 $1$ 到 $n$ 之间的整数；数组 $b$ 包含 $1$ 到 $n$ 之间的整数以及 $-1$ 。
请判断是否可以通过将 $b$ 中所有的 $-1$ 替换为 $1$ 到 $n$ 之间的任意整数，使得最终的数组 $b$ 满足上述“很酷的”条件。

输入格式
第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$ （ $1 \le k \le n \le 2 \cdot 10^5$ ）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $1 \le a_i \le n$ ）。
第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ （ $1 \le b_i \le n$ 或 $b_i = -1$ ）。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

输出格式
对于每个测试用例，如果可以构造出满足条件的数组 $b$ ，输出 YES，否则输出 NO。

样例

Input
5
5 5
1 2 3 4 5
3 1 5 2 4
5 2
1 2 1 2 1
2 -1 -1 -1 -1
6 1
5 6 2 2 4 3
5 -1 -1 2 -1 3
2 1
1 2
2 -1
6 4
1 2 3 4 1 2
2 -1 3 -1 4 -1

Output
YES
YES
YES
NO
NO

样例解释第一个测试用例： $k=5$ 。唯一的长度为 $5$ 的子数组是整个数组本身。给定的 $b$ 已经是 $a$ 的一个重新排列，且没有 $-1$ ，满足条件，答案为 YES。
第二个测试用例： $k=2$ 。我们可以将所有的 $-1$ 替换，使得 $b = [2, 1, 2, 1, 2]$ 。此时在 $a$ 和 $b$ 中，每一个长度为 $2$ 的窗口要么是 $[1, 2]$ 要么是 $[2, 1]$ ，它们互为重新排列，因此答案为 YES。
第四个测试用例： $k=1$ 。长度为 $1$ 的窗口意味着对应位置的元素必须完全相同。因为已知 $a_1 = 1$ 而 $b_1 = 2$ ，两者不相等，所以无法满足条件，答案为 NO。

思路讲解

void Solve() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> B[i];

    // target: 第一个窗口 a[1..K] 的多重集，b[1..K] 也必须是它的一个排列
    map<ll, ll> target;
    for (int i = 1; i <= K; ++i) target[A[i]]++;

    // free_count: 第一个窗口中，值完全自由（可任意选取）的位置数
    int free_count = 0;

    // 按模 K 将位置分成 K 条链：链 r 包含位置 r, r+K, r+2K, ...
    // 每条链恰好有一个位置落在第一个窗口（即位置 r 本身）
    //
    // 关键推导：窗口从 [i, i+K-1] 滑到 [i+1, i+K] 时，
    //   需要 -{b_i} + {b_{i+K}} = -{a_i} + {a_{i+K}}
    // 因此：
    //   - 若 a_i ≠ a_{i+K}：必须 b_i = a_i 且 b_{i+K} = a_{i+K}
    //   - 若 a_i = a_{i+K}：只需 b_i = b_{i+K}（不一定等于 a）
    //
    // 对一条链来说：
    //   - 若链中存在相邻位置 a 值不同（"固定链"），则整条链的 b 值全部被唯一确定为 a 值
    //   - 若链中所有 a 值全相同（"自由链"），则链上所有 b 值必须相等，但具体取什么值是灵活的

    for (int r = 1; r <= K; ++r) {
        // 检查链 r 是否所有 a 值都相同
        bool all_equal = true;
        for (int p = r; p + K <= N; p += K) {
            if (A[p] != A[p + K]) { all_equal = false; break; }
        }

        if (!all_equal) {
            // 固定链：链上每个位置 b[p] 必须等于 a[p]
            // 检查已给定的 b 值是否与 a 一致
            for (int p = r; p <= N; p += K) {
                if (B[p] != -1 && B[p] != A[p]) {
                    cout << "NO\n"; return;
                }
            }
            // 位置 r（第一个窗口中的位置）的 b 值确定为 a[r]，从 target 中扣除
            target[A[r]]--;
        } else {
            // 自由链：链上所有 b 值必须相等
            // 检查所有已给定的 b 值是否互相一致
            ll forced = -1;
            for (int p = r; p <= N; p += K) {
                if (B[p] != -1) {
                    if (forced == -1) forced = B[p];       // 第一个给定值，记录
                    else if (forced != B[p]) {              // 与之前的给定值矛盾
                        cout << "NO\n"; return;
                    }
                }
            }
            if (forced != -1) target[forced]--;  // 链的值已确定，从 target 扣除
            else free_count++;                    // 链的值完全自由，待分配
        }
    }

    // 最终检查：target 中剩余的值（还没被匹配的）必须恰好分配给 free_count 个自由位置
    // 且不能有任何值被"过度消耗"（计数变负）
    ll remaining = 0;
    for (auto& [v, cnt] : target) {
        if (cnt < 0) { cout << "NO\n"; return; }
        remaining += cnt;
    }
    // 剩余的值刚好够填满所有自由位置 → YES，否则 → NO
    cout << (remaining == free_count ? "YES" : "NO") << "\n";
}

AC代码

源代码

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

Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)——CF-2211-D. AND-array

Posted on 2026-03-28 Edited on 2026-04-06

题目大意

题目描述

对于一个长度为 $n$ 的未知序列 $a$ ，定义其 AND-数组 $f(a)$ 如下：

$f(a)k = \sum{1 \le i_1 < i_2 < \dots < i_k \le n} a_{i_1} \mathbin{\&} a_{i_2} \mathbin{\&} \dots \mathbin{\&} a_{i_k}$

其中 $1 \le k \le n$ ， $\mathbin{\&}$ 表示按位与操作。换句话说， $f(a)_k$ 是序列 $a$ 中所有长度为 $k$ 的子序列的按位与结果之和。

现在给定一个长度为 $n$ 的序列 $b$ ，满足对于所有的 $1 \le i \le n$ ，都有 $b_i \equiv f(a)_i \pmod{10^9+7}$ 。

请根据给定的序列 $b$ ，构造并输出任意一个满足条件的序列 $a$ 。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。

每个测试用例包含两行：
第一行包含一个整数 $n$ （ $1 \le n \le 10^5$ ），表示序列 $a$ 和 $b$ 的长度。
第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ （ $0 \le b_i < 10^9+7$ ），表示序列 $b$ 。

保证存在长度为 $n$ 且满足 $0 \le a_i < 2^{29}$ 的序列 $a$ 使得条件成立。
保证所有测试用例中 $n$ 的总和不超过 $10^5$ 。

输出格式

对于每个测试用例，输出 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $0 \le a_i < 2^{29}$ ），表示重构出的序列 $a$ 。如果有多个满足条件的序列，输出任意一个即可。

样例输入

3
3
0 0 0
5
22 24 10 1 0
10
130 585 1560 2730 3276 2730 1560 585 130 13

样例输出

1
2
3

0 0 0
5 3 6 1 7
13 13 13 13 13 13 13 13 13 13

样例解释

在第二个样例中，若构造的序列 $a = [5, 3, 6, 1, 7]$ ，其 $f(a)_4$ 的值为：
$(a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} a_4) + (a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} a_5) + (a_1 \mathbin{\&} a_2 \mathbin{\&} a_4 \mathbin{\&} a_5) + (a_1 \mathbin{\&} a_3 \mathbin{\&} a_4 \mathbin{\&} a_5) + (a_2 \mathbin{\&} a_3 \mathbin{\&} a_4 \mathbin{\&} a_5) = 0 + 0 + 1 + 0 + 0 = 1$ 。
且 $f(a)_1 = a_1 + a_2 + a_3 + a_4 + a_5 = 22$ 。可以证明对于所有 $1 \le i \le 5$ 均有 $f(a)_i = b_i$ ，因此 $a = [5, 3, 6, 1, 7]$ 是一个合法的解。

思路讲解

AC代码

源代码