1 条题解

  • 0
    @ 2025-6-14 20:50:03

    「ALFR Round 5」地铁

    Link

    • 如图,首先,当 n,m2n,m \ge 2 时,我们考虑每一行或每一列都只有一条地铁线,如果 m>nm>n 那就就选 nn 条,反之则选 mm 条。这样可以使地铁线覆盖范围更广,同时也能使地铁线路最少。
    • 但是铁路还要满足无论从哪个地铁站出发乘坐地铁,经过若干次换乘(可以不换乘),都一定可以到达其它所有地铁站。所以必定有一条线路分别和上述的 min(n,m)\min(n,m) 条线路至少有一个交点。所以答案为 min(n,m)+1\min(n,m)+1
    • n=1n=1m=1m=1 时,此时只需要一条长为 nnmm 的铁路线来使其覆盖全部即可。
    • 故答案 yy 为:
    $$y = \begin{cases} \min(n, m) + 1, & \text{if } n \geq 2 \text{ and } m \geq 2 \\ 1, & \text{if } n = 1 \text{ or } m = 1 \end{cases} $$
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n,m,t;
    int main(){
    	cin>>t;
    	while(t--){
    		cin>>n>>m;
    		if(n==1||m==1) cout<<1<<endl;
    		else cout<<min(n,m)+1<<endl;
    	}
    }
    
    • 1

    信息

    ID
    141
    时间
    3000ms
    内存
    512MiB
    难度
    1
    标签
    递交数
    148
    已通过
    101
    上传者