Codeforces Global Round 1

Codeforces Global Round 1

题解：The Editorial of the First Codeforces Global Round

code1083，A：其实mod 2计算一下就行了

B：删掉最长的k-1段，sort

C：

Code Blocks？x是a的二进制最高位，

考虑对于a!=2^(x+1)-1，一定可以找到一个c<a，使得c&a=0，并且c xor a=2^(x+1)-1，那么gcd就是2^(x+1)-1了。已经最大

对于a=2^(x+1)-1，gcd(a&b,a^b)=gcd(b,a-b)=gcd(a,b)，所以，gcd最大是a的最大因数（除了自己），并且由于b<a，把b取到这个因数即可。

xcode？D：

发现，对于三个[x,x+1,x+2]，其实贡献等价于:[x,x,x],[x+1,x+1,x+1],[x+2,x+2,x+2]

所以，不妨对于形如[x,x+1,x+2]的只保留小于等于2个即可

codeforces官网，设f[i][t1][t2]表示，前i个，有t1个[i-1,i,i+1]，t2个[i,i+1,i+2]的最大值

那么枚举一个合法的t3,就是[i+1,i+2,i+3]的个数，对于剩下的i+1，直接[i+1,i+1,i+1]尽量拼凑即可。（因为后面不会再用到i+1了）

转移到f[i+1][t2][t3]

codeforces div3，（这样设的好处是，可以明确得到需要决策的剩下个数，并且对于i以后不会再考虑，所以[i,i,i]直接放就可以了）

E：

这种：c(i)'=c(i-1)+c(i+1)-c(i)的相邻两项关系，我们联想到，差分数组也是相邻两项的关系

codeforces注册。尝试一下，可以得到：

就是发现其实就是差分数组的临项交换

那么，可以转化过去，等价于，s1=t1并且差分数组排序后相等。

F：

（比赛时根本就没看到这里。。。其实题目并不难）

就是给出dfs序，在dfs序在[l,r]的叶子中找到距离v最小的距离

两种思路：

1.发现，如果固定1为根，那么每个点距离1的dis放进线段树，就是一个区间求min操作

根不定？离线+换根！

2.根不定？在线+分类讨论子树关系，相应的加上到根的距离或者减去到根的距离（大概区间会分成三段）

G：

分类讨论的博弈论（具体细节看题解）

首先发现初始白点可以等价变成4个空点的事实。然后图上就都是空点了。

发现这是树上的“三子棋”，规模比较小，手玩之后从度数考虑下。

1.如果有一个点有大于等于4的度数，那么先手必胜

2.如果一个点度数为3，并且两个儿子度数都不小于2，那么必胜

　　把这种情况也考虑到。

　　进一步，如果有大于等于3个有3个度数的点，那么也是先手必胜。

3.所以剩下的只用考虑小于等于2个3度数的点了

　　①一个3度数：就是2的考虑方法。

　　②两个3度数：如果存在一个子图呈“骨头”形，并且这个“骨头”总点数是奇数，那么先手必胜

4.剩下的都是平局（什么**游戏，后手必不胜啊。。）

H：

咕咕咕