传送门
A. Enju With math problem
题意:
给出 \(a_1,\cdots,a_{100}\), 满足 \(a_i\leq 1.5*10^8\).
现在问是否存在一个 \(pos\), 满足:
\[ \forall x\in [1,100],a_x=\varphi(x+pos-1) \]
思路:
假设素数间隔没有超过 \(100\), 那就很简单, 直接枚举 \(a_i\), 判断 \(a_i+1\) 是否为素数, 反解出 \(pos\) 再来逐一验证即可.
但是素数间隔很可能是超过 \(100\) 的.
因为 \(\varphi\) 为积性函数, 所以考虑两个素数的乘积形式, 假设为 \(p*q\), 并且一定存在一个较小的素数 \(p\), 乘以 \(q\) 可以让结果落在对应区间.
至于为什么, 还是考虑素数间隔总体来说是比较小的, 平均为 \(logn\) 级别, 所以将一个素数乘以某个较小的数能大概率落到连续区间内...(好吧, 我在口胡)
所以直接枚举一个较小的素数, 然后利用欧拉函数性质, 反解出 \(pos\), 同样逐一验证即可.
注意及时 break 是一个比较重要的减枝, 不然可能会 T.
- Code
- B. Fire-Fighting Hero
题意:
这个题意有点绕, 简单来说, 就是给出一个点 \(S\) 和一个点集 \(V\), 现在要求 \(S\) 和 \(V\) 到所有点最短路最大值的最小值.
思路:
显然从 \(S\) 出发只需要跑一次最短路即可.
那么对于点集 \(V\) 呢? 因为我们可以看作同时从每个点集中的点出发, 那么将其初始 \(d\) 赋为 \(0\) 就好了.
详见代码:
- Code
- C. Hello 2019
题意:
给出一个串 \(T\), 现在有多个询问, 对于每个询问, 需要回答区间中最少删除多少个数, 使得区间里面不含 \(8102\), 但是含 \(9102\) 这样的子序列.
思路:
\(cf\) 上面的一个原题... 和那道题的做法一样, 只是我们把串反过来处理即可.
- Code
- E. Magic Master
模拟题, 没什么好说的, 倒过来模拟即可.
可以使用双端队列来搞, 速度很快, 因为双端队列可以支持随机访问.
- Code
- G. Pangu Separates Heaven and Earth
愉快签到.
- Code
- H. The Nth Item
题意:
定义递推式:
\[ \begin{aligned} F(0) = 0&, F(1) = 1\F(n)=3*F(n-1)&+2*F(n-2),(n\geq 2) \end{aligned} \]
现在给出 \(Q\) 组询问,\(Q\leq 10^7\), 对于每次询问, 回答 \(F(n),n\leq 10^{18}\).
思路:
一开始打了个表找循环节, 打到 5000w 都没出来;
后面灵光一现, 从 \(MOD\) 往前面打, 找出循环节 \(P=\frac{MOD-1}{2}\).
那么对于每次询问, 直接上 \(BM\) 或者矩阵快速幂即可, 加个记忆化就能过了.
P.S: 矩阵快速幂的话可以用 \(k\) 进制快速幂, 然后预处理转移矩阵的 \(1,2,\cdots,2^k\) 即可. 这样的话每次询问大概就是 \(2*2*3\) 的复杂度.
题解的做法大概就是利用特征根法解得通项, 然后预处理出快速幂, 对于每次询问直接算就行了.
因为通项有个 \(\sqrt{17}\), 解决办法就是二次剩余.
- Code
来源: http://www.bubuko.com/infodetail-3189673.html