脚本宝典收集整理的这篇文章主要介绍了ARC127 比赛记录，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

打烂了。 被 A 卡了。 胡了 B 然后直接 skip 了。 被 C 卡了较长时间。 回头过 B。 卡了 D。

A

(1cdots n) 所有前缀数前缀 (1) 个数和。 求出至少有一个长度为 (k) 的前缀 (1) 的个数之和。 枚举 (k) 然后枚举这个前缀出现位置即可。 复杂度 (O(text{poly}(15)))。

B

直接构造。 发现第一位肯定有 (n) 个 (0) 和 (n) 个 (1) 和 (n) 个 (2)。 然后第一位的 (0) 和 (1) 不管只需要第一位的 (2) 后面跟着的最小即可。 直接暴搜搜出前 (3^{K-1}) 个最小的，然后直接填即可。

C

直接做做完了。 考虑先整体减一，第一位肯定是 (1) 然后诸位确定。 如果当前数是 (0)，那结束了。 否则如果属于 ([1,2^{m-1})) 肯定是 (0)，否则是 (1)。 如果属于 ([1,2^{m-1})) 那最高位就是 (0) 否则是 (1) 所以可以 (O(1)) 判断。 然后如果最高为是 (0) 就减 (1) 否则删去最高位。 根据结论对于一个二进制模拟进位复杂度均摊是 (O(1)) 的。 然后判断是否全 (0) 直接动态维护当前全局 (1) 个数即可。

D

卡 @AhoCorasick 的 我们需要判断 (a_ioplus a_j) 和 (b_ioplus b_j) 的关系。 考虑比较两个二进制数，是找到他们最高不相同位置然后比较，本质上就是 (oplus)。 那我们对于每个 (i) 我们把 (a_ioplus b_i) 作为代表，那两个数不同只需要比较代表元最高的不同位即可。 我们考虑在最高不同位处统计贡献。 考虑把所有当前这位是 (0) 的答案塞到桶里去，然后在对每个 (1) 在桶里查询。 有贡献当且仅当：它之前相同（信息量 (O(n))），当前这位不同。 然后贡献计算需要每位拆开，同时还需要记录贡献的是 (a) 还是 (b)。 这里直接分类讨论一下即可。 总复杂度是 (O(nLOG ^2n))。

脚本宝典总结

以上是脚本宝典为你收集整理的ARC127 比赛记录全部内容，希望文章能够帮你解决ARC127 比赛记录所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。