摸底考试 #2

Dubnium / 2023-08-27 / 原文

T1 数学题

令 \(A,B,C\) 为三个质数 \((A \leq B \leq C)\) , \(N=A \times B \times C\) ,给定整数 \(N\) ,求 \(B\)

【数据范围】

\(10 \leq N \leq 10^{14}\)

题解

分解质因数即可

时间复杂度 \(O(logN)\)

T2 子序列

给定一个长度为 \(n\) 的序列 : \(a_1,a_2,a_3, \cdots a_n\)
要求你从中选出一个子序列，使得这个子序列的和对 \(m\) 取模后最大

【数据范围】

\(1 \leq n \leq 35,0<m,a_1,a_2,a_3, \cdots ,a_n \leq 10^9\)

题解

因为 \(n\) 的规模非常小,故考虑 \(meet~in~the~middle\)

将 \(n\) 个数字分成两半,但对于每一半分别把暴力求出两段的子序列之和并存储到数组 \(a\) 和 \(b\) 中并分别排序去重,然后枚举 \(a\) 中的元素并在 \(b\) 中找到第一个小于等于 \(m-1-a_i\) 的值(答案最大就是 \(m-1\) ),最终统计答案即可

计算小于等于当前元素的方法是 \(upper\_bound-1\) (二分第一个大于该元素的值的前一个,注意边界需要特判)

时间复杂度 \(O(2^{n/2}+log2^{n/2})\)

T3 模

【数据范围】

\(1 \leq n,q \leq 10^4,m \leq 10,a_i \leq 10^4\)

题解

考虑建十棵树状数组(因为 \(m \leq 10\) ,所以总共的可能余数就 \(10\) 种),第 \(i\) 棵树状数组表示数组 \(A\) 中有多少个对 \(m\) 取模后值为 \(i\) 的数字,每次直接查询区间和即可

时间复杂度 \(O(nlogn)\) ( \(n,q\) 同阶)

T4 组队

【数据范围】

\(n \leq 10^5,1 \leq a_i \leq 10^7,0 \leq k \leq 20\)

题解

比较经典的需要辅助数组的DP题

状态设计:设 \(dp_{i,j}\) 表示当前已经划分到 \(i\) ,且已经改变了 \(j\) 个数能划分出的最小段数

状态转移:考虑到当前枚举到 \(i\) 点,且要进行 \(j\) 次修改,故考虑枚举上一段的修改次数 \(p\) ,并且结束点最远为 \(k\) (贪心的往后取),那么 \(dp_{i,j}\) 的答案即是 \(\min\left(dp_{i,j},\min\left\{dp_{k,p}+1\right\} \right)\)

但考虑到快速求出在修改次数为 \(p\) 时,区间 \(i\sim k\) 合法时的最远的 \(k\)

并不是 \(O(1)\) 的,考虑如何快速求出 \(k\) 值

设辅助数组 \(l_{i,j}\) 表示在消耗 \(j\) 次修改后,使得 \(pos\sim i\) 为一个合法区间的最远的 \(pos\) ,通过这个数组,我们可以大大减化了DP过程

此时的状态转移方程即为 \(dp_{i,j}=\min(dp_{i,j},dp_{l_{i,x},j-x}+1)\)

下面就是求 \(l\) 数组,可以发现在修改次数 \(j\) 确定时, 随着 \(i\) 的增加, \(l_{i,j}\) 一定是单调不减的,所以可以用双指针求解,复杂度为 \(O(nk)\)

现在考虑如何快速判断一个区间到底需要进行几次操作才能变成一个合法区间

不难发现平方数分解质因数后,其所有质因子的指数一定为偶数(偶数才可平分),所以只需要知道当前数字每个质因子上的指数的奇偶性即可,可以用 \(O(nlog10^7)\) 的复杂度求解。而在判断当前序列中是否有两数相乘为平方数时,只需查看是否有多个数字一样即可

在预处理 \(l\) 数组的时候,记录需要更改的数字个数 \(cnt\) ,每一次遇到相同的数字就 \(++cnt\) ,当cnt大于当前可供操作的次数 \(lim\) 时,就不断 \(++j\) ,这时遇到相同的数字就 \(--cnt\) (去掉贡献),直到合法为止,最终 \(l_{i,lim}\) 的答案就是 \(j\)

最终答案即是 \(\min\left\{dp_{n,i}\right\}(i\leq k)\)

时间复杂度为 \(O(nk^2)\)