2010年下半年每周集训之组队常规训练6解题报告

2010年下半年每周集训之组队常规训练6-by xzc

貌似这边还没写过解题报告,睡了一觉,来写一个,这段时间很多事,随便写了,写得不好不要介意。

很显然,今天的训练很水。

A:Who's in the Middle

排序,输出中间的数,水题,over

B:简单组合问题

DP,最优子结构+子问题重叠,果断选择DP处理

题目要求你根据构造集合,然后输出你能够构造出的集合的种数

输入m和r,m代表可以提供的元素数量,r代表你所构造的集合中的元素个数

集合中的元素明显无序且不会重复:

{a,a,a,a};
{a,a,a,b};
{a,a,b,b};
{a,b,b,b};
{b,b,b,b};

类似这个例子,就是只有两个可以用的元素,即a和b,每个构造的集合中的元素个数为4

所以上面的这个例子的m=2,r=4;输出能够构造出的集合种数为5

我的做法是构造一个r行m列的二维数组,初始化全部为0;

初始化第r行的数组元素为m,m-1,…,1;

然后自底向上加,第x行第y列的元素等于从第x+1行第y列到第x+1行第m列的元素之和

最后的结果就是数组的第一行第一列的值

C:A变B

这个也是水题,就是把输入的两个数变成二进制,然后看总共有几位是不一样的就可以了

D:Count The Number

这个题目思路解法和B一样,就不说了

E:Your Ride Is Here

水题,每组数据有两行字符,题目限制全部为大写字母

将每个字符转换成数字,A是1,B是2,C是3,以此类推至Z

然后每个数字相乘,对47取余,如果两行字符串这样处理的结果一样那么输出GO

否则,输出STAY

F:Milking Cows

题目要求解出两个时间,第一个时间是持续有人在挤奶的最长时间段,第二个时间是没有在挤奶的空闲时间段,每组数据先输入一个t,然后输入t行数据,每行数据两个x,y;表示一个挤奶的时间段,表示x至y的时间段里面有人在挤奶;

解法是对x排序,贪心策略,如果y<对应的x,那么两个时间段合并为一个时间段,最后输出最长的忙碌时间段和空闲时间段就OK了


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.