竞赛讨论区 > 【题解】牛客小白月赛23

【题解】牛客小白月赛23

头像
ACoder_NWPU
编辑于 2020-03-22 07:52:41 APP内打开
赞 1 | 收藏 6 | 回复16 | 浏览3087

A


基本的贪心思路是先把能消灭一整行的次数用完,使得剩下的列尽量少,然后看看看剩下的列有多少个,和b比较一下大小。

我就枚举每行是否要放“消灭一行”的技能,然后现在就是要看看还有那些列需要放一个“消灭一列”的技能,这个可以预处理。

整个算法的复杂度应该是

B

将p质因数分解,然后二分

C

反过来想,一开始是n个孤立节点,我要添加恰好条边,让他连通块尽量少多。

第一条肯定会让连通块数减少1,第二条也只能让连通块减少1,现在形成了一条包含三个点的链,接下来一条把这链的两个端点连起来,这一步没有让连通块的个数变少,再接下来一条边只能让连通块个数减少1......重复这样的过程:除非必须要把孤立点连进来,否则我就在大连通块内部连点。
形成个连通块能用完的最大边数依次为:
二分可以解决

D

注意这是个条件概率
先求全局条件下“有t个人参加party之前就被感染,且最后共k人感染”的概率,令



对每个t,假设用上式算出的概率是P(t)
那么对于一个t,所求的条件概率就是



E

有符号整数只是把最高位作为符号位而已,其真值仍然是一个在的整数,也就是模意义下的非负整数,所以无论c是多少,我枚举,都能得到对应的b = c-a。(该减法是在模意义下进行的)
所以答案总是

F

对于某个确定的序列,美丽度等于:


我要做的事情实际就是枚举这个序列,每个序列用上述式子求出美丽度。
前面那个1,显然每次都要算上,对答案的贡献就是
后面和式,我可以对于每个i,算一下对答案的贡献是多少。
其实就是要算的情况数,也就等于


预处后面那个积,这个式子是可以O(1)算的

G

先算出每条边在答案中被加了多少次
然后把这个次数升序排序,从前往后依次分配权值

H

直接说结论:如果,那肯定可以凑出,我只需要把所有的数字从大到小排序,依次加入数字,肯定在某个时刻和就等于
正确性:
如果我有一个,那肯定在第一步就找到方案了
如果没有,那肯定最大的数字不大于,假设我一个一个加入,当前已经加入的数字的和是S,再加入一个数字x的时候,考虑S的二进制表示加上一个2的幂,可能会产生进位,这个进位有可能最终使S的位数增加1,或者也可能保持不变。如果这次进位使得最终S的位数增加1,那么这次进位肯定是类似这种情形111000+1000,也就是从x的1那一位往上的位,在S中是连续一段1,这样的加法肯定执行完之后产生的结果肯定是2的幂次,既然最终的和不小于,那么在某一次进位的时候肯定产生了这个数。

I

字典序最大的子串肯定是个后缀,直接在所有的后缀中取max就可以

J

最大值减去最小值

标程

A题 B题 C题 D题 E题 F题 G题 H题 I题 J题

通知:
比赛时A题、D题的数据出了问题,赛后都已经修复数据并且重测。

16条回帖

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

近期热帖

等你来战

查看全部

热门推荐