T1
根据组合的定义可知,题目要求的是 NNN 个数中取 111 个数的方案数。显然答案为 NNN。所以直接输出输入的内容即可。
时间复杂度:O(∣N∣)O(|N|)O(∣N∣)。
T2
由题意得,试剂的大小为 π×h×(r0)2\pi\times h\times (r_0)^2π×h×(r0 )2,一个弹珠的大小为 4π3×(r1)3\dfrac{4\pi}{3}\times (r_1)^334π ×(r1 )3。
设在激活 xxx 秒以内是安全的。
则可列不等式:
kx×4π3×(r1)3≤π×h×(r0)2kx×43×(r1)3≤h×(r0)2kx≤34h×(r0)2(r1)3x≤logk34h×(r0)2(r1)3.k^x\times\dfrac{4\pi}{3}\times (r_1)^3\le\pi\times h\times (r_0)^2\\ k^x\times\dfrac{4}{3}\times (r_1)^3\le h\times (r_0)^2\\ k^x\le \frac{\frac{3}{4}h\times (r_0)^2}{(r_1)^3}\\ x\le \log_k^{\frac{\frac{3}{4}h\times
(r_0)^2}{(r_1)^3}}. kx×34π ×(r1 )3≤π×h×(r0 )2kx×34 ×(r1 )3≤h×(r0 )2kx≤(r1 )343 h×(r0 )2 x≤logk(r1 )343 h×(r0 )2 .
我们先计算上面的值。注意,为了避免精度误差,我们可以这样计算:
34h×(r0)2(r1)3=3h×(r0)24(r1)3\frac{\frac{3}{4}h\times (r_0)^2}{(r_1)^3}\\ =\frac{3h\times (r_0)^2}{4(r_1)^3} (r1 )343 h×(r0 )2 =4(r1 )33h×(r0 )2
注意到 h,r0,r1≤108h,r_0,r_1\le 10^8h,r0 ,r1 ≤108,记得开 __int128。
时间复杂度:O(T)O(T)O(T)。
T3
水题,看样例解释即可,不做解释。
时间复杂度:O(1)O(1)O(1)。
T4
这难度安排的真不合理啊...
矩阵快速幂板子题。
你可以按照我的巨大的表格题解推理,最终的结果为
[1235810000010000010000010]N−5×[11111]\begin{bmatrix} 1&2&3&5&8\\ 1&0&0&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&0 \end{bmatrix}^{N-5}\times \begin{bmatrix} 1\\1\\1\\1\\1 \end{bmatrix} 11000 20100 30010 50001 80000 N−5× 11111
的第一行的数。
注意最后的 AnsAnsAns 输出形式。
时间复杂度:O(T×K3logN)O(T\times K^3\log N)O(T×K3logN),其中 K=5K=5K=5。
T5
我有一种绝妙的方法,但这里空太小,写不下。
T6
唯一真史。
这题又是模板套模板,难度叠难度,只要会模板就行。
游戏1
优先队列广搜模板。
时间复杂度:O(N×Mlog(N×M))O(N\times M\log (N\times M))O(N×Mlog(N×M))。
游戏2
马拉车模板。懒得学了,直接复制。
时间复杂度:O(∣t∣)O(|t|)O(∣t∣)。
游戏3
最简单的一个游戏。
我们把 sss 分成前后两半,把后半部分反转,如果两半中某一位置的字符不同,就加上花费的最小值。
时间复杂度:O(s)O(s)O(s)。
总代码如下:
本题数据有误,导致我的正确解法无法通过。