| ||
|
|
2010年下半年每周集训之团队讨论赛2
|
做的不多 写下做了的思路
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:这个是很老的题目了 最长升序列长度即可 这个经典的题目就不讲了。