C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 3049 挑选数字

Problem

给出n个正整数,从中挑选若干个,使得他们的和为m。如果存在多个,输出排序后字典序最小的一组。如果没有找到任何一组,输出"No Solution"。

Solution

如果n大于15,从16开始分成两部分,先枚举后一半可能出现的值,map记录,然后按顺序枚举前一半,如果能和某个值组成m就记录每个数,返回,再枚举后一半,找到具体的数字。

主要是dfs写的太烂了,交对看别人的才知道怎么写。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<stdio.h>
#include<set>
#include<iostream>
#include<stack>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod=1e9+7;
inline int mo(ll a,int p){
return a>=p?a%p:a;
}
inline int rd() {
int x = 0, f = 1;
char ch;
while (ch < '0' || ch > '9') {
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
inline ll gcd(ll x, ll y){
return y==0?x:gcd(y,x%y);
}
inline ll speed(ll a,ll b){
ll cur=a,anss=1;
while(b){
if(b&1) anss=anss*cur;
cur=cur*cur;
b>>=1;
}
return anss;
}
const int MAXN=1e5;
bool ipr[MAXN+20];
int cnt,pri[MAXN/5];
void prime(){//埃式筛法
int N=sqrt(MAXN)+0.5,mul;
memset(ipr,true,sizeof(ipr));
ipr[1]=false;
for(int i=2;i<=N;i++){
if(ipr[i]==true){
i==2?mul=1:mul=2;
for(int j=i*i;j<=MAXN;j+=i*mul){
ipr[j]=false;
}
}
}
for(int i=2;i<=MAXN;i++){
if(ipr[i]==true){
pri[++cnt]=i;
}
}
}
int n,m;
int a[50];
int ans[50],ct=0,al=0,mid;
bool fg=false;
map<int,int>mp;
int sss=15;
void dfs(int cur,int sum,int cou){
if(fg) return;
if(sum==m){
fg=true;
ct=cou;
return;
}
if(cur==n+1) return;
ans[cou+1]=a[cur];
if(sum+a[cur]<=m&&al-sum-a[cur]>=m-sum-a[cur]) dfs(cur+1,sum+a[cur],cou+1);

if(al-sum>=m-sum) dfs(cur+1,sum,cou);

}
void dfs1(int cur,int sum){
mp[sum]=1;
if(cur==n+1) return;
dfs1(cur+1,sum+a[cur]);
dfs1(cur+1,sum);
}
void dfs2(int cur,int sum,int cou){
if(fg) return;
if(mp[m-sum]){
fg=true;
mid=sum;
ct=cou;
return;
}
if(cur==sss+1) return;
ans[cou+1]=a[cur];
if(sum+a[cur]<=m&&al-sum-a[cur]>=m-sum-a[cur]) dfs2(cur+1,sum+a[cur],cou+1);

if(al-sum>=m-sum) dfs2(cur+1,sum,cou);

}
bool fg2=false;
void dfs3(int cur,int sum,int cou){
if(fg2) return;
if(sum==m){
fg2=true;
ct=cou;
return;
}
if(cur==n+1) return;
ans[cou+1]=a[cur];
if(sum+a[cur]<=m&&al-sum-a[cur]>=m-sum-a[cur]) dfs3(cur+1,sum+a[cur],cou+1);
if(al-sum>=m-sum) dfs3(cur+1,sum,cou);

}
int main(){
//io_opt;

scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
al+=a[i];
}
if(al<m){
printf("No Solution\n");
return 0;
}
sort(a+1,a+1+n);
if(n<=sss){
dfs(1,0,0);
}
else{
dfs1(sss+1,0);
dfs2(1,0,0);
//cout<<ct<<endl;
if(fg) dfs3(sss+1,mid,ct);
//cout<<ct<<endl;
}


if(fg){
for(int i=1;i<=ct;i++){
printf("%d ",ans[i]);
}
printf("\n");
}
else{
printf("No Solution\n");
}
return 0;
}

  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/47161/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!