竞赛讨论区 > 【题解】牛客练习赛41
头像
lililalala
编辑于 2019-04-10 16:55
+ 关注

【题解】牛客练习赛41

A. 翻硬币问题

因为m是一个偶数,不妨分类讨论:
1.一回合可以直接翻转所有硬币(n=m)
很显然,答案Yes
2.一回合不能直接翻转所有硬币,因为m是偶数,所以只需要讨论n的奇偶性。
(1)n是奇数
某回合结束后所有硬币反面朝上可以等价于所有硬币都被翻转了奇数次。假设可以达成,那么
该回合后所有回合总翻转次数一定要为奇数(因为奇数个奇数相加是奇数)
然而m是偶数,即使在不使坏的情况下,无论翻转多少个回合,总翻转次数也一定是偶数,
所以在这种情况下是不可能赢得游戏的.答案是No
(2)n是偶数
同理,完成时所有硬币都一定要被翻转了奇数次,但是n是偶数,所以总翻转次数一定要为偶
数,在不被使坏的情况下,至少有可能完成,但是除去n=m的情况外,只要在第一回合后立即
被使坏,不管翻转哪一个硬币,都会使得总翻转次数由总是偶数变成总是奇数,和n为奇数
时原理相同,也不可能赢得游戏,答案是No
结论: n=m时答案是Yes,否则答案是No

B. 666RPG

简单的计数dp.
dp[i][j]代表第i个回合后分数为j的方案数
则:dp[i][j]=dp[i-1][j-ai] dp[i-1][-j]
因为开二维内存不够,需要使用滚动数组
特判屏蔽所有来自j=666的状态转移
复杂度O(n*n*1333)

C.抓捕盗窃犯

把每个地点看作一个点,那么每个点一定有且仅有一条有向出边。
每个点出度只有1,如果某些点组成了一个有向环,这个环上所有点不会有额外的出边,即这个环一定是一个简单环。
也易证每个点最终都会走向一个环。
结论:单独看待每个联通块,每个连通块一定有且只有一个环,只要在这个环上任何一个点建立哨卡,就能抓到这个联通块中的所有。可以使用把边都看成无向,使用并查集等找出所有连通块并求每个连通块上所有点的数量之和,从大到小排序,取前m大即可。
复杂度O(nlogn)


D.最小相似度

此题可以用FWT通过,但是出题时的想法是一道BFS就可过的题。
M最大只有20,如果把每个二进制串看成一个状态,最多只有2^20=1 048 576个状态。
我们把开始给定的所有二进制串看成起始点,每一步搜索对二进制串进行一个二进制位的翻转对全部状态进行BFS,设搜到的步数最大的状态步数为X,则答案就是M-X
复杂度O(N 2^M)

E.球的体积并

设两个球的体积分别为 ,半径分别为,两球球心距离为
分三种情况讨论: 两球/相离/外切,那么答案是
两球内含/内切时,答案是
两球相交时,我们可以认为相交部分就是两个球被平面所截的部分,我们称之为球冠。
对于球冠体积有公式: ;
其中为球半径,为截面圆半径,为垂直于截面的一条直径,即球冠的高 ;
那么对应的球冠参数为: , ;
对应的球冠参数为:, ;
代入球冠体积公式便可得到答案。



F.简单数学题

由题面可知没有平方根,加上x的最大质因子为71,说明它的质因子种数只有20种。
那么可映射成一个20位的二进制数。

其中为第大的素数,为第位二进制位,
我们不妨设

那么对于来说,它的表示方法的种数有

其中为A数组中经过bin映射后等于i的个数,为B数组中经过bin映射后等于j的个数,为C数组中经过bin映射后等于k的个数。
这里再用卷积加速即可。

参考代码:



全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