大意:
给定N个正整数,确定由其加法不能表示的正整数的最大值。例如给若干个邮票面值,问最大不能被这些邮票组合出来的面值是多少。如果没有这样的最大值,则输出0 。
分析与实现:
看上去很面熟是吧,不过与之前的有所不同。
首先,怎样的面值组合没有最大不可表示的值?例如2,4,所有的奇数都不能表示,6,9,所有不能被3整除的都不能表示。于是规律是:N个数的最大公约数如果是1,那么一定存在这样的最大值,否则,不可表示的值可以无限大。
如果这样的最大值存在,怎么找?很简单,设其最小面值为k,那么如存在n使得n,n+1,...n+k-1都可以表示,则之后所有的数都可通过加贴面值为k的邮票来表示了。
/* ID: blackco3 TASK: nuggets LANG: C++ */ #include <iostream> #include <algorithm> using namespace std; const int _max_pack_(256) ; int packs[_max_pack_], n_pack, unpacked[_max_pack_] ; int gcd(int a, int b) { while(a && b) a %= b , b = a ? b%a : b ; return a + b ; } int check_bound( ) { int gcd_val = packs[0] ; for( int i=1; i<n_pack; i++ ) gcd_val = gcd(gcd_val, packs[i] ); return gcd_val!=1 ; } int main() { freopen("nuggets.in", "r", stdin); freopen("nuggets.out","w",stdout); cin >> n_pack ; for( int i=0; i<n_pack; i++ ) cin >> packs[i] ; sort( packs, packs+n_pack ); if ( check_bound() ) { cout << 0 << endl ; return 0 ; } unpacked[0]=0 ; for( int i=1; i<packs[0]; i++ ) unpacked[i]=1 ; int max_unpack = packs[0]-1 , max_pack = packs[n_pack-1], min_pack=packs[0] ; for( int cur=packs[0], cursor=-max_pack; cur <= min_pack + max_unpack ; cur++ ){ int unpackable=1 ; for( int i=0; i<n_pack; i++ ){ if( cur>=packs[i] && !unpacked[(cur-packs[i])%max_pack] ){ unpackable=0 ; break ; } } if( unpacked[cur%max_pack]=unpackable ) max_unpack=cur ; } cout << max_unpack << endl ; return 0; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 882英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1132英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1847郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1643英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1195英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1062英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1401英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 771英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 796英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 969英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1204英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 914英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1092英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 772英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1230英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1043英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 929英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1304英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 867英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ... -
USACO Training Section 3.2 Stringsobits
2010-01-18 01:04 989英文原题 中文题译 大意:求至多有L个1的第i个N位二进 ...
相关推荐
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
[USACO 1.1.4]破碎的项链.cpp
USACO_培训USACO_培训Ride.java-> Gift1.java->
USACO全部译题 USACO Training Program Gateway
USACO1-5单元AC的代码~ 1 Chapter1 ...4.1 Section 4.1 4.2 Section 4.2 4.3 Section 4.3 4.4 Section 4.4 5 Chapter5 5.1 Section 5.1 5.2 Section 5.2 5.3 Section 5.3 5.4 Section 5.4 5.5 Section 5.5
USACO training 教程翻译合集(清晰明确)
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
One of the answer of the USACO training exercises.
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO题集及答案
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括