2024.02.18 测试

· · 个人记录

成功和鸟哥一起拿下新概念 rk1，特此纪念。

T1 家庭作业

link: gxyzOJ #3593

Description

小 y 最近收到一个家庭作业，计算 A 和 B 的最大公约数。由于这两个数太大了，我们给出了 n 个数，它们的乘积是 A，给出 m 个数，它们的乘积是 B。

输出这个最大公约数对 1000000000 的值。

Solution

Train of Thought 1

分解质因数。

从 \gcd 的定义入手，先做求质数的预处理，再对 a,b 两个数组做质因数分解，取相同的。

时间复杂度由于求质因数的方法而异，在 O(nm) \sim O(n^2m) 之间（ O(n)、埃氏筛求质数 O(n \log n)、暴力求质数 O(n^2)）

code from @wangsiqi2010916 (%%%)

#include <cstdio>
#define ll long long
using namespace std;
int n, m, a, b, cnt[50005], p[50005], p1[1005], mod = 1000000000, idx, cnt2[50005];
bool vis[50005];
ll ans = 1;
void get_prime() {
    for (int i = 2; i <= 50000; i++) {
        if (!vis[i]) p[++idx] = i;
        for (int j = 1; i * p[j] <= n; j++) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}
int main() {
    get_prime();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a);
        for (int j = 1; j <= idx; j++) {
            while (a % p[j] == 0) {
                a /= p[j];
                cnt[j]++;
            }
        }
        if (a > 1) p1[i] = a;
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &b);
        for (int j = 1; j <= idx; j++) {
            while (b % p[j] == 0) {
                b /= p[j];
                if (cnt2[j] < cnt[j]) {
                    cnt2[j]++;
                    ans = ans * p[j] % mod;
                }
            }
        }
        if (b > 1) {
            for (int j = 1; j <= n; j++) {
                if (b == p1[j]) {
                    ans = ans * p1[j] % mod;
                    p1[j] = 0;
                    break;
                }
            }
        }
    }
    printf("%lld", ans % mod);
    return 0;
}

Train of Thought 2

分别求每两个数之间的 \gcd 值，每个数取后除去 \gcd 值，ans = \prod_{i = 1}^{n} \prod_{j = 1}^{m} \gcd(a_i, b_j)。

时间复杂度 O(mn)。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005, mod = 1000000000;
int n, m, ans = 1;
int a[N], b[N];
int gcd(int a, int b) {
    if (a % b == 0) return b;
    return gcd(b, a % b);
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int t = gcd(a[i], b[j]);
            ans = ans * t % mod;
            a[i] /= t, b[j] /= t;
        }
    }
    cout << ans << '\n';
    return 0;
}

T2 距离之和

link: gxyzOJ #3594
link: Luogu P7745

更详细的题解：link

Description

想象一个机器人位于二维空间。初始时，机器人在 (0,0)。有4个命令 S,J,I,Z。

具体的，如果机器人在 (x, y)，在收到 S 命令之后，移动到 (x, y + 1)，收到 J 之后，移动到 (x, y - 1)，I 命令之后移动到 (x + 1, y)，Z 命令之后移动到 (x - 1, y)。

在这个二维空间有 n 个固定的点，在每个命令之后，每个固定点会计算自己与机器人的曼哈顿距离，然后返回这些距离的总和。

