Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

Codeforces Round #628 (Div. 2)

Codeforces Round #628 (Div. 2)

比赛还有五十分钟才结束,但是后面那两道现在才不到30人过了的题对于我来说应该是不可做题,就先写总结了.(希望不会FST)

A. EhAb AnD gCd

,

题目要求就是要找

让a=1,b=x-1即可.

B. CopyCopyCopyCopyCopy

因为序列重复了n次,完全可以在每次重复中选序列中的一个数,这样就相当于可以不考虑顺序地选择数组成LIS,排个序后就是西电C语言期末考试真题.

C. Ehab and Path-etic MEXs

只要能让0 1 2这三个数不在一条路径上,就能让这棵树的答案达到2.

并且,对于任意一棵树,答案最小是2,因为总可以找到一条路径包括0和1.

除了一条链的情况,其他的都可以通过先给叶子连的边填上0 1 2构造出答案.

D. Ehab the Xorcist

异或和一定小于等于加和,这是因为异或和是"不进位的加法",异或和比加和少的部分就是本该进位的两位变成了0,所以当异或和>加和或者两者差值为奇数时,无解.

答案不会超过3,这是因为可以构造这样一个数组:[a,a,b],其中a为两者差值的一半,b为满足加和条件的唯一b.这样通过异或,可以损失掉两个a,即两者的差值,并且不会影响到加和的结果.

因为每一位是独立的,如果a和b的1位不重叠,可以把他们压缩为一个数,即(a|b).

(umi生日快乐!)

评论