acm校赛题目 题解.doc

烤面包
除了写题,zqs还喜欢烤面包。
烤面包需要正反两面各烤一次,每个烤箱同时只能烤一个面包的一面,烤一面需要3分钟,现在他要烤N个面包,有N个烤箱,问烤完所有的面包需要多少时间?
输入:有多组输入数据,第一行为一个数字case,代表有多少组输入数据(case<=20)。
以下每组数据一行有2个整数N,M,代表需要烤N个面包,有M个烤箱(0<=N<=1000,1<=M<=1000)。
输出:一共case行,每行一个整数对应该组数据烤完所有面包需要多少时间。
样例输入:
2
2 1
3 3
样例输出:
12
6
思路:
该题需要分三种情况,第一种,没有面包,那自然不需要时间即为0,第二种面包不超过烤箱数量,那两次就可以烤完全部面包,第三种情况就是面包比烤箱多,因为面包为两面,使所有烤箱都保持满载状态,最后一次可能会有部分烤箱用不到,但也必须有那一次,所以面包数X2除以烤箱数取整再加一,得数X3即可。此题最大陷阱就是,面包不可能同时两面被烤,不能单纯的想有两个烤箱一个面包一次就能烤掉。
---------------------------------------------------------------------------
B
怒刷GPA
众所周知,WM现在在清华读博,熟不知他为了报送刷分很久的。
WM大一的时候成绩非常烂,我们学校的成绩满分是十分,没门成绩的得分是0到10中的一个数字,WM大一的时候有N门课,每门课都得了一个不是很理想的分数,大二的时候开始奋发学****现在告诉他大一的时候的成绩,()。
输入:
有多组输入数据,第一行为一个数字case,代表有多少组输入数据(case<=20)。
以下每组数据的第一行一个整数n,代表他们他一已经考了多少门课(n<=1000 )。
接下来一行n个数字,每个数字ci,代表第i门课他考了多少分(0<=ci<=10)。
输出:
一共case行,()。
样例输入:
2
2
9 10
1
8
样例输出:
0
3
题解思路:
计算原本n门课的总分数j,设需要再考k次10分,判断(k*10+j)/(n+k) ,输出k即可。
---------------------------------------------------------------------------

问题描述:
像所有的女孩子一样,LT讨厌排列,他现在向你寻求一个排列问题的答案。
给你一个数字N(1<=N<10000),并且保证N的各个位上没有0.
他想知道将N的每个位置上的数字全部拿出来,重新排列得到的所有数字的和是多少。
比如122的所有排列为:122+212+221=555。注意相同的数字只需要计算一次。
输入:有多组输入数据,第一行为一个数字case,代表有多少组输入数据(case<=20)。以下case行每行包含一个正整数N(1<=N<10000),N的意义如上所述。
输出:
一共case行,每行一个整数对应N的所有排列得到的数字和。
样例输入:
2
122
12
样例输出:
555
33
思路一:
思路一:
针对每一个case的数n,递归枚举每一种情况。
把一个数看作一个字符串进行读入记为s,初始递归状态为dfs(“”),维护一个全局变量vis数组来标识字符串的每一个元素有没有被访问过,在当前字符串str的长度小于s的长度时,i从0 -> ()枚举,如果当前元素没有被访问则把当前状态标记为已访问并dfs(str+s[i]),在每一句递归之后把当前元素标记为未访问。当str的长度等于s的长度时把字符串转换成数字,如果当前数字没有生成过则累加,并标记这个数字出现过,return递归函数。在所有的递归完成后输出结果。
void dfs(string str)
{
if(()==())
{
int temp=0;
for(int i=0;i<();i++)
temp=temp*10+str[i]-48;
if(!exist[temp])
{
ans+=temp;
exist[temp]=true;
}
return;
}
for(int i=0;i<();i++)
{
if(!vis[i])
{
vis[i]=true;
dfs(str+s[i]);
vis