题目简述

        Problem A1 / A2：给定一个长度为的只含字母'a'和字母'b'的字符串，判断能否按顺序划分成非空的三个子串，使得的在字典序意义下，要么同时不比大，要么同时不比小。

        Problem B：给定一个长度为的序列。判断能否将划分成两个不同（指所取的下标不同）的非空子序列和，使得子序列中元素按位或的结果相等。

        Problem C：给定，解方程

        其中。如果解存在，要求给出最小的解。

        Problem D：给定一个长度为的数组。如果与不互质，则在之间连一条边。给定起点和终点，求最短路径，要求输出其中一种行走方案。

        原题目地址：https://codeforces.com/contest/1775

思路

        Problem A1 / A2：一个小小的分类讨论题目，不想多说，详见代码。

        Problem B：按位或操作相当于集合取并集。要想两个子序列不同，最简单的制造不一致的方法是选择一个被和公共部分代表的集合包含的元素，使得不含但包含。如果连这种最简单的情形都无法成立，则无解。

        因此只需要依次判断每个元素的各个二进制位是否独自潇洒（我是指是不是只有它在这一位上为）。对于元素，一旦存在这么一个潇洒的二进制位，意味着它不可能被其它任何元素组代表的集合组的并集所包含。反之，把其它元素全选上，再利用就可以按前述策略制造不一致。用一个桶记录一下各个位上出现的个数，可以轻松完成判断，复杂度为，其中表示的二进制位中的数目。

        后话：虽然非常浅显，但是可以硬来证明一下最开始提到的情形确实是“最简单的情形”，我将直接使用用集合的语言来说明。这个“最简单”是指所有可行的集合序列，均存在对应的集合和某个下标序列，使得：

        开证。因为集合序列可行，因此存在下标序列：

        由于，因此存在，使得：

        令，这就完成了证明。

        Problem C：按位与操作相当于集合取交集，所以伴随，左式会越来越小。在这一长串连续按位之中，左式是以何种方式变小呢？例如：

        我们惊讶的发现，和按位与一下并不会影响结果，因为除了最低位，二者完全一致，而最低位已经是了，无法被按位与改变。而：

        一旦它参与进来，连续的三个将无一幸免永远变成。事实上，这一规律具有普适性。即对于任意位置的连续，当且仅当在达到在这些连续的位置恰好变成了，且连续的最高位再高一位由变成时，才会将这一段连续一并永久变为。

        于是，可能的关键节点不超过个（当然，其实只有这个数的一半左右）。因此我们可以枚举的二进制表示中所有连续片段，计算其对应的节点，以及按位与的最终结果。这里不详述计算方案，最后的复杂度是。

        Problem D：原始的图太大了，没有办法直接建图再跑BFS。但是节点是以互质关系来确定连接的，因此我们可以考虑从质因子出发做文章。和如果不直接相连，说明它们没用公共质因子（也就是互质了）。如何让它们连起来呢？需要找到一些中介。考虑一阶的情形，比如和有公共质因子，和有公共质因子，这就把和连上了。有了这一思考的基础，我们为什么要以数组元素为节点建图呢？

        直接以质因子为节点建图，这样每一个数组元素意味着若干个质因子之间的连接关系。这样边就表示“从包含某个质因子的数出发，经过边所代表的数组元素，可以与另一个包含质因子的数相连”。每个数组元素至多产生条边（双向边存成两条有向边），这样新图仅包含约个节点和条边，直接使用BFS求最短路，复杂度为。当然，需要一些琐碎的操作记录一条最短路径。

后记

        代码的github地址：https://github.com/cnzzx/AlgorithmCompetitions。

        A题的分类讨论花了我50分钟。不然E是有机会做的。烦躁。