2024年了，新开一个模拟赛。

2024.1.2

被龙哥吊打了。就只会做一道题，暴力还挂分。但是B题乱写的 \(k=1\) 有 \(30\) 分，乐。

T1 先欧拉筛，然后把每个数分解质因数，顺便统计答案。再做一个前缀和，就能 \(O(1)\) 回答询问了。时间 \(O(n \log n + m)\)。

T2 答案是满足单调性的，所以考虑二分答案。check 可以 dp，设 \(f_i\) 表示在前 \(i\) 个大厦中，第 \(i\) 个大厦不修改的满足条件的最小次数。初始时每个 \(f_i\) 都是 \(i-1\)。转移如果有一个 \(j\) 满足 \(\mid h_j -h_i \mid \le(i-j)\times x\)，那么就可以把 \([j+1,i-1]\) 中的数修改以满足条件，因此 \(f_i =\min \{f_j+i-j-1\}\)。最后看是否有一个 \(f_i+n-i\le k\) 就行了。\(O(n^2\log n)\)。

T3 若选了一个正数，那么和他连成一段的所有正数都会被选，因为这样一定更优。负数同理，因为选负数的目的就是把它两边的正数拼接到一起。于是我们把相邻的正数和负数压成一个数，让数列变成一个正负相间的序列。我们的最优策略一定是把所有正数都选上，若后面那个序列正数个数 \(\le m\) 那么和就是答案，因为根据题意一定有 \(\ge m\) 个正数。否则，我们就要舍弃一些正数，或者选一些负数把正数拼起来，让段数 \(\le m\)。直接贪心就是从小到大排序然后删，但是这样可能不对。因为有可能你把一个正数选了，但是最优策略其实是把他两边的负数一起选然后连起来。因此我们需要反悔贪心，在选了一朵花之后把他和相邻两朵花合并成一朵，如果再次贪心选择到新插入的花，就表示刚才的贪心需要反悔，实则选两段为负的花连接三段为正的花更优。

实现用优先队列和双向链表。

T4 每种符号不满足结合律，所以得换一种方式去思考。可以拆位，每一位互不影响。于是直接用线段树维护每一位从 \(0/1\) 开始，经过一个区间 \([l,r]\) 会变成什么。直接做就是两个 \(\log\)，但是如果把每一位放在一起变成一个数就可以 \(O(1)\) 修改，去掉一个 \(\log\) 了。

2024.1.4

CWOI

一分没挂，但是后两题一分没打。

T1 选直径的两个端点，并在他们两个下方每次选最大深度的叶子一定最优。答案就是 \(d+2(m-1)mx\)，\(d\) 是直径，\(mx\) 表示从 \(1\) 出发最深的叶子节点的深度。但是有些情况不合法。当树是一条链时，\(1\) 号点是不能扩展的，因此答案就是 \(md\)。还有可能直径的端点是一号点，此时选一号点不优，每次只能多加一个直径，因此要选次长直径去算答案。

T2 非简要题意：构造一种 \(n \times m\) 棋盘上的 \(k\) 子棋平局局面或报告无解。这个真的是非简要题意，简要题意：

一开始想了不能出现 \(k\) 子连，那么就在一个 \((k-1)\times (k-1)\) 的小矩阵里构造，交错放黑子、白子，相邻两个矩阵让他们黑白互换，这样就能保证黑子和白子数量一样。但这样有个问题：边上和下面会剩下来一坨。我直接把边上和下面也按顺序填了，一开始还感觉很对，但后面 rand 了一组数据，有可能会在填边角料时和上面填好的矩阵斜着连成 \(k\) 字，还极不好处理。因此我换了一种构造方式：直接竖着连着放 \(k-1\) 个黑子，再连着放 \(k-1\) 个白子（抵到 \(n\) 了就把 \(n\) 行放完就行），如果 \(m\) 是奇数多出来一列，那就在那一列前面 \(k-1\) 个白 \(k-1\) 个黑的放，最后剩下一小点黑白交错放，看上去很对，因为这样放最多就是多出来那列和前面的连成三子。既然可能连成三子，那 \(k=3\) 就会出锅。比如：