P9473 [yLOI2022] 西施江南 的题解

· · 题解

(此题解未通过，仅作总结)

题目大意

传送门

意思很简洁，不讲。

大体思路

可以发现，只要这 n 个数两两互质就是 Yes，否则是 No。

注意还要特判 n=2 的情况，因为不管怎样，这两个数一定满足条件，输出 Yes。

想到这里，我就打了一个 80 分暴力！（考试时的代码）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
int T, n, cnt = 0;
int a[500007];
bool nprime[100000007];
inline int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
int main() {
    T = read();
    while(T--) {
        n = read(); cnt = -1;
        ll maxx = 0;
        for(int i = 1; i <= n; i++) {
            a[i] = read();
            maxx = max(maxx, (ll)a[i]);
        }
        if(n <= 2) { printf("Yes\n"); continue; }
        bool flag = 1;
        for(int i = 1; i <= n && flag == 1; i++)
            for(int j = i + 1; j <= n; j++)
                if(gcd(a[i], a[j]) > 1) { printf("No\n"); flag = 0; break; }
        if(flag == 1) printf("Yes\n");
    }
    return 0;
}

评测记录

用时：23.45s

内存：3.54MB

这个暴力应该已经做到极致了，那么我们考虑其他做法。

我们发现，如果换一个角度思考，分解质因数，开一个 vis 数组（bool）来记录现在分解的这个数之前是否用过相同的质因数，如果相同，直接 break 即可。

于是正解就上来了！

#include <bits/stdc++.h>
using namespace std;
int T, n, maxx = 0;
int a[500007];
bool vis[100000007];
int main() {
    cin >> T;
    while(T--) {
        cin >> n;
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        if(n <= 2) { cout << "Yes\n"; continue; }
        bool flag = 1;
        for(int i = 1; i <= n && flag == 1; i++) {
            for(int j = 2; j * j <= a[i]; j++) {
                if(a[i] % j != 0) continue;
                if(vis[j] == 1) { cout << "No\n"; flag = 0; break; }
                while(a[i] % j == 0) a[i] /= j;
                vis[j] = 1;
            }
            if(a[i] != 0) {
                if(vis[a[i]] == 1) { cout << "No\n"; flag = 0; break; }
                vis[a[i]] = 1;
            }
        }
        if(flag) cout << "Yes\n";
    }
    return 0;
}

评测记录

用时：10.64s

内存：97.71MB

我们过了这题，可是美中不足的是，用时和内存都太大了，我们可以怎么优化呢？

优化 1

读入优化：加上快读，后面输出变成 printf 即可。

篇幅原因，代码我就不给了。

评测记录

用时：9.52s

内存：97.70MB

我们发现时间优化了整整 1 秒啊！

优化 2

我们发现时间上面的一个巨大瓶颈在于 memset 上面，因为我们需要将一个 10^8 那么大的数组进行大约 20 次的初始化，显然会消耗掉巨大的时间！

于是我们定义一个 maxx 变量用来记录这一组数据让 vis 数组变为 1 的最大下标，后面直接 memset(vis, 0, maxx + 1); 这样就可以节省掉很多时间。

#include <bits/stdc++.h>
using namespace std;
int T, n, maxx = 0;
int a[500007];
bool vis[100000007];
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
int main() {
    T = read();
    while(T--) {
        n = read();
        memset(vis, 0, maxx + 1);
        maxx = 0;
        for(int i = 1; i <= n; i++)
            a[i] = read();
        if(n <= 2) { printf("Yes\n"); continue; }
        bool flag = 1;
        for(int i = 1; i <= n && flag == 1; i++) {
            for(int j = 2; j * j <= a[i]; j++) {
                if(a[i] % j != 0) continue;
                if(vis[j] == 1) { printf("No\n"); flag = 0; break; }
                while(a[i] % j == 0) a[i] /= j;
                vis[j] = 1;
                maxx = max(maxx, j);
            }
            if(a[i] != 0) {
                if(vis[a[i]] == 1) { printf("No\n"); flag = 0; break; }
                vis[a[i]] = 1;
                maxx = max(maxx, a[i]); //注意这里也要加！ 
            }
        }
        if(flag) printf("Yes\n");
    }
    return 0;
}

评测记录

用时：4.42s

内存：97.66MB

我们可以发现，时间减了有 5 秒了！！！

其中还有一些小优化我就不说了，应该影响不大。

但是我们发现空间还是非常的大，但是由于作者太弱，想不出其他优化的方法了（感觉可以把 vis 数组缩小到 10007，但是写着写着发现并没有那么简单 ┭┮﹏┭┮）。。

好了，题解就到这了，如果有更好的此类方法的优化，欢迎私信作者！