2025 多边形 · 方案一枚举所有子集

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1092 字

每个子集算一遍总和与最大值

2025
搜索

正文

// CSP-J 2025 复赛 T4 · 多边形
// 原题：https://oj.yecheng.tv/p/CSP2025JD
// 题意：n 根木棍，选若干根（至少 3 根）首尾相连拼多边形。
// 能拼成多边形当且仅当「长度之和 > 最长那根的 2 倍」。
// 问有多少种选法（按下标集合区分），答案对 998244353 取模。
//
// 方案一 · 枚举所有子集（直观，只能过 n 很小的数据）
// n 根木棍每根有选和不选两种可能，一共 2^n 种子集。
// 用一个二进制数 mask 表示一种选法，第 i 位是 1 就表示选第 i 根，
// 对每个 mask 数出根数、总和与最大值，满足条件就给答案加一。
// 2^20 大约是 100 万，还能跑；n 到 5000 就完全不行了 —— 满分请看法二。

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

const int MOD = 998244353;

int main() {
    freopen("polygon.in", "r", stdin);
    freopen("polygon.out", "w", stdout);

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

    long long ans = 0;
    int total = 1 << n;
    for (int mask = 1; mask < total; mask++) {
        int cnt = 0;
        int mx = 0;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                cnt++;
                sum += a[i];
                if (a[i] > mx) mx = a[i];
            }
        }
        if (cnt >= 3 && sum > 2LL * mx) ans = (ans + 1) % MOD;
    }
    cout << ans << "\n";
    return 0;
}

2025 多边形 · 方案一 枚举所有子集

正文

CSP-J 标程 · 复赛真题的其它内容

2025 多边形 · 方案一枚举所有子集