前言:
有幸拿到rk1,但由于服务器卡成OI赛制,少A整整一道题。
这里多吐槽一句，连我们学校校内软卓选拔都舍得开一个月600的云服务器(当时我负责的这事儿)。北师大也太勤俭持家了吧,弄两天弹性服务也成啊呜呜呜
面试:
感觉凉透了，老师一直在问我rk能保研不(双非低rk的伤)。然后英语问答也没准备好，让介绍家乡，我就憋了三句话(我感觉让我用中文说，也就能说三句话).还是要多准备模板啊！！！
A.签到题(略)
B.数列比较
题目思路:
将a,b数组对应的存成点对。对第一维度(a)升序排序,那么条件转化为:
当
a
[
i
]
>
a
[
i
?
1
]
当a[i] > a[i-1]
当a[i]>a[i?1]时，必须有
b
[
i
]
≥
b
[
j
]
,
j
∈
[
1
,
i
?
1
]
b[i] \geq b[j],j\in[1,i-1]
b[i]≥b[j],j∈[1,i?1].即
b
[
i
]
≥
max
?
j
=
1
i
?
1
b
[
j
]
b[i] \geq \max_{j=1}^{i-1}b[j]
b[i]≥maxj=1i?1?b[j].
所以根据我们的条件,对第一维排序，当相等的时候，对第二维升序排序。
这么排完后，我们只需要 O ( n ) O(n) O(n)的 c h e c k check check一遍第二维是否非降即可。
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
C矩阵乘法
n
≤
100
n \leq 100
n≤100
题目思路:
就枚举 a , b , c , d a,b,c,d a,b,c,d,强行解方程完事了，有点无聊的题目。当然，我还被卡常了，打了个表过了。
时间复杂度: O ( n 4 ) O(n^4) O(n4)
D.猴子打字
题目思路:
经典题目，我tm还能推错转移方程，自撒算了我靠。
不懂怎么做这题的，推荐看我这篇博客的第3题，把状态机思想弄明白
n ≤ 90 % n \leq 90\% n≤90%的做法:状态机 d p dp dp.
令 d p ( i , j = 0 / 1 / 2 / 3 ) dp(i,j=0/1/2/3) dp(i,j=0/1/2/3) 代表前 i i i个长度,并且当前以状态 j j j结尾的方案数.
j = 0 j=0 j=0代表当前没出现 b n u bnu bnu,且结尾也不是 b b b.
j = 1 j=1 j=1代表当前没出现 b n u bnu bnu,且结尾恰好是 b b b.
j = 2 j=2 j=2代表当前没出现 b n u bnu bnu,且结尾恰好是 b n bn bn.
j = 3 j=3 j=3代表当前已经出现了 b n u bnu bnu.
PS:这么定义状态是因为 b n u bnu bnu子串的出现一定是如上述按若干个小阶段构造出来的。
此时可以构建出有限状态机出来。状态的转移就像在图上游走。
如下图所示:
那么状态转移方程直接对着图推就好了:
d
p
(
i
,
0
)
=
d
p
(
i
?
1
,
0
)
?
(
k
?
1
)
+
d
p
(
i
?
1
,
1
)
?
(
k
?
2
)
+
d
p
(
i
?
1
,
2
)
?
(
k
?
2
)
dp(i,0)=dp(i-1,0) * (k-1) + dp(i-1,1)*(k-2) + dp(i-1,2)*(k-2)
dp(i,0)=dp(i?1,0)?(k?1)+dp(i?1,1)?(k?2)+dp(i?1,2)?(k?2)
d
p
(
i
,
1
)
=
d
p
(
i
?
1
,
0
)
+
d
p
(
i
?
1
,
1
)
+
d
p
(
i
?
1
,
2
)
dp(i,1)=dp(i-1,0) + dp(i-1,1) + dp(i-1,2)
dp(i,1)=dp(i?1,0)+dp(i?1,1)+dp(i?1,2)
d
p
(
i
,
2
)
=
d
p
(
i
?
1
,
1
)
dp(i,2)=dp(i-1,1)
dp(i,2)=dp(i?1,1)
d
p
(
i
,
3
)
=
d
p
(
i
?
1
,
2
)
+
d
p
(
i
?
1
,
3
)
?
k
dp(i,3)=dp(i-1,2) + dp(i-1,3)*k
dp(i,3)=dp(i?1,2)+dp(i?1,3)?k
n = 1 e 7 n=1e7 n=1e7时,开滚动数组优化空间即可.
满分做法:矩阵快速幂优化dp
这只要会矩阵快速幂优化fib递推式就可以了.
so,对于上面的转移方程，我们将没有的项补0可以构造出下面的矩阵递推式:
令转移矩阵为: T = ( k ? 1 k ? 2 k ? 2 0 1 1 1 0 0 1 0 0 0 0 1 k ) T=\begin{pmatrix} k-1& k-2 & k-2 & 0\\ 1& 1& 1&0 \\ 0& 1& 0&0 \\ 0& 0 & 1 &k \end{pmatrix} T=?????k?1100?k?2110?k?2101?000k??????.
那么有:
(
d
p
(
n
,
0
)
d
p
(
n
,
1
)
d
p
(
n
,
2
)
d
p
(
n
,
3
)
)
=
T
(
d
p
(
n
?
1
,
0
)
d
p
(
n
?
1
,
1
)
d
p
(
n
?
1
,
2
)
d
p
(
n
?
1
,
3
)
)
=
T
n
(
d
p
(
0
,
0
)
d
p
(
0
,
1
)
d
p
(
0
,
2
)
d
p
(
0
,
3
)
)
=
T
n
(
1
0
0
0
)
\begin{pmatrix} dp(n,0) \\ dp(n,1) \\ dp(n,2) \\ dp(n,3) \end{pmatrix}=T\begin{pmatrix} dp(n-1,0) \\ dp(n-1,1) \\ dp(n-1,2) \\ dp(n-1,3) \end{pmatrix}=T^n\begin{pmatrix} dp(0,0) \\ dp(0,1) \\ dp(0,2) \\ dp(0,3) \end{pmatrix}=T^n\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}
?????dp(n,0)dp(n,1)dp(n,2)dp(n,3)??????=T?????dp(n?1,0)dp(n?1,1)dp(n?1,2)dp(n?1,3)??????=Tn?????dp(0,0)dp(0,1)dp(0,2)dp(0,3)??????=Tn?????1000??????
所以答案: a n s = T n [ 4 ] [ 1 ] ans =T^n[4][1] ans=Tn[4][1].
直接矩阵快速幂就好了~~
时间复杂度: O ( 4 3 l o g n ) O(4^3logn) O(43logn)
D.春游
题目思路:
40 % 40\% 40%的数据我直接bfs加输出路径了.
30 % 30\% 30%的数据，直接 [ u + 1 , v ] [u+1,v] [u+1,v]之间找一个不是 v v v的约数的素数。(把素数筛出来，二分u后枚举素数)。这样确实非常快，但是没有正确性。总之是乱搞的。
满分做法待补~~