2023 年 1 月第一周做题记录

省选计划强迫我们必须做这个，这是为了完成作业的无奈之举。

过于简单的题就不写了。

ARC 系列

早期的 4 题场（其实当时是和 ABC 和场）和现代的 6 题场都会做。

ARC 102 (4)

A. Triangular Relationship（自行做出）

发现 $n$ 不大，因此考虑枚举 $a$ 。三元组应该形如 $(i,pk-i,qk-i)$ 的形式，若满足 $b+c=(p+q)k-2i$ 是 $k$ 的倍数，则需要 $2i$ 是 $k$ 的倍数，满足这一条件时，统计 $p$ 的数量并平方就是此时 $i$ 对应的答案数。 $p$ 应满足 $1\le pk-i\le n$ ，解不等式即可。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int main(void) {
    int n, k; long long ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) if (2 * i % k == 0) {
        int cnt = (n + i) / k - (i + k) / k + 1;
        ans += 1ll * cnt * cnt;
    }
    printf("%lld\n", ans);
    return 0;
}

后来看了眼题解，存在 $O(1)$ 公式，不过也不难想。

B. All Your Paths are Different Lengths（看了眼题解）

Portal.

给你一个数 $L$ ，构造一个有向图使得从 $1$ 到 $n$ 恰好有 $L$ 条路径且路径长度恰好为 $0$ 到 $L-1$ 。边有边权。点数小于等于 $20$ ，边数小于等于 $60$ 。 $2\leq L\leq 10^6$ 。

可以联想到二进制拆分。这样之后还有从 $2^{k}\sim l-1$ 的长度需要处理。我们可以让其从某个点直接“穿越”到终点，这样是没有重复长路的路径的。只要我们把 $l$ 的每一位 $1$ 都搞出来，“穿越”的边自然也就能求出来了。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int n, m, l;
int u[65], v[65], w[65];
void add(int x, int y, int d) { u[++m] = x; v[m] = y; w[m] = d; }

int main(void) {
    scanf("%d", &l);
    int b = 1, t = l - 1; n = 1;
    while (t >= b) {
        add(n, n + 1, b); add(n, n + 1, 0);
        t -= b; b <<= 1; ++n;
    }
    for (int i = 0; i < n - 1; ++i)
        if ((l >> i) & 1) add(i + 1, n, l & ~((1 << i + 1) - 1));
    printf("%d %d\n", n, m);
    for (int i = 1; i <= m; ++i)
        printf("%d %d %d\n", u[i], v[i], w[i]);
    return 0;
}

C. Stop. Otherwise…（看题解）

Portal.

有 $n$ 个不可区分的骰子，每个骰子有 $K$ 个面，上面有 $1$ 到 $K$ 。注意骰子之间不可区分，两个局面不同当且仅当存在一个点数 $i$ 使得投出 $i$ 的数量不同。

现在对于 $[2,2K]$ 中的每一个数 $x$ ，要求出任意投这个 $n$ 个骰子使得不存在任意两个骰子的点数和为 $x$ 的方案数。

$n,K\le 2000$ ，答案对 $998244353$ 取模。

考虑对单个 $x$ 如何求解。那么对于点数 $i\in [1,K]$ ，应该有以下几种情况：

$x-i\in [1,K]$ ，此时 $i$ 和 $x-i$ 至多只能出现一种，称为这一对数最多只能出现一种；
$x-i=i$ 时，这个 $i$ 只能出现一次；
$x-i\not\in [1,K]$ ，这个 $i$ 的出现无限制。

设 $f(i,j)$ 表示考虑了 $i$ 对数，其中选择了 $j$ 个数的方案数； $g(i,j)$ 代表考虑 $i$ 个没有限制的数，选择 $j$ 个数的方案数。那么：

$f(i,j)=f(i-1,j)+2\times \sum_{k=0}^{j-1} f(i-1,k)\\ \ \\ g(i,j)=\sum_{k=0}^j g(i-1,k)$

然后枚举每一种选的个数，组合起来即可。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;
const int MOD = 998244353;

int k, n;
int f[2005][2005], g[2005][2005];

