Educational codeforces round 75 题解

前排吐槽,为什么最近codeforces的比赛变得这么频繁=。=

昨天晚上十一点开始比赛,今天还得早起,直接导致傻一天(

A. Broken Keyboard

sb水题,根据题意,如果某个字母重复了两次(如aa),并不能确定这个字母所在的键是好还是坏。
如果某个字母单个出现(如bab中,a单独出现),则可以证明a一定是好的。

B. Binary Palindromes

水题,分别统计0和1的数目,贪心瞎搞

C. Minimize The Integer

一个重要的结论:不管如何变动,奇数之间的相对位置不变,偶数之间的相对位置不变。
于是就可以用类似于归并排序的方式,构造出一个最小的数字。

D. Salary Changing

一道写跪的贪心(说起来为什么这几道题都是贪心)
看数据范围能知道是二分,主要思想是二分答案,每次尝试不同的工资,check是否能满足条件。
check的方式:将每个人按照左端点排序,由大到小选取n/2+1个人,使得他们的工资>=当前询问值,其他人取左端点。具体的代码里有注释。


后排恭喜黄学长刷新最高分记录(撒花

《Educational codeforces round 75 题解》

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注