POI2007合集
POI2007
2023.12.01～2023.12.02
好像如果稍微难一点的题目写过题解的直接贴链接的话就显的这篇整理很空虚啊！所以之后就把题解复制下来（
P3451 [POI2007] ATR-Tourist Attractions
先跑出 $[1,k+1]$ 的最短路，然后状压。
但是这dm题目卡空间啊。发现只需要让状压的空间 $/2$ 就可以过，观察到 $f_{S,i}$ 中，$i$ 一定在 $S$ 中，所以把 $S$ 开到 $2^{k-1}$ 次方就可以过了。
时间复杂度 $O(km\log m+2^kk^2)$，空间复杂度 $O(nk+2^{k-1}k)$。
P3452 [POI2007] BIU-Offices
题目本质上就是求补图的连通块的个数和数目。
先讲一下我的优化建边的暴力。
观察到对于一个点 $x$，给除了边 $(x,y)$ 的点连边，转化为许多区间。考虑 ST 表优化建边，如果这个没有遍历过，则向左右两个区间连边；反之直接与这个区间合并。
这样点数是 $O(n\log n)$ 的，边数是 $O(m)$ 的，只不过转化为区间的过程需要排序。如果用基数排序的话可以做到 $O(n\log n+m)$，像我一样暴力排序就只能 $O(n\log n+m\log m)$，感觉有点劣啊。/kk
考虑从搜索的角度优化。
维护一个链表记录没有遍历过的点，和待搜索的队列，从队首取出一个数 $x$，考虑直接遍历整个链表，如果这个点不与没有被遍历过，则入队并在链表中删除。
容易发现，每个点在删除之前最多只会遍历这个点的度数次。总复杂度是 $O(n+m)$ 的，感觉有点厉害。
P3453 [POI2007] DRZ-Trees
感觉像大分类讨论，先咕咕了。
P3454 [POI2007] OSI-Axes of Symmetry
这种带点计算几何题目还是一点思路都没有。
以一点开始，交替记录边角。这样是一个长度为 $2n$ 的环。
原问题可以转化为环上有几个位置，满足删去当前位置以后得到回文串。删去当前位置可以理解为平分当前的边/角。
不想写马拉车，不如哈希。
复杂度 $O(Tn)$。
P3455 [POI2007] ZAP-Queries
莫反板子。
P3456 [POI2007] GRZ-Ridges and Valleys
并查集维护一下即可。
P3457 [POI2007] POW-The Flood
丹砂成功了，但是做完看题解发现想复杂了。/kk
首先，观察到如果在 $x$ 放抽水机能把 $y$ 中的水抽干，当且仅当存在一条路径，路径上的点都 $\le h_y$。
这启发我们给所有点按海拔排序。
并查集维护满足在这个点放抽水机使得 $x$ 被抽干的连通块。
然后观察到如果在不是城市的点放抽水机肯定不优。我们直接钦定把饮水机放在当前连通块中是城市且高度最小的点上。并查集维护连边的方向。这样贪心感觉很对。
复杂度 $O(nm)$，要乘上并查集复杂度（一般我认为是常数）。
写完之后看题解，发现如果合并时当前点为城市且连通块没有饮水机就在当前城市放，这样更好写啊，而且和上面啊的做法似乎本质相同。
P3458 [POI2007] SKA-Rock Garden
结论题。
看题解发现把点都折到 $y=x$ 一侧更优。这样我们先算出来篱笆的坐标和大小。
发现篱笆的坐标可能有四种，于是枚举然后计算每种情况下需要移动的最小值。
P3459 [POI2007] MEG-Megalopolis
dfs 序之后树状数组板子。
P3460 [POI2007] TET-Tetris Attack
本来想的贪心是选择目前同种颜色中距离相差最小的。暴力很好写但是很难维护（至少也要二维线段树或者 kdt 之类的）。
考虑维护一个栈一个个加入，如果新加入的点栈里已经有同种颜色的了，那么直接交换过去删掉。否则放到栈顶。
这样应该是不劣的。这种题也只能多做题找感觉了。
复杂度 $O(n+Ans)$。
P3461 [POI2007] KOL-Railway
根本就没人做这种题啊。
P3462 [POI2007] ODW-Weights
容易发现成倍数关系这样不同重量的砝码个数就很少啊。
$a$ 是砝码重量排完序去重以后的值。
但考虑更高妙的进制做法，设第 $i$ 位的权重是 $a_i$，考虑把每个容器先进制分解，然后对于砝码直接从小到大的去放肯定更优，如果这一位不够了就上去借，如果上面借不到了也就之后的都放不了了。
复杂度 $O(m\log w)$。
P3463 [POI2007] EGZ-Driving Exam
令 $f_i$ 表示从 $i$ 开始向左行驶可以到 $1$ 需要添加道路的最小值，$g_i$ 表示从 $i$ 开始向右行驶到 $n$ 需要添加道路的最小值。这个可以树状数组 $O(n\log n)$ 处理出来。
注意到 $f,g$ 都是单调的，然后双指针指一下就好了。注意问的是新增的起点，所以要减去原来的起点。
P3464 [POI2007] WAG-Quaternary Balance
P5925 [POI2007] 天然气管道Gaz
观察到没有让你判无解，所以答案是 $\sum bx_j-ax_i+ay_i-by_j$，然后其实你并不需要匹配出来，把答案分开算加起来就好了。
P6564 [POI2007] 堆积木KLO
注意到 $f_i=f_j+1$ 要满足充要条件：
- $i-a_i\ge i-a_j$。
- $a_i-1\ge a_j$
- $i>j$，也就是 $i\ge j$。
一看好像是三维偏序，其实如果满足一二条件就满足了第三个，重新排序以后做二维偏序，复杂度 $O(n\log n)$。