[数据结构与算法]noi2021题目分析大纲

写在前面
金牌线 393
银牌线 205
100银 282

day1T1

据说有类似原题

染色[SDOI2011]

$n,m<=5000$

暴力标记
喜提30

$A,B/A$

区间修改+单点修改+区间查询线段树
喜提20

$B$

树剖线段树维护标记

因为查询点必定为父子关系，所以考虑把操作1换成区间修改的“修改的最晚时间是什么”

查询的时候只要考虑这两个点的最晚修改时间是否相同

（其实这个是和正解最接近的部分分）

喜提20

$n,m<=2e4$

不知名log^3做法（并没有找到也没有想到什么参考）

估计是给正解常数大的人

10pts

$n,m<=1e5$

树剖线段树，维护区间左边颜色，区间右边颜色，区间内重边数目

20pts

day1T2

（吐槽）据说是过了一车人的LGV，不过…

据说和CF167E大致相同

CF167E

很容易观察到题目考察的内容——交点数的奇偶性——只与两条路径的起点与终点有关系。

如果起点是1,2,3,…n,终点是 $p_1,p_2,p_3...p_n$

那么交点数的奇偶性就是 $p_{1?n}$ 的逆序对数

$k==2$

邻接矩阵的行列式的答案

35pts

$B$

（感觉意思就是保证每一层的节点数都是1）

20pts

$n<=10$

估计是乱出的，我感觉它是想出个$2^{10}?2^{10}$的dp，然后数据范围出错了…（但是砍掉一半好像也没法做）

咨询了一些人 姑且把它当做乱出处理了
不包含AB，10pts (是不是给正解数组开小的人的)

$n_1=n_2=...=n_k/A$

行列式的值乘起来

（已经和正解非常接近了qwq）

(没有计算包含B的） 20pts

正解

乘起来的行列式/或者说lGV定理 不过如果是从上面的部分分推过来的话，其实可能会跳过LGV这一步

至于为什么行列式乘起来不对：喂喂，你的行列式是正方形耶…

但是不同的点数之间可能会出现长方形

20pts

day1T3

注意到题目只考虑可达性 因此要考虑缩点

自闭了我读错题了 我一直以为 加的两条边是可以钦定的 没想到是题目给定的 我恨…

所以我的那个new idea是不是可以出题之类的）

$n,q<=5,k=0/n<=1000$

考虑 一个点合法 当且仅当正向的时候 这个点能被$s$ 走到

边反向之后 这个点能被$t$ 走到

标记一下就好

复杂度应该是$mq$，但是就是可以冲过去）

28pts

$m=n?1$

首先 这个条件转换完之后 是一颗外向树

具体来说 因为题目保证联通，又有一个限制，如果$x,y$可以到达$z$ 那么x可以到$y$ 或者 $y$ 可以到 $z$

也就是说 到达一个点会出现两种方式

如果出现这种情况 $n?1$ 条边会不够用

因此是外向树

在这个条件下

$k=0$

直接统计 8pts

$k=1$

8pts

$k=2$

12pts

贴一个分讨的做法…就不人工手写了(主要还是因为看错题了所以非常悲伤）

k=1

分类讨论一下

$d[x]$表示x的深度

如果$s,t$是父子关系

如果$s$ 是子节点 那么从$s$ 往下最长链的叶子处 连一条边到根节点一定最优（答案是$s$子树内的最长链+$d[s]$）

如果$t$ 是子节点 答案是max($s,t$路径上的点,不经过$s,t$路径的最长链)+$d[t]$

否则 是$s$子树内的最长链+$d[t]$

维护的时候应该需要记录一下最长链，次长链，以及条数

k=2？

正解

所有做法的基础：

做法1： 结合外向树做法分类讨论

做法2： 结合暴力虚树

注意 要写$O(1)$ lca,不然会卡常到明年…

day2T1

数据点 1,3

bitset+unoerdered_map
$O(256^{k+1}logq)$
8pts
乱搞做法：（据说 没有深究正确性）

枚举有几位不一样 ，然后在trie上跑（也许可以多过几个k比价小的点）

复杂度是在 $O(256^{k}q)$左右（吧）

数据点 8,9

思路大致和上面相同 不过因为k=1，改成hash
8pts

正解

抽屉原理，转成16组，1<<16进制

day2T2

$n,q<=2000$

暴力直接做

20pts

$A$

注意 F和R都会改变操作序列

所以意思就是F,R也不会使得操作序列出现连续相同段

所以可能出现的序列只有两种：

$$WEWEWE...$$
$$EWEWEW...$$

比起维护当前序列，直接维护两种可能的序列，判断当前是哪种直接输出应该更简单

注意 每次添加数的时候 虽然是加在了最后，但是实际做的时候，效果应该是原来有…然后最前面多了一项

15pts

$B,C$

从这里往下的每一档部分分 都需要推出矩乘

不会平衡树15pts

$C$

不会平衡树维护reverse 20pts

正解

操作W对应

$$\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$$

操作E对应

$$\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}1& ?1\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}2& ?1\\ 1& 0\end{array}\right)$$

