2023 年 1 月第二周做题记录

AGC 系列

第一次做 AGC，非常兴奋！

会先做早期的，难度会小很多。

AGC 024

Portal.

B. Backfront

Portal.

如果我们把 $x$ 放到了最前面，那么小于 $x$ 的数字显然都必须操作。这样没有被操作的数字是一段连续的数字，它们原来的相对位置的递增的，找出这样最长的一段数字即可。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int n, ans = 1, s = 1;
int a[200005];

int main(void) {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; ++i) scanf("%d", &x), a[x] = i;
    for (int i = 1; i < n; ++i) {
        if (a[i + 1] > a[i]) ans = max(ans, ++s);
        else s = 1;
    }
    printf("%d\n", n - ans);
    return 0;
}

CF Div.2 系列

以后这里只会写有必要写的题。

Codeforces Round #585 (Div. 2)

Portal.

E. Marbles

Portal.

如果知道最后的颜色顺序，那么答案便可以直接统计。观察到颜色数很少，那么设 $f(i)$ 表示当前考虑的颜色顺序状压后为 $i$ ，枚举其中哪个颜色放在最后并计算代价即可。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

int n, cnt[25];
i64 f[1100000], w[25][25]; // w(x, y): y 换到 x 前的代价

int main(void) {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x); ++cnt[--x];
        for (int j = 0; j < 20; ++j) w[j][x] += cnt[j];
    }
    for (int i = 1; i < 1 << 20; ++i) {
        f[i] = 1e18;
        for (int j = 0; j < 20; ++j)
            if (i & (1 << j)) {
                i64 sum = 0; 
                for (int k = 0; k < 20; ++k)
                    if ((1 << k) & (i ^ (1 << j))) sum += w[j][k];
                f[i] = min(f[i], f[i ^ (1 << j)] + sum);
            }
    }
    printf("%lld\n", f[(1 << 20) - 1]);
    return 0;
}

Codeforces Round #845 (Div. 2)

Portal.

B. Emordnilap

Portal.

序列可以分成前后两个部分。假设前半部分有 $m$ 个逆序对，那么就有 $\frac{n(n-1)}{2}-m$ 个正序对，也就是说后半部分有 $\frac{n(n-1)}{2}-m$ 个逆序对；后半部分的任意一个数 $i$ 在前半部分有 $i-1$ 个比它小，逆序对数为 $\frac{n(n-1)}{2}$ 。因此任意一个排列的逆序对数都是 $n(n-1)$ ，总答案就是 $n!n(n-1)$ 。

D. Score of a Tree

Portal.

诈骗题（我是被骗的）！

一个点的贡献是它自己的权值，它所有儿子的异或和，它所有孙子的异或和，以此类推。总共有 $2^n$ 种情况，对于每个节点，它要么初始权值为 $1$ ，要么初始权值为 $0$ ，每一种都对应 $2^{n-1}$ 种情况。

设叶子节点为 $1$ 层，节点 $i$ 的层数 $s_i$ 为 $\max\{s_{son[i]}\}+1$ 。第 $i$ 个节点在时间 $0\sim s_i-1$ 的时刻内都会有一个 $2^{n-1}$ 的贡献，因此答案为 $2^{n-1}\sum s_i$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007; 

int poww(int a, int b) {
    int res = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) res = 1ll * res * a % P; 
    return res;
}

int n, f[200005];
vector<int> G[200005];

void dfs(int x, int fa) {
    for (int y : G[x]) if (y != fa)
        dfs(y, x), f[x] = max(f[x], f[y] + 1);
}

void solve(void) {
    cin >> n; for (int i = 1; i <= n; ++i) G[i].clear(), f[i] = 1;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v; 
        G[u].emplace_back(v); G[v].emplace_back(u);
    } dfs(1, 0); int ans = 0;
    for (int i = 1; i <= n; ++i) ans = (ans + f[i]) % P;
    cout << 1ll * ans * poww(2, n - 1) % P << "\n"; 
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

E. Edge Reverse

Portal.

显然是二分答案，可以反转的边相当于无向边，将图 SCC 缩点后应该恰好有一个入度为 $0$ 的点才能满足条件。

查看代码

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

struct edge {
    int u, v, w; 
    bool operator < (const edge &a) const {
        return w < a.w; 
    }
} e[200005];

int n, m; 
vector<int> G[200005];
int dfn[200005], low[200005], num, st[200005], tot;
int cnt, col[200005], deg[200005];
bool ins[200005]; 

void tarjan(int x) {
    dfn[x] = low[x] = ++num; ins[st[++tot] = x] = true; 
    for (int y : G[x])
        if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if (ins[y]) low[x] = min(low[x], dfn[y]);
    if (dfn[x] == low[x]) {
        int y; ++cnt; 
        do ins[y = st[tot--]] = false, col[y] = cnt; while (x != y);
    }
}

bool P(int x) {
    for (int i = 1; i <= n; ++i) G[i].clear(), dfn[i] = ins[i] = deg[i] = 0;
    for (int i = 1; i <= m; ++i) {
        G[e[i].u].emplace_back(e[i].v);
        if (i <= x) G[e[i].v].emplace_back(e[i].u);
    } num = tot = cnt = 0; 
    for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
    for (int u = 1; u <= n; ++u) for (int v : G[u]) if (col[u] != col[v]) ++deg[col[v]];
    int res = 0; 
    for (int i = 1; i <= cnt; ++i) res += (deg[i] == 0);
    return res == 1; 
}

