会员标识 avatar-decorate
王清楚 level
牛客运营 identity
获赞
4684
粉丝
1.2W
关注
58
看过 TA
9831
女
焦作市第一中学
2020
C++
IP属地：北京
qwq
私信
关注
发布(612) 评论 刷题 收藏
头像 会员标识
2021-11-23 14:32
牛客运营
【题解】Wannafly挑战赛6
T1 完全平方数 中完全平方数个数就是 注意特判0 T2 比赛  算出一个题被做出来的概率，然后枚举一下每个题是否被做出来，算算贡献  T3 逆序对  考虑每一位为0的贡献：设这当前为第i位，前面则有位，即个数，根据和个数应该相同，那么的个数为这些数总数的一半，即这样的数字共有个（即后面的位数），所以每一位的贡献是总的个数为：   即  快速幂搞一搞就好，注意取模。 T4 锁 答案是这样的居民子集个数重要度的和不足，但加入任何一个新居民都将导致重要度的和大于等于。必要:由于上面的集合重要度都不够,他们都至少缺一把锁。若不足把锁,这些子集中必有两个缺同一把锁。把这两个子集和并起来,仍然缺这把锁,...
0 点赞 评论 收藏
分享
头像 会员标识
2021-11-23 14:31
牛客运营
【题解】Wannafly挑战赛5
T1 珂朵莉与宇宙  值域只有  所以只用考虑的完全平方数   for一遍，然后暴力一下    T2 可编程拖拉机比赛  按题意模拟即可就是用ceil减去floor  T3 标准差 出题人的做法： 枚举平均数 ,重算边权, .二分答案，判断ST之间是否有长度为负的路径即可(负环也可以) .通过计算可得二分的复杂度是。或者也可以是.Bellman-Ford求负环复杂度。总复杂度,不太满。 验题人的做法： 首先发现这个才，才 我们可以两眼一闭大力搜  先搞出根可达的所有点  然后搜，找到一个环的话，要么不在上面转，要么在上面转永久次，所以可以直接拿那个环的方差来当答案  然后就15ms AC…… ...
0 点赞 评论 收藏
分享
头像 会员标识
2021-11-23 14:30
牛客运营
【题解】Wannafly挑战赛4
T1 解方程  枚举a 和b，那么 c 唯一确定，用数组或者map 判断一下这样子的c 是否存在。  T2 小AA的数列 按位（二进制的位）考虑每位对于答案的贡献。令表示前个元素里 第位为的数字个数的奇偶性。考虑数列中第个元素为区间右端点，对于 第位，我们只要求出中有多少个元素与不相等且 区间长度为偶数就可以了，而这可以用一个前缀和搞定。 ans  其中第一维表示考虑第位，第二维表示考虑的前缀和的位置，第三维表 示前缀里第bit位为1的数字个数的奇偶数，第四维用来满足长度为偶数的要求。 T3 割草机  首先把最后的那些全是空地的行去掉（因为割草机去这些行是完全没有意义 的）。   问题其实等同...
0 点赞 评论 收藏
分享
头像 会员标识
2021-11-23 14:27
牛客运营
【题解】Wannafly挑战赛3
T1 珂学送分 用表示这段子序列可以切成的期望段数，对于每个，我们可以找到一个最大的，使得这段的和不超过，那么有。随着的减小，其对应的也会减小，所以可以用一根单调的指针维护。的计算有一个后缀和解决。  T2 遇见 找到A的车的挡位的最快速度和最慢速度，那么他和B之间的相对速度就是（B的速度+A的速度），用总距离除以最快和最慢的速度，分别计算即可。注意单位之间的转换，1m/s=3.6km/h。  T3 位数差  设为在十进制下的位数，那么  可以在读入的时候算好，而计算 ，其实和a数组里元素的顺序没什么关系，所以可以把数组排序后从大到小枚举每个，考虑比小的数加上去的情况，位数要不不变，要不就加，...
0 点赞 评论 收藏
分享
头像 会员标识
2021-11-23 12:21
已编辑
牛客运营
【题解】 Wannafly挑战赛2
T1 Cut 采取逆向思维。问题就变成我们采取不断合并的策略，使得总代价最大。于是变成了经典的哈夫曼树题。每次从剩下的元素中挑选两个最大的进行合并，直至剩下一个元素。此题得解。 T2 Travel 通过一些观察可得：节点 到节点 的最短路肯定为以下两种情况之一： 1、不经过额外的 条边直接从 到 。 2、从先走到某个为额外边端点的 ，再从 走到某个同样为额外边端点的 ，最后从 走到 。 预处理所有额外边的端点间两两最短路，询问时暴力枚举更新答案即可。 时间复杂度： 。 算法二： 进一步观察可得，以上第二种路径可进一步化简为：从 先走到第一个为特殊边端点的 ，再从 走到最后一个为特殊边端点的 ，...
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了：
牛客网
牛客网在线编程
牛客网题解
牛客企业服务