专栏文章

题解：P14360 [CSP-J 2025] 多边形 / polygon（民间数据）

HHim_shu
P14360题解参与者 14已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@minfh8gt
此快照首次捕获于
2025/12/02 01:33
3 个月前
此快照最后确认于
2025/12/02 01:33
3 个月前
查看原文

背景

考场应该切了，44 题总用时 3030 分钟。

题意

给你 nn 个木棍，求出可以拼出的多边形数？

分析

符合条件要满足 ∑i=1mli>2×max⁡i=1mli\sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i。
不妨两边都减去 max⁡i=1mli\max_{i=1}^{m} l_i。
变成 ∑i=1mli−max⁡i=1mli>max⁡i=1mli\sum_{i=1}^{m} l_i -\max_{i=1}^{m} l_i> \max_{i=1}^{m} l_i。
这个是不是更加熟悉了。
注意到，排序就可以解决最大值的问题。
那么问题就变成了，对于每一个 ii，求前面大于 aia_i 的方案数。
明显背包版题，只是注意到 ∑i=1nai\sum_{i=1}^{n} a_i 很大，直接做会超时加超空间。
但我们只要求大于 aia_i 的方案数，而且 ai≤5000a_i \le 5000，那么把 50015001 到 ∑i=1nai\sum_{i=1}^{n} a_i 都放进 dp5001dp_{5001} 就行了。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
#define Filein(x) freopen(x".in","r",stdin)
const int N=5e3+5,M=1e5+10,mod=998244353;
int n;
int a[N];
int dp[M];
void work(){
    cin>>n;
    int V=0,ans=0;
    for(int i=1;i<=n;i++)
        cin>>a[i],V+=a[i];
    V=min(V,5001);
    sort(a+1,a+n+1);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=a[i]+1;j<=V;j++)
            ans=(ans+dp[j])%mod;
        for(int j=V;j>=0;j--)
            dp[min(j+a[i],5001)]=(dp[min(j+a[i],5001)]+dp[j])%mod;
        //通过min(j+a[i],5001)实现把大于压缩进一个
    }
    cout<<ans;
}
void clear(){}
signed main(){
    int _=1;
    while(_--)work(),clear();
    return 0;
}
/*

*/

评价

T4 放板子题太水了，今年 CSP-S 我考炸了，也算是安慰吧！

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...