ps：两个点 (x1, y1) 和 (x2, y2 的曼哈顿距离为 |x1 - x2| + |y1 - y2|。

Solution

40 pts

每次移动后暴力求出每个点的哈曼顿距离，相加输出即可。

code

#include <bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
namespace xycyx {
    int n, m;
    int hmd[N];
    int X[N], Y[N];
    char c;
    int botx = 0, boty = 0;
    int get_hmd(int X1, int Y1) {
        return abs(X1 - botx) + abs(Y1 - boty);
    }
    void solve() {
        ios::sync_with_stdio();
        cin.tie(0);
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> X[i] >> Y[i];
        for (int i = 1; i <= m; i++) {
            cin >> c;
            if (c == 'S') boty++;
            if (c == 'J') boty--;
            if (c == 'I') botx++;
            if (c == 'Z') botx--;
            int ans = 0;
            for (int i = 1; i <= n; i++)
                ans += get_hmd(X[i], Y[i]);
            cout << ans << '\n';
        }
    }
}
signed main() {
    xycyx::solve();
    return 0;
} //40pts

100 pts

鉴于数据范围，时间复杂度应为 O(m)，故每次查询的时间复杂度都为 O(1)。考虑二分。

对于两条坐标轴，每次移动后分别二分求出有多少个点小于当前机器人的位置，多少点大于当前机器人的位置即可。

可以使用 upper_bound 和 lower_bound。

code

注意先排序后再二分查找。

#include <bits/stdc++.h>
#define N 100000
#define M 300000
#define ll long long
using namespace std;
namespace cyxyc {
    int n, m;
    int X1, Y1, X2, Y2, X, Y;
    ll ans = 0;
    int x[N + 5], y[N + 5];
    char str[M + 5];
    void solve() {
        ios::sync_with_stdio();
        cin.tie(0);
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> x[i] >> y[i];
            ans += abs(x[i]) + abs(y[i]);
        }
        cin >> str + 1;
        sort(x + 1, x + 1 + n), sort(y + 1, y + 1 + n);
        X1 = upper_bound(x + 1, x + 1 + n, X) - (x + 1);
        Y1 = upper_bound(y + 1, y + 1 + n, Y) - (y + 1);
        X2 = lower_bound(x + 1, x + 1 + n, X) - (x + 1);
        Y2 = lower_bound(y + 1, y + 1 + n, Y) - (y + 1);
        for (int i = 1; i <= m; i++) {
            if (str[i] == 'S') {
                ans += 2 * Y1 - n;
                Y++;
                Y1 = upper_bound(y + 1, y + 1 + n, Y) - (y + 1);
                Y2 = lower_bound(y + 1, y + 1 + n, Y) - (y + 1);
            }
            if (str[i] == 'J') {
                ans += n - 2 * Y2;
                Y--;
                Y1 = upper_bound(y + 1, y + 1 + n, Y) - (y + 1);
                Y2 = lower_bound(y + 1, y + 1 + n, Y) - (y + 1);
            }
            if (str[i] == 'I') {
                ans += 2 * X1 - n;
                X++;
                X1 = upper_bound(x + 1, x + 1 + n, X) - (x + 1);
                X2 = lower_bound(x + 1, x + 1 + n, X) - (x + 1);
            }
            if (str[i] == 'Z') {
                ans += n - 2 * X2;
                X--;
                X1 = upper_bound(x + 1, x + 1 + n, X) - (x + 1);
                X2 = lower_bound(x + 1, x + 1 + n, X) - (x + 1);
            }
            printf("%lld\n", ans);
        }
    }
}
int main() {
    cyxyc::solve();
    return 0;
}

T3 country

link: gxyzOJ #3596
link: BZOJ2061

Description

gaoxin 神犇频繁的在发言中表现对伟大，光荣，正确的xx的热爱，我们可以做如下定义：

A = 伟大，光荣，正确的

B = xx

C = 引领我们向前

赞美祖国 = ABC

拼命赞美祖国=赞美祖国 \times 10

gaoxin 的发言=拼命赞美祖国 \times 100

显然这个定义必须是无环的。

WJMZBMR感到十分的有压力，他好不容易数出了某个字串的出现次数。

某天他打开电视，发现某人的发言有同样的结构。他很无语，想知道某些字串出现的次数。你能帮帮他吗？

一些定义：

为了简化期间，在输入中用英文表示。

那么上面的系统可以写成：

同时存在一个母字串名，他就是某人的发言。

Solution

不会。还没改出来。

%%% dingzibo_______ dalao's solution
Want to find dalao dzb? Click here: dingzibo_______

%%%，截至2024年2月18日20点22分，已有 7 位 dalao 改出此题，他（她）们分别是 @dingzibo_______，@Dyc780511，@shaanxi_liuyuhe_yyyy，@wangsiqi2010916，@No0Chenquanlin，@STAR_light_，@zhangxy__hp。快来 % 他（她）们！

T4 太空飞船

link: gxyzOJ #3597
link: Luogu U407608

Solution

40 pts

直接 O(n^4) 的暴力即可。

code from @Laoshan_PLUS (%%%)

#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int MAXN = 10005;
int n, m, a[MAXN];
long long ans;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n < 4) {
        cout << 0 << '\n';
        return 0;
    }
    sort(a + 1, a + n + 1);
    m = unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= m; i++)
        for (int j = i + 1; j <= m; j++)
            for (int k = j + 1; k <= m; k++)
                for (int l = k + 1; l <= m; l++)
                    if (__gcd(a[i], __gcd(a[j], __gcd(a[k], a[l]))) == 1)
                        ans++;
    cout << ans << '\n';

    return 0;
}

