牛客挑战赛47

https://ac.nowcoder.com/acm/contest/10743

A

思维题。
最终的gcd最大值必为排序后每两个相邻数的差值的gcd。
那么就计算最小的数需要加多少才能成为这个gcd的倍数就可以了。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
ll a[N], d[N];
int main() {
    ll n;
    sc(n);
    for (int i = 1; i <= n; ++i) sc(a[i]);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i < n; ++i) d[i] = a[i + 1] - a[i];
    ll ans = d[1];
    for (int i = 2; i < n; ++i) ans = __gcd(ans, d[i]);
    if (ans == 1) puts("1 0");
    else cout << ans<<' ' << ans - a[1] % ans;
    return 0;
}

B

是k-gcd的变形，说是埃筛也没什么问题。无论选多少个数，答案必然在之间，那么就可以枚举每个因数，通过桶来看有多少个数是它的倍数。
从大到小枚举就是最优的枚举方案，所以只有没有访问过的才会记录。
最后覆盖一遍答案就可以了，因为如果有个数都是的倍数，那么必然也可以选出来个数，使其满足是的倍数。

#include <stdio.h>
const int maxn = 1e5 + 7;
int a[maxn], ans[maxn];
int main() {
    int n, x;
    scanf("%d", &n);
    int maxa = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x), ++a[x];
        if (x > maxa) maxa = x;
    }
    for (int i = maxa; i; --i) {
        int cnt = 0;  //有cnt个数是i的倍数
        for (int j = i; j <= maxa; j += i) cnt += a[j];
        if (!ans[cnt]) ans[cnt] = i;
    }
    for (int i = n; i > 1; --i) {
        if (ans[i + 1] > ans[i]) ans[i] = ans[i + 1];
    }
    for (int i = 2; i <= n; ++i) printf("%d ", ans[i]);
    return 0;
}

C

其实就是Floyd，但是可能会T（虽然数据水并没有），但是题目只要求是否可达，所以此处可用bitset优化。

具体来说是建两张图：

1. 一定能到图：收纳所有一定存在的边
2. 可能能到图：只要不是一定不存在的边，都收纳进去

#include <bits/stdc++.h>
using namespace std;
int n, m1, m2, q, x, y;
const int maxn = 1005;
bitset<maxn> f[maxn], g[maxn];
int main() {
    scanf("%d%d%d%d", &n, &m1, &m2, &q);
    for (int i = 1; i <= n; i++) {
        f[i].reset();  //初始化为0
        g[i].set();    //初始化为1
        f[i][i] = 1;   //自己必定可达自己
    }
    for (int i = 1; i <= m1; ++i) scanf("%d%d", &x, &y), f[x][y] = 1;
    for (int i = 1; i <= m2; ++i) scanf("%d%d", &x, &y), g[x][y] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (f[j][i]) f[j] |= f[i];
            if (g[j][i]) g[j] |= g[i];
        }
    while (q--) {
        scanf("%d%d", &x, &y);
        printf(f[x][y] ? "Yes " : "No ");
        puts(g[x][y] ? "Yes" : "No");
    }
    return 0;
}