题单1

题单2

派遣

大根堆更好维护。

航空管制

DFS 做法

拓扑排序，由于所有依赖关系中，后飞的航班 $k$ 值现在一定大于先飞的航班，所以按 $k$ 值从大到小安排航班。

至于最小起飞序号我们可以通过对反图进行一次 $DFS$，标记出 $A$ 和 $A$ 的祖先，然后仿照第一问，在不安排 $A$ 和 $A$ 的祖先的情况下，根据 $k$ 值从大到小，从后往前安排其他航班。

而 $A$ 最早的起飞时间，就是这些空出来的起飞时间中最后一个。

堆做法

我们希望使得某一个东西在拓扑序中出现的尽可能早，这个时候就可以建出一张反图来，使得这个东西在反图中的拓扑序尽量靠后，从而使得其出现的尽可能地早

这是为什么呢，比如说我们希望$1$出现的尽可能早，直接在正图上开一个小根堆来进行拓扑排序显然错的

为什么呢，因为这样只能使字典序尽可能小，而不是使得$1$尽可能靠前

但是我们建出反图来呢，显然反图上按照上述方法来跑的话会使得反向字典序最小，而最小的反向字典序一定是$1$最靠后的

这道题可以建出一个反图来，从而使得限制条件变成了每一个航班在拓扑序中的位置$>n-k[i]$，于是我们直接用小根堆来维护$n-k[i]$就好了，

假设当前枚举点是 $x$，那么所有在 DAG 上可以由 $x$ 到达的点都永远无法到达，但是对于其他点的相对拓扑序没有改变，可直接枚举原来的拓扑序，再强制删掉由 $x$ 可达的点。

而找到 DAG 上可以由 $x$ 到达的点这一步可以用 bitset 优化

修筑绿化带

1. 预处理出以$A[i,j]、B[i,j]$分别为右下角的花坛$(C*D)$、大矩形$(A\*B)$的肥沃度和

2. 按行，利用单调队列求出$P[i,j]=以A[i, j-B+1+D→j-1]$中的最小值，即以$(i, j-B+1+D→j-1)$为右下角的花坛肥沃度的最小值。

3. 按列，利用单调队列求出$Q[i,j]=以P[i-A+1+C→i-1, j]$中的最小值，即以$(i-A+1+C→i-1, j-B+1+D→j-1)$ 为右下角的花坛肥沃度的最小值，显然，这些花坛包含在了以$(i,j)$为右下角的大矩形中；

4. 显然$B[i,j]-Q[i,j]$即为以$(i,j)$为右下角的绿化带的最大肥沃值。

虚拟内存

关于排序的优先级，直接先按照出现的次数排序，再按照时间排序

1. 若内存未被排满，直接将其塞入。

2. 若已排满，其实当前页在不在队列中都不重要，遇到已经存在页就加1即可。因此可以直接通过取队首元素，将其出队直到能够放置时就行了。

yyy loves Maths VII

我们定义 $f[i]$ 表示使用了集合 $i$ 内的卡片有多少种赢的方案。转移时，我们记 $dis[i]$ 表示使用了集合 $i$ 内的卡片到达的位置，显然当 $dis[i]$ 为“厄运数字”时不能转移。否则我们枚举这次使用的卡片 ，那么有转移方程：$f[i]=\sum_{j=1}^n[j\in i]\cdot f[i\ \texttt{XOR}\ j]$（其中 $i\ \texttt{XOR}\ j$ 本质是从集合 $i$ 中删去元素 $j$）。

不错的题解

GameZ游戏排名系统

开两个平衡树，一个是得分$->$名字，一个是名字的哈希值$->$得分

得分要开双关键字，存成绩和插入时间，用pb_ds即可。

对称的正方形

二维哈希$+$二分，可以上pb_ds

等差子序列

简化题意，找到一个三个数的等差数列就行了

因此我们可以去枚举中间数值，判断另外两个数值是否都在左侧

动态维护存在性$01$序列，看看有哪些数字已经在左边出现过，如果这个序列是回文序列，说明加减公差后的数值都在这个中点的一端，因此无解，反之则有解。

字符$hash$是前缀和关系，可以维护。

泉

很好求出至少有 $i$ 对的个数 $f(i)$，所以我们可以通过二项式反演得到答案。

考虑到元素个数为 $6$，我们可以状压 $S$ 表示强制让 $S$ 里面的这些元素相同的对数。

为了快速判断相等，我们可以每次构建哈希表，每次把必选的元素哈希起来。

在插入的过程中维护一下元素个数就好了。记得每次要清空。

双旋转字符串

最后组成双旋转字符串时，A 是前一半字符串 B 是后一半字符串的一部分。又因为双旋转字符串的性质即后一半字符串旋转可以得到前一半字符串，所以 A 通过旋转后 B 一定可以成为 A 的子串。

根据上方结论，可以得到 B 一定是字符串 AA 的子串。

可以用 $hash$ 去求后面，或者是用 $trie$ 树匹配，值得一提，我们依旧需要去枚举一遍字符串。

丽洁体

