专栏文章

题解：P11703 [ROIR 2025] 个人 OI 比赛的原则

wwzb13958817049
P11703题解参与者 2已保存评论 1

文章操作

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

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

思路

首先考虑判断 Yes 和 No，可以看出来是 01 背包，内存较大可以用滚动数组，但是 bitset 也不会 MLE，代码如下：
CPP
for(int i=1;i<=n;i++){
	for(int j=0;j<v[i].size();j++){
		int u=v[i][j];
		for(int k=s;k>=u;k--){
			dp[i][k]=dp[i][k]|dp[i][k-u];
			dp[i][k]=dp[i][k]|dp[i-1][k-u];
		}
	}
}
再写 DFS 输出即可，题中指出 (k1+k2+…kn)×s≤107(k_1 + k_2 + … k_n) \times s \le 10^7 所以并不会 TLE。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,s;
bitset<100000> dp[100005];
vector<ll> v[100005],ans[100005];
void dfs(int x,int u,int last){
	if(x==0){
		if(u==0){
			for(int i=1;i<=n;i++){
				cout<<ans[i].size()<<"\n";
				for(int j=0;j<ans[i].size();j++){
					cout<<ans[i][j]<<" ";
				}
				cout<<"\n";
			}
			exit(0);
		}
		return ;
	}
	for(int i=last;i<v[x].size();i++){
		int y=v[x][i];
		if(u>=y && dp[x][u-y]){
			ans[x].push_back(i+1);
			dfs(x,u-y,i+1);
			ans[x].erase(--ans[x].end());
		}
		if(u>=y && dp[x-1][u-y]){
			ans[x].push_back(i+1);
			dfs(x-1,u-y,0);
			ans[x].erase(--ans[x].end());
		}
	}
}
int main(){
	ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		ll x;cin>>x;
		for(int j=1;j<=x;j++){
			ll y;cin>>y;
			v[i].push_back(y);
		}
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<v[i].size();j++){
			int u=v[i][j];
			for(int k=s;k>=u;k--){
				dp[i][k]=dp[i][k]|dp[i][k-u];
				dp[i][k]=dp[i][k]|dp[i-1][k-u];
			}
		}
	}
	if(dp[n][s]==0) cout<<"No";
	else{
		cout<<"Yes\n";
		dfs(n,s,0);
	}	
	return 0;
}

评论

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

正在加载评论...