ac-m编程比赛学习入门题目集.doc
《ac-m编程比赛学习入门题目集.doc》由会员分享,可在线阅读,更多相关《ac-m编程比赛学习入门题目集.doc(68页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、#*最少钱币数:最少钱币数:【问题描述问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。 例如:给定了 6 种钱币面值为 2、5、10、20、50、100,用来凑 15 元,可以用 5 个 2 元、 1 个 5 元,或者 3 个 5 元,或者 1 个 5 元、1 个 10 元,等等。显然,最少需要 2 个钱币才 能凑成 15 元。 你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑 成某个给出的钱数。【要求要求】 【数据输入数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值 M(1 13,12-23,13-1
2、2,13-32,23-21, 23-31。 注意:注意:文件里只有一个整数 N(2N1000)。 【数据输出数据输出】输出一个整数,为可能的过程的总数除以 10007 的余数。【样例输入样例输入】 4【样例输出样例输出】 96 #*猴子的争斗猴子的争斗Time limit: 1s Memory limit: 32768K Total Submit : 184 Accepted Submit : 75 【问题描述问题描述】 从前在一个森林里,有 N 只好斗的猴子。一开始,他们互不认识。互不认识的猴子间是无 法避免争斗的,而且争斗只会发生在两只互不认识的猴子间。决斗结束后,这两只猴子和 他们各自的
3、朋友们通过这场决斗相互间都认识了,争斗便不会再发生在这一大群猴子中的 任两只。由于争斗是比较激烈的,所以同一时间内不会有两场决斗一起发生。经过 N-1 次 决斗后,这 N 只猴子间相互都认识了,现在问有多少种可能的决斗过程。例如 N=3,有 6 种不同的过程:12-13,12-23,13-12,13-32,23-21, 23-31。【要求要求】 【数据输入数据输入】文件里只有一个整数 N(2N1000)。 【数据输出数据输出】输出一个整数,为可能的过程的总数除以 10007 的余数。【样例输入样例输入】 4【样例输出样例输出】 96 #*排序排序Time limit: 10s Memory l
4、imit: 32768K Total Submit : 70 Accepted Submit : 2 【问题描述问题描述】 通常我们对一个长度为 n(n24)的整数数列进行排序操作,其实就是讲他们按照从小到大 的顺序重整。一般情况下我们可以比较任意两个数之间的大小并交换他们的位置,但这里 我们限制只能数列的某一个前缀序列翻转,除此之外的任何操作都是不允许的。更精确地 说,假设数列 a1,a2,an,一个合法的操作是把数列变为 ak,ak-1,a2, a1, ak+1, ak+2, an,其中 10(即所有项的和为,且所有部分和为正) 。 例如 N=2 的时候,共有 3 组这样的序列:1, 1,
5、 1, -2, 1, 1, -21, 1, 1, 1, -2, 1, -21, 1, 1, 1, 1, -2, -2【要求要求】 【数据输入数据输入】第一行输入 N(N1000)。【数据输出数据输出】满足 P 性质的序列数目【样例输入样例输入】 2【样例输出样例输出】 3#*宠物宠物timelimit:1 seconds memlimit:32768 K Prev |Next【问题描述问题描述】fzk 非常喜欢养宠物,比如他现在就养了 2 头奶牛,3 只小熊,4 个猩猩,5 头大象,还有一个 daizi。fzk 把他的宠物关在一些笼子里,例如,fzk 当前的分配是: 笼 子 1: 奶牛,dai
6、zi ;笼子 2: 奶牛;笼子 3: 猩猩,大象;笼子 4: 小熊,猩猩这样总 共需要 4 个笼子。为了节省资金,fzk 想用尽可能少的笼子来装下所有宠物。他的办法是在 当前的分配下,合并一些笼子。假设每个笼子都足够大,可以装下任意多的宠物,而两个 笼子如果装有相同的一种或多种宠物,就可以合并。现在给出 fzk 当前的分配,你能否帮 助 fzk 算出按照他的方法合并后,总共只需要几个笼子? 比如对于上面的分配,可以合并 为: 笼子 1:奶牛,daizi ;笼子 2:猩猩,小熊,大象总共需要 2 个笼子。 【要求要求】 【数据输入数据输入】首先一个整数 t 表示测试数据组数(1=0) ,表示当前
7、分配下总共的笼子数。在接下来的 k 行中,每行描述一个笼子中 关的宠物。其中第 i 行的结构是:Ni name1 name2 name3 nameNi。其中 Ni(Ni0)是该 笼子中的宠物的种类数,name1,nameNi 是这些宠物的 种类名称(他们互不相同) 。所有的 name 都是由小写字母组成的字符串,长度不超过 10 位;所有的 Ni 之和不超过 10000,不同的宠物种类数不超过 1000。 【数据输出数据输出】对每组测试数据,输出一个整数,表示笼子合并之后 fzk 可以使用的最少的 笼子数。 【样例输入样例输入】 1 4 2 nainiu daizi 1 nainiu 2 xi
8、ngxing daxiang 2 xiaoxiong xingxing【样例输出样例输出】 2#*多边形多边形timelimit:1 seconds memlimit:32768 K Prev |Next【问题描述问题描述】 在一个坐标平面上,给一个 n 个点的集合,能不能画出一个简单多边形(除相邻边外其他 任意两条边没有公共点) 。要求这个多边形的顶点集合就是给定的点集,而且多边形的边必 须与 x 轴或 y 轴平行.更进一步,要求多边形相邻的边不平行,也就是说,多边形的边是一条横 线段,接着一条竖线段,再接着一条横线段.【要求要求】 【数据输入数据输入】输入包括多组数据. 输入数据的第一行包
9、括一个整数 t,表示有 t 组输入数据,t 3 1 4 2 4 (1,3 城市都不玩,游玩过城市 2 后再到城市 4) 共 7 种路线。 #*割钢管割钢管Time Limit:1000MS Memory Limit:65536K Total Submit:7 Accepted:6 【问题描述问题描述】 A 公司有一台钢管切割机提供钢管加工业务。钢管切割机每次可以将一根钢管按照要求在 指定位置切割为 2 段。每次切割的费用为钢管的长度。 给定一根长度为 L 的钢管,要求将其在位置 l1l2.ln;处切割为的 n+1 段钢管,应如何切 割才能使总切割费用最小。 【要求要求】 【数据输入数据输入】多
10、组测试数据。 每组数据第 1 行有 2 个正整数 L 和 n,L 表示钢管的长度,n 表示切割次数。第 2 行有 n 个 正整数,表示切割位置 l1l2.ln。其中,0L5001,0n501。【数据输出数据输出】最小切割总费用并换行. 【样例输入样例输入】 15 4 3 9 12 14【样例输出样例输出】 33#*亲和数亲和数Time Limit:1000MS Memory Limit:65536K Total Submit:35 Accepted:26 【问题描述问题描述】 古希腊数学家毕达哥拉斯在自然数研究中发现,220 的所有真约数(即不是自身的约数)之和 为: 1+2+4+5+10+1
11、1+20+22+44+55+110284。 而 284 的所有真约数为 1、2、4、71、 142,加起来恰好为 220。人们对这样的数感到很惊 奇,并称之为亲和数。一般地讲,如果两个数中任何一个数都是另一个数的真约数之和, 则这两个数就是亲和数。 你的任务就编写一个程序,判断给定的两个数是否是亲和数【要求要求】 【数据输入数据输入】输入数据第一行包含一个数 M,接下有 M 行,每行一个实例,包含两个整数 A,B; 其中 0 = A,B = 600000 ;【数据输出数据输出】对于每个测试实例,如果 A 和 B 是亲和数的话输出 YES,否则输出 NO。【样例输入样例输入】 2 220 284
12、 100 200【样例输出样例输出】 YES NO#*分解素因子分解素因子Time Limit:1000MS Memory Limit:65536K Total Submit:14 Accepted:11 【问题描述问题描述】 假设 x 是一个正整数,它的值不超过 65535(即 1x=65535),请编写一个程序,将 x 分解 为若干个素数的乘积。 【要求要求】 【数据输入数据输入】输入的第一行含一个正整数 k (1=k=10),表示测试例的个数,后面紧接着 k 行,每行对应一个测试例,包含一个正整数 x。 【数据输出数据输出】每个测试例对应一行输出,输出 x 的素数乘积表示式,式中的素数从
13、小到大 排列,两个素数之间用“*”表示乘法。 【样例输入样例输入】 2 11 9828【样例输出样例输出】 11 2*2*3*3*3*7*13#*有趣的数列有趣的数列Time Limit:1000MS Memory Limit:65536K Total Submit:2 Accepted:1 【问题描述问题描述】 数列 F(n)和 G(n)是由下列三个条件所确定的两个自然数列: (1) F(1) = 1; (2) G(n) = n*a - 1 - F(n),a 是一个大于 4 的整数; (3) F(n+1)是与 2n 个数:F(1),F(2),.,F(n);G(1),G(2),.,G(n)不同
14、的最小自然数。 给定 a 和 n,你能求出满足以上条件的数列 F(n)和 G(n)吗?【要求要求】 【数据输入数据输入】测试数据有多行,每行包含两个数 a 和 n,其中:4 a = 1000, 1 = n = 1000000; 当 a = n = 0 时,输入结束,此行无须处理。【数据输出数据输出】为简便起见,只须输出数列 F(n)和 G(n)的第 n 项 f(n), g(n); 输出数据有一行,分别包含两个数 f(n)和 g(n)。【样例输入样例输入】 5 1 5 3 0 0【样例输出样例输出】 1 3 4 10#*洗牌问题洗牌问题Time Limit:1s Memory limit:32M
15、 Accepted Submit:301 Total Submit:644 【问题描述问题描述】 设 2n 张牌分别标记为 1, 2, ., n, n+1, ., 2n,初始时这 2n 张牌按其标号从小到大排列。经 一次洗牌后,原来的排列顺序变成 n+1, 1, n+2, 2, ., 2n, n。即前 n 张牌被放到偶数位置 2, 4, ., 2n,而后 n 张牌被放到奇数位置 1, 3, ., 2n-1。可以证明对于任何一个自然数 n,经过若 干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的 n 的值(n105),最少需 要经过多少次洗牌可恢复到初始状态。 【数据输入数据输入】输入数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ac 编程 比赛 学习 入门 题目
限制150内