自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:15:29，当前版本为作者最后更新于2025-05-04 23:21:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Subtask 1

数据范围很小，可以用很多种方法通过。甚至可以手画所有 $10$ 以内的情况，然后打一份表输出。看起来有 $100$ 种情况，但是实际上真正要画的不是很多。

#include<bits/stdc++.h>
using namespace std;
int ans[15][15]={{0},
{0,1,1,1,1,1,1,1,1,1,1},
{0,1,2,2,2,2,2,2,2,2,2},
{0,1,2,2,3,3,3,3,3,3,3},
{0,1,2,3,3,3,4,4,4,4,4},
{0,1,2,3,3,4,4,4,4,5,5},
{0,1,2,3,4,4,4,5,5,5,5},
{0,1,2,3,4,4,5,5,5,6,6},
{0,1,2,3,4,4,5,5,6,6,6},
{0,1,2,3,4,5,5,6,6,6,7},
{0,1,2,3,4,5,5,6,6,7,7}};
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--){
		int n,m;cin>>n>>m;
		cout<<ans[n][m]<<"\n";
	}
	return 0;
}

你可能想要尝试找规律来通过这题：

斜着读并放到 OEIS 里面搜，可以搜到 A163994，但是实际上本题与 A163994 并不相同。例如 $5\times8$ 的情况，按照 OEIS 上面搜到的数列应该是 $5$，但实际上只用 $4$ 条地铁（下图直接由题目中的图片修改而来）：

把最小的使得 $ans_{n,m}=n$ 的 $m$ 给列出来再放到 OEIS 搜，可以搜到 A002620（$m=\lfloor\dfrac{(n+1)^2}{4}\rfloor$），这个倒是对的。证明放在这篇题解的最后面了，因为需要用到 Subtask 6 中推出的一个式子。不过在 $m$ 小于这个数时显然也不可以通过什么 OEIS 里面的数列快速求出答案了，所以搜了也还是没用。

Subtask 2

通过手画找规律之类的方法可以得知此时的答案为 $\lceil\dfrac23 n\rceil$。有特殊的构造方法，见 Hard Version 的 Subtask 3。

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--){
		int n,m;cin>>n>>m;
		cout<<(int)ceil(2.0/3.0*n)<<"\n";
	}
	return 0;
}

Subtask 3

首先，每条线路都只可能是从左上到右下，或者从左下到右上的。设这两种线路的数量分别为 $x,y$。

假设只有一条这样的线路，那么它最多经过 $n+m-1$ 个站点。在理想状态下，每条线路都可以经过 $n+m-1$ 个站点。可惜的是，本题并不理想，两条同向线路会至少在两个交叉口相交（在道路网的两角），两条不同向线路至少会在一个交叉口相交。设“无效点”为因为两条或多条线路相交所以需要在贡献中减去的交叉路口（“无效点”是相对线路而言的，如果一个交叉路口被 $k$ 条线路经过，那么算 $k-1$ 个“无效点”），那么肯定要想办法减少“无效点”的数量。

只考虑一个方向的线路的其中一个角落，在这里放进 $x$ 条线路，求最少会有几个“无效点”。考虑把这些“无效点”从线路中去掉，那么剩下的线路就互不相交。此时不难找到一个安排这些线路的方法：

首先，到左上角的距离为 $0,1,2,\dots$ 的交叉口的数量分别为 $1,2,3,\dots$。每次安排一个新的线路到能到达的最左上角（假设其为 $a$，则到左上角的距离小于 $a$ 的交叉口个数为 $0$），然后往一个方向连出去（此时到左上角的距离大于等于 $a$ 的交叉口个数全部 $-1$），直到安排完 $x$ 条线路。这样可以发现，每条线路删去“无效点”后的起点到左上角的距离分别为 $0,1,2,\dots,x-1$，因此被删掉的“无效点”个数也就是 $\dfrac{x(x-1)}{2}$。再加上右下角，那么从左上到右下的线路之间产生的“无效点”数量就是 $x(x-1)$，同理，左下到右上的线路的“无效点”数量是 $y(y-1)$。

另外别忘了考虑不同向线路交叉产生的 $xy$ 个“无效点”，因此最后实际覆盖的点的数量最多为 $(x+y)(n+m-1)-x(x-1)-y(y-1)-xy$。

原问题就可以转化为：找到最小的 $x+y$，使得 $(x+y)(n+m-1)-x(x-1)-y(y-1)-xy\ge nm$（对于一组满足这个式子的 $(x,y)$，一定可以构造两个方向的地铁数量分别是 $(x,y)$ 的能覆盖所有点的方案，具体见 Hard Version）。推一下这个式子：

$$nm+(x^2+y^2+xy)-(x+y)(n+m)\le0$$ $$xy\ge(x+y)^2-(x+y)(n+m)+nm$$

