Codeforces Round #435 (Div. 2)

A. Mahmoud and Ehab and the MEX
给一个n元素的非负整数集,每次操作可以选择增加或删除一个数,问最少需要几次操作,使得比x小的数都在集合中,且x本身不能出现在集合中。用set模拟。

B. Mahmoud and Ehab and the bipartiteness
给一个二分图,且这个二分图是一个数的结构,问最多加几条边,使得这个图还是二分图。
最多是|s| * |t| – (n-1),用二分图染色计算|s|,|t|即可。

C. Mahmoud and Ehab and the xor
求n个数,使得这n个数的异或和为x。不存在输出“NO”,否则输出“YES” 以及n个数(任意一种情况)
NO 只有一种情况,n = 2, x = 0;
令\(pw = 2 ^ {17}, pw > 10 ^ {5}\) 然后我们从1,一直输出到n-3; 异或具有的性质是\(a \oplus b \oplus b = a\) 令他们的异或和为y。如果x=y,那么输出 \(pw, pw*2, (pw*2) \oplus pw\)
如果x!=y,那么输出 \(0, pw, pw \oplus x \oplus y\)。

D. Mahmoud and Ehab and the binary string
交互题,注意刷新,在不超过十五次的询问下,找出字符串的任意一组0和1的位置,每次询问会得到询问串与原串的汉明距离,保证输出至少存在一个1和一个0。
设每次询问得到的结果是有多少个正确的位置, 即 n-汉明距离。
先问1111…得到ans1,第二次问01111…得到ans2,如果ans1>ans2,那么第一个位置一定是1,否则是0,然后二分的在剩余长度里去找另一个数。

发表评论

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

Foreignbill