16/10/9 题解

  • 内容
  • 评论
  • 相关

比赛名称平顶山学院16-17年第一学期第一次比赛

参赛人员:         ACM算法公关部大二成员       

    出 题 人:           陶林娟、徐成东            

比赛时间: 2016年10月8日19:00-10月15日19:00

归档时间:             2016年10月12日          

计算机学院(软件学院)制

  • 题目描述

题目名称:A + B Problem II

题目来源:HDOJ

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.

输入

A test case with N = 0 terminates the input and this test case is not to be processed.

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.

输出

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.

样例输入

2

1 2

112233445566778899 998877665544332211

样例输出

Case 1:

1 + 2 = 3

 

Case 2:

112233445566778899 + 998877665544332211 = 1111111111111111110

  • 考核知识点

大数相加问题。

  • 常见误区

对进位标记时注意P的初始化和退出循环后最后一次相加的进位。

  • 解题思路

用字符串读入,然后存入数组。通过数组模拟加法运算,进位,最后得到数组C,用循环输出即可。.

  • 参考答案(附关键注释)

 

  • 整理者

学号姓名 :151210125  程常虹

院系 :计算机学院(软件学院)

专业班级:15计科1班

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  • 题目描述

题目名称:Let the Balloon Rise

题目来源:HDOJ

Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.

 

This year, they decide to leave this lovely job to you.

输入

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.

 

A test case with N = 0 terminates the input and this test case is not to be processed.

输出

For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.

样例输入

5

green

red

blue

red

red

3

pink

orange

pink

0

样例输出

red

pink

  • 考核知识点

模拟题

  • 常见误区

注意次数都一样的时候输出第一个

  • 解题思路

暴力解!使用结构体将彩球和出现次数绑定,然后每输入一个单词就遍历一遍如果存在就在次数上加一,没有的话添加上这个单词。最后找出次数最多的输出。

  • 参考答案(附关键注释)

 

  • 整理者

学号姓名 :151210220  胡娇

院系 :计算机学院(软件学院)

专业班级: 15计科2班

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  • 题目描述

题目名称:milk

题目来源:HDOJ

Ignatius drinks milk everyday, now he is in the supermarket and he wants to choose a bottle of milk. There are many kinds of milk in the supermarket, so Ignatius wants to know which kind of milk is the cheapest.

 

Here are some rules:

  1. Ignatius will never drink the milk which is produced 6 days ago or earlier. That means if the milk is produced 2005-1-1, Ignatius will never drink this bottle after 2005-1-6(inclusive).
  2. Ignatius drinks 200mL milk everyday.
  3. If the milk left in the bottle is less than 200mL, Ignatius will throw it away.
  4. All the milk in the supermarket is just produced today.

 

Note that Ignatius only wants to buy one bottle of milk, so if the volumn of a bottle is smaller than 200mL, you should ignore it.

Given some information of milk, your task is to tell Ignatius which milk is the cheapest.

输入

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.

Each test case starts with a single integer N(1<=N<=100) which is the number of kinds of milk. Then N lines follow, each line contains a string S(the length will at most 100 characters) which indicate the brand of milk, then two integers for the brand: P(Yuan) which is the price of a bottle, V(mL) which is the volume of a bottle.

输出

For each test case, you should output the brand of the milk which is the cheapest. If there are more than one cheapest brand, you should output the one which has the largest volume.

样例输入

2

2

Yili 10 500

Mengniu 20 1000

4

Yili 10 500

Mengniu 20 1000

Guangming 1 199

Yanpai 40 10000

样例输出

Mengniu

Mengniu

  • 考核知识点

结构体的应用以及结构体排序。

  • 常见误区

无。

  • 解题思路

首先建立一个结构体,结构体的成员有牛奶名称,买这种牛奶每天的平均花费,这种牛奶一盒的体积。定义一个结构体数组用来存储n种不同牌子的牛奶的信息,题目中说喝的牛奶生产出来不超过五天,那么如果牛奶的体积大于1000毫升,就直接按五天算,若牛奶的体积本身小于200,直接忽略该品牌的牛奶,其它情况直接用牛奶体积除以每天喝的牛奶的体积,就是喝的天数,然后算出每种牛奶每天的平均消费,之后进行结构体排序,按照每天平均消费从小到大牌,如果两种牛奶每天平均花费是一样的,按照题目要求,我们要再进行牛奶体积从大到小排序,最后输出结构体数组第一个元素的牛奶名称成员即为答案。

  • 参考答案(附关键注释)

 

  • 整理者

学号姓名 :151210107  温雅新

院系 :计算机学院(软件学院)

专业班级: 15计科1班

 

 

 

 

 

 

 

  • 题目描述

题目名称:Big Number

题目来源:HDOJ

As we know, Big Number is always troublesome. But it's really important in our ACM. And today, your task is to write a program to calculate A mod B.

To make the problem easier, I promise that B will be smaller than 100000.

Is it too hard? No, I work it out in 10 minutes, and my program contains less than 25 lines.

输入

The input contains several test cases. Each test case consists of two positive integers A and B. The length of A will not exceed 1000, and B will be smaller than 100000. Process to the end of file.

输出

For each test case, you have to ouput the result of A mod B.

样例输入

2 3

12 7

152455856554521 3250

样例输出

2

5

1521

  • 考核知识点

大数对整数取余数学题

  • 常见误区

  • 解题思路

将大数用字符数组储存,根据秦九韶公式按每一位来计算

举个例子,1314 % 7= 5

由秦九韶公式:

1314= ((1*10+3)*10+1)*10+4

所以有

1314 % 7= ( ( (1 * 10 % 7 +3 )*10 % 7 +1)*10 % 7 +4 )%7;

  • 参考答案(附关键注释)

 

  • 整理者