考虑枚举所有可能的 $x$，然后可以二分得出满足该式的 $y$。时间复杂度 $O(Tn\log n)$（在本题的时间复杂度分析中 $n=\min(n,m)$）。

#include<bits/stdc++.h>
using namespace std;
long long n,m;
bool check(long long x,long long y){
	return x*y>=(x+y)*(x+y)-(x+y)*(n+m)+n*m;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--){
		cin>>n>>m;
		int ans=1e9;
		for(int x=0;x<=min(n,m)/2+1;x++){
			int l=1,r=min(n,m);
			while(l<r){
				int mid=(l+r)>>1;
				if(check(x,mid)){
					r=mid;
				}else l=mid+1;
			}
			ans=min(ans,x+l);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Subtask 4

注意到枚举出一个 $x$ 后，剩下的式子只有 $y$ 一个变量，因此可以解出这个一元二次不等式，不需要二分。时间复杂度 $O(Tn)$。

#include<bits/stdc++.h>
using namespace std;
long long n,m;
bool check(long long x,long long y){
	return x*y>=(x+y)*(x+y)-(x+y)*(n+m)+n*m;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--){
		cin>>n>>m;
		long long ans=min(n,m);
		for(long long x=0;x<=min(n,m)/2+1;x++){
			long long b=-(n+m-x),c=n*m-(n+m-x)*x;
			long long y=ceil((-b-sqrt(b*b-4*c))/2);
			ans=min(ans,x+y);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Subtask 5

继续考虑在 Subtask 3 中得到的式子。直接继续推这个式子是推不下去的。但是不难发现，当 $x+y$ 已经确定时，要让式子前面的 $xy$ 尽量大，这个不等式才能尽量满足。因为两数和一定时，它们的差越小，乘积越大，所以 $x,y$ 要尽量接近。由此可以推出：无论如何，取 $x,y$ 最接近的解一定不劣。

因此，可以二分最终的答案 $ans$，那么 $x=\lfloor\dfrac{ans}2\rfloor,y=s-x$。时间复杂度 $O(T\log n)$。

#include<bits/stdc++.h>
using namespace std;
long long n,m;
bool check(long long s){
	__int128 x=s/2,y=s-x;
	return x*y>=(x+y)*(x+y)-(x+y)*(n+m)+(__int128)n*m;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--){
		cin>>n>>m;
		long long l=1,r=min(n,m);
		while(l<r){
			long long mid=(l+r)>>1;
			if(check(mid)){
				r=mid;
			}else l=mid+1;
		}
		cout<<l<<"\n";
	}
	return 0;
}

Subtask 6

我们可能需要在 $O(1)$ 的时间内计算出每组数据的答案。先假设 $x,y$ 可以是任意实数。由于取 $x,y$ 最接近的解一定不劣，因此不妨设 $x=y$。那么可以推出：

$$nm+3x^2-2x(n+m)\le0$$ $$3x^2-2(n+m)x+nm\le0$$

目标是要让原式中的 $x+y$ 尽量小，所以这个式子中的 $x$ 要尽量小。这是一个一元二次不等式，可以直接求出满足该式的 $x$ 最小值：

$$\begin{aligned}x_{\min}&=\dfrac{2(n+m)-\sqrt{4(n+m)^2-12nm}}{6}\\ &=\dfrac{(n+m)-\sqrt{n^2+m^2-nm}}{3}\end{aligned}$$

因此，当 $x=y$ 时，$(x+y)_{\min}=2x_{\min}=2\times\dfrac{(n+m)-\sqrt{n^2+m^2-nm}}{3}$。

考虑回现实情况，$x,y$ 需要是整数。不管怎么样，必须满足 $ans=x+y\ge2\times\dfrac{(n+m)-\sqrt{n^2+m^2-nm}}{3}$。于是就可以得出答案：

$$ans=\lceil2\times\dfrac{(n+m)-\sqrt{n^2+m^2-nm}}{3}\rceil $$

如果 $ans=\lceil2x\rceil$ 是偶数，那么可以取 $ansx=ansy=\lceil x\rceil$。根据前面的计算，这组 $(x,y)$ 显然是满足前面推出的不等式的。因此，此时计算出来的 $ans$ 没有问题。

但是，$ans$ 是在 $x=y$ 的前提下推出来的，在 $x=y+1$ 的情况下有没有可能不满足上面的不等式呢？

若 $ans$ 为奇数，那么设其为 $2k+1$，则 $k<\dfrac{(n+m)-\sqrt{n^2+m^2-nm}}{3}\le k+\dfrac12$（因为它的两倍在 $2k$ 和 $2k+1$ 之间）。首先，因为按照 $x=y$ 计算出来的 $x$ 的解大于 $k$，因此不存在 $2k$ 的答案，最终答案必然大于等于 $2k+1$。其次，因为按照 $x=y$ 计算出来的 $x$ 的解小于等于 $k+\dfrac12$，所以（如果 $x,y$ 可以是任意实数的话）$x=y=k+\dfrac12$ 满足前面推出的式子 $xy\ge(x+y)^2-(n+m)(x+y)+nm$，即 $k^2+k+\dfrac14\ge4k^2+4k+1-(n+m)(2k+1)+nm$。

如果 $ans$ 是奇数时不一定是正确答案，那么说明 $x=k,y=k+1$ 可能不满足 $xy\ge(x+y)^2-(n+m)(x+y)+nm$（前面说要满足该式最好尽量让 $x,y$ 接近，而这就是 $x,y$ 最接近的一组整数解）。假设它不满足，那么代入 $x,y$ 的值，可以列出：

$$\left\{\begin{aligned}&k^2+k+\dfrac14\ge4k^2+4k+1-(n+m)(2k+1)+nm\\&k^2+k<4k^2+4k+1-(n+m)(2k+1)+nm\end{aligned}\right. $$

对于下式，其左右侧必然都是整数。因此下式右侧的 $4k^2+4k+1-(n+m)(2k+1)+nm$ 应该大于等于 $k^2+k+1$。然而，根据上式，它又要小于等于 $k^2+k+\dfrac14$，矛盾。因此“$ans$ 是奇数时它并不是正确答案”的情况不存在。所以 $ans$ 是奇数时，答案也是 $\lceil2\times\dfrac{(n+m)-\sqrt{n^2+m^2-nm}}{3}\rceil$。

（其实不放心的话还可以算出 $ans$ 之后拿附近的 $x$ 和 $y$ 验证一下然后输出符合条件的 $x+y$ 最小的答案）

为了避免精度误差，计算出答案 $ans$ 时，可以再验证一遍 $ans-1,ans,ans+1$ 是否满足条件，然后输出最小的满足条件的那个数。sqrtl 的复杂度可以看成 $O(1)$，总时间复杂度 $O(T)$。

我们只证明了答案至少为这个数，要证明一定有对应的方案，还需要将其构造出来。不过不进行构造证明直接输出答案就能获得本题的 $50$ 分了。构造方案见 Hard Version。

#include<bits/stdc++.h>
using namespace std;
long long n,m;
bool check(__int128 s){
	__int128 x=s/2,y=s-x;
	return x*y>=(x+y)*(x+y)-(x+y)*((__int128)n+m)+(__int128)n*m;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
    while(t--){
		cin>>n>>m;
		long long ans=ceil(2*(n+m-sqrtl((__int128)n*n+(__int128)m*m-(__int128)n*m))/3);
		if(check(ans-1))cout<<ans-1<<"\n";
		else if(check(ans))cout<<ans<<"\n";
		else cout<<ans+1<<"\n";
	} 
	return 0;
}

这里的 __int128 也可以改成 long double。

附对于 Subtask 1 部分提到的 $m\ge\lfloor\dfrac{(n+1)^2}{4}\rfloor$ 时答案即为 $n$ 的证明：

$$\begin{aligned}&\lceil2\times\dfrac{(n+m)-\sqrt{n^2+m^2-nm}}{3}\rceil=n\\\Longleftrightarrow\ &\dfrac23\times(n+m-\sqrt{n^2+m^2-nm})>n-1\\\Longleftrightarrow\ &m-\dfrac12n+\dfrac32>\sqrt{n^2+m^2-nm}\\\Longleftrightarrow\ &m^2+\dfrac14n^2+\dfrac94-nm+3m-\dfrac32n>n^2+m^2-nm\\\Longleftrightarrow\ &4m>n^2+2n-3\\\Longleftrightarrow\ &m>\dfrac{(n+1)^2}{4}-1\\\Longleftrightarrow\ &m\ge\lfloor\dfrac{(n+1)^2}{4}\rfloor\end{aligned} $$

---

一些关于这两题的 fun facts：

1. 本题来源于我两年前的灵感。当时我画了 $10$ 以内的 $n=m$ 的情况，发现了 $ans=1,2,2,3,4,4,5,6,6,\dots$ 的规律，即 Subtask 1（不过没发现 Subtask 5 的通用构造方法）。
2. 本题的线路不能「绕路」，实际上灵感来源于游戏「跳舞的线」，其实也有一些对某些城市地铁线路拐来拐去，交而不换的吐槽。
3. 这题刚出出来的时候，我认为这题的难度与 CSP-J 2022 T2 相差不大，因为那题也是解一元二次。
4. 分成两个 Version 的想法是在组题的时候才有的，原本这题只有 Easy Version。
5. Easy Version 样例中的倒数第二组数据是 sqrtl 会出现精度误差的数据，最后一组输入有意义且满足 $ans=n-9999$。