前后可以直接做，找中间的即可，由于不存在朴素的 $LCS$ 线性或 $log$ 算法，这体现我们注意条件所有单词长度不超过5，出现次数不超过500;

所以 $B$ 的开头最多在原串里出现 $500$ 次，所以我们可以暴力枚举这个串从哪儿开头，复杂度仅有 $500\cdot|\mathtt T|$

由于“单词长度不超过 $5$”，所以我们可以暴力匹配两个串是否相等，不用字符哈希。

消棋子

大致思路为用$set$维护行和列
第一问直接模拟即可
第二问，我们考虑一个贪心，因为删去颜色后只能使以后的答案更优，所以贪心策略就是能删就删
用队列维护当前删去颜色，考虑从删去扩展到其他颜色。
通过观察样例会发现，在两个格子所在的$2$行和$2$列所遇到的第一个颜色我们能够更新，所以$check$后合法的弹入队列。
至于输出方案，洛谷中不需要输出方案，就在更新的时候一并记录即可。

POW-The Flood

用并查集维护贪心。

免费道路

先找到必须边，开始思路是类似次小生成树，然而过不掉，如果我们先将必须边连上，会构成一堆联通块，且每一个联通块都有$0$边，解法显然。

蚯蚓排队

首先蚯蚓可以用链表维护这个序列。

然后发现 $k$ 很少，意味着每次合并或删除所动的子串数量非常少。这启发我们可以把所有出现的长度 $\le k$ 的子串全部通过哈希塞进一个桶里面，然后查询的时候我们直接再桶中查询。

对于如何维护这个桶，我们可以用一个散列表。

具体一点的操作。对于合并，我们找到第一个队伍靠近尾巴的 $k$ 个和第二个队伍的靠近头的 $k$ 个，然后找到所有由两边合并所得到的子串，哈希值丢进散列。

对于删除，我们同样的这样操作，把两边合并得到的子串给从散列中扔出来。也就是合并的逆操作。

对于查询，对于每一个长 $k$ 的子串，在散列表中查询即可。

火锅盛宴

不同询问可以用不同数据结构解决。

飞飞侠

可以用线段树优化建图 $O(n^3lognlog(n^3logn))$。

也可以拆点，我们定义一个状态 $dp[i][j][k]$ 表示到达点 $(i,j)$ ，剩余的能量是 $k$ ，每走一格需要消耗$1$点能量，到达一个点相当于补充了 $a[i][j]$ 点能量。

所以一个点向外只有五种转移，分别是上下左右和不动。用这个东西跑最短路就可以了。

最优解，并查集优化，我们把已经更新的点放进一个集合内，根节点指向最右边节点的下一个点。这样当我们二次进入这个节点时，可以 $O(1)$ 地跳过当前所有节点。（因为第一次遍历完这个已更新集合的最后一个点时，这个并查集相当于进行了一次路径压缩，同时不会有新的节点加入，因此可以认为接下来的访问的复杂度都是 $O(1)$）

那么我们推广到这个题，沿用线段树的办法，我们把每一列建一个并查集，然后维护这一列哪些点已经被访问过。

然而如果直接加上并查集的话，我们忽略了一个重要条件：已经更新过的点不能被更新第二次，这是本算法正确的充要条件。

考虑我们从起点出发，找到一个点跳过去，这一个区域内的所有点都是等价的，因此会盲目的跳，这一个区域内的点（下面称作某一点的子节点）他们自己的子节点和这一区域内别的点的子节点是会相交的，这一片相交的区域，如果我们使用传统的最短路算法就会被多次更新，因为第一次进入这些点是没有决策的。

那么我们考虑更改边权，我们把跳到的点的 $a[i][j]$ 也算进边权，这样就是正确的了。

实验

不错的模型转换题。

Bajtocja

与连通性有关，那么就要用并查集。

但在一个图里连通了两个点集之后，难道要遍历该点集所有点对，看看在其他图里是否连通？

1.启发式合并。那么对答案的影响，可以考虑落在 “新加入该点集” 的那些点上。

2.考虑 “与一个点在 dd 张图里都连通的点的个数” 。

连通意味着处在同一个连通块中。那么记录每个点在 dd 张图中分别属于哪些连通块，这形成一个字符串。

哈希记录某个字符串对应的点数即可。

需要用哈希表，而且消失的哈希值要删除，才能不超时。

造林

数据结构维护树形$DP$

Redistricting P

数据结构优化$DP$。

对于$\forall p,q$ ($p, q$满足转移条件)：

若$f[p] \neq f[q]$，则我们肯定把小的放队首，因为即使它要加$1$也一定不会劣于另一个

若$f[p] = f[q]$, 则我们把$sum$小的放队首，这样拿$sum[i]$减后才更可能不小于$0$

机棚障碍

大杂烩，大概用了前缀和，二分答案，并查集，hash，bfs，二叉堆（优先队列），树链剖分，st表。

点权加入并查集的时候，周围还未涉及到的点必须当做没看见。

询问的两点可能一个是另一个的祖先甚至是根。

队长快跑

好题

You are the Miserable

很有意思的链表模拟题。