AtCoder Beginner Contest 210

发表于2021-07-27更新于2023-09-15字数统计2.2k阅读时长24分

比赛链接

D National Railway

Description

题目链接

Solution

对于 (i,j)(i,j)，我们只需要考虑 i′≤ii' \le i 的点和它之间的代价，分两种情况：

  1. j′≤jj' \le j，代价为 Ai,j+C∗(i+j)+Ai′,j′−C∗(i′+j′)A_{i,j}+C*(i+j)+A_{i',j'}-C*(i'+j')。
  2. j′>jj' > j，代价为 Ai,j+C∗(i−j)+Ai′,j′−C∗(i′−j′)A_{i,j}+C*(i-j)+A_{i',j'}-C*(i'-j')。

我们只需要对 Ai′,j′−C∗(i′+j′)A_{i',j'}-C*(i'+j') 和 Ai′,j′−C∗(i′−j′)A_{i',j'}-C*(i'-j') 记录二维前缀/后缀最小值即可。

Code

National Railway
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 1E3 + 5;
const int MOD = 1E9 + 7;
int n, m;
LL a[MAXN][MAXN], mi1[MAXN][MAXN], mi2[MAXN][MAXN], c;

signed main() {
    // freopen("1.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin >> n >> m >> c;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++) mi1[i][j] = mi2[i][j] = LONG_LONG_MAX;
    LL ans = LONG_LONG_MAX;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            mi1[i][j] =
                min({a[i][j] - c * (i + j), mi1[i][j - 1], mi1[i - 1][j]});
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 1; j--)
            mi2[i][j] =
                min({a[i][j] - c * (i - j), mi2[i][j + 1], mi2[i - 1][j]});
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i > 1) ans = min(ans, a[i][j] + c * (i + j) + mi1[i - 1][j]);
            if (j > 1) ans = min(ans, a[i][j] + c * (i + j) + mi1[i][j - 1]);
            if (i > 1) ans = min(ans, a[i][j] + c * (i - j) + mi2[i - 1][j]);
            if (j < m) ans = min(ans, a[i][j] + c * (i - j) + mi2[i][j + 1]);
        }
    cout << ans;
    return 0;
}

E Ring MST

Description

题目链接

Solution

考虑 KruskalKruskal 算法，每次选择最小的不形成环的边不断加入。然而其时间复杂度为 O(ElogE)O(ElogE)，其中 EE 为图的边数。

在本题中，图的边数是巨大的，所以需要加快 KruskalKruskal 算法加边的过程。

设从小到大枚举到 CtC_t 时 KruskalKruskal 算法形成的图为 GtG_t，XtX_t 为 GtG_t 中联通块的个数。则新增的联通块个数为 Xt−1−XtX_{t-1} - X_t。

所以最终答案为 ∑t=1MCt(Xt−1−Xt)\sum\limits_{t=1}^{M}C_t(X_{t-1}-X_t)。如果 XM>1X_M > 1，则最终图不连通，输出 -1。

如何求得 XtX_t：
因为对于任意 i=1,2,...,ti = 1, 2, ..., t 和任意 x=0,1,...,N−1x = 0, 1, ..., N - 1，我们可以从顶点 xx 移动到 (x+Ai)mod  N(x + A_i) \mod N。所以在 GtG_t 中，我们可以从 vv 移动到 ww 当且仅当存在整数 k1,k2,...,ktk_1, k_2, ..., k_t，使得 w≡v+k1A1+k2A2+...+ktAtmod  Nw \equiv v + k_1A_1+k_2A_2+...+k_tA_t \mod N

上述式子 ⇔\Leftrightarrow w=v+k0N+k1A1+k2A2+...+ktAtw = v + k_0N+k_1A_1+k_2A_2+...+k_tA_t ⇔\Leftrightarrow w=v+kdtw=v + kd_t ⇔\Leftrightarrow w≡vmod  dtw \equiv v \mod d_t

其中 dt=gcd(N,A1,A2,...,At)d_t = gcd(N, A_1, A_2, ..., A_t)。

因此 uu 和 vv 属于相同联通块当且仅当 w≡vmod  dtw \equiv v \mod d_t，因此 Xt=dtX_t = d_t。

Code

Ring MST
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
#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int n, m;
array<pair<int, int>, MAXN> a;

void kruskal() {
    sort(a.begin() + 1, a.begin() + m + 1);
    int cnt = 0, gcd = n;
    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        int tmp = __gcd(gcd, a[i].second);
        int add = min(gcd - tmp, n - 1 - cnt);
        cnt += add;
        ans += 1LL * a[i].first * add;
        gcd = tmp;
    }
    cout << (gcd == 1 ? ans : -1) << "\n";
}

int main() {
    boost;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i].second >> a[i].first;
    kruskal();
    return 0;
}

F Coprime Solitaire

Description

题目链接

Solution

枚举 22 到 2∗1062*10^6 的素数 pp。

对于每个 pp，设所选择的卡牌为 Xp,1,Xp,2,...,Xp,kpX_{p,1}, X_{p, 2}, ..., X_{p,k_p} (区分正反面, 即 Xp,iX_{p,i} 可能是某个卡牌的正面或反面)。

则 Takahashi is happy 当且仅当 ∀p(≤2∗106)\forall p(\le 2*10^6) 且 pp 为素数，卡牌朝上的数字中只有至多一个有质因子 pp。即选了 Xp,iX_{p,i}，其它 Xp,jX_{p,j} 都不能选。

转化为逻辑表达式为 F:=⋀p:prime,p≤2∗106⋀1≤i,j≤kp,i≠j(Xp,i→¬Xp,j)=trueF:=\bigwedge\limits_{p:prime,p\le 2*10^6}\bigwedge\limits_{1\le i,j \le k_p, i \ne j} (X_{p,i} \rightarrow \neg X_{p,j}) = true

