NOI系列题目
NOI系列刷题
P7738 [NOI2021] 量子通信 [乱搞]
给定一个 $n$ 个单词的字典, 每个单词为长256的01串, $q$ 次询问一个串是否可以由字典中的串翻转 $k$ 位得到.
$n\le 4\times 10^5, q\le 1. 2\times 10^5, k\le 15$ ,字典是随机生成的.
没看输入格式的时候没有意识到字典是随机生成的, 想了些字典树上dp之类的东西. 没想到其实是个乱搞题.
如果把每个单词每16位一组分成16组, 那么翻转15位的情况下至少有一组是相同的. 所以对于询问的串直接枚举是哪一位相同, 字典里这一位恰好相同的只有 $\dfrac{n}{65536}$ 个, 于是复杂度就是 $\dfrac{nq}{256}$ .
最后的问题就是如何快速找到字典里确定了某一组所有单词, 用vector存即可. 不要智障的打算插入到set/map/有序数组里就不会TLE.
P7737 [NOI2021] 庆典 [图论] [tarjan] [虚树] [拓扑排序]
给定一张 $n$ 点 $m$ 边有向图, 记 $a\Rightarrow b$ 表示 $a$ 可以走到 $b$ , 那么若有 $x\Rightarrow z, y\Rightarrow z$ 则一定有 $x\Rightarrow y$ 或 $y\Rightarrow x$ .
有 $q$ 次询问, 每次额外添加 $k$ 条边, 询问从 $s$ 到 $t$ 的路径可以经过多少点. 询问间独立. 新添加的边可以不满足原图的限制.
可以经过指有一条从 $s$ 到 $t$ 的路径经过这个点.
$n, q\le 3\times 10^5, m\le 6\times 10^5, k\le 2$ . 保证在把有向图视为无向图后图连通.
有一个简单暴力, 一个点能出现在路径上当且仅当它能到达终点且反图上能到起点. 所以就在正图和反图分别处理每个点能到哪些点, 每次暴力判就好了. 复杂度 $O(nm)$
首先发现缩点是不影响答案的, 先缩SCC, 图变成了DAG.
考虑能不能想办法把DAG搞成树, 发现因为原图的限制, 若有边 $x\to z, y\to z, x\to y$ 我们可以删掉边 $x\to z$ . 也就是说, 每个点的入边可以只留一条, 于是就成了一棵树. 具体的, DAG上应该只保留拓扑序最晚的即可.
如果 $k=0$ , 那么求的就是一条链上的SCC大小的和. 但现在我们的树上又多了两条边, 产生了114514种分类讨论, 于是有另一种做法: 把两条边的端点以及询问的起点终点这6个点建一棵虚树, 再连上新加的两条边, 在这个小的DAG上跑一开始那个暴力, 复杂度 $n\log n$ , 瓶颈在于求lca和虚树.
200+行代码预警
P1224 [NOI2013] 向量内积
给定 $n$ 个 $d$ 维向量, $q$ 次询问找出两个向量点积为 $k$ 的倍数, 或者判断无解.
$k\in {2, 3}$ , 复杂度 $nd^2$
首先 $k$ 只有两个想到分类讨论:
若 $k=2$ :
重点是结合律可以改变矩阵的运算代价.
把 $n$ 个向量排成矩阵 $A$ , 则无解当且仅当 $AA^T$ 所有位置都为 $1\pmod 2$
然而直接 $AA^T$ 复杂度是 $n^3$ 爆炸, 考虑不精准判断, 这里的奇妙之处在于拿一个 $1\times n$ 向量 $R$ 乘上它们: 若 $RAA^T$ 中有一个位置不等于原来 $R$ 的和则对应 $AA^T$ 中的一列中有一个 $1$ , 在其中判断即可. 而且 $RAA^T=(RA)A^T$ , 复杂度 $nd$
若 $k=3$ :
有了 $k=2$ 后考虑膜3意义下每个数都平方后就又成了01矩阵, 设 $B=AA^T$ , 则要得到 $B_{i, j}^2r_i=B_{i, j}r_i B^T_{j, i}$ . 所以把 $r$ 变成只有一个对角的 $n\times n$ 矩阵 $R$ , 则 $BRB^T$ 的对角线就是所有 $B^2_{i, j}r_i$ 了.
然后因为这三个都是 $n\times n$ 的不能直接乘, 而是要变成 $AA^TRAA^T=(A(A^T(RA)))A^T$ , 并且最后一次矩阵乘的时候只计算对角线, 复杂度 $nd^2$ .
为了保证正确率可以多随几次, 就通过本题了.
P6772 [NOI2020] 美食家
精灵王国共有 $n$ 座城市, 城市从 $1$ 到 $n$ 编号, 其中城市 $i$ 的美食能为小 W 提供 $c_i$ 的愉悦值. 精灵王国的城市通过 $m$ 条单向道路连接, 道路从 $1$ 到 $m$ 编号, 其中道路 $i$ 的起点为城市 $u_i$ , 终点为城市 $v_i$ , 沿它通行需要花费 $w_i$ 天. 也就是说, 若小 W 在第 $d$ 天从城市 $u_i$ 沿道路 $i$ 通行, 那么他会在第 $d + w_i$ 天到达城市 $v_i$ .
小 W 计划在精灵王国进行一场为期 $T$ 天的旅行, 更具体地: 他会在第 $0$ 天从城市 $1$ 出发, 经过 $T$ 天的旅行, 最终在恰好第 $T$ 天回到城市 $1$ 结束旅行. 由于小 W 是一位美食家, 每当他到达一座城市时(包括第 $0$ 天和第 $T$ 天的城市 $1$ ), 他都会品尝该城市的美食并获得其所提供的愉悦值, 若小 W 多次到达同一座城市, 他将获得多次愉悦值. 注意旅行途中小 W不能在任何城市停留, 即当他到达一座城市且还未结束旅行时, 他当天必须立即从该城市出发前往其他城市.
此外, 精灵王国会在不同的时间举办 $k$ 次美食节. 具体来说, 第 $i$ 次美食节将于第 $t_i$ 天在城市 $x_i$ 举办, 若小 W 第 $t_i$ 天时恰好在城市 $x_i$ , 那么他在品尝城市 $x_i$ 的美食时会额外得到 $y_i$ 的愉悦值. 现在小 W 想请作为精灵王国接待使者的你帮他算出, 他在旅行中能获得的愉悦值之和的最大值.
对于所有测试点, $1 \leq n \leq 50$ , $n \leq m \leq 501$ , $0 \leq k \leq 200$ , $1 \leq t_i \leq T \leq 10^9$ , $1 \leq w_i \leq 5$ , $1 \leq c_i \leq 52501$ , $1 \leq u_i, v_i, x_i \leq n$ , $1 \leq y_i \leq 10^9$ .
在这图上走是随便走的, 使得大部分处理路径的科技不能用, 而看看数据范围想到邻接矩阵自乘的trick.
但这张图上是点权而不是点权, 朴素的把点权转移到入边上再特判起点.
但我们不是求路径条数, 定义矩阵乘法为外 $\max$ 内加.
但边有通过时间, 拆边复杂度很高. 于是把一个点拆成5个用, 不能共用一共5个点是因为要区分从哪里走进来的.
对于美食节在相邻两次之间用矩阵快速幂即可.
复杂度看起来过不了实际能过.