Codeforces Round #764 (Div. 3)

A.Plus One on the Subset

每次选择任意个数字，将其值+1，那么最少需要多少次可以让所有数字相等，显然我们不需要动最大的那个数，答案就是 $maxa_{i} - mina_{i}$

B.Make AP

给出三个正整数a,b,c,我们能否在不改变a,b,c的顺序的前通下，将其中某个数乘上一个正整数，使得这三个数构成等差数列？那么只需要改变其中一个数，我们分3种情况讨论就行了，假如改变a，那么c - b即为公差，由此得到等差数列中的 $a^{‘}$ ,看a能否得到它就可以了

C.Division by Two and Permutation

给我们n个数，我们可以将它们不断除2若干次，能否得到一个1-n的排列，那么对于每个数我们首先对其不断除2使其小于n，之后，我们从n到1枚举，如果i的个数大于1，那么我们就对i除2，使得值为i的数只有一个，最后我们统计一下1-n,是否每个数的个数都是1就行了

D.Palindromes Coloring

给我们一个长度为n的字符串，k种颜色，那么我们可以将其中任意的字符染成k种颜色中的一种或者不染色，但是对于每种颜色都要有字符染成这种颜色，对于染成同一种颜色的字符，我们可以任意的交换，使其构成一个回文串，如果不能构成回文串，就不能这样染色，那么最后我们会得到k个回文串，那么这k个回文串中的最小长度最大是多少？

那么首先我们统计一下每个字符的数量，那么我们每次给这k个字符串每个发一对相同字符直到不能都发一对相同字符，那么此时每个字符串的数量是相同的，我们手中会有0到k-1对相同字符，和0到26个单个字符，我们无法再给这k个字符串每个2个相同字符，我们知道每个回文串中最多只有一个单个字符，那么我们只需要判断手中的字符能否给这k个字符串都发一个字符即可

E.Masha-forgetful

给我们n个长度为m的字符串和一个目标字符串，我们能否将目标字符串分解成一个个互不相交的连续长度至少为2的子字符串，使得任意一个子字符串都可以在这n个给定字符串中匹配到？

那么我们思考以下问题

每次匹配的时候是否匹配的越长越好，显然不是，考虑以下样例 123411 111451 111161 123456 第一次最长匹配到“1234”，第二次“45”，那么我们就无法匹配6了

那么是不是每次匹配的长度越短越好呢，也就是每次都匹配长度为2，考虑以下样例 123111 456111 123456 如果我们第一次匹配了“12”，就没有办法匹配“3”了，因为长度至少为2，此时第一次必须匹配3个那么由此我们可以想到对于任意一个长度的字符串，我们都可以将其划分为若干个长度为2和3的字符串’

但是对于一个长度为5的字符串，假如我们第一次匹配了3个，而必须匹配2个才有解，就会导致答案错误，那么我们如何匹配才不会影响后面的匹配呢？考虑每次2种选择肯定是不行的

对于一个长度为n的问题，如果我们知道后面2个字符是有解的，我们就只需要判断前n-2个字符是否有解，如果没有解，我们判一下前n-3字符是否有解我们定义f数组，f[i]表示上一次匹配结束的位置，f[i]是有解当且仅当f[i - 2]有解且i - 2 + 1到第i个字符是有解的或者f[i-3]有解且i - 3 + 1到第i个字符是有解的。

那么我们就需要将给出的字符按找2个或者3个的长度如何存起来，便于我们快速查找，可以用map哈希，带log也是可以的，那么直接用字符串哈希也是可以的，那么使用字符串哈希值得注意的是怎么解决冲突，在此就不提了

F.Interacdive Problem

这是一个交互题，交互题大多数都是二分，反正每个交互题都得找规律，废话。

不想说题意了

一个数字c初始可能是[1, n - 1]，我们将它加上一个数字c，那么就会变成[c + 1, n - 1 + c]，那么如果初始数大于等于n - c，那么给得到数就会是1，否则此数原来就是[1, n - c - 1]。由此我们可以知道我们将原题的的规模缩小了，锁定在了一个更小长度的区间里，那么此问题明显具有两段性，于是我们便可以二分区间长度，就可以在10次以内解决这个问题。

假设答案在[l, r]中，我们询问一个可以使得区间中点mid恰好是n的倍数的数x，那么如果当前得到的数大于上次的到的数，那么l = mid + x，否则r = mid - 1 + x，我们每次缩小后的区间要么完全落于n的倍数左边，或者右边(包含端点)，区间中点必然不是n的倍数，那么使得区间中点恰好是n的倍数的数也就必然不会是n

G.MinOr Tree

删去若干条边得到一棵树，使得边权的or值最小

删边显然不是给人做的，我们考虑加边，这种问题（or, and, xor）一般都是按位贪心，我们考虑从高位向低位贪心，将当前位置为0，如果我们使用当前位为0的边可以使得到一棵树（至于更高位，我们已经判断过如何最优，更高位k为0，那么这一位为1的边肯定也是不用的），那么此位就可以为0，否则此为必须为1,就可以了