学号姓名 :151360205  徐帅武

院系 :信息工程学院

专业班级: 15物联2班

 

 

 

 

 

 

 

 

 

 

 

 

  • 题目描述

题目名称:吃糖果

HOHO,终于从Speakless手上赢走了所有的糖果,是Gardon吃糖果时有个特殊的癖好,就是不喜欢将一样的糖果放在一起吃,喜欢先吃一种,下一次吃另一种,这样;可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完?请你写个程序帮忙计算一下。

输入

第一行有一个整数T,接下来T组数据,每组数据占2行,第一行是一个整数N(0<N<=1000000),第二行是N个数,表示N种糖果的数目Mi(0<Mi<=1000000)。

输出

对于每组数据,输出一行,包含一个"Yes"或者"No"。

样例输入

2

3

4 1 1

5

5 4 3 2 1

样例输出

No

Yes

  • 考核知识点

简单的找规律数学问题。

  • 常见误区

规律可能找的有点小问题和最后输出的数据类型问题,最后的数据格式应该注意一下,要用long long int型来计算糖果的总数。

  • 解题思路

这道题可分成奇偶数来分别看待。首先如果是偶数的话,则其中最大的某糖果的数目应该小于等于总糖果数的一半,若是奇数,则其中最大的某糖果数应该是小于等于总糖果数对2取整再加上1。还有另一种比较简单的做法,就是无论糖果的奇偶数如何,都可以先令糖果总数加上1再对2取整.值得注意的是,因为糖果数较大,应用longlongint型的数来计算糖果总数。

  • 参考答案(附关键注释)

 

  • 整理者

学号姓名 :151210242 陶林娟

院系 :计算机学院(软件学院)

专业班级: 15计科2班

 

 

 

 

 

 

 

 

 

  • 题目描述

题目名称:圆桌会议

题目来源:HDOJ

HDU ACM集训队的队员在暑假集训时经常要讨论自己在做题中遇到的问题.每当面临自己解决不了的问题时,他们就会围坐在一张圆形的桌子旁进行交流,经过大家的讨论后一般没有解决不了的问题,这也只有HDU ACM集训队特有的圆桌会议,有一天你也可以进来体会一下哦:),在一天在讨论的时候,Eddy想出了一个极为古怪的想法,如果他们在每一分钟内,一对相邻的两个ACM队员交换一下位子,那么要多少时间才能得到与原始状态相反的座位顺序呢?(即对于每个队员,原先在他左面的队员后来在他右面,原先在他右面的队员在他左面),这当然难不倒其他的聪明的其他队友们,马上就把这个古怪的问题给解决了,你知道是怎么解决的吗??

输入

对于给定数目N(1<=N<=32767),表示有N个人,求要多少时间才能得到与原始状态相反的座位顺序(reverse)即对于每个人,原先在他左面的人后来在他右面,原先在他右面的人在他左面。

输出

对每个数据输出一行,表示需要的时间(以分钟为单位)。

样例输入

4

5

6

样例输出

2

4

6

  • 考核知识点

数学模拟题

  • 常见误区

不知道圆要分为两部分求逆序。

  • 解题思路

假设一个直线上站着n个人,则一个人左右互换==n个人逆序排列,共需要n*(n-1)/2;

一个圆上的人使他的左右人互换,可以分为两部分;

将圆环分尽量为相等的两段,分别移动。

证明如下:

设n为总长度,分为两段,长度分别为a,b。

总次数:=a*(a-1)/2+b*(b-1)/2=a*(a-1)/2+(n-a)*(n-a-1)/2=(2*a^2-2*n*a+n^2)/2。

其中n为常量,a为变量。二次曲线开口向上,最小值对应的a=-(-2*n)/(2*2)=n/2。

  • 参考答案(附关键注释)

 

  • 整理者

学号姓名 :151210132 许娜

院系 :计算机学院(软件学院)

专业班级: 15计科1班

 

 

 

 

 

 

 

 

 

 

 

 

  • 题目描述

题目名称:钱币兑换问题

题目来源:HDOJ

在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

输入

每行只有一个正整数N,N小于32768。

输出

对应每个输入,输出兑换方法数。

样例输入

2934

12553

样例输出

718831

13137761

  • 考核知识点

数学规律,完全背包。

  • 常见误区
    • 3分可分成2分和1分,2分可以分成1分。
    • 先找3分的个数,再找2分的个数。
    • 运行前面的时候把全是1分的考虑进去了。
  • 解题思路

首先找出全是三分的个数,然后找出在3分个数不同的情况下2分的个数,因为2分可用1分来代替,所以总数减去3分后二分的个数就是在3分2分1分都存在的情况下的情况数,此外还要加上减去3分外全是2分的个数。

  • 参考答案(附关键注释)

 

 

  • 整理者

学号姓名 :151360207  杨其道

院系 :信息工程学院

专业班级:15物联网2班

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  • 题目描述

题目名称:取石子游戏

题目来源:HDOJ

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

输入

输入有多组.每组第1行是2<=n<2^31. n=0退出.

输出

先取者负输出"Second win". 先取者胜输出"First win". 参看Sample Output.      样例输入

2

13

10000

0

样例输出

Second win

Second win

First win

  • 考核知识点

斐波那契数列,数学思维。

  • 常见误区

错找规律导致答案错误。

  • 解题思路

一般碰到这种题都是找规律的,一般把前几个数找一找有没有共同的规律,就能找到解题方法,切记每个数据都一定要算对。

  • 参考答案(附关键注释)

 

  • 整理者

学号姓名 :151210104  郭旭东

院系 :计算机学院(软件学院)

专业班级: 15计科1班

 

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注