ARC 杂题选做（咕咕咕中）

懒得全写，挑一些感觉不错的题写。翻译就不自己翻了，直接贺洛谷题面。

不放代码了，想看的话去对应题目里搜 Royaka 看就行。

NOIp 考完，补完 whk 再来填坑。

[ARC074F] Lotus Leaves

给定一个 \(H×W\) 的网格图，o是可以踩踏的点，.是不可踩踏的点。

现有一人在S处，向T移动，若此人现在在 \((i,j)\) 上，那么下一步他可以移动到 \((i,k),(k\in[1,W])\) 或 \((k,j),(k\in[1,H])\) 上。

问最少需要将多少个o改成.，可以使这个人无法从S到达T，输出最少需要更改的数目；如果无论如何都不能使这个人无法从S到T，则输出 -1

• $ 2\le H,W\le 100$。

明显的最小割。但我对网络流建图有点生疏了，这里写一下建图方法：

为了方便，设起点为 \(s\)，终点为 \(t\)。

源点 \(S\) 向 \(s\) 所在的行列连边，\(t\) 所在的行列向汇点 \(T\) 连边，若一个点可走则行列间连双向边。

求最小割即可。

[ARC076F] Exhausted

有 \(m\) 个椅子在数轴上排列，第 \(i\) 张椅子的坐标为i。

高桥君和他的朋友一共有 \(n\) 个人。高桥君他们因为玩了太久的游戏，大家的腰和背都很痛，所以他们很有必要坐在椅子上休息一下。

高桥君他们每个人坐的椅子的坐标都很讲究，第 \(i\) 个人想坐在坐标在 \(l_i\) 以下（包括 \(l_i\)）的椅子上，或者坐在坐标在 \(r_i\) 以上(包括 \(r_i\))的椅子上。当然，一个的椅子只能坐一个人。

可这样计算下去，可能会让他们不能都坐在椅子上休息。青木君关心高桥君他们的健康，尽可能多地增加椅子，让高桥君他们都能够坐在椅子上休息。 椅子可以添加到任意的实数坐标上，请求出需要添加椅子数量的最小值。

\(1 \leq N,M \leq 2\times 10^5\)，\(0\leq l_i < r_i \leq M+1\)。所有的数都是整数。

添加的最小值可以转化为匹配的最大值，因此这道题可以转化为二分图匹配。

引理：Hall 定理。

假设二分图左右点集分别为 \(X,Y\)，不妨设 \(|X|\le |Y|\)，设 \(\text{Nb}(X)\) 表示与 \(X\) 有连边的点的集合。则二分图存在完美匹配（即匹配个数为 \(|X|\)），当且仅当 \(\forall X_0\subseteq X,|X|\le |\text{Nb}(X_0)|\)。

一个二分图的最大匹配数等于 \(|X|-\max\{|X_0|-|\text{Nb}(X_0)|\}\)。

综上，原题等价于求 \(\max\{|X_0|-|\text{Nb}(X_0)|\}\)。

因为邻居点集形式 \([1,l_i]\cup [r_i,m]\) 的形式，不好处理，我们考虑转化：并集等于全集减去补集的交集。

因此，又化为 \(\max\{|X_0|+|\bigcap_{i\in \text{Nb}(X_0)} (l_i,r_i)|\}-m\)。

将区间排下序然后线段树优化 DP 即可。时间复杂度 \(\mathcal O(n\log m)\)，代码写挂了。

E - Awkward Response

交互题。

给定一个数字 \(N\)，要你通过若干次询问得到 \(N\)。

一次交互格式类似于 ? x，其中 \(x\) 是你询问的数字，交互库会返回答案 \(\tt Y\) 或者 \(\tt N\)，分别表示 \(\tt Yes\) 和 \(\tt No\)。

返回 \(\tt Y\) 当且仅当满足下述条件中的一个：

• \(x \leqslant N\) 并且 \(str(x) \leqslant str(N)\)
• \(x > N\) 并且 \(str(x) > str(N)\)

其中 \(str(x)\) 的含义是将十进制整数 \(x\) 转成字符串，字符串比较按字典序比较。下面这行代码则是一个交互的示例，其中 \(s\) 是字符串变量，用来读取交互库返回的答案。

void query(int x){printf("? %d\n",x);fflush(stdout);scanf("%s",s);}

若找到答案，请按 ! x 的格式输出，其中 \(x\) 为你找到的数字 \(N\)。

你最多询问 \(64\) 次。

$ 1\leq N \leq 10^{9}$

首先特判一步：如果询问 \(10^9\) 返回 \(\tt Y\)，那么答案一定是 \(10\dots 0\) 的形式，一直询问 \(99\dots 9\)，找出第一个为 \(\tt N\) 的即可。

一直询问 \(10^x\) 直到答案为 \(\tt N\)，此时位数就确定了。在位数值域范围内二分查询。

但是字典序非常烦人，我们考虑二分到 \(mid\) 时查询 \(10mid\)，这样一定满足 \(10mid\gt N\)，而此时两者的字典序大小就对应了 \(mid\) 和 \(N\) 的数值大小，这时二分就变得可以接受了。

[ARC078F] Mole and Abandoned Mine

给一个 \(n\) 个点 \(m\) 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 1 到 \(n\) 只有 1 条路径（不经过重复点），问割掉的边权和最小是多少。

• $ 2\ \leq\ N\ \leq\ 15 $
• $ N-1\ \leq\ M\ \leq\ N(N-1)/2 $
• $ 1\ \leq\ a_i,\ b_i\ \leq\ N $
• $ 1\ \leq\ c_i\ \leq\ 10^{6} $。

状压 DP。转向考虑保留的边权和最大化。

设 \(f(i,S)\) 表示当前 \(1\to i\) 只经过 \(S\) 中的点时有唯一一条路径的最大边权和。

考虑一个点 \(u\)，可能是 \(1\to n\) 路径上的点，也可能是废点。

令 \(sum(S)=\sum\limits_{u,v\in S}w(u,v)\)，那么对于两种情况分开考虑：

• 如果 \(u\) 是 \(1\to u\) 的「关键点」，则 \(f(u,S\cup\{u\})=\max\limits_{t\in S}\{f(t,S)+w(t,u)\}\)

• 若为废点，则 \(f(t,S\cup T)=\max\{f(t,S)+sum(T|\{u\})\}(T\cap S=\emptyset)\)

时间复杂度 \(\mathcal O(n\times 3^n)\)。

写不动了，以后再写叭。