我们令 Fp:=⋀1≤i,j≤kp,i≠j(Xp,i→¬Xp,j)F_p:= \bigwedge\limits_{1\le i,j \le k_p, i \ne j} (X_{p,i} \rightarrow \neg X_{p,j})

该问题可通过 2-SAT 算法解决。但是根据上述表达式建图边数过多，无法在规定时间内通过该题，还需要引入 2 类增补变量 Yp,1,Yp,2,...,Yp,kpY_{p,1}, Y_{p,2},...,Y_{p,k_p} 和 Zp,1,Zp,2,...,Zp,kpZ_{p,1}, Z_{p,2},...,Z_{p,k_p}，用 Fp′F_p' 来替换 FpF_p:

Fp′:=⋀1≤i≤kp(Yp,i→¬Xp,i)∧⋀2≤i≤kp(Yp,i→Yp,i−1)∧⋀2≤i≤kp(Xp,i→Yp,i−1)∧⋀1≤i≤kp(Zp,i→¬Xp,i)∧⋀1≤i≤kp−1(Zp,i→Zp,i+1)∧⋀1≤i≤kp−1(Xp,i→Zp,i+1)F_p':= \bigwedge\limits_{1\le i\le k_p}(Y_{p,i} \rightarrow \neg X_{p,i}) \wedge \bigwedge\limits_{2\le i\le k_p}(Y_{p,i} \rightarrow Y_{p,i-1}) \wedge \bigwedge\limits_{2\le i\le k_p}(X_{p,i} \rightarrow Y_{p,i-1}) \wedge \\ \bigwedge\limits_{1\le i\le k_p}(Z_{p,i} \rightarrow \neg X_{p,i}) \wedge \bigwedge\limits_{1\le i\le k_p-1}(Z_{p,i} \rightarrow Z_{p,i+1}) \wedge \bigwedge\limits_{1\le i\le k_p-1}(X_{p,i} \rightarrow Z_{p,i+1})

画下图可知这些增补变量相当于两条链，把 Xp,iX_{p,i} 与 Xp,1≤j<iX_{p,1\le j < i} 以及 Xp,iX_{p,i} 与 Xp,i<j≤kpX_{p, i<j \le k_p} 间接连接起来，从而不用两两加边。

最后令 F′=⋀p:prime,p≤2∗106Fp′F'=\bigwedge\limits_{p:prime,p\le 2*10^6}F_p'，则 F′⇔FF' \Leftrightarrow F。

时间复杂度 O(Nlogmax⁡(Ai,Bi))O(Nlog{\max(A_i,B_i)})。

注意即使 A,BA, B 全部相同，最多也只由 8 个不同素数组成，所以即使一个 pp 的倍数对应多个 AiA_i 或 BiB_i，复杂度也是 O(Nlogmax⁡(Ai,Bi))O(Nlog{\max(A_i,B_i)}) 的。

Code

Coprime Solitaire
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 3e4 + 4, MAXV = 2e6 + 6, MOD = 1e9 + 7;

int n, tot, cntscc, top, N;
int dfn[MAXV], low[MAXV], stk[MAXV], ins[MAXV], belong[MAXV];
array<int, MAXN> a, b;
vector<int> primes;
vector<int> ids[MAXV], g[MAXV];

void seive() {
    vector<bool> isprime(MAXV);
    fill(isprime.begin(), isprime.end(), true);
    isprime[0] = isprime[1] = false;
    for (int i = 2; i < MAXV; i++) {
        if (isprime[i]) primes.push_back(i);
        for (auto& j : primes) {
            if (i * j >= MAXV) break;
            isprime[i * j] = false;
            if (i % j == 0) break;
        }
    }
}

void add(int u, int v) { g[u].push_back(v); }

void tarjan(int cur) {
    dfn[cur] = low[cur] = ++tot;
    stk[++top] = cur, ins[cur] = true;
    for (const auto& to : g[cur]) {
        if (!dfn[to]) {
            tarjan(to);
            low[cur] = min(low[cur], low[to]);
        } else if (ins[to]) {
            low[cur] = min(low[cur], dfn[to]);
        }
    }
    if (dfn[cur] == low[cur]) {
        ++cntscc;
        int tmp;
        do {
            tmp = stk[top--];
            ins[tmp] = false;
            belong[tmp] = cntscc;
        } while (cur != tmp);
    }
}

int main() {
    boost;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        ids[a[i]].push_back(i);
        ids[b[i]].push_back(i + n); // 某个值对应所有节点编号
    }
    seive();
    vector<int> nodes;
    N = 2 * n;
    for (auto& i : primes) {
        nodes.clear();
        for (int j = i; j < MAXV; j += i) { // p, 2p, ... kp
            for (const auto& id: ids[j]) nodes.push_back(id);
        }
        for (int j = N + 1; j <= N + nodes.size(); j++) {
            int x = nodes[j - N - 1];
            int nx = x > n ? x - n : x + n;
            add(j, nx);
            if (j > N + 1) add(j, j - 1), add(x, j - 1);
        }
        for (int j = N + nodes.size() + 1; j <= N + nodes.size() * 2; j++) {
            int x = nodes[j - N - nodes.size() - 1];
            int nx = x > n ? x - n : x + n;
            add(j, nx);
            if (j != N + nodes.size() * 2) add(j, j + 1), add(x, j + 1);
        }
        N += nodes.size() * 2;
    }
    for (int i = 1; i <= 2 * n; i++) 
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i++)
        if (belong[i] == belong[i + n]) {
            cout << "No\n";
            return 0;
        }
    cout << "Yes\n";
    return 0;
}