2022-01-13 21:18 已编辑惠州学院算法工程师

关注

牛客小白月赛43 题解

A

一个数有 $m$ 个因子，第 $m$ 个因子必然是它本身，所以不管哪个因子，都必然能整除它本身，所以直接输出 $n$ 即可。

时间复杂度 $O(T)$

$std$ ：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50310925

B

第一步： $a$ 或者 $b$ 等于 $target$ ，输出 $0$ 。
第二步： $target\ \%\ 2=1$ $($ $target$ 是奇数 $)$ 由于不管怎么操作，都必然会翻倍，所以 $target$ 需要是偶数才能实现，输出 $-1$ 。
第三步： $a+b>=target/2$ ，这种情况必然可以通过 $1$ 次操作，让其中一个瓶子的饮料变成 $target/2$ 毫升，然后结束操作的时候翻倍达到了 $target$ ，输出 $1$ 。
第四步： $a+b<target/2$ ，不管怎么倒饮料，设 $sum$ 为两个瓶子的饮料总毫升，每次操作后 $sum$ 都会翻倍 $($ 变成 $sum*2$ $)$ ，所以直接把一个瓶子的饮料全部倒入另一个瓶子，反复操作，直到 $sum>=target/2$ ，然后就变成了第三步的情况，然后一次操作达成。

时间复杂度 $O\ (T*log(target) )$

$std$ ：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50311168

C

由于数据很小，直接二进制枚举三边的棍子组成情况，然后判断情况是否合法，合法的情况用海伦公式求面积即可。
时间复杂度 $O\ ((1<<n)^3)$

$std$ ：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50311253

D

一个区间或运算后是否为奇数，根据或运算的性质，只需要判断这个区间的是否存在一个元素的二进制下的最低位是 $1$ ，如果存在，这个区间或运算后是奇数，反之为偶数。
本题求的是或运算后是奇数的区间，因此 “有趣的区间” $=$ “总区间个数” $-$ “无趣的区间”

“总区间个数”： $(1+n)*n/2$

“无趣的区间”的计算方法：
区间或运算后为偶数的，即整个区间的元素最低位全 $0$ 。一段区间 $[L,R]$ 内元素最低为全是 $0$ ，那么区间 $[l,r]$ $(L<=l<=r<=R)$ 的区间同样全是 $0$ ，该段区间 $[L,R]$ 区间长度为 $len=R-L+1$ ，包含了 $(1+len)*len/2$ 个“无趣的区间”，因此只需要找出数组中连续的最低位为的 $0$ 的全部区间，算出它们一共包含了多少区间即可。

时间复杂度 $O\ (n)$

$std$ ：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50311277

E

一个十进制数每一位累加是 $3$ 的倍数，那么这个数必然会被 $3$ 整除。该题可以用动态规划求解， $dp[\ ][3]$ ，其中 $dp[i][j]$ 表示只选择数字 $1 \sim i$ ，累加和 $\% 3 = j$ 的方案有多少。

一个暴力的做法，对于每个数字 $i$ ，枚举选择 $0 \sim cnt_i$ 个

for (int i=1; i<=9; i++) {
    for (int j=0; j<=cnt[i]; j++) {
        for (int MOD=0; MOD<3; MOD++) {
            dp[i][(j*i+MOD)%3]+=dp[i-1][MOD];
            dp[i][(j*i+MOD)%3]%=mod;
        }
    }
}

复杂度和 $cnt_i$ 总和相关，由于数据高达 $1e9$ ，不可行

仔细观察发现，对于一个数 $i$ ，选了 $1,4,7,..,3*x+1$ 个的时候，得到的关于 $3$ 的模数都是相等的，即 $1*i\ \%\ 3=4*i\ \%\ 3=7*i\ \%\ 3=...=(3*x+1)*i\ \%\ 3$

同理

$2*i\ \%\ 3=5*i\ \%\ 3=8*i\ \%\ 3=...=(3*x+2)*i\ \%\ 3$

$0*i\ \%\ 3=3*i\ \%\ 3=6*i\ \%\ 3=...=(3*x)*i\ \%\ 3$

因此只有 $3$ 个可能的模数，复杂度可以优化成 $O\ (9*3*3)$ 。

$std$ ：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50311320

F

一个显然的结论：如果每个人两两之间都存在偶数距离的路径，那么必然存在一种方法使得他们集中（可以先让一个人每次都在其初始节点和某个相邻节点之间“反复横跳”，然后其他节点的人都往这个人初始位置走那条偶数路径，到达之后可以选择跟着这个人“反复横跳“，直到全部点都到达，因为是偶数距离，所以"反复横跳"最后还是会跳回初始的位置）。
（以下奇数路径偶数路径指的都是距离）

做法一：
只需要找奇环，有奇环必然全部点能相遇（两个人的距离可以通过这个奇环改变奇偶性）。找奇环的常见方法：二分图染色，有冲突就有奇环。
没奇环只需要选任意一个初始有人的点 $bfs$ 求最短路，判断到 $k$ 个点最短距离是否都为偶数（没奇环，任意两点路径距离无法改变奇偶性，只能都是奇数，或者都是偶数）。

问：不是两两之间距离是偶数才满足吗？为什么只需要选其中一个点 $bfs$ 就行了呢？
因为如果存在一条 $x->v$ 的偶数路径，也存在一条 $x->u$ 的偶数路径，那么路径 $u->x->v$ 必然存在偶数路径。

问：为什么没有奇环两点之间就不能同时存在奇偶两种路径呢？
感性理解：二分图染色，没有奇环的时候。两个颜色相同的不同节点，可能的距离都是偶数。两个颜色不同的不同节点，可能的距离都是奇数。

问：为什么求最短路就行了呢？

因为在无奇环的情况下，都是奇数路径或者都是偶数路径，所以最短路和其他路径的奇偶性都是一样的。

做法二：
简单粗暴，直接选一个有人的点 $bfs$ ，假设这个点为 $x$ ，设数组 $dis[\ ][2]$ ，若 $dis[u][0]=true$ ，表示点 $x$ 到 $u$ 存在一条偶数路径，若 $dis[u][1]=true$ 表示存在一条 $x$ 到 $u$ 的奇数路径，因此只需要看这个点到其它有人的点是否都存在偶数路径即可。