A
题目大意
给你一个只含字母 a, b 字符串，要把它拆分成三段，使得其中间那段要么同时小于等于两边要么同时大于等于两边。
题解
由于只有 a, b 我们可以分讨解决
如果 \([2, \dots, n-1]\) 中间有 b，那么中间那段选 \([2, \dots, n-1]\) 一定合法（因为如果前面的字符相同长度长的字典序更大）
如果中间没有 b，那么我们就找到第一个字母 a 的位置，中间那个即选第一个 a，一定合法
B
题目大意
给定一个序列 c，定义 \(f(S)\) 为 \(S\) 中所有元素的或的和，要求是否存在序列 \(c\) 的两个子区间使得 \(f(A) = f(B)\)
题解
注意到如果存在这样的两个子区间，那么一定存在一个元素使得整个序列的或和在删掉这个元素后不改变。
为什么？因为我们这个元素在他这个子区间内贡献的 1 的位置在另一个子区间中一定有一个对应的，所以这个位置就不重要了。
所以我们枚举这个位置判断即可
C
题目大意
定义 \(f(l, r) = l \& (l+1)\&(l+2)\&\dots\&r\)
给你 \(n, x\)
要求最小的 \(m\) 使得 \(f(n, m) = x\)
题解
其实有单 \(log\) 做法，但是我比较想偷懒，写了个 \(log^2\) 做法，结果反而写的更久。
显然与运算具有单调性，当 \(l\) 固定 \(r\) 增加时，\(f(l, r)\) 一定不上升，所以我们可以二分。
考虑我们要怎么 check，可以单独考虑每一位，如果我们的 \(r\) 已经越过了一条线，那么 \(f(l, r)\) 的这一位一定是 \(0\)，不难发现这一位最小应该是 \(2^k - (2^k-1) \& n\)
可惜我傻逼把 \(2^k-1\) 写成了 \(2^{k-1}\)，图图增加了一个小时的调试时间，哈哈。
D
题目大意
给定一个序列 \(\{a_n\}\)，\((i, j)\) 之间有一条长度为 \(1\) 的边当且仅当 \(\mathcal{gcd}(a_i, b_j) \not =1\)，求 \(s\) 到 \(t\) 的最短路。
题解
又看错题了……
简单的套路题，不难想到两个点之间有边当且仅当他们之间有公因数，所以我们可以把每个点向他们的所有因数连边，然后直接跑最短路就完事了。
E
题目大意
给定一个序列 \(\{a_n \}\)。
定义一个操作为选择这个序列的一个子序列，然后将子序列上的奇数位加一偶数位减一或反之。
题解
看到每次只能加减一，不难想到我们可以转化这道题。
把原来的数正的化成 \(x\) 个 \(1\)
负的化成 \(x\) 个 \(-1\)
\(1\) 和 \(-1\) 一定是配对的，而且你选择的前缀和不是全负的就是全正的。
标签：dots,843,题解,大意,序列,题目,Div,我们 From： https://www.cnblogs.com/luanmenglei/p/17041646.html