[CSP-J 2025] 多边形 / polygon 题解记录

题意

其实很简单不要被题目长度吓到,就是给你n个数让你选出至少三个数,并且这些数的和>这些数最大值的两倍

思路

这题思路其实你理解了的话就不难 ,但有点难想

看数据范围,对于所有数据n=5000,显然枚举子集的办法根本不行,但我们可以转变一下想法,我们只枚举他的最大值,然后根据他的最大值求出以该数为最大值符合条件的个数可不可呢,但是又有个问题我们怎么求满足条件的数呢? 首先这个数是最大值,那所有其他能选的数都一定<=他,那也就是我们可以给数组排个序,k=1,到n,然后对于每个a[k]就是最大值,选的那些数就从他前面选,但千万不要觉得是枚举的来选,复杂度1秒是承受不不住的,这个时候要聪明一点,还记得前面说到子集吗,我问你1-k个数每个数可选可不选有多少种选择方案?是不是

2^k

种,那我们就可以用一个数组叫pow2[i]来表示1~i的子集总数即pow[i]=pow[i-1]*2%mod即可,并且a[k]是一定要包含的,所以a[k]不参与决策(a[k]一定选)。那我再问你,选择的那些数组合出来的和是多少一定不可以满足条件?肯定是<=a[k]啊是吧,因为这样选出来的那些数+a[k]就<=1-k的最大值的两倍了,是吧,那我们就需要一个数组记录当前的数的所可能的和(1-5000)每个数字有多少种合成方法,注意,这里的所有不包括a[k],因为前面说过了a[k]作为最大值所以不参与决策,所以算的时候不可以算进a[k]。

ok,那剩下的就超级简单了,我们用一个sum = 一到k-1这些数的组成1~a[k]的总方法,那此时sum是不可行的方案总数是吧,那我们怎么知道总方案数呢,其实就是前面说的子集就是总方案数,那合规的就是pow2[k-1]-sum,至于为啥是k-1自己想下,前面说过

AC代码

CPP

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5007, mod = 998244353;
// pow2[i]是前i个数的总共的子集数,f[i]是当前的数能组成i有多少种方法
long long pow2[N], f[N], a[N];
int n;
int main()
{
    pow2[0] = 1;
    pow2[1] = 2;
    cin >> n;
    cin >> a[1];
    for (int i = 2; i <= n; i++)
    {
        cin >> a[i];
        pow2[i] = pow2[i - 1] * 2 % mod;
    }
    sort(a + 1, a + 1 + n);
    f[0] = 1;
    long long ans = 0;
    for (int k = 1; k <= n; k++)
    {
        long long sum = 0;
        for (int i = 0; i <= a[k]; i++)
        {
            sum =(sum+ f[i])%mod;
        }
        long long sh = (pow2[k - 1] - sum + mod) % mod;
        ans += (sh % mod);
        for (int i = 5000; i >= a[k]; i--)
        {
            f[i] = (f[i] + f[i - a[k]]) % mod;
        }
    }
    cout << ans % mod;
    return 0;
}

~~因为前面讲的太详细了就不加注释了哈~~

[CSP-J 2025] 多边形 / polygon 题解记录

文章操作

题意

思路

AC代码

相关推荐

评论

[CSP-J 2025] 多边形 / polygon 题解记录