竞赛讨论区 > 牛客挑战赛54题解

牛客挑战赛54题解

头像
FST王者
编辑于 2021-11-26 18:03:28 APP内打开
赞 5 | 收藏 2 | 回复1 | 浏览620

A 小䓤的01串

将该01串重复两次,即可操作包含起点和终点相连的区间了。举个例子,对于字符串"abcdef"而言,我们重复两次可以得到"abcdefabcdef",那么"dfeab"区间可以通过取下标[3,7]得到。
显然合法染***间的长度一定是 。我们可以通过前缀和达成 查询,或使用队列等数据结构达成 转移。总复杂度

B 小䓤的一个数字

枚举操作二的次数,假设为次,则此时对二进制数为 的位 的代价为区间

C 小䓤的一些数字

  • 容易发现的取值最多有 种于是我们每段暴力跳即可

  • 就转为求

    • 法一

      容易发现 个,故分零块整块处理。具体的,令 ,则

    • 法二

      引入一个结论:

      证明来自《Concrete Math》:

      由此问题得到解决

D 小䓤的质因数

操作后,只剩一种质因子,只需要算出每种质因子最后剩余的概率。

表示一种质因子的次幂为 ,最后剩余这种质因子的概率,则

手动高斯消元可以做到 ,发现高斯消元的式子为 ,可以得道 为等差数列,结合 的初值,

复杂度为

E 小䓤的石头

按关键字排序后,问题变为对于定的左端点找到最小的合法右端点。

考虑双指针贪心,注意到问题不可撤销使用对顶栈技巧:即维护两个对顶栈,后一个栈维护的顺序和前一个栈维护的顺序相反,前一个栈空的时候就暴力重构。合并是朴素的。

然后模仿albus要第一个出场技巧每次插入/合并时高斯消元就可以处理本质可重K小异或和。

复杂度为

F 小䓤的树

以最小值为根,一定满足父节点小于子节点。

将点权转化到边权上,设 ,则加入的贡献为 可以直接加入贡献,剩下的部分变为对每个 找到 为新树的父亲使得 最小。

可以用点分治处理,将 转化为以 为变量, 为斜率的直线,即可用李超线段树计算最小代价。

复杂度为

G 小䓤的凸包

题目大意为给定

首先化式子,下设

,可以用各种方式求出

最简单的方式是用伯努利数展开自然数幂和,具体有

因此有

其中 在整除分块后我们只需求 范围的的区间和,这个可以配杜教筛实现。

是经典的类欧毒瘤套路可以见Loj138。

于是可以做到

Updated on 11.26,添加了标程。

B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49566307

C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49566302

D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49566310

E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49566313

F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49566329

G:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49566333

1条回帖

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

近期热帖

等你来战

查看全部

热门推荐