广州建设集团网站,网站访问量怎么赚钱,pc端网站怎么做自适应,公司内部网站开发昨天晚上写的一题 结果USACO一直挂中 今天交了下 有一点点的数论知识 背包很好想 就是不好确定上界 官方题解#xff1a; 这是一个背包问题。一般使用动态规划求解。 一种具体的实现是#xff1a;用一个线性表储存所有的节点是否可以相加得到的状态#xff0c;然后每次可以…昨天晚上写的一题 结果USACO一直挂中 今天交了下 有一点点的数论知识 背包很好想 就是不好确定上界 官方题解 这是一个背包问题。一般使用动态规划求解。 一种具体的实现是用一个线性表储存所有的节点是否可以相加得到的状态然后每次可以通过一个可以相加得到的节点通过加上一个输入的数求出新的可以相加得到的点。复杂度是O(N×结果)。 但是可以证明结果不会超过最大的两个数的最小公倍数如果有的话。参见数论。所以复杂度也是O(Na2)完全可以接受了。 判断无限解可以按上面的方法另外也可以算所有的数的最大公约数。如果不是1也就是说这些数不互质那么不被这个最大公约数整除的数一定构造不出来。当且仅当这种情况会有无限解。另外有一种不需要任何数论知识的方法是判断是不是按照每个输入的数的循环节循环如果是的话继续算显然不会有任何结果。 判断有没有更大的解也可以按这种方法另外如果连续最小的数那么多个数都可以构成也不会有更大的符合条件的解。 通过位压缩可以使程序在32位机上的运行速度快32倍由于程序代码会变长也可能是16倍或者更小的倍数。这样可以相当快的解决这个问题。不过复杂度还是O(Na2)。 “可以证明结果不会超过最大的两个数的最小公倍数”。我来证明一下。 已知不定方程 ax by c ( a , b 0 且 c ab )存在一组整数解( x0 , y0 ) (斐蜀定理)
求证该不定方程存在一组非负整数解 ( xn , yn ) .
证明 : 由不定方程通解式得 : xn x0 b * t , yn y0 - a * t ( t 是整数 )
令 xn , yn 0 解出 - ( x0 / b ) t ( y0 / a )
因为 c a * b 即 a * x0 b * y0 a * b 两边同除 a * b 得 :
y0 / a - ( - x0 / b ) 1
所以一定存在 整数t使得 - ( x0 / b ) t ( y0 / a ) .
所以方程一定有非负整数解. 证毕.特殊情况 无解的情况很显然只有输入的N个数里有1的情况才会无解否则1本身就是一个解因为没办法由更大的数相加得到。无限个解的情况见上面的#问题分析。对于这道题目这两种情况都应该输出0。 注如果有两个连续的数x,x1 在序列中的话那(x-1)*x以后的数都能通过这两个相加得到。所以如果x-1*x前无解则无解! 1 /*2 ID: shangca23 LANG: C4 TASK: nuggets5 */6 7 #include iostream8 #includecstdio9 #includecstring
10 #includealgorithm
11 #includestdlib.h
12 using namespace std;
13 #define N 70000
14 int dp[70010];
15 int a[12];
16 int gcd(int a,int b)
17 {
18 return b0?a:(gcd(b,a%b));
19 }
20 int main()
21 {
22 freopen(nuggets.in,r,stdin);
23 freopen(nuggets.out,w,stdout);
24 int i,j,n,y;
25 cinn;
26 for(i 1; i n ; i)
27 cina[i];
28 y a[1];
29 if(n1)
30 {
31 printf(0\n);
32 return 0;
33 }
34 for(i 2; i n ; i)
35 {
36 y gcd(y,a[i]);
37 }
38 if(y!1)
39 {
40 puts(0);
41 return 0;
42 }
43 int v N;
44 dp[0] 1;
45 for(j 1; j n ; j)
46 for(i a[j] ; i v ; i)
47 {
48 dp[i] max(dp[i],dp[i-a[j]]);
49 }
50 for(i v ; i1 ; i--)
51 {
52 if(dp[i]0)
53 break;
54 }
55 if(i0)
56 cout0\n;
57 else
58 coutiendl;
59 return 0;
60 } View Code 转载于:https://www.cnblogs.com/shangyu/p/3278723.html
