Maze

题面

考场

第一眼看到了那个 $n$ 好像特别小，就想着能不能用 $n\times n$ 的正方形来分成很多很多块，然后一起做，至于询问的话想了一下线段树来维护边上的点到另一边点的最短距离（每个节点上开二维数组存），然后写广搜初始化和旁边的情况。至于线段树上的合并可以枚举一下中间从哪里走然后更新整个的答案。

然后。。。分块块 $+$ 线段树加上两边的广搜，我第一次发现线段树写起来简单。最后一个小时开始写的，还没写完就 $250$ 行左右，还没搞完还没调试。没了。

出分：没交。

正解

很不幸的是分块和线段树两种都能做。没必要结合在一起。我服了我自己。

分块

虽说也是分块，但这是普通的分块，就是分成 $\sqrt m$ 块。然后也是两边暴力 $bfs$ 然后中间预处理完了就直接跳大块。修改的话是暴力重构是 $O(n^2\sqrt m)$ 的，询问要枚举中间的转移点，是 $O(n^3\sqrt m)$ 的。

总复杂度就是 $qn^3\sqrt m.$

好像这个开 $O3$ 优化可以过。

线段树

跟我前面用的线段树一样但有几点变动。

不需要分组！！！然后每个地方也是二维数组存的是从左端点到右端点的每对点之间的最短距离。转移的时候也是枚举一个中间点转移。然后查询直接分下去，修改直接改单点。

这样复杂度就都是 $qn^3\log m.$

好写多了。。

$code:$ https://paste.ubuntu.com/p/8qCFTTQkwM/

Mhw

题面

考场

看上去是个二分图的样子。题目给了两类人，在一定距离下他们有克制关系。那就相当于有向边啊。

因为要求的三点环必须有两条边是横跨两边，另一边在一半上的，所以只需要给那个在一半上的点定向就可以了。那么三点环有几种连边情况：（对于在一边的两点 $x,~y$ 和另一边上的点 $z$ ）

1. 对于两条边 $x\leftrightarrow z \& y \leftrightarrow z$ 他们的方向必须是反的。就是： $x\rightarrow z \& z \rightarrow y$ 或 $y\rightarrow z(\alpha) \& z \rightarrow x(\beta).$ 
     2. 对于上面的两种不同的边的方向，我们要给 $x \leftrightarrow y$ 定向，在最大值的时候就是在所有 $\alpha$ 和 $\beta$ 环里面找到较多的一个给它们定向，最小值则相反。

那么求两点间的边数就可以确定边的方向了。我只会 $n^3$ 的方法。。

出分： $20pt.O(n^3).$

正解

$O(n^3)$ 可以过 $1000????$ （要开 $O3$ 优化别想了。）

线段树扫描线

又是你。扫描线。

这玩意跟扫描线有什么关系啊。？

我们先继续上面的两项向下分析。先把两边的点染色，左边的染白色，右边染黑色。那么我们先考虑所有白点间的边。

我们记白点 $x$ 连向一个黑点的黑点总数是 $f_x.$ 而两个白点 $x,~~y $同时连向一个黑点的黑点总数是$ g_{x,~~y}.$

所以对于两个点 $x,~~y $间半环（两条确定边）个数就是$ f_x-g_{x,~~y}$ 相当于取一个补集。

那么对于所有的贡献就是：

$\Large \begin{aligned}Ans&=\sum\limits_{x,y\in S_{white}} \max\{f_x-g_{x,y},f_y-g_{x,y}\}\\\Large&=\sum\limits_{x,y\in S_{white}} \max\{f_x,f_y\}-g_{x,y}\end{aligned}$

那么我们再考虑右边的那个 $g_{x, y}$ 能不能也化成 $f_x$ ？

它的意思就是同时连向了一个黑点，那么反过来就是一个黑点被两个白点连了，那么既然我们还要求一遍所有黑点 $f$ 那么就相当于是对于每一个黑点，选两个连向自己的边的总数。所以把 $f$ 重新定义成连向异色点的。

那么就是： $\large \sum g_{x, y} = \sum\tbinom{f_k}2.$ 具体而言就是说：

$\Large Ans=\sum\limits_{x,y\in S_{white}} \max\{f_x,f_y\}-\sum\limits_{k\in S_{black}}\tbinom {f_k}2.$

剩下的就是求所有的 $f_x$ 了。

我们回到最初的连边条件：曼哈顿距离小于等于 $D.$ 这个不太好处理所以~~常规地~~把他转化成切比雪夫距离。至于它是什么：

