【火题合集】2.19考试

煞笔出题人一百块标程都不给我

1.题目一

首先每个点记录一下上一个跟它颜色相同的点在哪

然后用树状数组维护:若一个新的颜色出现,则在该点位置+1

则一段区间[L,R]颜色个数为ask(R)-ask(L-1)

那么把询问按右端点排序,每次将r[i-1]+1到r[i]的点+1,同时将上一个颜色相同的点-1

可以确保答案仍然正确(因为某种颜色在后面出现过了前面就不需要再统计了,同时后面一段必然在当前询问区间内)

于是复杂度O(mlogn)

2.题目二

还不会

3.题目三

暴搜加个剪枝就能过了。。

4.题目四

后悔当时YJP讲递推转矩阵快速幂的时候没听。。

不过现在会了!

矩阵快速幂真是一个神奇的东西!

首先我们定义一个矩阵

$$\begin{pmatrix}f(i)&i+1&1\end{pmatrix}$$

其中f(i)表示第i天的答案

那么第0天的矩阵为

$$\begin{pmatrix}0&1&1\end{pmatrix}$$

每天我们将矩阵乘以这样一个矩阵【矩阵乘法都学过吧 不会的自行去补

$$\begin{pmatrix}x&0&0\\1&1&0\\0&1&1\end{pmatrix}$$

那么我们将第i天的矩阵乘以它可以得到的是

$$\begin{pmatrix}f(i)&i+1&1\end{pmatrix}
\begin{pmatrix}x&0&0\\1&1&0\\0&1&1\end{pmatrix}=
\begin{pmatrix}xf(i)+i+1&i+2&1\end{pmatrix}$$

其中xf(i)+i+1即为第i+1天答案 i也自动加了1 是不是很神奇233

那么第n天的答案即为

$$\begin{pmatrix}0&1&1\end{pmatrix}\begin{pmatrix}x&0&0\\1&1&0\\0&1&1\end{pmatrix}^n$$

把后面的那个用快速幂算。。于是复杂度变为了O(logn)

就可以A了

说点什么

2 评论 在 "【火题合集】2.19考试"

提醒
排序:   最新 | 最旧 | 得票最多
游客

作为出题人我要%%%%%

wpDiscuz