英文原题 中文题译
大意:给定若干素数p1,..pk,找第N个素因子全为这些已知素数的合数。
又是一开始定错了方向,开始了整晚的折磨。唉。最后,完整的过了。
一上来,分析算法时就确定用优先队列找已有的最小的数,把接下来的乘积放如队列中。接着噩梦开始了。马上发现,数可能重复,而优先队列中无法排除重复数,于是想自己写一个可以清除重复数的优先队列,结果发现写不出来。倒是写了个二项堆模板。
无奈之下,用set来记录已经插入的数。依然错,发现输出的是负数,显然是整数越界。弄了很久才想起来long long next=cur*primes[i];之后判断next是否越界是无效的,必须先转换类型(晕,我是猪)。
排除此问题之后,在最后一个测试实例(最大的一个)上发现空间溢出,看了看,用了14M空间。于是,在扩展了N个数之后记录最大值,超过最大值的肯定不是要找的数。这样下来,空间变成8M,不越界了。
但是,时间是1.67秒,超过了1秒的限制。换用自己的Heap,时间差不多。很无奈之下下去吹了吹冷风,想:难道就这样挂了?一定要换方法吗?
最后逐行想过去,vis.find(next)==vis.end() && next<limit,就是它了, 交换了比较顺序,变成next<limit && vis.find(next)==vis.end(),时间立马降低一半,变成0.84秒,通过了。这也算是个常识性错误,唉。改晕头了才会写出这样的代码。也可见set的实现是很烂的,集合越大,性能越差。
补充,重写了一个暴力枚举的,时间上比之前的好。用一个数组记录每个素数上一次乘的数的位置和值,这样,每个乘法只做一次。用这种方式还可以记录出指数和(参见邮票Stamps一题)。
大意:给定若干素数p1,..pk,找第N个素因子全为这些已知素数的合数。
又是一开始定错了方向,开始了整晚的折磨。唉。最后,完整的过了。
一上来,分析算法时就确定用优先队列找已有的最小的数,把接下来的乘积放如队列中。接着噩梦开始了。马上发现,数可能重复,而优先队列中无法排除重复数,于是想自己写一个可以清除重复数的优先队列,结果发现写不出来。倒是写了个二项堆模板。
无奈之下,用set来记录已经插入的数。依然错,发现输出的是负数,显然是整数越界。弄了很久才想起来long long next=cur*primes[i];之后判断next是否越界是无效的,必须先转换类型(晕,我是猪)。
排除此问题之后,在最后一个测试实例(最大的一个)上发现空间溢出,看了看,用了14M空间。于是,在扩展了N个数之后记录最大值,超过最大值的肯定不是要找的数。这样下来,空间变成8M,不越界了。
但是,时间是1.67秒,超过了1秒的限制。换用自己的Heap,时间差不多。很无奈之下下去吹了吹冷风,想:难道就这样挂了?一定要换方法吗?
最后逐行想过去,vis.find(next)==vis.end() && next<limit,就是它了, 交换了比较顺序,变成next<limit && vis.find(next)==vis.end(),时间立马降低一半,变成0.84秒,通过了。这也算是个常识性错误,唉。改晕头了才会写出这样的代码。也可见set的实现是很烂的,集合越大,性能越差。
/* ID: blackco3 TASK: humble LANG: C++ */ #include <iostream> #include <queue> #include <set> using namespace std; #define _max_ 100 template < typename t_heap_value, int _max_heap_size_ > class Heap { t_heap_value heap[_max_heap_size_+1]; int size ; private : inline void swap( int i, int j ){ t_heap_value tmp ; tmp=heap[i], heap[i]=heap[j], heap[j]= tmp ; } inline void del( int pos){ heap[pos]=heap[size--]; while( (pos<<1)<=size ) { int left=pos<<1, right=left+1 ; if( right>size || heap[left]<heap[right] ) if( heap[left]<heap[pos] ) swap( pos, left ), pos=left ; else break ; else if( heap[right]<heap[pos] ) swap( pos, right ), pos=right ; else break ; } } public : Heap(){ size=0; } ; t_heap_value top(){ return heap[1]; } ; int empty(){ return size>0; } ; void pop(){ if(size) del(1); }; void push(t_heap_value v ){ heap[++size] = v ; for( int pos=size; pos>0 ; pos >>= 1 ) { if( heap[pos>>1]>heap[pos] ) swap(pos, pos>>1); else break ; } } void show() { for( int i=1; i<=size; i++ ) cout << heap[i] << " "; cout << endl ; } }; Heap<int,1000000> heap; set<int> vis; int main() { freopen("humble.in", "r", stdin); freopen("humble.out", "w", stdout); int n_prime, n_th, primes[_max_] ; cin >> n_prime >> n_th ; for( int i=0; i<n_prime; i++ ){ cin >> primes[i] ; } heap.push(1); for( int i=0, limit=0, count=0; i<n_th; i++ ){ register int cur=heap.top(); heap.pop(); for( int i=0; i<n_prime; i++ ){ long long next=((long long)cur)*primes[i]; if( next > 0x7fffffff ) continue ; if( count<n_th ){ if( vis.find(next)==vis.end() ){ vis.insert(next), heap.push(next); count++, limit=limit>next? limit : next ; } } else { if( next<limit && vis.find(next)==vis.end() ) vis.insert(next), heap.push(next); } } } cout << heap.top() << endl ; return 0; }
补充,重写了一个暴力枚举的,时间上比之前的好。用一个数组记录每个素数上一次乘的数的位置和值,这样,每个乘法只做一次。用这种方式还可以记录出指数和(参见邮票Stamps一题)。
/* ID: blackco3 TASK: humble LANG: C++ */ #include <iostream> using namespace std; #define _max_prime_ 100 #define _max_val_ 100001 int main() { freopen("humble.in", "r", stdin); freopen("humble.out", "w", stdout); int n_prime, n_th, primes[_max_prime_], pos[_max_prime_], pval[_max_prime_] ; cin >> n_prime >> n_th ; for( int i=0; i<n_prime; i++ ){ cin >> primes[i] ; pos[i]=0, pval[i]=primes[i] ; } int val[_max_val_]={1} ; for( int ival=1; ival<=n_th; ival++ ){ register int min_val=0x7fffffff, min_pos ; do{ min_val=0x7fffffff ; for( int x=0; x<n_prime; x++ ) if( pval[x] < min_val ) min_val=pval[x], min_pos=x ; if( min_val > val[ival-1] ) break ; pval[min_pos] = val[++pos[min_pos]]*primes[min_pos] ; }while( true ) ; val[ival]=min_val ; } cout << val[n_th] << endl ; return 0; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 888英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1136英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1852郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1647英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1201英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 976英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1074英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1408英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 786英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 801英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 976英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1211英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 919英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1097英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 778英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1235英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1052英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 934英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1313英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 871英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ...
相关推荐
做的很辛苦, 里面附有注释,大家支持一下吧...
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
USACO全部译题 USACO Training Program Gateway
自己写的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->
3.1 Section 3.1 3.2 Section 3.2 3.3 Section 3.3 3.4 Section 3.4 4 Chapter4 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 ...
USACO training 教程翻译合集(清晰明确)
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
One of the answer of the USACO training exercises.
Usaco部分代码(humble number是我目前看到最快的..)
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
USACO题集及答案
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看