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

题目大意

题目描述

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

1. 每个元素恰好属于一个子数组。

2. 所有子数组的元素和都相等。

例如，对于 $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$ 的元素（用空格分隔）。

样例输入

4
2 0
1 1
6 7
1 3

样例输出

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

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……）