合肥工业大学第十届程序设计大赛试题
要求每个小组做全本套题目
合肥工业大学第十届程序设计大赛试题
A.字母集合
时限：1s
【题目描述】
有一个字符集合，它只包含a-z这26个小写字母。根据集合的定义，集合的容量是集合含有不同元素的个数。由于该集合中包含了非常多的重复字母，因此让你编程计算下该集合的容量，也就是该集合包含了多少不相同的字母。
【输入】
有多组样例。第一行为样例的个数T。
接下来T行，每一行代表一个样例。这一行为一个字符串，表示一个集合。规定以’{’开头，以’}’结束。每个字符用’,’给开，逗号与逗号后的元素空出一个空格。
【输出】
每个集合的容量。一个样例占一行。
【输入样例】
2
{a, b, c}
{a, b, a, b}
【输出样例】
3
2
1
合肥工业大学第十届程序设计大赛试题
B吉利数字
时限：1s
【题目描述】
算卦大湿biboyouyun最近得出一个神奇的结论，如果一个数字，它的各个数位相加能够被10整除，则称它为吉利数。现在叫你计算某个区间内有多少个吉利数字。
【输入】
第一行为样例个数N。接下来N行，每一行代表一个输入样例，每个输入样例有2个数，分别代表某个区间的起点a和终点b。
注意所求区间为[a,b]，1<=a<=b<=10^9
【输出】
N行。对于第x个输入样例，在第x行输入该样例所对应的结果。
【输入样例】
2
1 10
1 20
【输出样例】
1
【Hint】1-10之内无幸运数，1-20内只有19 这1个幸运数
2
合肥工业大学第十届程序设计大赛试题
C炸弹袭击
时限：1s
【题目描述】
H族的领地是一片富饶之地，有丰富的资源，无数的黄金。尽管异族侵略者被压制几百多年，他们并没有放弃对这片土地的渴望。最近，他们研制了一枚重磅炸弹。试图用它摧毁H族的防御工事。H族的防御工事由多个基地构成，侵略者试图用炸弹摧毁尽量多的防御基地，现在，他们急需你的帮助。如果你能为他们解决难题，会有巨大的奖励。（该炸弹的攻击范围是一个半径为r单位的圆）
【输入】
第一行为样例的个数T。
每个样例中有若干行，第一行为炸弹的攻击半径r，r有可能不是整数(1<=r<=100)
第二行是一个整数n，表示H族防御基地的个数(1<=n<=100)
接下来n行，每行有两个数，代表H族某个防御基地的坐标
【输出】
只有一个数，代表炸弹能最多摧毁的H族防御基地数量。
【输入样例】
1
1
3
1 0
0 1
4 0
【输出样例】
2
3
合肥工业大学第十届程序设计大赛试题
D．机器人
时限：1s
【题目描述】
Paul有n个重物堆在一条线上。该重物由1连续编号到n，最左边的物品编号为1，最右边的物品编号为n。已知每个物品的重量，第i个物品的重量为Wi公斤。Paul需要收集所有重物，但是他很懒。因此他打算用他全新的机器人。该机器人有两个不同的手臂 - 左手和右手，可以连续执行以下操作：
用左手拿最左边的重物，花费Wi·l能量单位（Wi是最左边的物品的重量，l是某一参数）。如果与之前的动作是一样的（上一次用左手），机器人须额外花费Ql的能量单位;
用右手拿最右边的重物，花费Wj·r能量单位（Wj是最右边的物品的重量，r是某一参数）。如果与之前的动作是一样的（上一次用右手），机器人须额外花费Qr的能量单位;
Paul想让机器人花费尽可能少的能量来帮他完成任务。他想让你来解决这个问题。你的任务是求解机器人收集所有重物可花费的最低能量值。
【输入】
第一行是一个数T，代表有T组输入样例
每个输入样例样例有两行：第一行是五个变量n,?l,?r,?Ql,?Qr (1?≤?n?≤?105;?1?≤?l,?r?≤?100;?1?≤?Ql,?Qr?≤?104)；第二行是n个重物的重量w1,w2….wn (1?≤?wi?≤?100)。
【输出】
每个样例只有1个数，代表机器人最小消耗的能量
【输入样例】
2
3 4 4 19 1
42 3 99
4 7 2 3 9
1 2 3 4
【输出样例】
576
34
4
合肥工业大学第十届程序设计大赛试题
E.求对数
时限：1s
【题目描述】
小寒正研究一个包含n个整数的数组a（a1,?a2,?...,?an），现在她想请你帮忙找到整数对 l,?r (1?≤?l?≤?r?≤?n)，且同时满足下列两个条件： 1.数组[l,r]区间中任意一个数都能被aj整除（l?≤?j?≤?r）；
2.r-l的值最大；
快来帮助小寒找出所有符合要求的整数对（l，r）。
【输入】
有多组测试数据，第一行为样例数T。其中每组数据符合下述格式：
第一行输入整数n（1?≤?n?≤?3·10^5）
第二行输入n个整数 a1,?a2,?...,?an (1?≤?ai?≤?10^6),相邻两个整数间有单个空格
【输出】
对于每组测试数据，输出格式如下
第一行输出两个整数分别表示符合要求的整数对的对数和r-l的值
第二行按升序输出符合要求的整数对的l值
【输入样例】 2
5 4 6 9 3 6
5 1 3 5 7 9
【输出样例】
1 3
2
1 4
1
5
合肥工业大学第十届程序设计大赛试题
F．斐波那契数列
时限：1s
【题目描述】
著名的斐波那契数列：Fn = Fn-1 + Fn-2 (F1=F2=1)，前几个斐波那契数为,1,1,2,3,5,8,13,21….
某一个整数可以拆成若干彼此不同的斐波那契数之和，比如13=13,13=5+8，13=2+3+8；16=1+2+13,16=1+2+5+8,16=3+13,16=3+5+8
现在求解这样一个问题，给定某个数值n，求有多少种方案可以把该数分解成若干彼此不同的斐波那契数之和
【输入】
第一行为T，表示样例数。
接下来T行，每一行一个样例，每个样例一个数N，1<=N<=10^18
【输出】
每个样例的答案。即该样例中N有多少种分法。
【输入样例】
2
13
16
【输出样例】
3
4
6
第二篇：程序设计报告三
20xx年春季学期
《程序设计专题》课程
实验报告
实验三 大数、枚举问题 专业班级：学生姓名： 学生学号： 12101020324
2012～
1
实验题目：数字三角形
实验数据储存结构设计
用一位数组来储存数据，即三角形每个位置的数字。
实验设计思想
利用枚举法，把三角形每个边上的情况全部枚举出来，然后输出每组满足条件的答案。
1．运行结果图
2．程序分析
程序有一个函数，有五层循环结构，利用循环的嵌套进行枚举，利用最内层的if判断是否满足条件输出。
2
实验题目：数字三角形最大路径
实验数据储存结构设计
利用二维数组来储存数据。
实验设计思想
把三角形从上到下进行加法计算，在最下面的那一行中寻找最大的数，该数就是最大路径。 实验结果及问题分析
1．运行结果图
2．程序分析
程序有一个函数，分三个部分，第一个部分利用双循环输入三角形的每个位置的数，第二部分同样利用双循环计算出由上到最底下那一行的每个位置的路径的和，第三部分利用双循环找到最大的数，也就是程序要求的结果。
3
实验题目：大整数加法
实验数据储存结构设计
利用两个二维数组来储存数据，一个储存源数据，一个处理处理后的数据。
实验设计思想
先利用-‘0’把源数据从字符串转化成真实数据，然后颠倒顺序，然后每位进行加法计算。 实验结果及问题分析
1． 运行结果图
2．程序分析
程序有一个函数，分为三部分，第一部分利用-‘0’得到数据的真值，然后利用循环进行每位的加法，在每次进行加法后判断是否需要进位并进位，然后进行下一位的加法，第三部分利用循环输出结果。 4
实验题目：大整数乘法
实验数据储存结构设计
用两个二维字符数组来储存输入的数据，用一个数组来储存并输出结果。
实验设计思想
把数据从字符类型转化为int类型，颠倒每位的顺序，然后模仿人的乘法的方法计算。 实验结果及问题分析
1．运行结果图
2．程序分析
程序有一个函数，分三部分，第一部分输入原始数据，然后转化为int类型的数据并颠倒顺序，第二部分进行每位的乘法，然后每位的乘法结束以后计算进位，第三部分找到最前的一位，倒序输出。 5
实验题目：大整数除法
实验数据储存结构设计
利用两个字符数组输入数据，然后再放到两个int数组中，计算结果放到另外一个int数组中。 实验设计思想
模仿人的计算方法，每次计算出一位上的结果，然后放到第三个数组中，得出最后的结果。 实验结果及问题分析
1．运行结果图
2．程序分析
程序有三个函数，第一个函数负责计算完每组数据以后清空所有的储存数据的位置，第二个函数负责用减法计算被除数从每位开始减去除数，最后返回减的次数，第三个是主函数，负责数据的输入，转换数据类型，调用另外两个函数，最后找到终止位置并在后面的位上补零，输出结果。 6
实验题目：斐波那契数列
实验数据储存结构设计
用一个大的字符数组来储存数列的值。
实验设计思想
利用数列的规律计算出数列里的每个的值，然后相应输出后三位。
实验结果及问题分析
1．运行结果图
2．程序分析
程序有二个函数，main函数负责输入数据，然后调用计算函数进行数列的计算，等到计算出要求的位数，停止调用，然后判断时候有前置的零，然后输出后三位的结果，计算函数中进行数据类型的转换，然后利用加法和进位计算数列中的每位的值。
7
实验题目：最小数
实验数据储存结构设计
利用两个字符数组储存数据，一个储存结果，一个暂存数据。
实验设计思想
每次去掉数中的一位，然后移位组成新的数放到结果数组中，如果新数较小，那么久复制到暂存数组中，再去掉一位，重复直至达到要去的位数。
实验结果及问题分析
1．运行结果图
2．程序分析
程序有一个函数，首先输入原来的数和要去掉的个数，然后逐位去掉，利用for放到新的数组中并与原数组进行比较，如果较小则保留，重复过程直至达到要求，然后输出结果
8
实验题目：求大整数的阶乘
实验数据储存结构设计
利用int数组来进行储存。
实验设计思想
先输入数据，然后利用基本的乘法的运算方法逐位进行运算，然后再输出。
实验结果及问题分析
1．运行结果图
2．程序分析
首先输入数据，然后利用循环每次让数组的每位成乘数，得出每位的结果后再进位，重复要求的阶乘次，最后得出结果并找到最终的位数，输出结果。
9
实验题目：赋值问题
实验数据储存结构设计
利用一个char数组标记变量是否赋值。
实验设计思想
在一个长度为26的数组中进行标记，若赋值则标为1，否则为0，即可找到赋值过的字母。 实验结果及问题分析
1．运行结果图
2．程序分析
程序有一个函数，先输入要输入的字符的组数，然后进行相应次的循环，每次循环找等号右边的字符是否被标记，如果被标记则左边字母也要标记，否则左边字母改为未标记，最后按顺序输出被标记位置对应的字母，并记录次数，如果没有输出则输出none。
10
………………………………………………………………………………………
本次实验总结体会
大数和枚举特别要求细心，在写程序和调试的时候要逐位的看是否正确，这样才能得到正确的程序。好的方法可以事半功倍，但是对我们的要求也更高。
11