专栏文章

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

nnewsname
P14360题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minfqpt8
此快照首次捕获于
2025/12/02 01:40
3 个月前
此快照最后确认于
2025/12/02 01:40
3 个月前
查看原文
今年的 T4好水呀，后悔没参加。
思路：
知识点：化归 + 截断背包。
把长度升序排好 a1≤⋯≤ana_1\le\dots\le a_n。任取可行方案，设其中最大棒是 aja_j，可行条件 ∑S>2max⁡S  ⟺  ∑(S∖aj)>aj\sum S>2\max S\iff \sum(S\setminus{a_j})>a_j， 于是答案变为对每个 jj：在 a1,…,aj−1{a_1,\dots,a_{j-1}} 中选若干根，其和大于 aja_j 的子集个数之和。注意因为都不大于 aja_j，单根不可能大于 aja_j，所以无需再显式排除选 0/10/1 根。
设 mx=max⁡ai≤5000mx=\max a_i\le 5000。用 0/10/1 计数背包维护前缀集合的子集和分布 fsf_s（只保留 0≤s≤mx0\le s\le mx），以及总子集数 tot=2ttot=2^{\text{t}}。（tt 为已处理根数），对于当前最大棒 aja_j，设 nn 为 在所有当前能拼出的子集和里，满足 s>ajs>a_j 的那些子集的数量，则所需个数为 ans×j=n=tot−∑×s=0ajf[s](modP)\text{ans}\times j=n=tot-\sum\times {s=0}^{a_j}f[s]\pmod P。
然后把 aja_j 加入背包：倒序转移 f[s+aj]+=f[s]f[s+a_j]+=f[s]（若 s+aj>mxs+a_j>mx 直接忽略，因为这些和以后对任何阈值 at≤mxa_t\le mx 都必然计入“大于阈值”的部分，已经通过 tottot 体现），并令 tot←2×tottot\leftarrow 2\times tot。
时间复杂度 O(n⋅mx)\mathcal O(n\cdot mx)，最劣时间复杂度 O(n2)\mathcal O(n^2)，空间复杂度 O(mx)\mathcal O(mx)。足以通过本题。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005,mod=998244353;
int a[maxn],f[maxn];
int main(){
      int n;
      cin>>n;
      int mx=0;
      for(int i=1;i<=n;i++){
	  	cin>>a[i];
	  	mx=max(a[i],mx);
	  }
	  sort(a+1,a+n+1);
	  f[0]=1;
	  int tot=1,ans=0;
	  for(int i=1;i<=n;i++){
	  	int lim=a[i],s=0;
	  	for(int t=0;t<=lim;t++){
		  	s+=f[t];
		  	if(s>=mod) s-=mod;
		  }
		  int add=tot-s;
		  if(add<0) add+=mod;
		  ans+=add;
		  ans%=mod;
		  for(int t=mx;t>=0;t--){
		  	if(f[t]){
			  	int u=t+a[i];
			  	if(u>mx) continue;
			  	int v=f[t]+f[u];
			  	v%=mod;
			  	f[u]=v;
			  }
		  }
		  tot<<=1;
		 tot%=mod;
	  }
	  cout<<ans%mod;
	return 0;
}

评论

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

正在加载评论...