即将掉蓝名的弱弱

2019-12-14 15:40 已编辑 C++

关注

【题解】牛客练习赛55

A-等火车

输出 $(s-t\%s)\%s$ 即可。

B-数字游戏

容易证明第一次擦掉的是奇数，甲必败，否则甲必胜。

当第一次擦掉是奇数的时候，黑板上一个有 $n$ 个偶数，甲最多擦掉 $n-2$ 个偶数，所以乙必胜。

当第一次擦掉是偶数的时候，设为 $i$

那么把 $2n-2$ 个整数分为 $(2,3),(4,5)...(i-2,i-1),(i+1,i+2)...(n-1,n-2)$

当乙擦掉一组中的某一个数的时候，甲把另一个擦掉。

最后只会剩下同一组的两个整数，它们互质，甲必胜。

所以答案输出 $n-1$

C-最大生成树

发现首先把 $1$ 和 $n$ 连边，然后 $2$ 至 $n-1$ 要不和 $1$ 连边，要不和 $n$ 连边。

容易证明这样的答案是最大的。

$Ans=n-1+\sum_{i=2}^{n/2}(n-i)+\sum_{i=n/2+1}^{n-1}(i-1)=(n/2-1)\times n-\frac{(n/2-1)\times (2+n/2)}{2}+\frac{(n/2-1)\times (n/2+n)}{2}-(n-n/2-1)$

用 $int128$ 存储即可。

D-求和

$Ans=\sum_{i=1}^n\sum_{j=i+1}^nf(i,j)-{n^2}$ 。

其中 $f(i,j)=\sum_{i1=0}^{a_i}\sum_{j1=0}^{b_i}\sum_{a2=0}^{a_j}\sum_{b2=0}^{b_j}C(i1+j1+i2+j2,i1+i2)$

考虑组合数意义，相当于从 $(-i1,-j1)$ 走到 $(i2,j2)$ 的方案数。

那么 $f(i,j)$ 相当于从 $(0,0)$ 至 $(-a_i,-b_i)$ 这个矩阵中选择一个点，走到 $(0,0)$ 至 $(a_j,b_j)$ 中选择一个点，走过去的方案数。

然后就把所有起点 $+1$ ， $dp$ 出来走到每一个终点的值，然后累加一下每一个矩阵的答案即可。

时间复杂度 $O((a+b)^2+n)$ 。

E-树

设 $f_i$ 表示从 $i$ 的深度。

那么 $dis(x,y)=f_x+f_y-2f_{lca(x,y)}$

$dis^2(x,y)=f^2_x+f^2_y+2f_xf_y+4f^2_{lca(x,y)}-4(f_x+f_y)f_{lca(x,y)}$

那么前 $3$ 部分可以直接计算。

后面两个部分，枚举 $lca=i$ 。

也就是要计算 $lca(x,y)=i$ 的 $(x,y)$ 这样的数对个数，以及这些数对的 $f_x+f_y$ 。

设 $size_i$ 表示 $i$ 这颗子树的大小。

数对个数即为 $size^2_i-\sum_{j\in son_i}size^2_j$

设 $sum_i$ 表示 $i$ 这颗子树的 $f_x$ 之和。

那么 $f_x+f_y$ 之和即为 $2\sum_{j\in {son_i}}sum_j \times (size_i-size_j)+2f_i\times size_i$

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

F-字符串

可以转化为一个 $n \times m$ 的矩阵，不能经过一条斜率为 $1$ 的线段的方案数。

那么把所有障碍点按照 $x$ 轴从大到小排序。

设 $f_i$ 表示从第 $i$ 个不能到达的点开始，不经过终点的方案数。

$f_i=C(n+m-x_i-y_i,n-x_i)-\sum_{j=1}^{i-1}f_j\times C_{x_j-x_i+y_j-y_i,x_i-x_j}$

由于斜率为 $1$ ，所以 $C_{x_j-x_i+y_j-y_i,x_i-x_j}=C(2j-2i,j-i)$ 。

设 $C_i=C(2i,i),P_i=C(n+m-x_i-y_i,n-x_i)$

$f_i=P_i-\sum_{j=1}^{i-1}f_j \times C_{i-j}$

把 $f,c$ 都看成一个多项式。

也就是 $F \times C=P$ 。

那么直接多项式求逆即可。

最后 $Ans=C(n+m,n)-\sum_{i=1}^nf_j \times C_{n+m-x_j-y_j,n-x_j}$

时间复杂度 $O(nlogn)$ 。

std:
a:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513174
b:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513176
c:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513178
d:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513180
e:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513183
f:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513185

全部评论

推荐最新楼层

杭州电子科技大学

int n = read() ; n >>= 1 ; n %= mod ; print((3ll * n * (n - 1) % mod + 1ll) % mod) ; 最大生成树的做法

1 回复

发布于 2019-12-13 22:32

塔子哥学算法

Fleet AntiSubmarine Warfare Training Center (San Diego) 计算机类

C题我是用prim模拟一下最大生成树的过程就可以找到规律啦😁嘿嘿

1 回复

发布于 2019-12-13 23:23

联易融

校招火热招聘中

官网直投

Java

a题为啥还要取一次模

