专栏文章

题解：P14360 [CSP-J 2025] 多边形 / polygon

II_Love_Furina
P14360题解参与者 13已保存评论 12

文章操作

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

当前评论
12 条
当前快照
1 份
快照标识符
@minf96oj
此快照首次捕获于
2025/12/02 01:27
3 个月前
此快照最后确认于
2025/12/02 01:27
3 个月前
查看原文
树状数组做法
这 mm (m≥3)(m \ge 3)根小木棍能拼成一个多边形当且仅当
∑i=1m−1li>lm\sum_{i=1}^{m-1}l_i > l_m
对 aa 排序，令 fsf_s 表示当前用若干根小木棍(不是一根)能构成总长度为 ss 的方案数，令 sumsum 为 ∑i=1nai\sum_{i=1}^n a_i 由上面的公式可知，对 aa 排序后以第 ii 根小木棍为多边形中的最长小木棍对答案的贡献为
∑i=ai+1sumfi \sum_{i=a_i+1}^{sum}f_i
发现 an≤5000a_n \le 5000，所以实际上不用维护到 sumsum，只需维护到 ana_n，然后对于 i>5000i > 5000 的 fi f_i 只需另建一个变量来记录次数即可。而对于 i≤5000i \le 5000 的部分，用树状数组维护即可，具体的，每次遍历到一个 ii，从大到小枚举 fs(fs≠0)f_s(f_s \neq 0)，将 fs+aif_{s+a_i} 加上 fsf_s，再枚举 aj(j<i)a_j(j<i)，将 fai+ajf_{a_i+a_j} 加上 11。
令 amaxa_{max} 为 aia_i 中最大值，可视为与 nn 同阶，则时间复杂度约为 O(n2log⁡n)O(n^2 \log{n} )。
AC 记录。
代码
CPP
#include <bits/stdc++.h>
#define lb(x) (x&(-x))
#define int long long
using namespace std;
inline int read()//读入优化 
{
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c))f=c=='-'?-f:f,c=getchar();
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
const int N=5e3+10,mod=998244353;
int n,a[N],ans;
int t[N];//树状数组
int f[N];//f_i 表示当前若干根小木棍长度和为i的方案数 
int maxn;//i>5000 的部分单独用一个变量记录
set<int>s;//实现从大到小枚举f_s,集合s中存f_s中的s 
int sum(int x)//树状数组求和
{
    int res=0;
    while(x)res=(res+t[x])%mod,x-=lb(x);
    return res;
}
void add(int x,int d)//树状数组更新
{
    while(x<=5000)t[x]=(t[x]+d)%mod,x+=lb(x);
}
signed main()
{
    n=read();
    for(int i=1; i<=n; i++)a[i]=read();
    sort(a+1,a+n+1);//对a排序
    for(int i=1; i<=n; i++)
    {
        if(i>=3)ans=((ans+sum(5000)-sum(a[i])+maxn)%mod+mod)%mod;//m>=3时加贡献
        maxn=(maxn*2)%mod;//大于5000的部分每次都会加上a_i,依旧大于5000,所以是乘2 
        for(auto j=s.end(); j!=s.begin();)
        {
            j--;
            if(*j+a[i]<=5000)f[*j+a[i]]=(f[*j+a[i]]+f[*j])%mod,add(*j+a[i],f[*j]);//从大到小枚举f_s,将f_{s+a_i}加上f_s。 
            else maxn=(maxn+f[*j])%mod;//超过5000的部分单独计算
        }
        for(auto j=s.end(); j!=s.begin();)
        {
            j--;
            if(*j+a[i]<=5000)s.insert(*j+a[i]);//s+a_i不超过5000时,f_{s+a_i}不为0,下一轮需要计算,用set存s可以去重 
        }

        for(int j=1; j<i; j++)
        {
            if(a[i]+a[j]<=5000)f[a[i]+a[j]]=(f[a[i]+a[j]]+1)%mod,add(a[i]+a[j],1),s.insert(a[i]+a[j]);//枚举a_j,将f_{a_i+a_j}加1 
            else maxn=(maxn+1)%mod;//超过5000的部分单独计算
        }
    }
    cout<<ans<<endl;//输出 
    return 0;
}

评论

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

正在加载评论...