网站出现404,网站建设合同交什么印花税,网站制作方案在哪找,专业网站设计的网站原题链接#xff1a;http://acm.uestc.edu.cn/problem.php?pid1668 由于题目意思指的是将分数拆分成不同的单位分数之和#xff0c;所以就不用考虑将2/3拆成1/31/3这种情况了#xff1b;又由于好的拆分要求项数即len要少#xff0c;最小的项要大#xff0c;故可以采用迭代…原题链接http://acm.uestc.edu.cn/problem.php?pid1668 由于题目意思指的是将分数拆分成不同的单位分数之和所以就不用考虑将2/3拆成1/31/3这种情况了又由于好的拆分要求项数即len要少最小的项要大故可以采用迭代加深搜索按项数不断增大的顺序进行搜索对每一种len要用一个数组将其的所有情况记录下来但这样太耗空间了因此将情况保存在ans数组里然后对ans不断进行更新。具体实现时要设两个标志flag,flag1,flag用来判断是不是第一次搜索len长的拆分flag1用来判断是否需要对ans进行更新。还有就是每次搜索的起点要弄好后面的要比前面的大要将a/b-1/z作为新的搜索分数其中z为当前搜到的符合要求的项。然后就可以比较方便地实现了。 1 #includestdio.h2 3 #includestring.h4 5 typedef long long ll;6 ll a,b,pre[1005],ans[1005];7 int flag;8 ll max(ll x,ll y)9 {
10 if(xy)return x;
11 return y;
12 }
13 ll gcd(ll small,ll big)
14 {
15 ll temp;
16 if(bigsmall)
17 {
18 tempbig;bigsmall;smalltemp;
19 }
20 if(big%small0)return small;
21 return gcd(big%small,small);
22 }
23 void ids(ll x,ll y,int len,int cur)
24 {
25 ll i,j,k;
26 if(curlen)
27 {
28 if(x1)
29 {
30 pre[len]y;
31 if(!flag)
32 {
33 for(i1;ilen;i)
34 ans[i]pre[i];
35 }
36 else
37 {
38 int temp,flag10;
39 for(templen;temp0;temp--)
40 {
41 if(pre[temp]ans[temp])break;
42 if(pre[temp]ans[temp])flag11;
43 if(flag1)break;
44 }
45 if(flag1)
46 {
47 for(i1;ilen;i)
48 ans[i]pre[i];
49 }
50 }
51 flag1;
52 }
53 return ;
54 }
55 jy/x;
56 if(j2)j2;
57 jmax(pre[cur-1]1,j);
58 while(x*j-y0)j;
59 while(1)
60 {
61 ll zx*j-y;
62 ll my*j;
63 kgcd(z,m);
64 z/k;m/k;
65 if(len-cur(z*j)/m)return ;
66 if(z*j(len-cur)*m)return ;
67 pre[cur]j;
68 ids(z,m,len,cur1);
69 j;
70 }
71 }
72 int main()
73 {
74 int i,j,T;
75 ll k;
76 scanf(%d,T);
77 while (T--)
78 {
79 scanf(%lld%lld,a,b);
80 kgcd(a,b);
81 a/k;b/k;
82 pre[0]1;
83 for(i1;i1000;i)
84 {
85 flag0;
86 ids(a,b,i,1);
87 if(flag)break;
88 }
89 for(j1;ji;j)
90 printf(%lld ,ans[j]);
91 printf(\n);
92 }
93 return 0;
94 } 转载于:https://www.cnblogs.com/i-love-acm/archive/2013/05/25/3099222.html
