先报个人难度:红,红/橙,黄,黄/绿,橙,黄,橙/黄,蓝。
T1 - 纪念品商店
如果他在商店区左边,就往右边移至商店区最左边的商店。
如果他在商店区右边,就往右边移至商店区最右边的商店。
时间复杂度 O(1)O(1)O(1)。
思考,如果要小码君恰好移动 DDD 步,还要特判哪种情况?
T2 - 删除元素使数组去重
这题数据范围不算太大,可以直接用桶模拟。
时间复杂度 O(N+Ai)O(N+A_i)O(N+Ai )。
T3 - 摩天轮
超难数学题。
本题分为两步:
1. 计算出当他们登上摩天轮 SiS_iSi 分钟后的坐标。
2. 通过坐标计算出角度。
由于摩天轮关于 XXX 轴平行,所以此时的旋转坐标公式应为:
y=(y1−y2)cosθ−(z1−z2)sinθ+y2y=(y_1-y_2)\cos \theta-(z_1-z_2)\sin \theta+y2y=(y1 −y2 )cosθ−(z1 −z2 )sinθ+y2,
z=(z1−z2)cosθ+(y1−y2)sinθ+z2z=(z_1-z_2)\cos \theta+(y_1-y_2)\sin \theta+z_2z=(z1 −z2 )cosθ+(y1 −y2 )sinθ+z2 .
并且因为摩天轮是平行于 ZZZ 轴的,所以 y1−y2=0y_1-y_2=0y1 −y2 =0.
最终的公式为 y=−(z1−z2)sinθ+y2y=-(z_1-z_2)\sin \theta+y2y=−(z1 −z2 )sinθ+y2,z=(z1−z2)cosθ+z2z=(z_1-z_2)\cos \theta+z_2z=(z1 −z2 )cosθ+z2 .
我们知道仰角和俯角实际上就是两个点构成的直角三角形的角度,如图所示:
α\alphaα 就是 AAA 看向 BBB 的仰角度数。
我们只需要知道 AC,BCAC,BCAC,BC 的长度即可套公式 α=arctan(ACBC)\alpha=\arctan(\dfrac{AC}{BC})α=arctan(BCAC ) 求出。
显然,在本题 ACACAC 就是小码君和小码酱在 XOYXOYXOY 平面上的距离,BCBCBC 就是两人的高度差。
说完了,上代码!
时间复杂度 O(Q)O(Q)O(Q)。
T4 - 线性探查法
这道题目考的是哈希,那肯定会卡哈希,所以我就不用 unordered_map 做了
本题插入的意思就是找到第一个内容为空的单元,如果直接暴力会被卡到 O(N)O(N)O(N)。
但是,众所又周知,线段树可以 O(logN)O(\log N)O(logN) 找到第一个符合条件的点!
那么,模拟,秒了。
诶等等,在样例的第 444 次操作中,由于前面没有空位,它探测到后面去了!
没事,像合并石子一样,再复制一个拼接到后面就能当循环空间用了。
时间复杂度 O(QlogN)O(Q\log N)O(QlogN)。
T5 - 统计 ACGO 的出现次数
先看这题:P2646 数数zzy - 洛谷 | 计算机科学教育新生态
如果字符串出现了 y ,那么在它之前的 z 任意挑两个和这个 y 都可以组成一个 zzy 的子序列。
所以核心代码如下:
这题同理,只不过复杂一些。
我们先记录 a 的数量。
如果一个字符是 c,那么在它之前所有的 a 与这个 c 都能组成一个 ac 的子序列,记录下来。
如果一个字符是 g,那么在它之前所有的 ac 与这个 g 都能组成一个 acg 的子序列,记录下来。
如果一个字符是 o,那么在它之前所有的 acg 与这个 o 都能组成一个 acgo 的子序列,记录下来。
答案就出来了!
时间复杂度:O(N)O(N)O(N)。
T6 - 美丽数 II
解法:我们从 222 开始,枚举不超过 Ai\sqrt{A_i}Ai 的质因子,然后判断即可。
注意一定得遍历质数,不然单次查询时间复杂度就会退化至 O(Ai)O(\sqrt{A_i})O(Ai )。
时间复杂度:O(AilnlnAi+QAilnAi)O(\sqrt{A_i}\ln\ln A_i+Q\dfrac{\sqrt{A_i}}{\ln A_i})O(Ai lnlnAi +QlnAi Ai )。
T7 - 数的集合
分类讨论:
这个数是不是质数?是?那就没得操作了,直接输出 000。
如果不是质数,那他有没有为 222 的质因子?
有:那就能把所有 2×i(2×i≤N)2\times i(2\times i \le N)2×i(2×i≤N) 的数都给加进这个集合内,然后所有 i(2×i≤N)i(2\times i \le N)i(2×i≤N) 也都进去了。
没有:那就把其中一个质因子 ×2\times 2×2 放进集合内,可以证明它必定小于 NNN。然后就和上面的一样了。
当 NNN 足够大时(N≥32N\ge 3^2N≥32 就行),显然不能进入集合的只有所有 >⌊N/2⌋\gt \lfloor N/2\rfloor>⌊N/2⌋ 的质数。显然这可以前缀和秒掉。
时间复杂度 O(NlnlnN+T)O(N\ln\ln N+T)O(NlnlnN+T)。
T8 - 巨大的表格
这道题可以发现 NNN 很小,但也没小到那种程度,注意到这题刚刚好能通过 O(N3)O(N^3)O(N3) 的算法。
而且 MMM 又这么大……还是递推题……
这就需要矩阵快速幂了。
我们可以构造如下的神秘矩阵:
[......,T,S×T,S2×T,S3×T,S4,S4...,0,T,S×T,S2×T,S3,S3...,0,0,T,S×T,S2,S2...,0,0,0,T,S,S...,0,0,0,0,1,1...,0,0,0,0,0,1]\begin{bmatrix} ...\\ ...,T,S\times T,S^2\times T,S^3\times T,S^4,S^4\\ ...,0,T,S\times T,S^2\times T,S^3,S^3 \\ ...,0,0,T,S\times T,S^2,S^2 \\ ...,0,0,0,T,S,S\\ ...,0,0,0,0,1,1\\
...,0,0,0,0,0,1 \end{bmatrix} ......,T,S×T,S2×T,S3×T,S4,S4...,0,T,S×T,S2×T,S3,S3...,0,0,T,S×T,S2,S2...,0,0,0,T,S,S...,0,0,0,0,1,1...,0,0,0,0,0,1
这个矩阵乘上
[...A4,i−1A3,i−1A2,i−1A1,i−1i−11]\begin{bmatrix} ...\\ A_{4,i-1}\\ A_{3,i-1}\\ A_{2,i-1}\\ A_{1,i-1}\\ i-1\\ 1 \end{bmatrix} ...A4,i−1 A3,i−1 A2,i−1 A1,i−1 i−11
就可以得到
[...A4,iA3,iA2,iA1,ii1].\begin{bmatrix} ...\\ A_{4,i}\\ A_{3,i}\\ A_{2,i}\\ A_{1,i}\\ i\\ 1 \end{bmatrix}. ...A4,i A3,i A2,i A1,i i1 .
然后就可以快速幂了。
构造矩阵的办法在这题的题解里详细介绍,可以去看看。
时间复杂度 O(QN3logM)O(QN^3\log M)O(QN3logM)。
初次推矩阵耗时可能长一些,但熟练之后两三分钟就可以完成了。加油!