A1&A2.Gardener and the Capybaras (hard version)
超级诈骗题。
直接 \(O(n^3)\) 枚举肯定不行。
我们考虑两种情况：
-
B 最小：直接看最小的字符是否在区间 \((1,len)\) 中，如果在则构造成功。
-
B 最大：因为 B 没法做到最小，所以说明 \((1,len)\) 里全是 b，为了让 B 的字典序最大，显然选区间 \((1,len)\)。
如果两个都实现不了，就无解。
复杂度 \(O(n)\)。
赛时也不知道咋回事，就是没做出来。
我们考虑枚举集合，假定只有第一组选了它，然后尝试构造。
显然，第二组为了和第一组一致，必须要有当前集合里的元素，如果没有则当前集合不能在第一组。
如果能构造出，那么可以将第二组加入到第一组中，这样就构造成功了。
感觉还挺有思维含量的。
复杂度 \(O(n)\)。
手动模拟一下样例可以发现，与操作会使 n 的二进制中连续的 1 变为 0，所以我们只需要判断 k 是否为 n 的前缀，且 k 和 n 的下一位为 0 即可。
复杂度 \(O(T\log n)\)。
带有技巧的最短路。
如果 u 能到 v，说明 \(\gcd(u,v)>1\)，也就是有相同因子。
所以我们考虑对于每个数 u，向他的所有质因子连一条长度为 1 的边，这样我们从 u 到 v 就两步，最终答案除以 2 即可。
每次遇到一个新的因子，都要新建节点。
需要注意的是，如果 u 的质因子中有真实存在的点，那么边权要设为 2，否则会少算。
最后跑一边最短路或 BFS 就行了。
复杂度 \(O(n \log n)\)。
思维题。
我们考虑每次 \(a\) 数组加一减一对于其前缀和 \(sum\) 的影响。
可以发现，假设相邻两次加一和减一的位置分别为 \(l\) 和 \(r\)，那么 \(sum\) 在 \([l,r)\) 内会加一。
先减后加也同理。
所以，一次加减操作相当于将 \(sum\) 若干段连续序列加一或减一。
而 \(sum\) 全部为 \(0\) 是 \(a\) 都变为 \(0\) 的充要条件。
因此我们只需要计算出 \(sum\) 归零的最小操作数，也就是 \(maxn-minn\)，其中 \(maxn\) 为最大正数，\(minn\) 为最小的负数。
复杂度 \(O(n)\)。
标签：CF1775,复杂度,第一组,最小,len,因子,sum From： https://www.cnblogs.com/HQJ2007/p/17561572.html