Codeforces Round #843 (Div. 2)A-D

好久没写cf题解了，因为最近懈怠了加期末考试补题的时候被大幅度摧残，哭哭。就是一直wa，人麻了。

A：

题意：

最近卡西米尔决定给自己弄三只水豚。园丁甚至想到了它们的名字，并把它们写在一张纸上。每只水豚的名字是由字母“a”和“b”组成的非空行。

用a、b和c行来表示水豚的名字。然后卡西米尔把非空的a、b和c行写在一行中，不带空格。例如，如果水豚的名字是“aba”，“ab”和“bb”，那么园丁写下的字符串看起来就会是“abaabbb”。

园丁想起了一个有趣的性质:要么字符串b在字典上同时不小于字符串a和c，要么字符串b在字典上同时不大于字符串a和c。换句话说，要么a≤b且c≤b被满足，要么b≤a且b≤c被满足(或者可能同时满足这两个条件)。这里≤表示字符串的字典“小于或等于”。因此，a≤b意味着字符串必须相等，或者字符串a在字典中的位置必须比字符串b更早。有关此操作的更详细解释，请参阅“Notes”部分。

今天，园丁看了看他的笔记，意识到他想不起那些名字了，因为上面没有空格。他不再确定是否可以恢复原始字符串a、b和c，所以他想找到满足上述属性的任意三联体名称。

想法：想法其实比较简单，我们发现我们只需要让中间部分字典序一定要大于等于前后或者小于等于字典序。那么我们很容易想到，我们只需要纠结中间部分就好了。如果我们能从2--n-1部分找到一个a，那么我们让第二部分只有一个a，这样一定会是最小的字典序。如果我们不能找到这样的字母，我们只需要把2--n-1当成一个部分，这样一定会是最大的部分，因为我们可以肯定的是2这个位置的字母一定会是b，b开头的越长字典序越大。解答结束。

代码如下：

B:

题意：

园丁Kazimir Kazimirovich有一个n个整数的数组c1,c2，…，cn。

他想检查原始数组是否有两个不同的子序列a和b，其中f(a)=f(b)，其中f(x)是序列x中所有数字的位或。

序列q是p的子序列，如果q可以通过删除几个(可能是全部或全部)元素从p中获得。

如果两个子序列的元素在原始序列中的索引集不同，则认为两个子序列不同，也就是说，在比较子序列时不考虑元素的值。

想法：

其实简单来说这题的题意是我们选一个p序列，然后把p序列的数字全都或起来，然后选一个p序列的子序列q，把q序列的数字全都或起来。最后如果数字是相等的我们就认为这两个序列是相等的。

由于是序列而不是子串，因此我们最贪心的方法就是让p序列包含全部元素，然后q从中选一个剔除，这是最优的方法。那么我们的问题就转化成了，我们只需要选择一个元素剔除掉然后不影响结果就是yes，即我们只需要寻找一个元素是否它当前包含的所有位都出现过不止一次。

代码：

C：

题意：

Petya和他的朋友，机器人petya++，喜欢解决令人兴奋的数学问题。

有一天，petya++想出了数字n和x，并在黑板上写下了如下等式:

N & (N +1) &…& m=x，

其中&表示按位AND操作。然后他建议他的朋友Petya找到这样一个最小m (m≥n)，使棋盘上的等式成立。

不幸的是，Petya无法在脑海中解决这个问题，他决定求助于电脑。他很快编写了一个程序，找到了答案。

你能解决这个难题吗?

想法：

一个分类讨论的模拟。我们首先先明确四种情况：

按位

如果n当前位为0，而x当前位为1时候，我们可以发现此时是不可能的情况，因为0无论或上任何数都是0，此时情况不成立。

如果n当前位为0，而x当前位为0时候，我们可以发现对结果没任何影响，即此刻的最大值这一位取0也好，取1也好。

如果n当前位为1，而x当前位为1时候，我们可以发现我们最大的数字这一位肯定要是1，而且前面不能有任何的进位行为，不然在这个过程中会产生这一位有些是0的情况。

如果n当前位为1，而x当前位为0，我们可以发现最大位一定要有变位的经历，即要选择在前面某一位加上1，使其有个在这一位变0的过程，那么我们通过看前后可以提前知道，只有两位都是0的时候可以随意变，所以我们此时需要让两位都是0的时候那一位变成1，但我们此刻需要注意的是，我们要比较一下这一位是不是比我们记录的最低位的11大，如果大的话不符合3.但我们其实只需要比较一次，因为一旦出现10之后，我们就发现不能再出现x出现1的情况了，因为此时的最大数字在低位一定会出现0，所以出现这种情况我们直接-1就好了。

所以其实这题就是按情况模拟，代码如下：

D：

题意：

火星是一种不同寻常的蜘蛛的家园——二元蜘蛛。

现在，火星科学家正在观察一群n只蜘蛛，其中第1只有ai条腿。

有些蜘蛛彼此是朋友。也就是说，如果gcd(ai,aj)≠1，则第i个蜘蛛和第j个蜘蛛是朋友，即存在某个整数k≥2，使得ai和aj同时被k除而无余数。这里gcd(x,y)表示整数x和y的最大公约数(gcd)。

科学家们发现蜘蛛可以传递信息。如果两只蜘蛛是朋友，那么它们可以在一秒钟内直接传递信息。否则，蜘蛛必须将消息传递给他的朋友，他又必须将消息传递给他的朋友，依此类推，直到消息到达接收者。

让我们看一个例子。

假设一只有八条腿的蜘蛛想要向一只有15条腿的蜘蛛发送一条信息。他不能直接做，因为gcd(8,15)=1。但他可以通过有六条腿的蜘蛛发送消息，因为gcd(8,6)=2和gcd(6,15)=3。因此，消息将在两秒钟内到达。

现在，科学家们正在观察第s只蜘蛛是如何向第t只蜘蛛发送信息的。研究人员有一个假设，蜘蛛总是以最佳方式传递信息。出于这个原因，科学家们需要一个程序来计算发送信息的最短时间，并推断出最佳路线之一。

思路：

其实我们只要把时间复杂度计算好了，这题其实就是个简单剪枝模拟bfs。我们首先先进行一个我也不知道什么时间复杂度反正不会超过n根号n的筛素因数，然后把它加入vector里面，然后再把每一个i的素因数算好，然后bfs嗯扩展就好了，在我的想法中这个bfs硬扩展的时间复杂度不会超过n根号n。其实写这题就是想着感觉暴力能过，就是一种直觉吧。。。

个人感觉。。。d比c好写

代码如下：