acm校赛题目+题解

《acm校赛题目+题解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、A.烤面包除了写题，zqs还喜欢烤面包。烤面包需要正反两面各烤一次，每个烤箱同时只能烤一个面包的一面，烤一面需要3分钟，现在他要烤N个面包，有N个烤箱，问烤完所有的面包需要多少时间？输入：有多组输入数据，第一行为一个数字case，代表有多少组输入数据（case<=20）。以下每组数据一行有2个整数N，M，代表需要烤N个面包，有M个烤箱（0<=N<=1000,1<=M<=1000）。输出：一共case行，每行一个整数对应该组数据烤完所有面包需要多少时间。样例输入：22133样例输出：126思路：　　该题需要分三种情况,第一种，没有面包，那自然不需要时间即为0,第二种面包不超过烤箱数量，那两次就

2、可以烤完全部面包，第三种情况就是面包比烤箱多，因为面包为两面，使所有烤箱都保持满载状态，最后一次可能会有部分烤箱用不到，但也必须有那一次，所以面包数X2除以烤箱数取整再加一，得数X3即可。此题最大陷阱就是，面包不可能同时两面被烤，不能单纯的想有两个烤箱一个面包一次就能烤掉。---------------------------------------------------------------------------B怒刷GPA众所周知，WM现在在清华读博，熟不知他为了报送刷分很久的。WM大一的时候成绩非常烂，我们学校的成绩满分是十分，没门成绩的得分是0到10中的一个数字，WM大一的时候

3、有N门课，每门课都得了一个不是很理想的分数，大二的时候开始奋发学习，现在告诉他大一的时候的成绩，他想知道他在后面的课程中连续得到多少个10分才能将平均分提高到9.5以上（包括9.5）。输入：有多组输入数据，第一行为一个数字case，代表有多少组输入数据（case<=20）。以下每组数据的第一行一个整数n，代表他们他一已经考了多少门课（n<=1000）。接下来一行n个数字，每个数字ci，代表第i门课他考了多少分（0<=ci<=10）。输出：一共case行，每行一个整数对应该组数据他需要再考多少个十分可以将平均分提高到9.5以上（包括9.5）。样例输入：2291018样例输出：03题解思路：　　

4、计算原本n门课的总分数j，设需要再考k次10分，判断(k*10+j)/(n+k)何时大于等于9.5，输出k即可。---------------------------------------------------------------------------C．排列问题描述：像所有的女孩子一样，LT讨厌排列，他现在向你寻求一个排列问题的答案。给你一个数字N（1<=N<10000），并且保证N的各个位上没有0.他想知道将N的每个位置上的数字全部拿出来，重新排列得到的所有数字的和是多少。比如122的所有排列为：122+212+221=555。注意相同的数字只需要计算一次。输入：有多组输入数据

5、，第一行为一个数字case，代表有多少组输入数据（case<=20）。以下case行每行包含一个正整数N（1<=N<10000），N的意义如上所述。输出：一共case行，每行一个整数对应N的所有排列得到的数字和。样例输入：212212样例输出：55533思路一：　　思路一：针对每一个case的数n，递归枚举每一种情况。把一个数看作一个字符串进行读入记为s，初始递归状态为dfs(“”)，维护一个全局变量vis数组来标识字符串的每一个元素有没有被访问过，在当前字符串str的长度小于s的长度时，i从0->s.size()枚举，如果当前元素没有被访问则把当前状态标记为已访问并dfs(str+s[i]

6、)，在每一句递归之后把当前元素标记为未访问。当str的长度等于s的长度时把字符串转换成数字，如果当前数字没有生成过则累加，并标记这个数字出现过，return递归函数。在所有的递归完成后输出结果。voiddfs(stringstr){if(str.size()==s.size()){inttemp=0;for(inti=0;i

7、]=true;dfs(str+s[i]);vis[i]=false;}}}思路二：　　对于寻找C题的思路，首先我们看两个数：122和123。可以看到：当n=122时，全排列有3种情况，即(3!/2!);当n=123时，全排列有6种情况，即3!。那么对结果与全排列得出的数字相比较，进而我们将很容易得到了如下公式：　　全排列的和=n的各位之和*全排列的情况数*digit/n的位数；这里有两点要声明：1.关于dig