【贪心/构造】AHSOFNU 新生训练 by hzwer

2016年6月11日1,2153

简单题系列

比赛地址http://acm.hust.edu.cn/vjudge/contest/view.action?cid=119385#overview

其实codeforces的题完全不需要题解吧

 

【cf432A】Choosing Teams 组队

总共有n个人,每个人最多参加5场比赛,现在给出每个人已经参加过的比赛次数,现在要组尽量多的队伍去继续参加比赛,每支队伍三个人,要求组成的队伍至少再参加k场比赛。

 

一眼题

 

【cf508B】Anton and currency you all know 最大偶数

交换n的某俩个数位,求其能成为的最大偶数

选择一个在最前面、比最后一个数字小的偶数交换若不存在,选择最后一个偶数,将其与最后一个数字交换

【cf401C】Team 01序列

构造一个01序列,包含n个0,m个1

要求不存在连续2个0,或3个1

【cf500C】New Year Book Reading 栈

一个人m天要读n本书每本书重量wi,每天读1本,他每天把要看的书x从栈里拿出来(拿起x上面的,拿出x,再把上面的书放回去),看完x后放到栈顶,问根据他的阅读顺序怎样初始化书的排列顺序能使他搬书的总重量最小,输出总重量

结论:初始把先看的书放在最上方

第一本书放栈顶显然没问题,考虑要阅读的第二本不同的书,显然放在第一本下面。

假设已经放了要看的前i-1本书,考虑第i本,如果插在前i-1本之中,把它拿出来显然更优,于是就能归纳出结论。

1-n最多凑出n-1种差值所以让前k+1项差值为1到k,后面的差值全为1

形如1 7 2 6 3 5 4这样差值是6 5 4 3 2 1

【cf235A】LCM Challenge 最大公约数

求三个不同的小于n的数字,使它们的lcm最大

 

显然是在接近n数内找三个两两互质的,由于懒得推公式所以可以小范围暴力一下

【cf468A】24 Game 24点

用1-n得出24点

 

思路就是用1-4得出24,剩下的互相抵消

发现每4个可以a+1,a+2,a+3,a+4可以消掉,加上中间俩个,减去两边两个,所以我讨论了模4后的4种情况

事实上可以分奇偶讨论。。a+1,a+2可以通过 *(a+2-(a+1))消去。。。


【cf639C】Bear and Polynomials 多项式

在差的绝对值为K范围内修改一个多项式Q的某一系数,使得Q(2)=0

 

先全部进位一下,然后找出最低位的1,不可能改动比它高位的系数

比它低位的系数依次枚举一下

注意超过2K就直接退出

【cf508E】Arthur and Brackets

给出一些括号,这个括号左括号的先后顺序确定,左右括号的距离的范围确定,构造一种合法的方案。

 

经过尝试构造后发现。。。

将括号的dis设小不会更劣

如(())变成()()更有利于加入其它的括号

于是从后往前依次考虑每个括号,使得它尽量包含少的括号

复杂度n^2

其实知道上面的结论以后,用个栈贪心即可,具体看下面第二个代码。。。

 

  • 江户川柯南2016年6月11日 下午11:12 回复

    Orz黄学长

    #1  
  • 某弱2016年6月16日 下午2:55 回复

    orz,黄学长今年高考如何?

    #2