MX-X12-T7 / ALFR R5G1 地铁（Easy Version）题解

cff_0102 · 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 最小值：

&=\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：

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