int main(void) {
    int T; scanf("%d", &T); while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        sort(e + 1, e + m + 1);
        int L = -1, R = m + 1; 
        while (L + 1 != R) {
            int mid = L + R >> 1; 
            if (P(mid)) R = mid;
            else L = mid; 
        }
        printf("%d\n", R != m + 1 ? e[R].w : -1);
    }
    return 0;
}

F. Comfortably Numb

Portal.

找出序列中权值最大的位置，答案区间要么在它左侧或右侧，要么跨越区间。合并时采用启发式合并的思想，枚举小区间中的下标作为答案的一段，就是要在大区间中找一个异或值最大的，可以使用可持久化 01 Trie 解决。

查看代码

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

int n; 
int a[200005], f[21][200005], lg[200005], s[200005];
int ch[6400005][2], tot, root[200005], val[6400005];

int qmax(int l, int r) {
    int k = lg[r - l + 1];
    if (a[f[k][l]] > a[f[k][r - (1 << k) + 1]]) return f[k][l];
    return f[k][r - (1 << k) + 1];
}

void insert(int x, int pre, int v) {
    for (int i = 29; i >= 0; --i) {
        int c = v >> i & 1; ch[x][!c] = ch[pre][!c];
        if (!ch[x][c]) ch[x][c] = ++tot; 
        x = ch[x][c], pre = ch[pre][c];
        val[x] = val[pre] + 1;     
    }
    
}
int query(int x, int y, int v) {
    int res = 0; 
    for (int i = 29; i >= 0; --i) {
        int c = v >> i & 1; 
        if (val[ch[y][!c]] - val[ch[x][!c]]) x = ch[x][!c], y = ch[y][!c], res |= 1 << i; 
        else x = ch[x][c], y = ch[y][c];
    }
    return res; 
}

int merge(int l, int r) {
    if (l >= r) return 0; 
    int mid = qmax(l, r), ans = max(merge(l, mid - 1), merge(mid + 1, r));
    if (r - mid < mid - l) { // 将右半段合并到左半段
        for (int i = mid; i <= r; ++i) // 枚举右端点
            ans = max(ans, query(l > 1 ? root[l - 2] : 0, root[mid - 1], a[mid] ^ s[i]));
    } else {
        for (int i = l; i <= mid; ++i) // 枚举左端点
            ans = max(ans, query(root[mid - 1], root[r], a[mid] ^ s[i - 1]));
    }
    return ans; 
}

void solve(void) {
    for (int i = 0; i <= tot; ++i) ch[i][0] = ch[i][1] = val[i] = 0; 
    cin >> n; tot = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i], f[0][i] = i, s[i] = s[i - 1] ^ a[i];
    for (int i = 0; i <= n; ++i) {
        root[i] = ++tot;
        insert(root[i], i == 0 ? 0 : root[i - 1], s[i]);
    }
    for (int j = 1; 1 << j <= n; ++j) for (int i = 1; i + (1 << j) - 1 <= n; ++i) 
        if (a[f[j - 1][i]] > a[f[j - 1][i + (1 << j - 1)]]) 
            f[j][i] = f[j - 1][i]; 
        else f[j][i] = f[j - 1][i + (1 << j - 1)];
    cout << merge(1, n) << "\n";
}

int main(void) {
    for (int i = 2; i <= 200000; ++i) lg[i] = lg[i >> 1] + 1; 
    ios::sync_with_stdio(false); int T; cin >> T; while (T--) solve();
    return 0;
}

CF Div.1 系列

感动！

Codeforces Round #576 (Div. 1)

Portal.

C. Matching vs Independent Set

Portal.

我们暴力查找边的独立集，如果最后独立集中有 $x$ 条边，那么点的独立集至少有 $3n-2x$ 个点，这两个至少有一个 $\ge n$ 。

查看代码

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

int n, m;
bool a[300005];

int main(void) {
    int T; scanf("%d", &T); while (T--) {
        scanf("%d%d", &n, &m); fill(a + 1, a + n * 3 + 1, 0); vector<int> ans; 
        for (int i = 1; i <= m; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            if (!a[u] && !a[v]) a[u] = a[v] = 1, ans.emplace_back(i);
        }
        if (ans.size() >= n) {
            puts("Matching");
            for (int i = 0; i < n; ++i) printf("%d ", ans[i]); 
        } else {
            puts("IndSet");
            for (int i = 1, cnt = 0; i <= n * 3 && cnt < n; ++i)
                if (!a[i]) printf("%d ", i), ++cnt; 
        }
        putchar('\n');
    }
    return 0;
}

F. GCD Groups 2

Portal.

将一个数加入其中一个分组，如果最大公约数可以变小就加，否则加入另一个。多次随机重复上述过程即可得到正确答案。

查看代码

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

int gcd(int x, int y) {
    if (y == 0) return x; 
    return gcd(y, x % y);
}

int n, a[100005], id[100005], c[100005], g[3]; 
mt19937 Rand(time(0)); 

bool solve(void) {
    c[id[1]] = 1; g[1] = a[id[1]]; 
    c[id[2]] = 2; g[2] = a[id[2]]; 
    for (int i = 3; i <= n; ++i)
        if (a[id[i]] % g[1] == 0) {
            c[id[i]] = 2; 
            g[2] = gcd(g[2], a[id[i]]);
        } else {
            c[id[i]] = 1; 
            g[1] = gcd(g[1], a[id[i]]);
        }
    return g[1] == 1 && g[2] == 1; 
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), id[i] = i;
    for (int op = 1; op <= 100; ++op) {
        shuffle(id + 1, id + n + 1, Rand); 
        if (solve()) {
            puts("YES");
            for (int i = 1; i <= n; ++i) printf("%d ", c[i]);
            putchar('\n'); return 0; 
        }
    } 
    puts("NO"); return 0;
}