Codeforces Round #738(Div.2)

A - Mocha and Math

题意简述：

现在你有一组数组，你可以选定一个区间，并且让这个区间的对称位置进行按位与运算并替换掉，而且，你可以随意的执行这个操作。

最后请问操作完后最小的最大值是多少

思路：

可以发现， $a_1$ 可以和任何数进行按位与运算， $a_2$ 同理，以此类推，所有数都可以互相进行按位与运算。

Submission #125955835 - Codeforces

B - Mocha and Red and Blue

题意简述：

有一串板砖，当相邻的砖颜色相同的时候，我们就视这些板砖为不好的砖，我们有两种颜色，对于一串板砖，我们知道了部分，给出最好的砖块排列

Submission #125968330 - Codeforces

C - Mocha and Hiking

题意简述：

有 $n + 1$ 个城市，其中 $n$ 个城市是从 $i$ 号到 $i + 1$ 号的

另外第 $n + 1$ 个城市，和 1 ~ n 都存在路径，且都是单向路。

求问，有没有哈密顿路径，有就打出来。

Submission #125987483 - Codeforces

D1 - Mocha and Diana (Easy Version)

题意简述：

有两个森林，当第一个森林的 u v 相连的时候，第二个森林也会相连。如果在同一个连通块中，则不连。求问，最多能连多少个

思路：

用并查集维护连通块，暴力扫即可

Submission #125995116 - Codeforces

D2 - Mocha and Diana (Hard Version)

思路：

我们将其简化为网格图的形式，其中行数表示在第一个森林中，列数表示在第二个森林中。对于每行，我们维护一个行集合，集合里的元素是行所在的集合中所有元素，在第二个森林中元素所在的集合。同样的列集合也是如此。

所以，题目的意思变成了，我们最多能够找到多少对 $(i, j)$ $i\ne j$ ，将这两个集合合并。

那么我们在找的过程中，将会涉及到一些合并操作，我们采取按秩合并的方式进行合并，这里秩的大小是集合元素的个数，将小的元素插入大的元素中。

并且在合并过程中，我们只保留代表元。

Submission #126104556 - Codeforces

E - Mocha and Stars

题意简述:

首先我们忽略其中一个条件： $gcd(a_1,a_2,...a_n)=1]$

对于条件

$\sum\limits_{i=1}^n\le m \\ a_i\in[L_i,R_i]$

我们设 $F [i]$ 表示，数字 $i$ 共有多少个，

那么我们便有如下的过程转移方程

$\begin{cases} & 0 &(i < L) \\ & \sum\limits_{j=0}^{i-L} F[j] &(L\le i \le R) \\ & \sum\limits_{j=i-R} ^{i-L} &(i > R) \end{cases}$

对于片段和，我们可以采用前缀和的思想来快速求出，因此，我们定义 $S [i]$ 表示上一次前 $i$ 项的和，那么我们的方程就变成了。

$F[i]=\begin{cases} & 0 &(i < L) \\ & S[i-L] &(L\le i \le R) \\ & S[i-L] - S[i-R-1] &(i > R) \end{cases}$
最后，我们将 $\gcd$ 条件放入其中，我们可以通过容斥原理来搞定。求取莫比乌斯函数后。（详细请见对称筛）

那么对于每个 d 来说

我们要求的不等式就是，
$\sum\limits_{i=1}^n b_i\times d \le m \\ b_i\times d = a_i \in[L_i,R_i]$
我们将这个 d 除去就得到
$KaTeX parse error: Expected group after '_' at position 6: \sum_?\limits{i=1}^n …$
这个式子和上述式子完全一致，因此，我们就可以再次求取答案。