点赞回复

发布于 2019-12-13 22:22

L201910031029397

Java

为什么数字游戏那题乙先擦偶数的时候，最后一定剩下在一组的数

点赞回复

发布于 2019-12-13 23:41

东莞市东莞中学松山湖学校

甲不是应该擦掉偶数吗？擦奇数剩下的数肯定不会互质啊？

点赞回复

发布于 2019-12-14 09:48

Java

E有点分治莽过去的gg吗

点赞回复

发布于 2019-12-14 10:19

C++

D,F两道题正好把我的多一个log的做法全卡掉了....😑😑

点赞回复

发布于 2019-12-14 18:39

东莞市东莞中学松山湖学校

T5 原来std是O(n)的，，，我比赛线段树O(n log n)居然过去了海星

点赞回复

发布于 2019-12-15 11:08

迷人的熊熊在debug

04-22 17:04

美团工作体验（五）:导师制度

导师对个人工作的积极影响业务理解加深：导师通过介绍公司的业务线和工作重心，帮助我更快地理解了公司的运营模式和市场定位，从而能够更有效地融入团队和参与到工作中。职责明晰与规划：导师不仅告知了我目前的工作职责，还预先规划了我将要负责的板块，让我对自己的职业路径有了清晰的认识和期待。职业发展指导：导师针对我的职业规划提供了宝贵的建议，帮助我设定了长远的职业目标，并指导我如何步步为营地实现这些目标。工作效率提升：在导师的指导下，我学会了如何聚焦于关键任务，提高了工作效率，同时也学会了如何平衡工作与生活，保持良好的工作状态。导师对个人生活的积极影响生活质量改善：导师不仅关注我的工作进展，也关心我的生活细...

投递美团等公司10个岗位 >

点赞评论收藏

转发

活跃的伊泽瑞尔在吃瓜

03-05 11:43

门头沟学院机械类

求改简历，求实习{嵌入式，c++}

牛友们都找到实习了吗，为什么我0offer，是不因为我简历不行，求大家修改，听劝

点赞评论收藏

转发

03-25 10:31

已编辑

南京理工大学计算机类

佬们，帮看看简历

听劝！想找实习leecode刚开始刷题，倒是本科刷牛客刷了一百多道，现在都忘了，八股没背。问题1：移动端开发/Java后端开发/前端开发 我走哪一个比较好？问题2：能找到大厂实习吗？问题3：研二目前还没小论文，敢投实习吗？请佬们指点迷津#简历被挂麻了，求建议#

投递牛客等公司10个岗位简历被挂麻了，求建议

点赞评论收藏

转发

04-24 09:30

已编辑

南京大学计算机类

HR面试面经问题汇总（共计30+问题，2500+字数）

（引流 阿里 腾讯 美团 华为 快手 字节）最近经常逛牛客，很多佬分享技术面经，但HR面内容比较少，正好朋友也在最近面hr面，我面过的hr面略多一点，稍微有点经验，本帖内容也参照了一些知乎，牛客，还有博客上的hr面面经，就打算汇总起来补齐这部分的空缺，同时也非常感谢阿里云内推人对我hr面的耐心指导，虽然我最终没有去阿里云叠个护甲，下面内容不代表本人的态度和回答，只是总结和汇总，给出建议回答，且建议回答并不一定是最优回答，实际回答需要根据自身情况考虑，有没有覆盖到的问题佬们也可以在评论区补充和给出现有问题的另一种回答hr面耗时一般在15min-30min左右，主要涉及一些基本问题，如个人情况，学...

找实习多的是你不知道的事投递实习岗位前的准备

点赞评论收藏

转发

3 2 评论

全站热榜

正在热议

# 牛友的五一计划 #

7389次浏览 192人参与

# 如何一边实习一边秋招 #

199590次浏览 3975人参与

# 牛客帮帮团来啦！有问必答 #

387539次浏览 7688人参与

# 如何看待offer收割机的行为 #

191658次浏览 2963人参与

# 春招别灰心，我们一人来一句鼓励 #

20399次浏览 301人参与

# 无实习如何秋招上岸 #

170785次浏览 2698人参与

# 硬件人的春招flag #

14447次浏览 199人参与

# 晒一晒我的offer #

2808241次浏览 49778人参与

# 非技术岗薪资爆料 #

7235次浏览 148人参与

# 在国企工作的人，躺平了吗？ #

72088次浏览 874人参与

# 第一次面试 #

15936次浏览 242人参与

# 你更愿意参加线上面试还是线下面试？ #

6654次浏览 92人参与

# 华为求职进展汇总 #

439866次浏览 4421人参与

# 来聊聊机械薪资天花板是哪家 #

21428次浏览 169人参与

# 简历中的项目经历要怎么写 #

379138次浏览 6378人参与

# 通信硬件薪资爆料 #

146021次浏览 1100人参与

# 机械人怎么评价今年的华为 #

54415次浏览 449人参与

# 应届生应该先就业还是先择业 #

12255次浏览 115人参与

# 除了offer，现在你还缺点啥？ #

2650次浏览 53人参与

# 女生做医疗销售有前景吗 #

3783次浏览 48人参与

牛客网
牛客企业服务