60 pts

考虑动态规划。设 f_{i, j, k} 表示选取到第 i 个数，已选取的数的最大公约数为 j，选取的个数为 k(0 \le k \le 4) 的总方案数。转移方程如下：

f_{i, \gcd(a[i],j), k} += f_{i-1, j, k-1}

则最终答案为 f_{n, 1, 4}，其中第一维 i 可用滚动数组优化。

100 pts

容斥原理（莫比乌斯反演？ 不会）。

易得，ans = 总方案数 - 不可行方案。

设 num_i 表示集合中是 i 倍数的元素的个数，故 ans = C_n^4 - \sum{C_{num_i}^4}。

但是显然的，num_6 已经在 num_2 和 num_3 被统计过，所以应改为：

ans = C_n^4 - C_{num_2}^4 - C_{num_3}^4 - C_{num_5}^4 - \cdots + C_{num_{2 \times 3}}^4 + C_{num_{2 \times 5}}^4 + \cdots + C_{num_{2 \times 3 \times 5}} + \cdots - \cdots \cdots

化简，可得：

ans = C_n^4 + \sum{C_{num_i}^4} \times (-1)^{cnt_i}

其中 cnt_i 表示 i 所包含的质数的数量。

code

#include <bits/stdc++.h>
#define int long long
#define N 10000
using namespace std;
namespace yydz_wcnm {
    int n;
    int a[N + 5], num[N + 5];
    int ans, C[N + 5];
    void init() {
        for (int i = 4; i <= N; i++)
            C[i] = i * (i - 1) * (i - 2) * (i - 3) / 24;
        ans = C[n];
    }
    void solve() {
        ios::sync_with_stdio();
        cin.tie(0);
        cin >> n;
        init();
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            num[a[i]] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j * j <= a[i]; j++) {
                if (a[i] % j == 0) {
                    num[j]++;
                    if (j * j != a[i]) num[a[i] / j]++;
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            bool flag = 0;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0 && i / j % j == 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag) continue;
            int cnt = 0, x = i;
            for (int j = 2; j * j <= x; j++)
                if (x % j == 0) {
                    cnt++;
                    while (x % j == 0) x /= j;
                }
            if (x != 1) cnt++;
            if (cnt & 1) ans -= C[num[i]];
            else ans += C[num[i]];
        }
        cout << ans << '\n';
    }
}
signed main() {
    yydz_wcnm::solve();
    return 0;
}

也可以预处理质数后再求求组合数。

code from @wangsiqi2010916 (%%% \times 2)

#include <cstdio>
#define ll long long
using namespace std;
int n, p[10000], m, num[10005], vis[10005], cnt[10005];
ll ans, x[10005];
void get_prime() {
    for (int i = 2; i <= 10000; i++) {
        if (!vis[i]) {
            p[++m] = i;
            num[i] = 1;
        }
        for (int j = 1; i * p[j] <= 10000; j++) {
            if (i % p[j] && vis[i] != 2) {
                vis[i * p[j]] = 1;
                num[i * p[j]] = num[i] + 1;
            } else {
                vis[i * p[j]] = 2;
            }
            if (i % p[j] == 0) break;
        }
    }
}
int main() {
    get_prime();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        x[i] = 1ll * i * (i - 1) * (i - 2) * (i - 3) / 24;
    }
    if (n < 4) {
        printf("0");
        return 0;
    }
    ans = 1ll * x[n];
    for (int i = 1; i <= n; i++) {
        int a;
        scanf("%d", &a);
        for (int j = 1; j * j <= a; j++) {
            if (a % j == 0) {
                cnt[j]++;
                if (a / j != j) cnt[a / j]++;
            }
        }
    }
    for (int i = 2; i <= 10000; i++) {
        if (vis[i] == 2 || cnt[i] < 4) continue;
        if (num[i] % 2) ans = ans - x[cnt[i]];
        else ans = ans + x[cnt[i]];
    }
    printf("%lld", ans);
    return 0;
}

总结

秽土鼬一个。暴力打满，rk1（正着数的）到手。

不要被预处理冲昏了小脑。

看题在再认真仔细一些，多想，多试。注意末尾等特殊情况。

好好理解题意，手推样例。

不会的题，暴力暴力暴力还是暴力；会的题写正解之前暴力暴力暴力还是暴力。