codeforces round #618 题解

A. Non-zero

可以每次给一个元素+1,求和不为0且每个元素都不为0所需的最小操作次数
先把所有0都+1,再检查和,如果是0就再+1

B. Assigning to Classes

把数分为两组,求两组中位数之差的最小值。其实不管怎么分组,只有中间的两个数有用
思路是排序后取中间的两个数,但因为t=1e4,n=1e5,用O(nlogn)的排序不行,需要一种O(n)取中位数的方法
nth_element函数是algorithm库里的,其实是sort的一部分。nth_element(v.begin(),v.begin()+k,v.end()),作用是使得第k大的元素被放置到v.begin()+k位置上,其它元素顺序不保证(其实是快排:把比它小的放到左边,大的放到右边)

C. Anu Has a Function

f(x,y)=(x|y)-y,那么只有x[i]=1,y[i]=0的时候,结果的当前位是1.
因此对于所有数的某一位来讲,必须满足:
1.在这一位上,所有的数字中只有一个1
2.含有这个1的数字是第一个数
才能让这个1保留下来。
因此,要找到一个最大的数字,我们要尽可能保留一个更高位次的1。
从高到低枚举位数,如果这一位有且仅有一个1,那么将贡献这个1的数字作为第一个数,其它的数任意顺序即可

D. Aerodynamic

纸上画了画,发现图形满足对边平行且相等就可以。
黄学长:那不就是中心对称嘛……
所以判断一下图形是不是中心对称的就行。因为点是按照顺序给的所以很好写。

E. Water Balance

本质上是单调栈维护斜率,栈里放的是一个块,代表这个块被取了平均值。每次加入一个元素,看是否能给当前栈顶元素带来贡献,如果可以则加入块里,再观察是否能和下面的合并……不断合并最后输出就可以
写了一个很辣鸡的方法,期望复杂度O(nlogn),但是被卡了qwq有空补代码吧

点赞

发表评论

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