题目链接&＃xff1a;http://codeforces.com/contest/960/problem/C
题意&＃xff1a;对于任意包含n个元素的集合&＃xff0c;他的子集有2^n-1个&＃xff08;不包括空集&＃xff09;&＃xff0c;然后现在告诉你某个集合的子集中&＃xff0c;满足最大元素-最小元素差值 分析&＃xff1a;做这道题的时候一直在纠结什么情况输出-1&＃xff0c;最后直接判断元素个数&＃xff0c;如果大于10000&＃xff0c;就输出-1.然后还有不知道自己的策略是不是最优策略&＃xff0c;感觉不是最优策略但是AC了。具体思路是我们可以考虑对于任意一个有k个元素的集合&＃xff0c;他有2^k-1个子集&＃xff0c;如果这个集合的最大元素和最小元素差值小于d&＃xff0c;那么所有子集都是满足的&＃xff0c;因此可以对于他给定的x&＃xff0c;拆分为元素个数为i个的小集合&＃xff0c;小集合之间的最大元素和最小元素不满足情况&＃xff0c;集合之内的一定满足就可以了。然后对于元素个数为i的小集合&＃xff0c;我们只需要任意取i个相同元素就可以了。集合之间为了保证不满足&＃xff0c;我们第一个集合从1开始&＃xff0c;第二个就是1&＃43;d,以此类推就可以了。&＃xff08;我感觉这样不是最优&＃xff0c;要想用最少的元素构造最多的满足条件的子集&＃xff0c;比如现在要构造x&＃61;11&＃xff0c;d&＃61;3的集合&＃xff0c;如果用我的策略&＃xff0c;需要构造1 1 1 4 4 7这6个元素来满足&＃xff0c;但是如果我们用末尾添加策略&＃xff08;就是在已经构造好的集合最后添加一个元素&＃xff0c;使得该元素与已有集合中的m个元素差值小于d&＃xff0c;那么这次添加多出的满足条件的子集个数又增加了2^m个&＃xff09;的话&＃xff0c;只需要1 2 3 4就可以满足了&＃xff0c;所以我的策略应该不是最优&＃xff0c;比赛刚打到一半有事出去了&＃xff0c;没来的急码&＃xff0c;大家可以尝试一下&＃xff09; AC代码&＃xff1a;&＃xff08;不太靠谱策略&＃xff09; 1 #include 
2
3 using namespace std;
4
5 long long a[50];
6 int b[50];
7 int main(){
8 ios_base::sync_with_stdio(0);
9 cin.tie(0);
10 long long x,d;
11 a[0]&＃61;1;
12 for(int i&＃61;1;i<&＃61;50;i&＃43;&＃43;){
13 a[i]&＃61;a[i-1]*2;
14 }
15 for(int i&＃61;0;i<&＃61;50;i&＃43;&＃43;){
16 a[i]--;
17 }
18 cin>>x>>d;
19 long long n&＃61;0;
20 memset(b,0,sizeof(b));
21 for(int i&＃61;50;i>&＃61;1;i--){
22 if(x>&＃61;a[i]){
23 b[i]&＃61;x/a[i];
24 x&＃61;x%a[i];
25 n&＃43;&＃61;b[i]*i;
26 }
27 }
28 if(n>10000) {
29 cout<<-1<<endl;
30 return 0;
31 }
32 cout<
33 long long ans&＃61;1;
34 for(int i&＃61;1;i<&＃61;50;i&＃43;&＃43;){
35 for(int j&＃61;1;j<&＃61;b[i];j&＃43;&＃43;){
36 for(int k&＃61;0;k
37 cout<
38 }
39 ans&＃43;&＃61;d;
40 }
41 }
42 cout<<endl;
43 return 0;
44 }
京公网安备 11010802041100号