竞赛讨论区 > 牛客小白月赛43 题解

牛客小白月赛43 题解

头像
fuzhiji
编辑于 2022-01-13 21:18:26 APP内打开
赞 25 | 收藏 10 | 回复0 | 浏览1347

A

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

时间复杂度

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

B

第一步: 或者 等于 ,输出
第二步: 是奇数 由于不管怎么操作,都必然会翻倍,所以 需要是偶数才能实现,输出
第三步:,这种情况必然可以通过 次操作,让其中一个瓶子的饮料变成 毫升,然后结束操作的时候翻倍达到了 ,输出
第四步:,不管怎么倒饮料,设 为两个瓶子的饮料总毫升,每次操作后 都会翻倍 变成 ,所以直接把一个瓶子的饮料全部倒入另一个瓶子,反复操作,直到,然后就变成了第三步的情况,然后一次操作达成。

时间复杂度

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

C

由于数据很小,直接二进制枚举三边的棍子组成情况,然后判断情况是否合法,合法的情况用海伦公式求面积即可。
时间复杂度

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

D

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

“总区间个数”

“无趣的区间”的计算方法:
区间或运算后为偶数的,即整个区间的元素最低位全 。一段区间 内元素最低为全是 ,那么区间 的区间同样全是 ,该段区间 区间长度为 ,包含了 “无趣的区间”,因此只需要找出数组中连续的最低位为的 的全部区间,算出它们一共包含了多少区间即可。

时间复杂度

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

E

一个十进制数每一位累加是 的倍数,那么这个数必然会被 整除。该题可以用动态规划求解,,其中 表示只选择数字 ,累加和 的方案有多少。

一个暴力的做法,对于每个数字 ,枚举选择

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;
        }
    }
}

复杂度和 总和相关,由于数据高达 ,不可行

仔细观察发现,对于一个数 ,选了 个的时候,得到的关于 的模数都是相等的,即

同理

因此只有 个可能的模数,复杂度可以优化成

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

F

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

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

问:不是两两之间距离是偶数才满足吗?为什么只需要选其中一个点 就行了呢?
因为如果存在一条 的偶数路径,也存在一条 的偶数路径,那么路径 必然存在偶数路径。

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

问:为什么求最短路就行了呢?

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

做法二:
简单粗暴,直接选一个有人的点 ,假设这个点为 ,设数组,若,表示点 存在一条偶数路径,若 表示存在一条 的奇数路径,因此只需要看这个点到其它有人的点是否都存在偶数路径即可。

复杂度

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50311335

0条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