int main(void) {
    scanf("%d%d", &k, &n); f[0][0] = g[0][0] = 1;
    for (int i = 1; i <= k; ++i) {
        i64 s0 = 0;
        for (int j = 0; j <= n; ++j) {
            f[i][j] = (f[i - 1][j] + s0 * 2) % MOD; s0 = (s0 + f[i - 1][j]) % MOD;
            g[i][j] = (g[i - 1][j] + (j > 0 ? g[i][j - 1] : 0)) % MOD;
        }
    }
    for (int x = 2; x <= (k << 1); ++x) {
        i64 ans = 0; int c1, c2 = (x % 2 == 0), c3 = 0;
        for (int i = 1; i <= k; ++i) c3 += (x - i < 1 || x - i > k);
        c1 = (k - c2 - c3) >> 1;
        for (int i = 0; i <= n; ++i) {
            ans = (ans + 1ll * f[c1][i] * g[c3][n - i]) % MOD;
            if (c2 && i < n) ans = (ans + 1ll * f[c1][i] * g[c3][n - i - 1]) % MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

D. Revenge of BBuBBBlesort!

到底有多少个冒泡排序复仇题！

Portal.

ARC 103 (4)

Portal.

A. /\/\/\/（自行做出）

Portal.

很无聊，直接糊个排序上去。

查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int n, ans = 0, a[100001];
struct Node {
    int id, cnt;
    bool operator < (const Node &a) const {
        return cnt > a.cnt;
    }
} b1[100001], b2[100001];

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++)
        if (i & 1) b1[a[i]].id = a[i], b1[a[i]].cnt++;
        else b2[a[i]].id = a[i], b2[a[i]].cnt++;
    sort(b1 + 1, b1 + 100001); sort(b2 + 1, b2 + 100001);
    if (b1[1].id != b2[1].id) ans = (n - b1[1].cnt - b2[1].cnt);
    else ans = min(n - b1[1].cnt - b2[2].cnt, n - b1[2].cnt - b2[1].cnt);
    printf("%d\n", ans);
    return 0;
}

B. Robot Arms

Portal.

ABC 系列

CF Div.2 系列

Codeforces Round #554 (Div. 2)

Portal.

C. Neko does Maths（自行做出）

Portal.

要求的是 $\text{lcm}(a+k,b+k)=\cfrac{(a+k)(b+k)}{\gcd(a+k,b+k)}=\cfrac{(a+k)(b+k)}{\gcd(b+k,a-b)}$ ，那么假设 $a>b$ ， $\gcd(b+k,a-b)$ 的值一定是 $a-b$ 的约数。那么我们枚举 $a-b$ 的约数 $i$ 并计算出让 $i$ 是 $b+k$ 的约数的最小 $k$ 即可，时间复杂度为 $O(\sqrt{a-b})$ 。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y); }
long long lcm(int x, int y) { return 1ll * x / gcd(x, y) * y; }

int a, b, k;
long long ans;

int calc(int x) {
    if (b % x == 0) return 0;
    return x - b % x;
}
void upd(int t) {
    long long tmp = 1ll * (a + t) / gcd(b + t, a - b) * (b + t);
    if (tmp < ans) ans = tmp, k = t;
    else if (tmp == ans) k = min(k, t);
}

int main(void) {
    scanf("%d%d", &a, &b); if (a < b) swap(a, b);
    ans = lcm(a, b), k = 0;
    for (int i = 1; i * i <= a - b; ++i)
        if ((a - b) % i == 0) {
            int t = calc(i); upd(t);
            t = calc((a - b) / i); upd(t);
        }
    printf("%d\n", k);
    return 0;
}

D. Neko and Aki’s Prank（看题解）

Portal.

有一个由所有长为 $2n$ 的合法括号序列组成的 Trie，现在要求这棵树上最多的边数，符合边两两之间均没有共同节点。

我们来看 $n=3$ 时候的 Trie 树：

实际上我们只需要贪心地选择边即可选到最大值，原因很简单，不选择这一条而选择下一条并不会使贡献变大。

可以发现，所有深度为偶数的节点都会连接一条边，所以现在的问题成了求深度为偶数的节点的个数。

