PYYZ 摸底测 Day2 总结

link

T1 数学题

Problem

给 $n$，有 $abc=n$，其中 $a,b,c$ 均为质数且有 $a\leq b\leq c$，求 $b$。

$100\% \rightarrow 10\leq n\leq 10^{14}$

$1\text{s}/128\text{MB}$

Solution

分解质因数即可，注意一下同一个因数出现两次以上的情况。

时间复杂度 $\mathcal{O}(\sqrt n)$。

Summary

$100\text{pts}$

T2 子序列

Problem

给出一个长度为 $n$ 的序列 $a_i$，找出一个子序列使得其和对 $m$ 取模后的值最大，输出这个值。

$100\text{pts}\rightarrow 1\leq n\leq 35,1\leq m,a_i\leq 10^9$

$1\text{s}/256\text{MB}$

Solution

考虑 Meet in the Middle，将两边分别爆搜子序列所得到的和存进两个 set 中，然后遍历第一个 set 的所有数 $x$，在第二个 set 中找最大的 $y$ 满足 $y < m-x$，答案显然为 $\max (x+y)$。

时间复杂度 $\mathcal{O}(2^{\frac{n} {2}}\log 2^{\frac{n}{2}})$。

Summary

原来 xb 昨天晚上讲 Meet in the Middle 是有原因的。

赛时没想到，然后写了个**的 $\mathcal{O}(n^5\log n^5)$ 的暴力居然在 OJ 乱草了 $70\text{pts}$，在本地草 $80\text{pts}$ 还是因为 MLE 没 TLE。

对于昨天讲过的 Meet in the Middle，wssb，仅仅对于没想出来打的暴力来说，赢麻了。

以后遇到指数乘二级别的数据先想 Meet in the Middle。

T3 模

Problem

给出长度为 $n$ 的序列 $a_i$ 和 $m,q$，$q$ 次询问：

• 单点加减，如果不够减就不减，输出修改后的数。
• 查询区间 $[l,r]$ 中所有模 $m$ 意义下值为 $x$ 的数的和。

$100\% \rightarrow 1\leq n,q,a_i\leq 10^4,m\leq 10$

$1\text{s}/512\text{MB}$

Solution

模数很小，考虑直接建 $10$ 个树状数组，按取模后所得值分类，修改的时候把数从原来取模后所得值对应的树状数组中删除掉，再把数从后来的数的取模后所得值对应中的树状数组中添加上，查询的时候直接差分查询对应的树状数组就行。

时间复杂度 $\mathcal{O}(n\log n)$。

Summary

这题比 T1 过的都多，算是签到题。

$100\text{pts}$

T4 组队

Problem

给出一个长度为 $n$ 的序列 $a_i$，至多可以修改 $k$ 次使得 $a_i$ 变为任意整数，求将序列至少分成多少块才能使得每个块中任意两数之积不为平方数。

$30\% \rightarrow 1\leq n\leq 10^3,k=0$

$100\% \rightarrow 1\leq n\leq 10^5,1\leq a_i\leq 10^7,0\leq k\leq 20$

$1\text{s}/256\text{MB}$

Solution

考虑 DP，设 $f_{i,j}$ 为前 $i$ 个数中修改了 $j$ 次分成的最小块数，很自然的想到枚举 $k,p$ 并 $f_{i,j}\leftarrow f_{k,p}$，那么就要保证 $[i+1,k]$ 内作为一整块时需要修改的数为 $p-j$。

如何快速转移？设 $g_{i,j}$ 为最小的 $x$ 满足 $[x,i]$ 作为一整块时修改的次数为 $j$，这样的话转移方程就为 $f_{i,j}=\min f_{g_{i,k},j-k}+1$，答案显然为 $\max_{i=1}^{n} f_{n,i}$。

为什么？因为对于每一个 $k$ （即枚举的从上一个划分点到 $i$ 消耗的修改次数，也就是说 $g_{i,j}$ 实际上是方便快速找划分点）来说只会修改一次，而又因为 $g_{i,j}$ 求的是最小的 $x$，最远所以最优。

如何求 $g_{i,j}$？对于一个 $j$ 来说，若（出现次数为奇数的因子）的出现次数加起来有 $\geq 2$ 时说明绝对有积为平方数，需要一次修改。由于 $10^7$ 内的质数有大约 $2\times 10^5$ 个，所以保证一次修改就能使得没有两数积为平方数。若需要修改的次数超过了当前枚举的 $j$，则说明需要分开。且当 $i$ 增加时 $g_{i,j}$ 必然单调不减，双指针即可，具体实现见提交记录。

预处理复杂度 $\mathcal{O}(nk)$，转移复杂度 $\mathcal{O}(nk^2)$，故总时间复杂度 $\mathcal{O}(nk^2)$。

Summary

$30\text{pts}$ 暴力，想到状态了转移确实没想到，gg。

T5 玩树

Problem

给出一个有 $n$ 个结点的树，点权为 $a_i$，定义一条有 $k$ 个节点的路径权值 $\mathrm{path}_{i,j}$ 为 $\frac{\prod_{p=1}^{k}a_p}{k}$，求 $\min \mathrm{path}_{i,j}$，多测。

$10\% \rightarrow n\leq 10,a_i\leq 10$

$100\% \rightarrow 1\leq n\leq 5\times 10^4,\sum n\leq 5\times 10^5,1\leq a_i\leq 10^9$

$2\text{s}/512\text{MB}$

Solution

首先，答案的路径中至多有一个 $2$，其它全为 $1$。

为什么？若存在 $a_i > 2$，则删掉之后分子除以 $a_i$，而分母只除以 $2$，显然更优。若有多个 $2$，若只在一边则显然分开后只有 $1$ 的一边更优，而若只有两个 $2$ 且都在中间，则从中间分开后答案不变，再接一个 $1$ 后答案还能更优，故可以直接把所有 $a_i > 2$ 的点全删掉。

设 $f_{x,k}$ 为以 $x$ 为根，权值积为 $k$ 的最长长度，那么若枚举两点权值积分别为 $i,j$，则答案为 $\min \frac{i\cdot j}{f_{x,i}+f_{y,j}}$。

怎么求 $f_{x,k}$？$f_{x,a_x\cdot i}=\max f_{y,i}+1(a_x\cdot i\leq 2)$。

当 $\forall i\in [1,n],a_i > 2$ 时直接输出 $\frac{\min a_i}{1}$。

还有要设答案初值为 $\frac{\min a_i}{1}$。

时间复杂度 $\mathcal{O}(n)$。

Summary

$10\text{pts}$ 的暴力居然没人写？于是我要了