前言

划水打了这场比赛，感觉签到题稍有点多，^_^，整体做起来挺舒服的。

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

A. 宇宙万法的那个源头

式子可以拆为 11145 * (10^5x + 10^(5x - 5) + ... + 10^5 + 1)

所以质数一定小于11145，然后巴拉巴拉一顿分析....

回到正题，因为3是11145的因子，且这个数是奇数

所以3就是天选之子。

B. 小苯的台灯

如果模数较小，那么一定存在循环节（I题 带猫猫任务也涉及这块）。

所以模拟就行了，因为存在较小的循环节。

C. 小苯的排列构造

可以把 2 4 1 3 作为内核

然后n > 4按奇偶在两边拓展

大概是这样子 2n - 1, 2n - 3, ..., 9, 7, 5, || 2, 4, 1, 3, || 6, 8, 10, ..., 2n - 2, 2n

当n<4时，不存在这样的序列。

D. 408之计算机网络

模拟题, 可以把ip地址转换为一个32位整数，C语言中有个类型，叫做union，感觉可以简化不少。

这边的思路，是拆位统计，如果所有的ip在i位都相等，则属于CIDR前缀。

属于简单，但是写起来稍头痛。

E. 小苯的连续因子

本质是区间LCM(最小公倍数)最小。

要区间lcm最小，那[l, r]一定是[1, k]，这样时间复杂度为

但是这个需要高精度支持，涉及高精度后，时间复杂度远比之前的高很多了。

那如何求解呢？ 至少持平O(nlogn), 甚至O(n)

其实是小于等于k的所有质数(带次数)的乘积，这样就能减少时间复杂度。

欧拉筛, 枚举质数及其指数(质数总个数为), 因此感觉整体接近

埃式筛也可以过，并没有卡时间复杂度，卡的是直接lcm，因为高精度代价大。

F. 小苯选择队友

分组 + 前缀和预处理 + 滑窗

分组是为了枚举战队，然后模型就转变为

寻求数组中最大的子数组和

这就是经典问题了，DP/双指针都可以。

G. 轻舟已过万重山

防AK题，忽视

H. 小红的字符串构造

防AK题，忽视

I. 小苯的带猫猫任务

0-1背包的裸题

每个猫都是独立的，难点在于如何确定猫的最小代价

pos - left * x + right * y = 0 % like

这边有两种方式，至少我这边想到的。

• exgcd，求得xy的组合, 保留最小的px+qy
• 预处理right的循环节(like<=3000), 然后枚举left的x值, O(n)代价求得最小的px+qy

所以整体上，

J. 408之数据结构

使用了“珂朵莉树”

我对这个数据结构定义有点模糊

大概的意思，

• 使用set
• key为区间
• set内区间不存在重叠

因为set(java的treeset)支持lower_bound/upper_bound，所以添加和查询相对容易，满足mex操作即可。

当然这题也可以借助

• 链式并查集

瞄了下官解，好像解法更优，用set存 不存在的数，如果添加就remove，查询就是find first.

K. 小苯的矩阵

LIS的变体

同列的值只能取一个，所以难点其实在这里

如何规避这个问题，可以对同列从大到小进行遍历，然后进行常规的LIS操作

这样就可以得到解了。

从大到小，这个trick技巧，完美避免干扰。

官解说，灵感来自某一场力扣周赛，其实那题我印象很深，为啥呢？因为那题我看错题了，看错的题意就是这个题的弱化版，T_T.

L. 小苯的异或疑惑（easy）

和M一起讲

M. 小苯的异或疑惑（hard）

异或的技巧，因为每个值，参与次数 n - 1次

如果n-1为偶数，那结果一定为0

如果n-1位奇数，那每个值参与异或一次

所以最终结果为 数组整体的异或和。

N. 中华文化，博大精深！

原神，启动！

写在最后