div4太没劲了，感觉只要会编程都能做，不更它了

不过div1入场失败次数++

官方中文题解

1349A Orac and LCM

求$n$个数的两两的$lcm$的集合$gcd$。

$lcm$是两个数唯一分解后每个质因子较大次数 的乘积，$gcd$则是较小的次数 的乘积，因此就是对每个数质因子分解，每个质数取第二小的次数 的乘积就是答案。

a.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 2e5 + 5;

multiset<int> p[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0, t, tp; i < n; ++i) {
        cin >> t;
        tp = t;
        for (int j = 2; j * j <= t; ++j) {
            if (tp % j == 0) {
                int k = 1;
                while (tp % j == 0) {
                    tp /= j;
                    k *= j;
                }
                p[j].emplace(k);
            }
        }
        if (tp != 1)
            p[tp].emplace(tp);
    }
    ull ans = 1;
    for (int i = 2; i < N; ++i) {
        if (p[i].size() == n - 1)
            ans *= *p[i].begin();
        if (p[i].size() == n)
            ans *= *(++p[i].begin());
    }
    cout << ans << endl;
    return 0;
}

1349B Orac and Medians

题意很简单，不赘述了。
想了半天，结束后看了才发现就是个脑筋急转弯。
首先如果没有$k$，那么必定无解；其次可以发现和邻近的数是否 $\ge k$ 有关。
实际上，如果有解必定只要两种情况：

  • 相邻两个 $\ge k$，那么可以把所有数（除了$k$）先变成 $\ge k$，再通通变成$k$；
  • 相邻三个数中有两个 $\ge k$， 那么可以按上述操作。

其他情况都可以归入这两种，于是直接挨个判断。

b.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, k;
        cin >> n >> k;
        bool fl = false;
        vector<int> a(n);
        for (int &i : a) {
            cin >> i;
            if (i < k) i = -1;
            else if (i > k) i = 1;
            else {
                i = 1;
                fl = true;
            }
        }
        if (!fl) {
            cout << "no" << endl;
            continue;
        }
        if (n == 1) {
            cout << "yes" << endl;
            continue;
        }

        fl = false;
        for (int i = 0; i < n - 1 && !fl; ++i) {
            if (a[i] + a[i + 1] > 0)
                fl = true;
            if (i < n - 2 && a[i] + a[i + 1] + a[i + 2] > 0)
                fl = true;
        }
        if (fl) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}

1349C Orac and Game of Life

这道题的话要抽象出一个状态，设对于方块$(i,j)$，它的周围有同色方块，那么它以后一直会是有同色相邻方块的，称它为“好方块”；否则为“坏方块”。
可以通过题意和上述的定义发现只能从坏$\to$好，并且一个方块变好后会$0\leftrightarrow 1$来回变换，它第一次变成好的回合就是距最近好块的曼哈顿距离，$bfs$解决。

c.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;
int to[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<string> s(n);
    for (auto &i : s) cin >> i;
    vector<vector<ll>> d(n, vector<ll>(m, INF64));
    queue<pii> que;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            bool good = false;
            for (auto &t2 : to) {
                int x = i + t2[0];
                int y = j + t2[1];
                if (0 <= x && x < n && 0 <= y && y < m && s[i][j] == s[x][y])
                    good = true;
            }
            if (good) {
                d[i][j] = 0;
                que.emplace(i, j);
            }
        }
    }
    while (!que.empty()) {
        auto[ux, uy] = que.front();
        que.pop();
        for (auto &t2 : to) {
            int x = ux + t2[0];
            int y = uy + t2[1];
            if (0 <= x && x < n && 0 <= y && y < m && d[x][y] == INF64) {
                d[x][y] = d[ux][uy] + 1;
                que.emplace(x, y);
            }
        }
    }
    int x, y;
    ll p;
    while (q--) {
        cin >> x >> y >> p;
        --x, --y;
        int t;
        if (p <= d[x][y]) t = 0;
        else t = (p - d[x][y]) & 1;
        cout << ((s[x][y] - '0') ^ t) << endl;
    }
    return 0;
}

下一题分数也太顶了，有缘相见叭