之所以这样讨论 是因为当最后一项不是1的时候 用的是第二种情况，最后一项是1时，用的是第一种情况，但我们发现，当最后一项是1时，用第一种和第二种得到的答案相同，因此默认都用第一种就好了

最开始的初值是

$\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$

注意 rotate是关键字…建议不要关codeblock的代码补全 起码不会撞关键字）

30pts

day2T3

吐槽一下…题解第一篇的all没有任何实际含义，纯纯是为了减掉0那个时候的容斥值，想了好半天…

再吐槽一下

注意这个条件

你以为这个条件没有任何用处？

不 你太naive了

这个条件的用处是：对于一种钦定完之后会爆炸的序列，它有一种合法方案，为全填空

所有的代码参考见这个博客

大佬的博客

算法1

暴力dfs+验证（hash）

注意 因为得到的最终的纸带不同会记做不同方案，所以每个点都要验证

复杂度$O(3^{mn}{n}^{2}m)$

可以过掉点123

12pts

算法2

我会容斥！

考虑枚举 $i$ 表示对于一些纸条来说，可以作为起点，且均合法的点集合（状压表示）

然后一一枚举过程中走到的第$r$ 个位置

可以计算出当前走的是第几步

然后可以判断，$r$这个位置可能的结尾值都有什么

接着判断每个方块对应的开始，结尾的值都可能是什么

那么容斥在哪里呢？

具体来说 比如一个纸条 可以以1,2位置为起点 那么以1的时候会计算一次 以2的时候会计算一次，以12的时候仍然会计算一次

所以需要容斥

记枚举到的合法的点数为 $k$ 容斥系数是 $(?1{)}^{k+1}$

复杂度$O(n^2{2}^{n}m)$

可过12347 20pts

可以发现 复杂度瓶颈主要在 $2^n$ 上

算法3

我会优化算法2！

考虑枚举最后一个合法位置$r$

那么我们就可以发现走的距离大于$c>n?r$ 的一定会爆炸

那么其实 我们前面记录的距离一定是$min(r,n?r)$

这样复杂度就变成了$O(2^{n/2})$

具体来说 我们转移的时候需要维护min的状态，min前面是否出现过一个转移点

做dp的时候处理当前位置，做完$r$结尾的dp之后 再处理$r$之后的位置

（详情见代码）

喜提ex28pts

算法4

我会优化算法3！

具体来说 这个算法不再循环M，考虑在bitset里维护 $rc[i][op]$ 表示往后走$i$ 的位置 状态为$op$ 的机器人都有哪些

那么统计答案的时候 只要把bitset对应算法3做相应的操作，再统计有多少个位置有值就好

复杂度$O(\frac{n^{2}m{2}^n}{w})$

（分数比起上一档来说没有显著变化）

算法5

注意到$m?>\frac{m}{w}$

$2^n?>2^{\frac{n}{2}}$

在这两项上我们很难再有所突破 所以转而考虑$n^2$

注意到 我们在维护bitset的时候 每次都会扫一遍当前枚举到的状态$i$ 这其实很没有必要

具体来说 比如两个状态的二进制表示是$1000001,1000000$

我们发现 只有最后一位不一样

因此我们可以结合lowbit的思想 具体来说，不每次去扫状态$i$

改为$f[i][op]=f[lb(i)][op]|f[ixorlb(i)][op]$

共计得分100

（老实说 这个题的思维难度真的很大…）

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