YDOI R1T1 Running题解

· · 题解

subtask 1：

超市只有 1 个，所以找到一个速度使得到达这个超市的时间为 2 秒即是最大速度，即最大速度为 \frac{a_1}{2}，判断速度是否为整数，是则输出速度，否则无解。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a;
int n;
int main() {
    cin>>n>>a;
    if(a%2==0) cout<<a/2;
    else cout<<-1;
    return 0;
}

subtask 2：

显而易见，v 一定小于等于 a_1，而 a_1 \le 2\times10^6，所以枚举 v 即可，判断到达超市的时间是不是偶数，总时间复杂度 O(a_1n)。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[55];
signed main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=a[1]; i>=1; i--) {
        bool f=true;
        for(int j=1; j<=n; j++) 
            if(a[j]%i||a[j]/i%2) f=false;
        if(f) {
            cout<<i;
            return 0;
        } 
    }
    cout<<-1;
    return 0;
}

subtask 3：

在枚举 v 的过程中，如果 v \nmid a_1，那么到达第一个超市的时间就不是整数，所以我们就可以只枚举 a_1 的因数，这样就保证了到达第一个超市的时间为整数，总时间复杂度 O(n\tau(a_1))，\tau(a_1) 是指 a_1 的正因子个数。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[10005],ans=-1;
bool check(int x) {
    for(int i=1; i<=n; i++)
        if(a[i]%x||a[i]/x%2) return false;
    return true;
}
signed main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=sqrt(a[1]); i>=1; i--) {
        if(a[1]%i==0) {
            if(check(i)) ans=max(ans,i);
            if(check(a[1]/i)) ans=max(ans,a[1]/i);
        }
    }
    cout<<ans;
    return 0;
}

subtask 4：

我们先不管必须在偶数时间经过这个条件，要求出一个 v 使得每次到达某个超市时时间是整数，就要保证 v \mid a_i，所以 v 就是所有 a_i 的公因数，最大的 v 就是所有 a_i 的最大公因数。

求出 v 后可以证明至少有一个超市到达时间是奇数，原因是如果每个超市到达时间都是偶数，那么所有的 a_i 除以 v 后还至少有 2 这个公因子，不符合 v 是最大公因数的定义。

接着再看偶数时间经过这个条件，把 v 除以 2 后到达每个超市的时间会多一倍，所以这样就保证了到达时间为偶数，注意：如果 2 \nmid v，则 v 除以 2 后不是整数，不符合题意，输出无解，时间复杂度为 O(n \log V)。

相信聪明的你一定看得懂简单的代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int n,a[N];
signed main() {
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    int v=a[1];
    for(int i=2; i<=n; i++)
        v=__gcd(v,a[i]);
    if(v%2==1) cout<<-1;
    else cout<<v/2;
    return 0;
}