【题解】牛客小白月赛23

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题的数据出了问题,赛后都已经修复数据并且重测。
全部评论
D题公式是错的,会出现重复情况。
13 回复
分享
发布于 2020-03-21 22:08
A题数据现在是不是还不太对啊?
1 回复
分享
发布于 2020-03-21 22:32
小红书
校招火热招聘中
官网直投
能详细说一下B是怎么做嘛 实在是想不出来
1 回复
分享
发布于 2020-03-22 15:08
I 题字符串最大表示法为啥过不了啊,可以举一个反例吗?
点赞 回复
分享
发布于 2020-03-21 22:05
同问I题,找到第一个最大的字母后直接输出后缀为啥不对呀??
点赞 回复
分享
发布于 2020-03-21 22:14
C题要高精度吗
点赞 回复
分享
发布于 2020-03-21 22:43
没有std嘛
点赞 回复
分享
发布于 2020-03-21 22:50
能不能给个标程啊
点赞 回复
分享
发布于 2020-03-21 22:53
问大佬们个G题 为啥随便拿一个点去dfs所有子树大小即可。。我是找出来重心以重心为根再去dfs算子树大小 😥
点赞 回复
分享
发布于 2020-03-21 22:58
A题这个复杂度是怎么得到的啊???
点赞 回复
分享
发布于 2020-03-21 23:00
看了大佬A题的标程,子集前缀和感觉很牛逼。 但是好多人直接 O(2^n * m) 水过去了啊🤣
点赞 回复
分享
发布于 2020-03-22 01:27
B 同样做法直接T
点赞 回复
分享
发布于 2020-03-22 08:41
F题按照题解思路写了一遍 为什么不对呀,求大佬指点 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43221790
点赞 回复
分享
发布于 2020-03-22 20:07
请问H 题为什么用sort排vector,就超时, 用pair的就能过呢? ~~~~~~~~~  ll br[N]={0}; ll f[100010]; vector<pair<ll ,ll > > v; int main(){     ios::sync_with_stdio(0);     cin.tie(0), cout.tie(0);     cin >>t;     while(t--){         cin >>n;    ll sum =0 ;         for(int i=1 ;i<=n;i++){             cin>>m;             v.push_back({(1<<m) , i});             sum +=(1<<m);         }         if(sum < (1<<30)){              cout<<"impossible"<<endl;              continue ;         }         sort(v.begin(),v.end());         for(int i=1 ;i<=n;i++)br[i]=0 ;         sum = (1<<30) ;         for(int i=v.size()-1 ;i>=0;i--)             if(sum>=v[i].first){                     sum-=v[i].first;                 br[v[i].second] = 1;             }         for(int i=1 ;i<=n;i++)cout<<br[i];cout<<endl;     }     return 0;   } ~~~~~~~~~
点赞 回复
分享
发布于 2020-03-22 23:08
你好博主,E题为什么是模$2^32$次方呢?不是模$2^31$次方吗?
点赞 回复
分享
发布于 2020-03-23 15:33
A题,如果分两种情况讨论,1、先选行    选含有敌人前a大的  行,在选前b大的列  2、先选列, 选含敌人前b大的行,再选前a大的列     如果至少有一种情况使得敌人全部消失,那么就yes。这种思路个人感觉没问题啊,可是一直Wa.......
点赞 回复
分享
发布于 2020-03-23 22:21

相关推荐

1 5 评论
分享
牛客网
牛客企业服务