Codeforces Round #505

A. Doggo Recoloring

题目描述：给定一个字符串，每次选择一个在字符串里面出现至少两次的字符，然后将这种字符变成那一种指定的字符，问最终这个字符串能否只剩一种字符。

solution
当长度为(1)是，答案是(Yes)，当长度大于(1)时，如果有字符至少出现两次，则答案为(Yes)。

时间复杂度：(O(n))

B. Weakened Common Divisor

题目描述：有(n)个数对，定义这(n)个数对的弱公约数(d)为对于每个数对，(d)至少是一个数的约数，求任意一个弱公约数。

solution
每个数对的最小公倍数的最大公约数((ans))的质因数一定是答案。求质因数时可以先求(sqrt{10^9})的质数，然后判断是否是最大公约数的质因数；也可以用(ans)与每个数对里的数求公约数（如果求了之后答案不是(1))，最后那个就是答案。

时间复杂度：(O(n))

C. Plasticine zebra

题目描述：给定一个由(w, b)构成的字符串，可以进行若干次操作，每次将字符串分成两部分，每部分分别翻转，使得最终的字符串中(b, w)交替的子串最长，输出长度。

solution
观察可知，最多只会进行一次操作。

时间复杂度：(O(n))

D. Recovering BST

题目描述：给定一个二叉排序树的中序遍历，把这棵树还原出来，使得树的相邻两个点的最大公约数不是(1)，问是否能还原。

solution
(dp)求出每个区间是否能成为左子树和右子树，枚举区间([L, R])内的一个位置(i)，如果(i)的左边能成为左子树，(i)的右边能成为右子树，则这个区间可以成为子树，如果(i)与(R+1)的数的最大公约数大于(1)，则([L, R])能成为左子树，类似的，如果(i)与(L-1)的数的最大公约数大于(1)，则([L, R])能成为右子树。最后整个区间能成为子树即可。

时间复杂度：(O(n^3))