设 $f(i,j)$ 代表有 $i$ 个左括号， $j$ 个右括号在 Trie 上能形成的括号序列个数。初始 $f(0,0)$ ，转移时，可以选择添加一个左括号或者右括号，只需要满足 $j\le i$ ，因此 $f(i,j)=f(i-1,j)+f(i,j-1)$ 。当 $i+j$ 为偶数时，这个节点在 Trie 上的深度也是偶数，加起来就是答案。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
const int MOD = 1000000007;

int n, ans;
int f[1005][1005];

int main(void) {
    scanf("%d", &n);
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        f[i][0] = 1;
        for (int j = 1; j <= i; ++j) 
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % MOD;
    }
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= i; ++j)
            if ((i + j) & 1) ans = (ans + f[i][j]) % MOD;
    printf("%d\n", ans);
    return 0;
}

E. Neko and Flashback（看了眼题解）

Portal.

对于一个 $i$ ，有 $b_i=\min\{a_i,a_{i+1}\},c_i=\max\{a_i,a_{i+1}\}$ ，也就是说 $b_i,c_i$ 各是 $a_i,a_{i+1}$ 其中的一个（当然需要 $b_i\le c_i$ ，否则无解）。注意这个输出方式， $p$ 的作用是将 $a$ 排列，也就是说我们只需要求出 $a$ 有哪些数组成即可。将给定的 $a_i,a_{i+1}$ 的关系看成一条无向边，走过这个路径就相当于满足了一个限制条件。那么在图上找出欧拉路，就可以得到一个满足所有的限制条件的序列 $a$ （需要先离散化后再建图）。时间复杂度 $O((n+m)\log m)$ 。

查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int n, tot, cur[100005], deg[200005], st[200005];
int b[100005], c[100005], B[200005];
vector<int> edges;
vector<int> G[200005];
inline void addedge(int u, int v) {
    edges.emplace_back(v); G[u].emplace_back(edges.size() - 1);
    ++deg[v];
}

void dfs(int x) {
    for (; cur[x] < G[x].size(); ++cur[x]) {
        int y = edges[G[x][cur[x]]];
        if (y) {
            edges[G[x][cur[x]]] = 0, edges[G[x][cur[x]] ^ 1] = 0;
            dfs(y);
        }
    }
    st[++tot] = x; 
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) scanf("%d", b + i), B[++tot] = b[i];
    for (int i = 1; i < n; ++i) scanf("%d", c + i), B[++tot] = c[i];
    sort(B + 1, B + tot + 1); tot = unique(B + 1, B + tot + 1) - (B + 1);
    for (int i = 1; i < n; ++i) {
        b[i] = lower_bound(B + 1, B + tot + 1, b[i]) - B;
        c[i] = lower_bound(B + 1, B + tot + 1, c[i]) - B; 
        if (b[i] > c[i]) return puts("-1"), 0;
        addedge(b[i], c[i]); addedge(c[i], b[i]);
    }
    int cnt = 0, h = 0;
    for (int i = 1; i <= tot; ++i) if (deg[i] & 1) {
        ++cnt;
        if (!h) h = i;
    }
    if (cnt == 1 || cnt > 2) return puts("-1"), 0;
    tot = 0; dfs(h ? h : 1);
    if (tot != n) return puts("-1"), 0;
    for (int i = tot; i >= 1; --i) printf("%d ", B[st[i]]);
    putchar('\n');
    return 0;
}

CF Div.1 系列

包括和场。

Codeforces Round #639 (Div. 1)

Portal.

A. Hilbert’s Hotel（自行做出）

Portal.

当存在 $i+a_i$ 余数相同时，就有问题。

查看代码

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

int main(void) {
    int T; scanf("%d", &T); while (T--) {
        int n, x; scanf("%d", &n); map<int, int> s;
        for (int i = 1; i <= n; ++i) scanf("%d", &x), s[((x + i) % n + n) % n]++;
        bool flag = true;
        for (auto x : s)
            if (x.second >= 2) { flag = false; break; }
        puts(flag ? "YES" : "NO");
    }    
    return 0;
}