2015 Multi-University Training Contest 6 Solutions

官方题解:2015 Multi-University Training Contest 6 solutions BY ZJU


 

 

 

1001 Average

HDU 5353:http://acm.hdu.edu.cn/showproblem.php?pid=5353

题意:n个人围成一圈,每对相邻两人可以且最多交换一个糖果,现求一个合法的交换顺序让所有人的糖果数相同(不能则输出NO)

\(1\leqslant n\leqslant 10^5\)

枚举第一人与第二人的三种交换情况。判断哪种能让糖果数相等

其他人若想要全部相等,按照贪心,剩下的交换情况便会固定。

注意全为0时不能交换。所以应把第一人与第二人什么都不做的情况放在最前面

 

 


 

 

 

1008 Hiking

HDU 5360:http://acm.hdu.edu.cn/showproblem.php?pid=5360

题意:邀请 \(n\) 个人去远足,但每个人都有一个条件:在他之前有至少 \(l_i\) 个人接受邀请,但不超过 \(r_i\) 个人接受邀请。一个人只要接受了就不能反悔,无论最后的结果是否满足条件。询问一个邀请顺序使最多的人接受邀请。

\(1\leqslant n\leqslant 10^5\)

贪心
先按 \(l_i\) 升序排列

然后对于当前已接受邀请人数 \(cnt\) ,取满足 \(cnt\geqslant l_i\)\(r_i\) 最小的人为下一个邀请目标

可以用优先队列来实现

 

 


 

 

 

1011 Key Set

HDU 5363:http://acm.hdu.edu.cn/showproblem.php?pid=5363

题意:一个集合S包含n个数1~n,当一个集合里数的和为偶数时这个集合被称作Key Set,现在问集合S有多少个非空子集是Key Set

\(1\leqslant n\leqslant 10^9\)

通过观察数据可以得出通项公式 \(a_n=2^n-1\)

用快速幂便可得出答案

 

 


 

 

(待续...)

Categories: ACM