对于两个 $k$ 维的点 $A,~B$ ，其中 $A=(a_1,a_2,…,a_k)$ ，
则他们的切比雪夫距离定义为： $\large\max\limits_{i=1}^k\{|a_i-b_i|\}.$

~~曼哈顿距离是什么就不说了。。~~

那么怎么转换呢？曼哈顿距离只是二维的，所以对于 $(x,y)$ ，就变成 $(x+y,x-y).$

但其实理解起来没那么复杂。我们要算的是曼哈顿距离小于等于 $D$ 就是说要在范围内的点集。因为是曼哈顿距离，所以他就是一个斜着的正方形。这个就已经变成了二维的矩形内选点，但是线段树扫描线只能搞横平竖直的矩形，所以考虑把所有正方形旋转 $45^\circ$ 。而这个其实就可以用上面的那个变换。

还有一个问题，就是这样转换完之后长度没变吗？没变！证明如下：

对于两个点 $A(x_1, y_1),~~B(x_2,y_2) $，他们变换之后变成了：$ A’(x_1+y_1, x_1 -y_1),~~B’(x_2+y_2,x_2-y_2). $ 然后之前的曼哈顿距离是：$ |x_1-x_2|+|y_1-y_2|. $ 现在的切比雪夫距离是：$ \max\{|(x_1+y_1)-(x_2+y_2)|, |(x_1-y_1)-(x_2-y_2)|\}. $ 还记得三角不等式吗：$ |a-b|\leq|a|+|b|. $和$ |a+b|\leq|a|+|b|. $ 我们记$ a=x_1-x_2,~b=y_1-y_2$，不就是最大值吗？
证完。

那么就用线段树扫描线扫以一个点为中心的矩形里面包含的点的数量即可。（前缀点数和。）

$code:$ https://paste.ubuntu.com/p/PTvD7P2Yqr/

Factory

题面

考场

一开始想到思路的竟然是这题。

既然要任意情况都行，所以最后的矩阵一定是一个对角线上全是 $1$ 的正方形的方案。

所以就贪心排个序，然后顺着用并查集记一下现在所在的正方形大小。

然后自己黑了自己。。然后随便排了下序过了，然后交了。

出分： $30pt.$ 贪心是错的。

正解

神仙状压 $DP.$

听了三遍之后感觉差不多了。

首先题目给的一个人会不会操作几台机器给出的一张表其实就可以相当于是一张二分图。

那么一个人会操作就相当于给那个机器连上了一条边。由于上面那个小结论，我们就是需要把每个二分图上的联通块连成完全二分图并且两边点数相等。

证明呢？考虑反证：

如果不连通，那么设人有一些没和 $x$ 连边，那么当和 $x$ 连边的人不做 $x$ 的时候，就没人做 $x$ 了。

如果联通了但是点数不相等，那么就无法一一分配。

然后我们把每个联通块记成一个二元组 $(x_i,~y_i)$ 那么考虑怎么选这些二元组让代价最小。那么考虑状压 $DP$ 看每个联通块选不选时候的答案。

如可统计答案呢？因为已连边数不变，要加的边数等于总边数减已连边数，所以最小化总边数即可。总边数则是 $\large\sum\limits_{S’\subseteq S}\sum\limits_{i\in S’} x_i\times\sum y_i=\sum\limits_{S’\subseteq S}(\sum\limits_{i\in S’}x_i)^2.$

最暴力的方法 $dp_S$ 表示选 $S$ 集合的答案，转移则枚举子集，如果子集满足 $\large \sum\limits_{i~~\in~~S’} x_i=\sum\limits_{i~~\in~~S’} y_i $就用它更新答案。复杂度是$ 3^{cnt} $，$ cnt$ 是二元组数量。

然后慢慢优化它。

设 $dp_{S,i} $表示现在已选的数是$ S $，在处理的联通块里面的$ \sum x=i. $那么每次枚举一个二元组加到状态里面即可，然后如果$ S $有$ \sum x=\sum y $（之前配好了，现在也配好了，所以总的是好的。），就相当于目前已经可以更新答案了就给$ dp_{S,0} $更新。时间复杂度是$ 2^{cnt}n.$ 还需要进一步优化。

发现其实不需要把每一个二元组记下来，只需要记每一种二元组出现了多少次。这个可以用一个 $cnt$ 压起来，每次向上枚举就可以了，出题人说其实 $n=30$ 时一共只有 $1.7e5$ 左右种二元组，每一次就只需要枚举一种二元组，那么时间复杂度就是 $O(n\times 1.7e5)$ ，是能过的。空间复杂度可能有点高，但是也不会太大。

$code:$