地理微米
题意
给一块 \(n\times m\) 的木板，不重叠地摆放若干 L 型卡片（占 \(3\) 个格子），在中心钉一个钉子。现在给你木板上钉子的位置，求有多少种放置卡片的方式。答案对 \(998244353\) 取模。
\(n\times m\le3\times10^6\)。
题解
先从判断可行性开始。对每个 \(1\)，其左右需放一个 \(1\)，其上下需放一个 \(1\)，且不能重叠。不难想到一种简单的网络流做法，但复杂度不允许。
优化一下模型。左右之间连一条无向边，上下之间同理。若左右有一个也为 \(1\)，则另一个连自环；若都为 \(1\)，显然不行。此时转化为给无向边定向，使得每个 \(0\) 点入度不超过 \(1\)。则可行当且仅当每个连通块的边数不大于点数。
接着考虑计数。若连通块为树，有一个点入度为 \(0\)，其他均为 \(1\)。则以入度为 \(0\) 的点为根，每条边指向儿子。共有点数种方式。若连通块为基环树，则环上两种方向为两种方式。但若环为自环，只有一种方式。于是此题得解。
激光塔
题意
给定二维平面上 \(N\) 个激光塔的坐标与朝向（上下左右）。并有贡献，计算方式如下：开始时每个塔贡献 \(P\)。若两个塔 \(i,j\) 距离不超过 \(R\) 且 \(X_i\neq X_j,Y_i\neq Y_j\)，则若朝向相同，贡献 \(G\)；相反，贡献 \(-G\)；否则不贡献。
你可以贡献 \(-P\)，将一座激光塔任意方向旋转 \(90^{\circ}\)。一座塔可以旋转任意次。旋转后不同塔之间的贡献也会相应改变。求操作后的最大贡献。
\(1\le N\le 50,1\le R,P,G\le 1000,-1000\le X_i,Y_i\le 1000\)。
题解
距离没有什么特殊性质。直接改为塔之间连边。
连边的塔之间的贡献计算方式特殊，从这里入手。发现是长度为 \(\sqrt G\) 向量的点积。点积的计算方式 \(x_ix_j+y_iy_j\) 启发我们将 \(x,y\) 隔离考虑。但旋转操作又不方便隔离。
将坐标系旋转 \(45^{\circ}\)。则 \(x_i,y_i\in\{\pm\sqrt{\frac{G}{2}}\}\)。于是旋转操作变成了将 \(x_i\) 或 \(y_i\) 取反。于是可以隔离。以下考虑 \(x\)。
对于连边的两座塔，若 \(x\) 同号，贡献 \(\frac{G}{2}\)；若异号，贡献 \(-\frac{G}{2}\)。不妨看作全部贡献 \(\frac{G}{2}\)，若异号，增加 \(G\) 的消耗。将某个 \(x\) 取反，增加 \(P\) 的消耗。目标是最小化消耗。
这是一个网络流模型。源点向 \(x\) 为正的所有点连容量为 \(P\) 的边，\(x\) 为负的所有点向汇点连容量为 \(P\) 的边。原图中有边的两点，网络中连容量为 \(G\) 的双向边。最小割即为最小消耗。读者自证不难。于是此题得解。
反思
看完题解后，感觉这两题都不算难。尤其是第一题，初二的小朋友都会。但为什么考试时就是做不出来呢？
感觉最大的原因是思维不活跃。这也是老毛病了，必须尽快解决。最近都在学一些套路性强的东西，接下来一段时间的重心应该转移到思维题上。板刷 CF，限时训练。
标签：le,frac,记录,题解,贡献,4.29,校赛,旋转,1000 From： https://www.cnblogs.com/fish07/p/17365185.html