2010年下半年每周集训之团队讨论赛2解题报告

2010年下半年每周集训之团队讨论赛2-by helihui

做的不多 写下做了的思路

A:数据视乎给弱了  直接暴力过掉了  不过时间有点多

然后就是

1.如果是奇数(以15为例),那么15当然可以拆为15+0(15除以1),7+8(15除以2)。当用15除以3时,商5,发现如果给5加上一个数,变6,减去一个数,变4,而4+6+5正好是15,当用15除以5时,商3,那么给3减去一个数是2,加上一个数是4,减去2个数是1,加上2个数是5,1+2+3+4+5=15。于是猜测,用15去除以从1,3,5,7,9。。。。能被几个整除就有几种拆分方法(但是要加上15/2和15/2+1的情况)

2.如果是偶数(以10为例),首先想一下,如果一个偶数能拆为连续数相加的话,第一种情况,奇数的个数比偶数个数多1或者少1,(如18=5+6+7,28=1+2+3+4+5+6+7,包括10是0+1+2+3+4),换句话说,一个偶数,必须拆成1,3,5,7,9个数相加,才有可能成立。比如10就不可能分成2个连续数相加。

第二种情况(像26=5+6+7+8)这种拆分成2个N次放个数的时候,主意6+7=5+8,因此,可以看成是13+2;仍然可以用这个数除以一个奇数获得。

综合以上2种情况,偶数的时候,仍然用这个偶数除以1,3,5,7,9。。。。能被几个整除就有几种拆分方法

网上解题  分析的比较好。

B:这个当时没怎么去想。是O(n)的时间  后来回去做了下  当时的思路可以过

也就是从头扫描,用一个变量控制奇偶p=1表示奇 p=1时候扫描升序中最大的加到sum里

一旦非升序那么就p=0 找降序中最小的  一旦非降序了 p=1升序找。。。一直到最后就可以 了

输出sum  OK答案出来了.

D:题其实很简单。题目理解成应该 矮的cow能看到高的cow  那么反过来高的cow也能看到矮的cow  也就是说输入数据的谁看说都无所谓。

处理方法:开始的时候将所有cow的高度初始化为最高  然后对于输入的两个端点之间的牛当然高度要减去1        一直这样处理  最后就是答案了 很简单吧  不过题目输入数据有两个相同的端点的情况  所以需要排重  排重光用数组不行  两个端点很大  我用C++ set容器了 呵~~~~

G:这个是很老的题目了  最长升序列长度即可  这个经典的题目就不讲了。


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

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

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