我的刷题日记

发表于 2023-09-25 更新于 2024-06-10 分类于算法本文字数： 15k 阅读时长 ≈ 56 分钟

悲报: 要去 CCPC 桂林赛区坐牢了.

校赛被队友带飞了, 身不由己, 现在希望自己要打出点成绩不要太丢脸. 从今天开始高强度刷题. Codeforces Div 1/2 一题不落, Atcoder ABC 狠狠开刷, 区域赛的 vp 狠狠开打...

就看看我又没有恒心做到日更了, 不管怎的先开个究极大坑在这里.

UPD: 是我想多了. 不过 11 月还有校赛, 狠狠练习

Educational Codeforces Round 155 (Rated for Div. 2)

9.25 补

A. Rigged!

题意: $n$ 个人举重比赛, 每个人有 $s$ 和 $e$, 代表最大举重重量和举重次数, 确定一个 $w>0$ 使得第一个人能赢. 反之输出 -1.

题解: 如果 $s_i \geqslant s_0$ 且 $e_i \geqslant e_0$ 无解, 如果有解答案不超过 $s_0$.

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

int T = 1;

void solve()
{
    int n, s1, e1;
    bool ok = true;
    cin >> n >> s1 >> e1;
    for (int i = 1; i < n; i++)
    {
        int s, e;
        cin >> s >> e;
        if (s >= s1 && e >= e1)
            ok = false;
    }
    cout << (ok ? s1 : -1) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

B. Chips on the Board

题意: 一个 $n\times n$ 的矩阵, 每一列或者每一行都要有一个 chip, 摆放 chip 需要 $a_i + b_j$ 的代价, 求最小代价.

题解: 在同一列的话只要让那一行最小就可以, 反之亦然, 然后取一个 min 就可以了.

注意 a 求和会爆 int, 不过开 LL 应该是基操了.

void solve()
{
    int n;
    cin >> n;
    LL sa = 0;
    int mina = 1e9;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        sa += a;
        mina = min(mina, a);
    }
    LL sb = 0;
    int minb = 1e9;
    for (int i = 0; i < n; i++)
    {
        int b;
        cin >> b;
        sb += b;
        minb = min(minb, b);
    }
    cout << min(sa + 1LL * minb * n, sb + 1LL * mina * n) << '\n';
}

C. Make it Alternating

题意: 给定一个 01 字符串 $s$, 可以删去 $s_i$, 要求让相邻字符不同, 求最小操作数以及操作方案.

题解: 例如 100001 -> 101 长度为 $n$ 的连续区间要删去 $n - 1$ 个字符, 方案数是 $\binom{n}{n-1}=n$ 个, 方案数乘法原理累计起来, 排列一下删除字符的操作 $\text{ans}!$ 就是方案数.

void solve()
{
    LL ans = 0, ways = 1;
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        int j = i;
        while (j + 1 < n && s[j + 1] == s[j])
            j++;
        int len = j - i + 1;
        ans += len - 1;
        ways = ways * len % MOD;
        i = j;
    }
    for (int i = 1; i <= ans; i++)
        ways = ways * i % MOD;
    cout << ans << ' ' << ways << '\n';
}

双指针算法复习

求连续区间长度

for (int i = 0; i < n; i++)
{
    int j = i;
    while (j + 1 < n && s[j + 1] == s[j])
        j++;
    int len = j - i + 1;
    // ...
    i = j;
}

求最长连续不重复子区间长度

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        s[a[i]] ++;
        while (s[a[i]] > 1)
            s[a[j++]] --;
        ans = min(ans, i - j + 1);
    }
    cout << ans << '\n';
}

D. Sum of XOR Functions

题意: 计算一个求和

\[\sum_{l=1}^n\sum_{r=l}^nf(l,r)\cdot(r-l+1)\]

这里 $f(l,r)=a_l\oplus a_{l+1}\oplus\cdots\oplus a_{r-1}\oplus a_r$ 表示一个异或和.

题解:

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
using LL = long long;
template <const int T>
struct ModInt
{
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {}
    int val() { return x; }
    ModInt operator+(const ModInt &a) const
    {
        int x0 = x + a.x;
        return ModInt(x0 < mod ? x0 : x0 - mod);
    }
    ModInt operator-(const ModInt &a) const
    {
        int x0 = x - a.x;
        return ModInt(x0 < 0 ? x0 + mod : x0);
    }
    ModInt operator*(const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator/(const ModInt &a) const { return *this * a.inv(); }
    bool operator==(const ModInt &a) const { return x == a.x; };
    bool operator!=(const ModInt &a) const { return x != a.x; };
    void operator+=(const ModInt &a)
    {
        x += a.x;
        if (x >= mod)
            x -= mod;
    }
    void operator-=(const ModInt &a)
    {
        x -= a.x;
        if (x < 0)
            x += mod;
    }
    void operator*=(const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator/=(const ModInt &a) { *this = *this / a; }
    friend ModInt operator+(int y, const ModInt &a)
    {
        int x0 = y + a.x;
        return ModInt(x0 < mod ? x0 : x0 - mod);
    }
    friend ModInt operator-(int y, const ModInt &a)
    {
        int x0 = y - a.x;
        return ModInt(x0 < 0 ? x0 + mod : x0);
    }
    friend ModInt operator*(int y, const ModInt &a) { return ModInt(1LL * y * a.x % mod); }
    friend ModInt operator/(int y, const ModInt &a) { return ModInt(y) / a; }
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x; }
    friend istream &operator>>(istream &is, ModInt &t) { return is >> t.x; }

    ModInt pow(int64_t n) const
    {
        ModInt res(1), mul(x);
        while (n)
        {
            if (n & 1)
                res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }

    ModInt inv() const
    {
        int a = x, b = mod, u = 1, v = 0;
        while (b)
        {
            int t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        if (u < 0)
            u += mod;
        return u;
    }
};
using mint = ModInt<998244353>;

int main()
{

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    vector<int> s(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> s[i], s[i] ^= s[i - 1];
    mint ans = 0;
    for (int i = 0; i <= 30; i++)
    {
        mint cnt[2] = {1, 0}, sum[2] = {0};
        for (int j = 1; j <= n; j++)
        {
            int bit = (s[j] >> i & 1);
            ans += (j * cnt[bit ^ 1] - sum[bit ^ 1]) * (1 << i);
            cnt[bit] += 1;
            sum[bit] += j;
        }
    }
    cout << ans << '\n';
}

拆位技巧

参考: 一类二进制拆位算贡献的题目

考虑每一位的贡献. 例如

\[\sum_{i=1}^n\sum_{j=1}^n(a_i\oplus a_j)\]

考虑的是

\[\sum_{k=0}^m2^k\times\sum_{j=1}^n[bit_{i,k}\neq bit_{j,k}]\]

如果 $bit_{i,k}=0$, 考虑 $bit_{j,k_1} = 1$ 的 $k_1$ 个数, 答案就是 $2^k \cdot cnt_{k_1}$.
如果 $bit_{i,k}=1$, 考虑 $bit_{j,k_1} = 0$ 的 $k_0$ 个数, 答案就是 $2^k \cdot cnt_{k_0}$.

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int f[2][35];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 30; j++)
            f[(a[i] << j) & 1][j] ++;

    LL ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 30; j++)
            ans += f[((a[i] << j) & 1) ^ 1][j] * (1 << j);
    cout << ans << '\n';
}

Codeforces Round 899 (Div. 2)

A. Increasing Sequence

题意: 给定序列 a, 定义序列 b 如果满足各个数大于 0 且单调递增, 同时 $a_i\neq b_i$, 则称 b 为好数组. 找到所有好数组中 $b_n$ 的最小值.

#include <bits/stdc++.h>
using LL = long long;
using namespace std;
typedef pair<int, int> PII;

const int MOD = 998244353, N = 1e2 + 5;
int T = 1;

void solve()
{
    int n;
    cin >> n;
    int ans[2] = {1, 1};
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        ans[0] = ans[1];
        if (a == ans[0])
            ans[0] ++;
        ans[1] = ans[0] + 1;
    }
    cout << ans[0] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

B. Sets and Union

题意: 如果集合 $S$ 等于 $S_1, S_2, \dots, S_n$ 之中一些集合的并, 那么称 $S$ 可维护. 注意这里 $S\neq \bigcup S_i$.

找到最大的可维护集合 $S$, 输出它元素的个数.

题解: 关注下这道题的数据大小 ($1\leqslant s_i \leqslant 50$), 集合不用 std::set, 可以用位向量表示.

例如一个位向量 [0...011] 代表集合 $\{0,1\}$.

这样操作的好处:

集合的并可以用 a | b
集合的大小就是 1 的个数: __builtin_popcount

我们要做的是求: 所有集合的并, 扣掉一个集合, 剩下集合的并.

可以这么做: 枚举所有元素 $a_i$, 只要判断 $a_i\in S_j$, 把所有不包含 $a_i$ 的集合合并即可. 答案取一个 max.

void solve()
{
    int n;
    cin >> n;
    LL Or = 0;
    vector<LL> a(n + 1);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        while (k--)
        {
            int x;
            cin >> x;
            a[i] |= 1LL << x;
        }
        Or |= a[i];
    }
    for (int i = 1; i <= 50; i++)
    {
        if (Or >> i & 1)
        {
            LL v = 0;
            for (int j = 0; j < n; j++)
                if (~a[j] >> i & 1)
                    v |= a[j];
            ans = max(ans, __builtin_popcountll(v));
        }
    }
    cout << ans << '\n';
}

C. Card Game

题意: $n$ 张牌按顺序从下往上堆叠(最上面是最高位的), 每张牌有属性 $a_i$. 你可以删除第 $i\leqslant n$ 张牌(每次删除会重新计算索引), 如果 $i$ 是奇数, 你可以获得 $a_i$ 个点数. 你可以在任意时刻结束游戏. 求最大分数.

注意 $a_i$ 可能是负的.

题解: 从上往下删, 首先我们可以把所有奇数位 >0 的删去, 如果偶数位是 >0 的我们在最下面调整一次奇偶, 就可以将偶数位的正数加入分数.

调整奇偶考虑 a[1], 但如果 a[1] < 0 就考虑删去 a[2].

讨论一下, a[1] < 0 就取 max(0, a[1]+a[2]), a[1] > 0 就取 max(a[1], a[1]+a[2]).

你会发现我们可能需要同时删去 a[1] 和 a[2], 这不就改变不了奇偶了么. 但实际上, 先删 a[1] 就能改变奇偶, 把上面的删掉了, 然后再删去 a[2] 就可以了.

注意卡 int 和 n > 1 的特判.

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    LL ans = 0;
    for (int i = 3; i <= n; i++)
        ans += max(0, a[i]);
    ans += max(a[1] > 0 ? a[1] : 0, n > 1 ? a[1] + a[2] : a[1]);
    cout << ans << '\n';
}

D. Tree XOR

换根 DP, 不会做.

Codeforces Round #900 (Div. 3)

A. How Much Does Daytona Cost?

题意: 给定数组 a, 整数 k, 确定是否存在一个 a 的连续子区间使得 k 是这个子区间的众数.

只需要回答 yes or no.

题解: 题目没有提到子区间的长度, 我们考虑长度为 1 的子序列, 只要 k 存在于 a, 那么它就是这个子序列的众数.

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        if (a[i] == k)
        {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

B. Aleksa and Stack

题意: 构造一个长度为 $n\geqslant 3$ 的严格单调递增数组, 使得 $3a_{i+2}$ 不能被 $a_i+a_{i+1}$ 整除. 输出这样的一个数组.

例如 n = 3, 那么 6 8 12 就是一个答案.

题解: $n\leqslant 2\cdot 10^5$ 那么给每个数添加一个大数, 例如 5e5 就可以避免整除的问题了.

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cout << i + 5e5 << ' ';
}

不偷鸡你可以模拟整个过程, 从 2, 3 然后判断整除关系即可.

C. Vasilije in Cacak

题意: 给定 3 个正整数 $n, k, x$, 判断能否在 1~n 之间挑出 k 个不同的数字, 使得它们的和为 $x$.

题解: x 的下界 $\sum_{1}^{k}$, 上界 $\sum_{n-k+1}^{n}$, 判断是否在这之间即可.

void solve()
{
    int n, k;
    LL x;
    cin >> n >> k >> x;
    if (x >= 1LL * (1 + k) * k / 2 && x <= 1LL * (2 * n - k + 1) * k / 2)
        cout << "YES\n";
    else
        cout << "NO\n";
}

D. Reverse Madness

题意: 给定小写字符组成的字符串 s, 长度为 n, 两个长度为 k 的整数数组 l 和 r, 两个数组满足

$l_1 = 1, r_k = n$
$l_i \leqslant r_i$
$l_i = r_{i-1}+1, i \geqslant 2$

需要对 s 进行 q 次操作, 每次操作给出一个整数 x

找到 $l_i \leqslant x \leqslant r_i$ 的下标 $i$
令 $a=\min(x,r_i+l_i-x)$, $b=\max(x, r_i+l_i-x)$
reverse(s[a:b])

输出 q 次操作后的字符串 s.

E. Iva & Pav

Codeforces Round 901 (Div. 2)

A. Jellyfish and Undertale

题意: 炸弹有 $b$ 的爆炸时间, 选择工具可以增加 $x_i$ 的时间, 但时间不能超过 $a$, 即 $\min{(x_i+c, a)}$, 问炸弹爆炸能拖多长时间才爆炸.

题解: 模拟即可

void solve()
{
    LL a, b, n;
    cin >> a >> b >> n;
    vector<LL> x(n + 1);
    LL ans = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i];
        ans += min(a - 1, x[i]);
    }
    cout << ans + b << endl;
}

B. Jellyfish and Game

题意: 进行 k 轮比赛, A 有 $n$ 个价值 $a_i$ 的苹果, B 有 $m$ 个价值 $b_i$ 的苹果, 他们会进行 $k$ 轮次的比赛, 如果 $i$ 是奇数, A 可以交换 B 的一个苹果或者不动, 偶数就是轮到 B 行动.

A 和 B 都想最大化他们的分数, 求 A 最后最高分是多少.

题解: 每个选手的策略都是交换自己价值最低的苹果和对手价值最高的苹果, 或者考虑不进行交换(因为自己价值最低的比对手价值最高的还要高). 答案和 k 的奇偶相关, k 为奇数对 A 最优, 偶数则对 B 最优.

偶数情况的代码实现还是有些难写的. 调了好久.

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<LL> a(n), b(m);
    LL ans = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i], ans += a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    if (k & 1) {
        ans = max(ans, ans + b[m - 1] - a[0]);
    }
    else {
        LL mi = b[0], ma = a[n - 1];
        // need swap
        if (a[0] < b[m - 1])
        {
            mi = min(mi, a[0]);
            ma = max(ma, b[m - 1]);
            ans += b[m - 1] - a[0];
        }
        ans += mi - ma;
    }
    cout << ans << '\n';
}

C. Jellyfish and Green Apple

题意: 有 $n$ 个苹果, 每个苹果的重量相同, 将这些苹果平分给 $m$ 个人, 允许将苹果切成两半. 输出需要切几刀. 如果不能在有限次数内平分输出 -1.

题解: 考虑 n / m 的最简形式, 例如 24 / 32 可以约分至 3 / 4, 答案就是 ans * gcd(n, m). 如果整除, 不用切输出 0, 如果 m 不是 2 的幂次则无解 -1.

接下来考虑 3 / 4 怎么分:

4 个人分出 4 份的 1/4 + 4 份的 1/2.
一个苹果需要切 3 刀, 分出 4 份的 1/4.
剩下两个苹果需要各切 1 刀.

推广: 记 $2^t = m$, 如果 $n$ 的第 $i$ 位(从 0 开始记)为 1, 代表需要切 $2^{t - i} - 1$ 刀, 1 个苹果可以切出 $2^{t - i}$ 个. 那么答案

\[\sum\frac{m}{2^{t- i}}(2^{t - i} - 1)=\sum\frac{2^t}{2^{t- i}}(2^{t - i} - 1)=\sum 2^i\cdot (2^{t - i} - 1)=\sum m - 2^i\]

记得开 LL? 反正我卡了好久.

void solve()
{
    int n, m;
    LL ans = 0;
    cin >> n >> m;

    int div = __gcd(n, m);
    n /= div, m /= div;

    if (n % m == 0)
        cout << 0 << '\n';
    else if (__builtin_popcount(m) != 1)
        cout << -1 << '\n';
    else
    {
        int t = __builtin_ffs(m) - 1;
        n %= m;
        // printf("n=%d m=%d t=%d\n", n, m, t);
        for (int i = 0; i < t; i++)
        {
            if (n >> i & 1)
                ans += (m - (1 << i));
        }
        cout << 1ll * div * ans << '\n';
    }
}

D. Jellyfish and Mex

题意: 给定长度为 n 的非负整数数组 a, m 初始化为 0, 然后执行 n 次如下的操作: 删去 a[i], 然后 m += MEX(a). 这里 MEX(a) 表示不属于数组 a 最小的数(minimum excluded). 求 m 最小值.

题解: 我们只关心把 a 中的 0 删去, 因为之后 mex(a) 就一定是 0. 而且 mex(a) 一定是单调不增的.

观察样例我们发现删去一个数, 就一定是一口气解决掉, 不会半途换个数. 至于是先删 0 还是 1, 2... 这里情况就很多了.

结合上面的分析我们可以这么去写 DP

状态表示: f[i]
- 集合: 删去 i 需要的代价
- 属性: 最小值
状态转移:
- 直接删 i / 上一次删除的是 j, j > i
- 后者 f[j] + j * (cnt[i] - 1) + i
- 取最小值

创新程序设计第三周-函数与递归(周三班)

蹭的学校里的算法课. 题单在这.

前面的题目都是语法题. 后面 4 道题有点难度的.

[语言月赛 202212] 打 ACM 最快乐的就是滚榜读队名了(Easy Version)

大模拟. 我真的会谢. 只过了 7, 8 两个测试点, 逆天. 调不动了.

B3712 [语言月赛 202302] 大碗宽面

这道题不需要图论的基础知识. 可以直接拿几个二维矩阵去做.

暴力枚举, 时间复杂度为 $O(n^3)$ 显然会爆.

bool isEnemy[N][N], isFriend[N][N];

void solve()
{
    int n, p, q;
    cin >> n >> p >> q;
    for (int i = 0; i < p; i++)
    {
        int u, v;
        cin >> u >> v;
        isEnemy[u][v] = isEnemy[v][u] = 1;
    }
    for (int i = 0; i < q; i++)
    {
        int u, v;
        cin >> u >> v;
        isFriend[u][v] = isFriend[v][u] = 1;
    }
    LL ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; i < n; i++)
        {
            if (isFriend[i][j])
                ans ++;
            else if (!isEnemy[i][j])
            {
                bool flag = true;
                for (int w = 0; w < n; w++)
                {
                    if ((isFriend[w][j] && isEnemy[w][i]) || (isFriend[w][i] && isEnemy[w][j]))
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans ++;
            }
        }
    }
    cout << ans << '\n';
}

考虑优化. 考虑是敌人对答案 $\frac{n(n-1)}{2}$ (两两都握手) 的影响. 我们把敌人关系存放在一个序偶数组里, 然后去枚举 w, 只要 w 不是俩人的朋友就将答案 -1, 同时标记 (u,v) 已经计算过. 已经计算过的就不必重复运算.

#include <bits/stdc++.h>
using LL = long long;
using namespace std;
typedef pair<int, int> PII;

const int MOD = 998244353, N = 3e4 + 5;
int T = 1;

bool isFriend[N][N], isEnemy[N][N];

void solve()
{
    int n, p, q;
    cin >> n >> p >> q;
    for (int i = 0; i < p; i++)
    {
        int u, v;
        cin >> u >> v;
        isFriend[u][v] = isFriend[v][u] = 1;
    }
    vector<PII> enemy;
    LL ans = 1ll * n * (n - 1) / 2;
    for (int i = 0; i < q; i++)
    {
        int u, v;
        cin >> u >> v;
        isEnemy[u][v] = isEnemy[v][u] = 1;
        ans --;
        enemy.push_back({u, v});
    }
    for (int i = 0; i < q; i++)
    {
        int u = enemy[i].first, v = enemy[i].second;
        for (int w = 0; w < n; w++)
        {
            if (isFriend[u][w] && !isFriend[v][w] && !isEnemy[v][w])
            {
                ans --;
                isEnemy[v][w] = isEnemy[w][v] = 1;
            }
            swap(u, v);
            if (isFriend[u][w] && !isFriend[v][w] && !isEnemy[v][w])
            {
                ans--;
                isEnemy[v][w] = isEnemy[w][v] = 1;
            }
        }
    }
    cout << ans << '\n';
}

B3851 [GESP202306 四级] 图像压缩

怎么又是模拟. 乐.

/**
 *
 * @author: besthope
 * @date: 2023/10/06 21:02:48
 *
 */

#include <bits/stdc++.h>
using LL = long long;
using namespace std;
typedef pair<int, int> PII;

const int N = 256 + 10;
int T = 1;

int gray_scale[N];

void solve()
{
    int n;
    cin >> n;
    vector<string> pic;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        pic.push_back(s);
        for (size_t j = 0; j < s.length(); j += 2)
        {
            string hexString = s.substr(j, 2);
            int val = stoi(hexString, 0, 16);
            gray_scale[val]++;
        }
    }
    vector<PII> t;
    for (int i = 0; i < N; i++)
    {
        if (gray_scale[i] > 0)
            t.push_back({gray_scale[i], i});
    }

    sort(t.begin(), t.end(),
         [](const PII &a, const PII &b)
         {
             if (a.first != b.first)
                 return a.first > b.first;
             return a.second < b.second;
         });

    int cnt = 0;
    vector<PII> compressed;
    for (auto pair : t)
    {
        cnt++;
        compressed.push_back({pair.second, cnt - 1});
        cout << uppercase << hex << setfill('0') << setw(2) << pair.second;
        if (cnt == 16)
            break;
    }

    cout << '\n';

    for (int i = 0; i < n; i++)
    {
        string s = pic[i];
        for (size_t j = 0; j < s.length(); j += 2)
        {
            string hexString = s.substr(j, 2);
            int val = stoi(hexString, 0, 16);
            int diff = 1e9;
            for (auto pair : compressed)
                diff = min(diff, abs(val - pair.first));
            for (auto pair : compressed)
            {
                if (abs(val - pair.first) == diff)
                {
                    val = pair.second;
                    break;
                }
            }
            cout << uppercase << hex << val;
        }
        cout << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

P9587 排名

挺好一道题目. 优化心路一步一步的.

补充一点: 降序排序, 也就是高到低会简单很多.

/**
 *
 * @author: besthope
 * @date: 2023/10/09 23:07:48
 *
 */

#include <bits/stdc++.h>
using LL = long long;
using namespace std;
typedef pair<int, int> PII;

const int MOD = 998244353, N = 5e5 + 5;
int T = 1;

PII a[N];
LL s[N], ans[N];

void solve()
{
    int c, n, k;
    cin >> c >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a[i] = {x, i};
    }
    sort(a + 1, a + 1 + n);
    reverse(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i].first;
    for (int i = 1; i <= n; i++)
    {
        int &idx = a[i].second;
        if (i < k)
            ans[idx] = 1ll * a[i].first * (k - i) - (s[k] - s[i]);
        else if (i >= k)
            ans[idx] = a[k].first - a[i].first;
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)

A. Goals of Victory

题意: $n$ 个队伍比赛, 一个队伍的效率定义为: 自己的比分总和 - 对手的比分总和.

例如 a 和 b 是 1-2, a 和 c 是 1-3, 那么 a 的效率就是 2 - 5 = -3.

给出 $n - 1$ 个队伍的效率, 求剩下一对的效率.

题解: 记 $a_i$ 为某一队的效率, $b_{ij}$ 为某一次对决的得分, 缺失的第 $j$ 组

\[a_j=(b_{j1}+b_{j2} \dots + b_{jn}) - (b_{1j} + b_{2j}+\dots+b_{nj})=-\sum_{i\neq j}^{n} a_i\]

很简单.

B. Helmets in Night Light

题意: 你要通知 $n$ 个人, 直接通知花费 $p$, 间接让被通知的村民去通知别人, 每通知一个人花费 $b_i$, 最多可以通知 $a_i$ 个人, 求通知 $n$ 个人的最小代价.

题解: 对通知的花费排序, 然后一个个减就可以了. 直接通知也可以看成是可以通知 $n - 1$ 个人的村民.

void solve()
{
    int n, p;
    cin >> n >> p;
    vector<PII> c(n);
    for (int i = 0; i < n; i++)
        cin >> c[i].second;
    for (int i = 0; i < n; i++)
        cin >> c[i].first;
    c.push_back({p, n - 1});
    LL ans = p;
    int tot = n - 1;
    sort(c.begin(), c.end());
    for (int i = 0; tot && i < n + 1; i++)
    {
        if (c[i].second >= tot)
        {
            ans += 1ll * c[i].first * tot;
            break;
        }
        else
        {
            ans += 1ll * c[i].first * c[i].second;
            tot -= c[i].second;
        }
    }
    cout << ans << '\n';
}

C. Joyboard

题意: 指派一个长度为 $n+1$ 非负整数数组的最后一个元素 $a_{n+1}$, 并且保证 $0\leqslant a_{n+1} \leqslant m$, 数组其它元素通过 $a_{i} = a_{i+1} \mod i$ 更新, 最后数组要有 $k$ 个不同的数, 求指派的方案数.

题解: 先打个表

void solve()
{
    int n, m, k, a[2];
    cin >> n >> m >> k;
    for (int i = 0; i <= m; i++)
    {
        st.insert(i);
        a[0] = i;
        for (int j = n; j >= 1; j--)
        {
            a[1] = a[0] % j;
            st.insert(a[1]);
            a[0] = a[1];
        }
        if (st.size() == k)
            cout << "a[n + 1] = " << i << ", size is " << st.size() << " k is: " << k << '\n';
        st.clear();
    }
}

然后发现只有当 k = 1, 2, 3 时会有答案. 其它情况必然无解.

当 k = 1 时:
- 整个数组里只能有一个数, 因为在更新过程中必然存在 mod 1 的情况, 所以这个数只能是 0.
当 k = 2 时:
- 只能有 0 和 a[n+1]. 记 t = a[n+1].
- 如果 t > n, 那么 t 必须是 n 的倍数. 否则会多一个.
- 如果 t <= n, 更新过程中一直是 t, 直到最后变为 0.
当 k = 3 时:
- t > n, 然后 t 不能是 n 的倍数.

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    int ans = 0;
    switch (k)
    {
    case 1:
        ans = 1;
        break;
    case 2:
        if (m > n)
            ans = n - 1 + m / n;
        else
            ans = m;
        break;
    case 3:
        if (m > n)
            ans = m - n - (m / n) + 1;
        break;
    default:
        break;
    }
    cout << ans << '\n';
}

D. Effects of Anti Pimples

题意: 给定一个数组, 初始皆为白色, 选择一个以上不同的下标然后涂黑, 然后将所有下标是涂黑元素倍数(至少是两倍)的白方块涂成绿色. 分数是所有涂黑和涂绿方块的最大值. 显然有 $2^n - 1$ 种方案, 答案输出所有答案的总和.

题意: 涂绿和涂黑没区别. 我们现考虑只涂黑, 并考虑每一个元素对答案的贡献. 显然 $a_i$ 对答案的贡献是包含 $a_i$ 且最大值为 $a_i$ 子序列的个数乘上 $a_i$, 对 a 升序排序以后, $a_i$ 对应新的下标 $c$(从 1 开始), 在剩下 $c - 1$ 个元素里选 0, 1, 2,..., c-1 个元素, 一共是 $2^{c-1}$ 个.

然后考虑涂绿, 实际上就是把 $a_i$ 更新成了 $\max\{a_i, a_{2i},\dots, a_{ti}\}$, 这个我们预处理一下就可以了.

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        for (int j = 2 * i; j <= n; j += i)
            a[i] = max(a[i], a[j]);
    sort(a + 1, a + n + 1);
    mint ans = 0, now = 1;
    for (int i = 1; i <= n; i++)
    {
        ans += now * a[i];
        now *= 2;
    }
    cout << ans << '\n';
}

Educational Codeforces Round 156 (Rated for Div. 2)

A. Sum of Three

题意: 问 $n=x+y+z$ 能否找到 $x,y,z$ 都不是 3 的倍数, 且 $x,y,z$ 互不相同.

注: $n \leqslant 10^9$

题解: 暴力就完了. 但也不要愣头青.

void solve()
{
    int n;
    cin >> n;
    for (int x = 1; x <= 10; x++)
    {
        for (int y = x + 1; y <= 10; y++)
        {
            int z = n - x - y;
            if (x % 3 && y % 3 && z % 3 && z > 0 && z != x && z != y)
            {
                cout << "YES\n";
                cout << x << ' ' << y << ' ' << z << '\n';
                return;
            }
        }
    }
    cout << "NO\n";
}

B. Fear of the Dark

题意: 给定点 $P, A, B$, 选择一个 $w$ 为圆 $A, B$ 的半径, 找到坐标原点到 $P$ 的一条路径, 要求路径必须被圆包围. 求最小半径 $w$.

题解: 计算几何题. 分几种情况讨论:

圆 A 包含 O, P: $r = AP$ 即可.
圆 B 同理.
圆 A 包含 O, 圆 B 包含 P: $r = AB / 2$
调换同理.

实现上的细节: std::hypot 可以帮助我们计算 $\sqrt{x^2+y^2}$, 比手写快而且更好用.

struct Point
{
    int x = 0;
    int y = 0;
};

double dist(Point A, Point B) {
    return hypot(A.x - B.x, A.y - B.y);
}

void solve()
{
    Point O, P, A, B;
    cin >> P.x >> P.y >> A.x >> A.y >> B.x >> B.y;
    double ans = min({max(dist(O, A), dist(A, P)),
                      max(dist(O, B), dist(B, P)),
                      max({dist(O, A), dist(A, B) / 2, dist(B, P)}),
                      max({dist(O, B), dist(A, B) / 2, dist(A, P)})});
    cout << fixed << setprecision(10) << ans << '\n';
}

C. Decreasing String

题意: 给定字符串 $s_1$, 现有如下更新规则: 删去字符串 $s_i$ 一个字符, 得到 $s_{i+1}$, 要求此时 $s_i > s_{i+1}$, 也就是字典序变小. 例如 bab 更新为 ab. 求: $S=s_1+s_2+\dots+s_n$, 求 $S[pos]$. 这里 pos 由题目给出.

题解: 如果 pos 很小我们甚至不怎么需要更新字符串, 所以先对 pos 预处理: pos 每次减去 $|s_i|$, 如果有剩余继续减, 反之我们只要求 $s_i[pos']$.

下一个问题是要怎么删: 如果是 abcd 则删去最后一个字符, 我们要找到第一个下降处, 例如 dacb 的 da, 就删去 d. 这个过程可以用单调栈去写, 维护一个严格单调递增的字符串.

void solve()
{
    string s;
    cin >> s;
    int n = s.length();
    LL pos;
    cin >> pos;
    pos --;
    int x, y;
    for (int i = 0; i < n; i++)
    {
        int len = n - i;
        if (pos < len)
        {
            x = i;
            y = pos;
            break;
        }
        pos -= len;
    }
    string stk;
    for (auto ch : s)
    {
        while (x > 0 && !stk.empty() && stk.back() > ch)
        {
            stk.pop_back();
            x--;
        }
        stk += ch;
    }
    cout << stk[y];
}

D. Monocarp and the Set

题意: $1,2,...,n$ 放到一个集合中, 但顺序不定. 给出一个字符串 s, 第 i 个字符按下面的方式解释

>: 表示插入的第 i+1 个元素是集合中的最大值
<: 表示插入的第 i+1 个元素是集合中的最小值
?: 表示插入的第 i+1 个元素不是最大值也不是最小值

求插入元素方案的总数.

题解: 思维. 首先如果 s[0] == ?(第二个插入的元素要么最大要么最小) 那么 ans = 0. 然后我们考虑之后的位置: 插入第 i+1 个元素, 把前 i 个位置的大小关系看成一个排列(其实这个东西叫插入 DP)

s[i] != '?': 只能插最大或最小, 方案数是唯一的.
s[i] == '?': 可以插入除最大最小以外, 中间的任一个位置的值, 有 i-2 种选法.
- 有点类似于插空法?
- 不好理解这里 i-2 的话可以逆向思维:
- 如果 > 表示从集合中删去最大元素, 显然 ? 就是 i-2 个元素里挑一个删掉
s[i] 是插入第 i + 2 个数(s[0]是插入第二个数), 所以 s[i] == '?' 的贡献就是 i.

修改操作, 其实就是撤销一个位置的贡献, 乘上这个位置的乘法逆元就可以了.

void solve()
{
    int n, m;
    cin >> n >> m;
    n--;

    mint ans = 1;
    string s;
    cin >> s;
    for (int i = 1; i <= n - 1; i++)
        if (s[i] == '?')
            ans *= i;
    cout << ((s[0] == '?') ? 0 : ans) << '\n';
    while (m--)
    {
        int x;
        char c;
        cin >> x >> c;
        x--;
        mint p = x;
        if (x && s[x] == '?')
            ans *= p.inv();
        s[x] = c;
        if (x && c == '?')
            ans *= x;
        cout << ((s[0] == '?') ? 0 : ans) << '\n';
    }
}

Codeforces Round 903 (Div. 3)

A. Don't Try to Count

题意: 给定一个长度为 $n$ 的字符串 $x$, 以及长度为 $m$ 的字符串 $s$, 你可以将 $x$ 复制任意倍数, 例如 aba -> abaaba, 问最小操作数, 使得 $s$ 成为 $x$ 的一个字串. 答案不存在, 则输出 -1.

数据范围: $nm\leqslant 25$

暴力就完了.

void solve()
{
    int n, m;
    cin >> n >> m;
    int ans = -1;
    string x, s;
    cin >> x >> s;
    for (int i = 0; i <= 5; i++)
    {
        if (x.find(s) != x.npos)
        {
            ans = i;
            break;
        }
        x += x;
    }
    cout << ans << '\n';
}

B. Three Threadlets

题意: 给定三个数, 可以将一个数分解为两个数之和, 例如 5 = 3 + 2, 问能不能在至多三次操作内, 使得分解的数都相等.

void solve()
{
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    int p = min({a[0], a[1], a[2]});
    int ans = 0;
    bool ok = true;
    for (int i = 0; i < 3; i++)
    {
        ans += a[i] / p - 1;
        if (a[i] % p || ans > 3)
            ok = false;
    }
    cout << (ok ? "YES\n" : "NO\n");
}

C. Perfect Square

牛客小白月赛 79

A B 签到题就略过了. 剩下的题目补补题解.

C. mex 和 gcd 的乘积

题意: 给定长度为 $n$ 的数列, 求这个数列中连续区间的 mex 和 gcd 的最大值是多少.

注: 约定 $\gcd(0, x) = x$

题解: 一开始以为这是道线段树维护区间最值的数据结构问题, 最后发现是道思维题.

首先关注几个点:

答案区间必须包含 0, 否则 mex = 0 答案最小.
mex 单调不减, gcd 单调不增

于是发现

mex >= 2, 那么区间必须包含 0, 1, 导致 gcd = 1, 此时 ans = mex
- 让 mex 最大, 则让连续区间 = 整个数组即可
mex = 1, 此时要让 gcd 最大, 那么区间除了 0 只能包含 0 相邻的数.
- 对这两个数取一个 max 就完了.

注意: 要对数组全是 0 的例子特判.

void solve()
{
    int n;
    cin >> n;
    int ma = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        ma = max(ma, a[i]);
        st[a[i]] ++;
    }
    int ans = 0;
    while (st[ans])
        ans ++;
    for (int i = 1; i <= n; i++)
    {
        if (!a[i])
            ans = max({ans, a[i - 1], a[i + 1]});
    }
    if (!ma)
        ans = 0;
    cout << ans << '\n';
}

D. 2^20

题意: 给定一个数, 可以 +1, 可以乘上 2, 问最小操作数, 使其成为 $2^{20}$ 的倍数

题解: $2^{20}$ 的倍数, 也就是 $n \cdot 2^{20}$, 对于 $n < 2^{20}$, 显然经过 20 步操作它一定能成为 $2^{20}$ 的倍数. 对于 $2\geqslant {20}$ 的数, 显然可以拆成 $n=p\cdot 2^{20}+n'$, 预处理模一下就可以了. 所以操作数一定不会大于 20, 且一定有解.

下一步是考虑 1 << 20 - 1 这类例子, 显然 +1 要比乘 20 次 2 更优. 那么我们可以枚举 +1 的次数, 然后算一个 min 就行了.

void solve()
{
    int n;
    cin >> n;
    n %= M;
    int ans = 20;
    if (n == 0)
    {
        cout << 0 << '\n';
        return;
    }
    for (int i = 0; i <= 20; i++, n++)
    {
        int p = __builtin_ctz(n);
        ans = min(ans, 20 - p + i);
    }
    cout << ans << '\n';
}

E. 重生之我是 QQ 邮箱

题意: 密码的最后 7 位是指定的一个序列, 前面的位置则无指定, 密码长度为 $n$, 可用字符有 6 个, 每次输入一个位置需要花费 1s, 记破解这个密码的期望时间为 $t$, 已知能将密码的破解时间翻倍 $m$ 次($0\leqslant m$), 求最终破解时间的个位是多少.

题解: 首先 $n\geqslant 7$ 才有解, 否则 -1.

这个期望很容易计算: 输对密码的概率是 $\frac{1}{6^7}$, 那么期望的次数是 $6^7$ 次(这是个几何分布)

所以答案要求的就是 $(6^7\cdot n)^{2^m} (\bmod 10)$.

解法一: 打表找规律

简单写个 python 小程序找找规律.

n = 7
2 4 6 6 6 6 6 6 6 6
n = 8
8 4 6 6 6 6 6 6 6 6
n = 9
4 6 6 6 6 6 6 6 6 6
n = 10
0 0 0 0 0 0 0 0 0 0
n = 11
6 6 6 6 6 6 6 6 6 6
n = 12
2 4 6 6 6 6 6 6 6 6

然后分类讨论就完了.

void solve()
{
    int n, m;
    cin >> n >> m;
    if (n < 7)
    {
        cout << -1 << '\n';
        return;
    }
    int ans = 0;
    switch (n % 5)
    {
    case 1:
        ans = 6;
        break;
    case 2:
        switch (m)
        {
        case 0:
            ans = 2;
            break;
        case 1:
            ans = 4;
            break;
        default:
            ans = 6;
            break;
        }
        break;
    case 3:
        switch (m)
        {
        case 0:
            ans = 8;
            break;
        case 1:
            ans = 4;
            break;
        default:
            ans = 6;
            break;
        }
        break;
    case 4:
        if (m >= 1)
            ans = 6;
        else
            ans = 4;
        break;
    default:
        break;
    }
    cout << ans << '\n';
}

方法二: 欧拉公式降次

\[a^b\equiv\begin{cases}a^{b\bmod\varphi(m)},&\gcd(a,m)=1,\\a^b,&\gcd(a,m)\neq1,b<\varphi(m),&\text{(mod}~m)\\a^{(b\bmod\varphi(m))+\varphi(m)},&\gcd(a,m)\neq1,b\geq\varphi(m).\end{cases}\]

$(6^7\cdot n)^{2^m} (\bmod 10)$ 显然 $6^7$ 和 $10$ 不互质, $\varphi(10)=4$, $m=0,1,2\dots$, 我们要判断下用第二行还是第三行

当 $m \leqslant 1$ 时, 用第二行, 也就是不用降次直接算
剩下的情况, 降次为 $2^m \bmod 4 + 4$.

$6^7\equiv 6\bmod 10$, 上述问题也等价于

\[(6^7\cdot n)^{2^m}\equiv (6n)^{2^m} \bmod 10\]

底数要保证在模 10 的意义内, 我也不知道为什么.

void solve()
{
    int n, m;
    cin >> n >> m;
    LL ans = -1;
    if (n >= 7)
    {
        int p = (1 << m) % 4;
        if (m >= 2)
            p += 4;
        ans = qpow(n % 10 * 6 % 10, p, 10);
    }
    cout << ans << '\n';
}

F. 是牛牛还是狗勾

鸽笼原理, 0/1 背包

G. 魔法树

树形 DP. 连通块

Codeforces Round 904 (Div. 2)

A. Simple Design

题意: 如果一个数的各位之和可以整除 $k$, 称其为 $k$-beautiful. 找到 $y\leqslant x$ 满足 $y$ 是 $k$-beautiful 的最小值.

题解: 暴力即可.

void solve()
{
    int x, k;
    cin >> x >> k;
    for (int i = x; ; i++)
    {
        int y = i;
        int sum = 0;
        while (y)
        {
            sum += y % 10;
            y /= 10;
        }
        if (sum % k == 0)
        {
            cout << i << '\n';
            break;
        }
    }
}

1
2
3

int f(int x) {
    return x ? f(x / 10) + x % 10 : 0;
}

B. Haunted House

题意: 给定一个长度为 $n$ 的二进制串, 可以交换串中相邻的字符, 问交换的最小次数, 使得这个二进制串表示的数整除 $2^i$, $1\leqslant i \leqslant n$, 也就是说交换几次可以整除 $2$, 交换几次可以整除 $2^2$, 以此类推. 无解的情况输出 -1.

题解: 整除 $2^i$ 就表示尾端有 $i$ 个 0. 从 $i=1$ 开始, 我们维护 $n-i$ 这个位置是 0, 这样 i 增大以后, 尾端都是 1. 每次维护对答案的贡献是最近的 0 离 $n-i$ 的距离.

void solve()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    LL ans = 0;
    int l = n;
    for (int i = 1; i <= n; i++)
    {
        if (ans != -1)
        {
            if (l > n - i && s[n - i] == '0')
                l --;
            else
            {
                // swap 1 with 0, find 0 on the left
                while (l > 0 && s[l - 1] != '0')
                    l --;
                // no solution
                if (l == 0)
                    ans = -1;
                else
                    ans += n - i + 1 - l;
                l --;
            }
        }
        cout << ans << " \n"[i == n];
    }
}

C. Medium Design

题意: 一个初始大小 m 的数组 a, 初始化全为 0, 给出 n 组子区间 $[l_i, r_i]$, 你可以选择将子区间上的每一个元素自增 1. 最后, 计算 $\max (a) - \min(a)$ 的最大值.

题解: 如果所有的子区间无法覆盖 $[1,m]$ 的某一点, 最小值为 0, 那么选中所有子区间最优. 问题是: 如果全覆盖怎么办.

我们设 $x$ 是最大值出现的位置, 显然我们选中了所有的包含 $x$ 的子区间, $l_i \leqslant x \leqslant r_i$, 这是因为:

如果它同时包含了最小值, 那么加上这个区间对答案无影响.
如果它不包含最小值, 加上这个区间对答案贡献 1.

为了让答案最大, 最小值应在两端取到, 以此让最大值和最小值之间重叠的区间尽可能小.

所以我们可以枚举所有包含 1 的子区间, 将这些线段移除, 使得最小值为 0, 剩下的区间全选, 得出最优答案. 然后对称地对包含 $m$ 的区间操作, 过程中取 max 即可.

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> l(n), r(n);
    vector<PII> f;
    for (int i = 0; i < n; i++)
    {
        cin >> l[i] >> r[i];
        l[i] --;
        if (l[i] != 0)
        {
            f.emplace_back(l[i], 1);
            f.emplace_back(r[i], -1);
        }
    }
    int ans = 0;
    int cur = 0, lst = 0;
    sort(f.begin(), f.end());
    for (auto [x, y] : f)
    {
        if (x > lst)
            ans = max(ans, cur);
        cur += y;
        lst = x;
    }
    if (m > lst)
        ans = max(ans, cur);
    f.clear();
    for (int i = 0; i < n; i++)
    {
        if (r[i] != m)
        {
            f.emplace_back(l[i], 1);
            f.emplace_back(r[i], -1);
        }
    }
    cur = 0, lst = 0;
    sort(f.begin(), f.end());
    for (auto [x, y] : f)
    {
        if (x > lst)
            ans = max(ans, cur);
        cur += y;
        lst = x;
    }
    if (m > lst)
        ans = max(ans, cur);
    cout << ans << '\n';
}

子问题的处理其实也挺难度的.

D. Counting Rhyme

题意: 给定整数序列 $a_1, a_2, \dots, a_n$, 我们称 $(i,j)$ good 如果不存在 $1\leqslant k\leqslant n$ 使得 $a_i$ 和 $a_j$ 都不能同时整除 $a_k$. 其中 $1\leqslant i < j \leqslant n$. 找出 good pair 的数量.

DP, 组合问题

Codeforces Round 905 (Div. 3)

A. Morning

void solve()
{
    string s;
    cin >> s;
    LL ans = 0;
    char cur = '1';
    for (int i = 0; i < 4; i++)
    {
        if (s[i] == '0')
            s[i] += 10;
        ans += abs(s[i] - cur) + 1;
        cur = s[i];
    }
    cout << ans << '\n';
}

B. Chemistry

void solve()
{
    unordered_map<char, int> mp;
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    bool ok = true;

    for (int i = 0; i < n; i++)
        mp[s[i]] ++;
    for (auto [ch, cnt] : mp)
    {
        if (cnt & 1)
            k --;
    }
    if (k < -1)
        ok = false;
    cout << (ok ? "YES\n" : "NO\n");
}

C.

Codeforces Round 906 Div. 2

A. Doremy's Paint 3

题意: 如果一个数组满足 $b_1+b_2=b_2+b_3=\dots=b_{n-1}+b_n=k$, 那么称这个数组是好的. 现在给定一个数组 $a$, 问经恰当排序后这个数组是否可以称为好的.

题解: 挺不错的一道思维题. 显然我们可以发现 $b_1=b_3=\dots$, $b_2=b_4=\dots$, 也就是说, 一个好数组至多只能包含两个数, 并且还发现它们的个数相差不超过 1.

void solve()
{
    int n;
    cin >> n;

    map<int, int> mp;
    bool ok = false;

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        mp[x] ++;
    }

    if (mp.size() == 1 ||
        (mp.size() == 2 && abs(mp.begin()->second - mp.rbegin()->second) <= 1))
        ok = true;

    cout << (ok ? "Yes\n" : "No\n");
}

B. Qingshan Loves Strings

题意: 一个二进制串称其 good 当且仅当相邻字符都不相同. 现在有两个二进制串 s 和 t, 可以将 t 插入到 s 的一个位置上, 判断能否使得 s good.

题解: 分类讨论

t 要保证合法
t = 1...0, 无解

有三种合法情况:

s 本身就是好的
t = 1...1, 那么 s 里就不能存在 11 的序列
t = 0...0, 那么 s 就不能存在 00 的序列

代码还是要写一会儿的.

bool ok(string s)
{
    for (size_t i = 1; i < s.size(); i++)
    {
        if (s[i] == s[i - 1])
            return false;
    }
    return true;
}

void solve()
{
    int n, m;
    cin >> n >> m;

    string s, t;
    cin >> s >> t;

    if (ok(s))
    {
        cout << "Yes\n";
        return;
    }
    if (!ok(t) || t[0] != t[m - 1])
    {
        cout << "No\n";
        return;
    }

    bool has_00 = false, has_11 = false;
    for (int i = 1; i < n; i++)
    {
        if (s[i] == '0' && s[i - 1] == '0')
            has_00 = true;
        if (s[i] == '1' && s[i - 1] == '1')
            has_11 = true;
    }
    if ((has_00 && t[0] == '0') || (has_11 && t[0] == '1'))
        cout << "No\n";
    else
        cout << "Yes\n";
}

C. Qingshan Loves Strings 2

题意: 字串 good 的定义更改为 $a_{i}\neq a_{k-i+1}, \forall i=1,2,\dots,k$, $k$ 为字符串的长度, 也即和对称位置不同.

可行的操作是: 将 01 插入 s 的某一位置

输出 s good 的操作序列

题目限定, 若有解, 操作 300 以下必可使得 s good

题解: 如果 0 和 1 的数量不等, 则必然无解(所以 n 为奇数必无解). 考虑有解的情况, 关注头尾

如果 front = end:
- front = 1, 在 front 前添加 01
- front = 0, 在 end 后添加 01
如果 front != end, 掐头去尾后就是一个 s'
- 然后迭代就可以了.

void solve()
{
    int n;
    cin >> n;

    string s;
    cin >> s;
    s += ' ';

    int cnt1 = 0, cnt0 = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '0')
            cnt0++;
        else
            cnt1++;
    }
    if (cnt1 != cnt0)
    {
        cout << -1 << "\n";
        return;
    }
    else
    {
        vector<int> seq;
        int l = 0, r = n - 1;
        while (l < r)
        {
            if (s[l] == s[r])
            {
                if (s[l] == '0')
                {
                    s.insert(r + 1, "01");
                    seq.push_back(r + 1);
                    r += 2;
                }
                else
                {
                    s.insert(l, "01");
                    seq.push_back(l);
                    r += 2;
                }
            }
            l++;
            r--;
            // cout << s << '\n';
        }
        int c = seq.size();
        cout << c << '\n';
        for (int i = 0; i < c; i++)
            cout << seq[i] << " \n"[i == c - 1];
    }
}

D. Doremy's Connecting Plan

题意: 连通一个无向图, 建一条 $i$ 到 $j$ 的边需要满足

\[\sum_{k\in S} a_k \geqslant ij\cdot c\]

也就是已经连通的块的总价值要大于 $ijc$. 已经连通的这个块包含 $i$ 或者 $j$.

判断能否将这个图连通.

题解: 先猜结论, 每个结点和 1 建边最优. 反之考虑 $i, j$ 建边比建两次边更优, 也即 $i,j$ 能相连而 $i,1$ 或者 $j,1$ 不能相连, 显然这不成立. 我们记 $s$ 为已经连通的块的总价值, 那么每次要判断

\[s + a_i \geqslant c\cdot i\]

我们对每个结点按价值减去 c * i 排序, 从高到低, 判断能否选择就可以了.

void solve()
{
    int n, c;
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        LL x;
        cin >> x;
        a[i] = {x, i};
    }
    LL sum = a[1].first;
    sort(a + 2, a + n + 1, [&] (const PII &u, const PII &v)
    {
        return u.first - c * u.second > v.first - c * v.second;
    });
    for (int i = 2; i <= n; i++)
    {
        sum += a[i].first;
        if (sum < a[i].second * c)
        {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

E. Doremy's Drying Plan

DP 不做

Codeforces Round 907 (Div. 2)

A. Sorting with Twos

题意: 给定序列 $a_1, a_2, \dots, a_n$, 可以进行下面的操作:

选定一个 $m$ 满足 $2^m\leqslant n$
将所有 $i \leqslant 2^m$ 的元素 -1.

问能否将这个数组修改为一个单调不减序列.

题解: 维护一个单调不减的数组, 从下标 1 开始维护, 我们要把 $[1,2^m]$ 的最右端的元素修改为 $a_{2^m+1}$ 的值, 前提是 $[2^{m}+1, 2^{m+1}]$ 这段区间是单调不减的, 否则无解. 只用判断 [3,4], [5,8], ... 的单调性即可.

例如 4 3 2 1 这个样例, 我们可以这么维护 3 3 2 1 -> 2 2 2 1, 但发现 [3,4] 这段区间单调递减, 所以无解.

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int m = 0; (1 << m) < n; m++)
    {
        int l = (1 << m) + 1;
        int r = min(n, 1 << (m + 1));
        if (!is_sorted(a + l, a + r + 1))
        {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

B. Deja Vu

题意: 给定数组 a 和 q 个询问 $x_i$, 每次询问对 a 中能够整除 $2^{x_i}$ 的元素加上 $2^{x_i-1}$, 输出 q 次询问后的数组 a.

题解: 首先 q 组询问可以压缩到 $1\sim 30$ 个数. 假设整除, 对于重复的数字也只能修改一次. 并且修改后会使得之后比 $x_i$ 大的询问都无效(见最后一组样例).

对于 $a_i$, 找到最大可整除的 $x$, 然后一直修改到最小的 $x$ 即可. 时间复杂度 $O(30n)$

void solve()
{
    int n, q;
    cin >> n >> q;
    set<int> mp;
    vector<int> a(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < q; i++)
    {
        int x;
        cin >> x;
        if (!mp.empty() && x >= *mp.begin())
            continue;
        mp.insert(x);
    }
    for (int i = 0; i < n; i++)
    {
        int p = __builtin_ctz(a[i]);
        for (auto it = mp.begin(); it != upper_bound(mp.begin(), mp.end(), p); it++)
            a[i] += (1 << (*it - 1));
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << " \n"[i == n - 1];
}

C. Smilo and Monsters

题意: 打怪, $n$ 个格子, 每个格子有 $a_i$ 只怪, 你可以一次只砍一个, 充一点充能, 或者把所有充能点数消耗了砍对应点数个数的怪. 问最小操作数.

题解: 贪心 + 模拟攒能量然后把含怪最大的格子扬了, 直到只剩一个格子, 剩一半开大.

比较考验代码实现的一道题目.

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    LL x = 0, ans = 0;
    int l = 0, r = n - 1;
    while (l < r)
    {
        if (x + a[l] < a[r])
        {
            ans += a[l];
            x += a[l];
            a[l ++] = 0;
        }
        else
        {
            a[l] -= a[r] - x;
            ans += a[r] - x + 1;
            x = 0;
            a[r --] = 0;
            // x + a[l] == a[r]
            if (!a[l])
                l ++;
        }
    }
    if (l == r && a[l])
    {
        int tot = a[l] + x;
        if (a[l] == 1)
            ans ++;
        else
        {
            if (tot & 1)
                ans += tot / 2 - x + 2;
            else
                ans += tot / 2 - x + 1;
        }
    }
    cout << ans << '\n';
}

D. Suspicious logarithms

题意: 定义 $f(x)=[\log_{2}x]$, 例如 $f(5)=2$. 又定义 $g(x)=[\log_{f(x)}x]$, 以 $f(x)$ 为底数, $x$ 为真数. 给出 $n$ 组查询 $l_i, r_i$, 求 $\sum_{k=l}^{r}g(k)$.

数据范围 $4 \leqslant l, r \leqslant 10^{18}$.

题解: 看代码, 有注释

#include <bits/stdc++.h>
using LL = long long;
using DLL = __int128_t;
using namespace std;

const int MOD = 1e9 + 7, N = 1e5 + 5;
int T = 1;

template <const int T>
struct ModInt
{
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {}
    int val() { return x; }
    ModInt operator+(const ModInt &a) const
    {
        int x0 = x + a.x;
        return ModInt(x0 < mod ? x0 : x0 - mod);
    }
    ModInt operator-(const ModInt &a) const
    {
        int x0 = x - a.x;
        return ModInt(x0 < 0 ? x0 + mod : x0);
    }
    ModInt operator*(const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator/(const ModInt &a) const { return *this * a.inv(); }
    bool operator==(const ModInt &a) const { return x == a.x; };
    bool operator!=(const ModInt &a) const { return x != a.x; };
    void operator+=(const ModInt &a)
    {
        x += a.x;
        if (x >= mod)
            x -= mod;
    }
    void operator-=(const ModInt &a)
    {
        x -= a.x;
        if (x < 0)
            x += mod;
    }
    void operator*=(const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator/=(const ModInt &a) { *this = *this / a; }
    friend ModInt operator+(int y, const ModInt &a)
    {
        int x0 = y + a.x;
        return ModInt(x0 < mod ? x0 : x0 - mod);
    }
    friend ModInt operator-(int y, const ModInt &a)
    {
        int x0 = y - a.x;
        return ModInt(x0 < 0 ? x0 + mod : x0);
    }
    friend ModInt operator*(int y, const ModInt &a) { return ModInt(1LL * y * a.x % mod); }
    friend ModInt operator/(int y, const ModInt &a) { return ModInt(y) / a; }
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x; }
    friend istream &operator>>(istream &is, ModInt &t) { return is >> t.x; }

    ModInt pow(int64_t n) const
    {
        ModInt res(1), mul(x);
        while (n)
        {
            if (n & 1)
                res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }

    ModInt inv() const
    {
        int a = x, b = mod, u = 1, v = 0;
        while (b)
        {
            int t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        if (u < 0)
            u += mod;
        return u;
    }
};
using mint = ModInt<MOD>;

// ans[base][x]: sum of log(k, base) from 1 to x
map<LL, mint> ans[70];
int base;

// Example:
// base = 3
// x = 40
// 1~2 3~8 9~26 27~40
// 0   1   2    3

mint get(LL x)
{
    if (ans[base].contains(x))
        return ans[base][x];
    mint sum = 0;
    LL pow = 1;
    for (int i = 1; i <= 60; i++)
    {
        if (DLL(pow) * base > x)
            break;
        pow *= base;

        LL l = pow, r = min(DLL(pow) * base - 1, DLL(x));
        sum += i * mint(r - l + 1);
    }
    return ans[base][x] = sum;
}

mint calc(LL x)
{
    mint sum = 0;
    for (int i = 2; i <= 60; i++)
    {
        // 2^i and 2^{i+1} - 1
        LL l = (1LL << i), r = (1LL << (i + 1)) - 1;
        if (l > x)
            break;
        // x > l:
        // i = [log(x, 2)] = f(x)
        r = min(r, x);
        base = i;
        sum += get(r);
        sum -= get(l - 1);
    }
    // Example:
    // x = 15
    // i = 2
    // sum = g(4) + ... + g(7)
    // i = 3
    // sum = g(4)+ ... + g(8) + ... + g(15)
    return sum;
}

void solve()
{
    LL l, r;
    cin >> l >> r;
    // g(l) + ... + g(r)
    cout << calc(r) - calc(l - 1) << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

Educational Codeforces Round 157 (Rated for Div. 2)

A. Treasure Chest

void solve()
{
    int x, y, k;
    cin >> x >> y >> k;
    int ans = 0;
    if (y <= x)
        ans = x;
    else
    {
        ans = y;
        if (x + k < y)
            ans += y - (x + k);
    }
    cout << ans << '\n';
}

B. Points and Minimum Distance

struct Point
{
    int x, y;
} p[N];

int a[N * 2];

int dist(Point a, Point b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < 2 * n; i++)
        cin >> a[i];
    sort(a, a + 2 * n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        p[i].x = a[i], p[i].y = a[2 * n - 1 - i];

    for (int i = 1; i < n; i++)
        ans += dist(p[i], p[i - 1]);
    cout << ans << '\n';

    for (int i = 0; i < n; i++)
        cout << p[i].x << ' ' << p[i].y << '\n';
}

C. Torn Lucky Ticket

HHKB Programming Contest 2023(AtCoder Beginner Contest 327)

A and B SKIP

C. Number Place

这里提供一种优雅的枚举方法(from jiangly)

void solve()
{
    array<array<int, 9>, 27> vis{};
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            int x;
            cin >> x;
            x --;
            for (auto a : {i, 9 + j, 18 + i / 3 * 3 + j / 3})
            {
                if (vis[a][x])
                {
                    cout << "No\n";
                    return;
                }
                vis[a][x] = 1;
            }
        }
    }
    cout << "Yes\n";
}

D. Good Tuple Problem

可以转换成判定二分图的板子题

可以 DFS 去找有无奇数边, 或者采用一种并查集的方法求解

E. Maximize Rating

固定 k, 讨论分子的最大化问题

状态表示: dp[i][j]
- 前 i 场选出 j 场
- 属性: 最大值
状态转移:
- 从 dp[i-1][j'] 转移到 dp[i][j]:
  - 不选第 i 场: 和 dp[i-1][j] 一样
  - 选第 i 场: 0.9 * dp[i-1][j-1] + p[i]
- 可以反向枚举 j, 滚动压缩到一维.

void solve()
{
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    vector<double> dp(n + 1);
    double ans = -1200;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j >= 0; j--)
            dp[j + 1] = max(dp[j + 1], dp[j] * 0.9 + p[i]);
    }
    double den = 0;
    for (int i = 1; i <= n; i++)
    {
        den = den * 0.9 + 1;
        ans = max(ans, dp[i] / den - 1200 / sqrt(i));
    }
    cout << fixed << setprecision(10) << ans << '\n';
}

创新程序学设计-搜索入门（周 3 班，第八周）

我要成为搜索高手!

A. Calling Extraterrestrial Intelligence Again

HDU 1239

题意: 给定 $4 < m \leqslant 100000$, $ 1 a $, 找到一组素数对 $p,q$, 满足 $pq\leqslant m$ 及 $\frac{a}{b} \leqslant \frac{p}{q} \leqslant 1$, 找到 pq 的最大值.

题解: 先打素数表, 然后暴力枚举素数对 $(p,q), q\geqslant p$, 如果 $pq > m$ 或 $pb<aq$ 就枚举下一个数对.

显然答案会出现在 $p, q$ 尽可能接近的位置(考虑 100000 1 1000 的例子), 素数范围最大不超过 $\sqrt{m}$, 素数分布 $\ln m$, 两层枚举时间复杂度 $O((\ln m)^2)$.

B. Tempter of the Bone

题意: 走迷宫, 不允许走回头路, 问是否存在一种方案, 使得到达终点的步数恰好为 $T$.

题解: 一种想法, 搜索所有可行方案, 然后找是否有一个方案步数为 $T$.

注意, 这里 $T$ 未必是最小步数, 所以对于 BFS 来说, 它可以从步数小的方案开始枚举, 但一旦枚举到可行方案就结束, 这也是为什么它能够枚举出最小值.

直接 DFS 会 T. 考虑一种可行性剪枝. 假设当前节点到 D 有通路, 那么剩余步长的奇偶性和到 D 的曼哈顿距离是一样的. 这种剪枝技巧叫做奇偶剪枝.

C. Asteroids!

题意: 三维走迷宫, BFS

题解: 板子题

D. Oil Deposits

题意: 上下左右以及对角线相邻的 @ 作为一个连通块. 求一个图里连通块的个数.

例如下面的样例就是只有 1 个连通块.

1
2
3

*@*@*
**@**
*@*@*

题解: 定义状态 dfs(x, y, id) 表示 (x,y) 这个点属于第 id 个连通块. DFS 将所有相连且未访问过的 @ 标记为相同的 id.

对全体未访问过的 @ 进行 DFS, 每次 id 自增 1. 答案就是最后的 id.

E. Substrings

题意: 给定 $n$ 个字符串 $s_i$ ($1\leqslant n \leqslant 100, 1\leqslant i \leqslant n, 1 \leqslant |s_i| \leqslant 100$), 找到一个字符串 $x$, 使得对于第 $i$ 个字符串 $s_i$, $x$ 或 $x$ 的翻转是 $s_i$ 的字串.

题解: 暴力搜索, 从长度最小的字符串的最大字串开始枚举, 判断字串以及它的翻转是否是全体字符串的字串.

void solve()
{
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++)
        cin >> s[i];
    sort(s.begin(), s.end());

    string a = s[0];
    int len = a.size();

    for (int i = len; i > 0; i--)
    {
        int start = len - i;
        for (int j = 0; j <= start; j++)
        {
            string sub = a.substr(j, i);
            string inv = string(sub.rbegin(), sub.rend());
            // cout << sub << ' ' << inv << '\n';
            for (int k = 0; k < n; k++)
            {
                if (s[k].find(sub) == s[k].npos && s[k].find(inv) == s[k].npos)
                    break;
                if (k == n - 1)
                {
                    cout << i << '\n';
                    return;
                }
            }
        }
    }
    cout << 0 << '\n';
}

F. Anagrams by Stack

题意: 模拟栈, i 表示进栈 o 表示出栈, 给定两个同形词(所包含的字母个数相等, 例如 foo 和 oof), 输出全部可行方案(一个栈操作的序列), 使得同形词 a 变为 b.

题解: 模拟整个出栈入栈的过程即可.

void dfs(int in, int out)
{
    if (in == out && ans == m)
    {
        for (auto op : seq)
            cout << op << ' ';
        cout << '\n';
        return;
    }
    if (in != n.size())
    {
        in ++;
        t += n[in - 1];
        seq.push_back('i');
        dfs(in, out);
        in --;
        seq.pop_back();
        t.pop_back();
    }
    if (!t.empty())
    {
        char ch = t.back();
        if (ch == m[out])
        {
            t.pop_back();
            ans += ch;
            seq.push_back('o');
            dfs(in, out + 1);
            t += ch;
            seq.pop_back();
            ans.pop_back();
        }
    }
}

G. Safecracker

题意: 求满足下列方程的解

\[v - w^2 + x^3 - y^4 + z^5 = target\]

target 是给定的一个数. 每个数会偏移一个 A, 答案就是 vwxyz 偏移后得到的一个字符序列, 如果有多组解, 输出字典序最大的一组解.

约定各个数偏移后在一个确定的字母集中. 这个字母集输入给出.

题解: 排列 vwxyz, 找到一组解即可.

H. Prime Ring Problem

题意: 1~n 排列形成一个环, 相邻两个数的和为素数, 输出这个环上的序列. 约定第一个位置永远为 1.

题解: 排列 1~n, 每次判断当前添加的数和答案序列中的上一个数之和是否为素数, 如果答案序列的长度为 n-1 了, 那么还要判断和 1 的和是否为素数.

I. A strange lift

题意: 从楼层 A 到 B, 每层楼可以上升或下降, 高度由一个整数序列给出, 问 A->B 的最少移动次数.

题解: 最小值问题, 考虑 BFS.

J. Solitaire

题意: 8*8 的一个棋盘, 给出 4 个棋子的初始位置和终止位置, 问: 能否在 8 步之内, 使这四个棋子从初始位置到达终止位置.

每一步移动满足下面的规则:

如果相邻格子无棋子, 可以移动到这个格子. (上下左右)
如果相邻格子有棋子, 则可以跳过一个格子, 移动到棋子对岸. 换句话说, 向有棋子的方向移动两格. (上下左右)

题解: 双向 BFS

八数码问题

正常求解可以用 BFS, 优化算法有双向 BFS 和 IDFS.

棋盘表示: 3*3 的矩阵压缩成一个字符串
状态转移: 移动空格上下左右可行性, 以及是否访问过

K. Sequence one

L. Sequence two

M. Red and Black

板子题

N. Eleven puzzle

O. DNA sequence

2023 年“奇点杯”第一届程序设计竞赛（校内赛）

总结下这次比赛:

基础太烂
- 签到题读入单行字符串忘了 getline(cin, s)
- B 题就一板子 DFS/BFS, 但是赛时想复杂了
不开 LL, 喜欢吃我罚时吗? 吃了 2 发
字符串得练
数学太烂了, 两道概率题推不动, 计算几何忘了乘法逆元

总之就是我太菜了. 哎, 补题吧.

K 小嗷犬与目标检测

题意: 给定两个矩形, 计算它们的 IoU

题解: 推出覆盖部分的面积, 然后就结束了

void solve()
{
    for (int i = 0; i < 4; i++)
    {
        LL x, y;
        cin >> x >> y;
        p[i] = {x, y};
    }
    mint tot = (p[1].x - p[0].x) * (p[1].y - p[0].y) + (p[3].x - p[2].x) * (p[3].y - p[2].y);
    LL l = min(p[1].x, p[3].x) - max(p[0].x, p[2].x);
    LL d = min(p[1].y, p[3].y) - max(p[0].y, p[2].y);
    mint overlap = max(0ll, l) * max(0ll, d);
    mint ans = overlap * (tot - overlap).inv();
    cout << ans << '\n';
}

E kokoro 与字符串

题意: 给定一个长度 $n$ 的字符串 $s$, 求删去 $k$ 个字符后, 剩下的字符字典序最大. 输出这个字符串.

题解: 按题模拟即可.

另外贪心算法我不会.

void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int r = 0;
    for (int i = 0; i < n; i++)
    {
        while (r > 0 && ans[r - 1] < s[i] && n - i + r > n - k)
            r --;
        ans[r] = s[i];
        r ++;
    }
    for (int i = 0; i < n - k; i++)
        cout << ans[i];
    cout << '\n';
}

创新程序学设计-动态规划（周 3 班，第 12 周）

最爱的 DP 专题

A. Bone Collector

HDU 2602

题解: 0/1 背包的模板题

状态表示 f[i][j] 前 i 件物品选取体积不大于 j 的最大价值

怎么转移: 从 i-1 件开始:

选: f[i-1][j-v[i]]+w[i]
不选: f[i-1][j]

滚动数组优化: 因为转移只和上一层有关, DP 数组可以开到一维.

枚举 j 时需要倒序遍历: 保证每次更新状态的时候, 用的是上一轮的结果, 否则会把第 i 件物品重复放入背包(完全背包问题)

时间复杂度 $O(NM)$

void solve()
{
    memset(f, 0, sizeof f);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    for (int i = 0; i < n; i++)
        cin >> v[i];

    for (int i = 0; i < n; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + c[i]);

    cout << f[m] << '\n';
}

C. Common Subsequence

HDU 1159

题解: LCS, 求最长公共子序列板子题

我们假设两个字符串分别为 a, b, 定义状态: f[i][j] 为 a 前 i 个字符和 b 前 j 个字符构成的 LCS 长度

状态转移: 考虑 f[i][j] 的上一个状态, 显然若 LCS 要变长, 必须是两个子串的最后一个字符相同 a[i-1] == b[j-1], 那么 f[i-1][j-1] + 1, 否则让 a 子串变长或 b 变长, 也就是 f[i][j-1] 或 f[i-1][j].

while (cin >> a >> b)
{
    memset(f, 0, sizeof f);
    int n = a.size(), m = b.size();

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i - 1] == b[j - 1])
                f[j] = f[i - 1][j - 1] + 1;
            else
                f[j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }
    cout << f[n][m] << '\n';
}

滚动数组优化:

void solve()
{
    string a, b;
    while (cin >> a >> b)
    {
        memset(f, 0, sizeof f);
        int n = a.size(), m = b.size();

        for (int i = 1; i <= n; i++)
        {
            int t = 0;
            for (int j = 1; j <= m; j++)
            {
                int now = f[j];
                if (a[i - 1] == b[j - 1])
                    f[j] = t + 1;
                else
                    f[j] = max(f[j], f[j - 1]);
                t = now;
            }
        }
        cout << f[m] << '\n';
    }
}

“海康威视杯“ 2022年第十四届四川省大学生程序设计大赛

队伍 VP 了一下, 过了 B F H K, H 本来我首开的, 思路对了但忘开 LL 千古罪人. 哎, 下次一定会注意

K. Kooky Clock

一开始因为 PI 的精度卡了 2 发. 现在我会用 acos(-1.0) 了

const double PI = acos(-1.0);
void solve()
{
    int T;
    cin >> T;
    for (int i = 0; i < 3; i++)
        cin >> l[i];
    for (int i = 0; i < 3; i++)
        cin >> t[i];
    double x = 0, y = 0;
 
    for (int i = 0; i < 3; i++)
    {
        double theta = (2.5 - (double)T * 2 / t[i]) * PI;
        x += cos(theta) * l[i];
        y += sin(theta) * l[i];
    }
    cout << fixed << setprecision(10) << x << ' ' << y << '\n';
}

H Hacking Interview Solution

题面很长, 但核心是在询问一个数组是否重复出现

一开始手写 Hash 但忘了双哈希怎么写, 然后想起可以 map 套 vector

小心 overflow

void solve()
{
    map<vector<int>, int> mp;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
    {
        vector<int> t(n);
        for (int j = 0; j < n; j++)
            cin >> t[i];
        mp[t] += 1;
    }
    LL ans = 0;
    for (auto [val, cnt] : mp)
        ans += 1LL * cnt * (cnt - 1) / 2;
    cout << ans << '\n';
}

F Factor Difference

给定 $n\leqslant 10^5$, 找到一个最小的 $x$ 满足

$x$ 是个正数
$x$ 至少有 8 个因子
$x$ 的每个因子之间的差都大于等于 $n$

题解: 需要找到 $x$ 的三个质因子, 也就是找到三个质数, 这样组合以后可以保证至少有 8 个因子. 但三个数的乘积未必最小, 考虑 n=1 特例 2*3*4=24. 可以特判, 或者考虑 c = min(c, a * a). 质数用线性筛一下.

void solve()
{
    int n;
    cin >> n;
    int a = *lower_bound(primes, primes + cnt, 1 + n);
    int b = *lower_bound(primes, primes + cnt, a + n);
    int c = *lower_bound(primes, primes + cnt, b + n);
    cout << 1LL * a * b * min(1LL * a * a, (LL)c) << '\n'; 
}

Codeforces Round 946 (Div. 3)

好久没做题了, 练练

A. Phone Desktop

void solve() {
    int x, y;
    cin >> x >> y;
    int ans = (y + 1) / 2;
    int l = x + y * 4 - ans * 15;
    if (l > 0)
        ans += (l + 14) / 15;
    cout << ans << '\n';
}

B. Symmetric Encoding

题解: 模拟一下即可. 用到了容器去重的一个写法.

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    string p = s;
 
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
 
    int m = s.size();
    
    string ans;
    
    for (auto ch : p) {
        ans.push_back(s[m - s.find(ch) - 1]);
    }
    cout << ans << '\n';
}

C. Beautiful Triple Pairs

题解: 每一个三元组的贡献有三种情况: 第一个位置不同, 23 相同, 第二个位置不同, 13 相同, 以此类推.

不同的位置置 0, 例如 3 2 2 和 1 2 2 都是 0 2 2, 用哈希表存储这个 tuple 的个数.
然后处理所有位置都相同的情况, 由容斥原理, 这种情况被重复计算了三次, 所以答案减去 3*cnt.

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    map<TII, int> mp1, mp2, mp3, mp;
    LL ans = 0;
    for (int i = 0; i < n - 2; i++)
    {
        TII t = {a[i], a[i + 1], a[i + 2]};
        mp[t]++;
        TII t1 = {0, a[i + 1], a[i + 2]};
        mp1[t1]++;
        TII t2 = {a[i], 0, a[i + 2]};
        mp2[t2]++;
        TII t3 = {a[i], a[i + 1], 0};
        mp3[t3]++;
        ans += mp1[t1] - 1;
        ans += mp2[t2] - 1;
        ans += mp3[t3] - 1;
        ans -= 3 * (mp[t] - 1);
    }
    cout << ans << '\n';
}

D. Ingenuity-2

Codeforces Round 950 (Div. 3)

A. Problem Generator

void solve()
{
    vector<int> cnt(7);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        cnt[s[i] - 'A'] ++;
    }
    int ans = 0;
    for (int i = 0; i < 7; i++) {
        ans += max(m - cnt[i], 0);
    }
    cout << ans << '\n';
}

B. Choosing Cubes

void solve()
{
    int n, f, k;
    cin >> n >> f >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int m = a[f - 1];
    sort(a.begin(), a.end(), greater<int>());
    auto l = lower_bound(a.begin(), a.end(), m, greater<int>()) - a.begin();
    auto r = upper_bound(a.begin(), a.end(), m, greater<int>()) - a.begin();
    if (r <= k)
        cout << "YES\n";
    else if (l >= k)
        cout << "NO\n";
    else
        cout << "MAYBE\n";
}

注: 不排序也可以统计大于等于 a[f-1] 的个数, 然后和 k 比较

C. Sofia and the Lost Operations

题解: d 的最后一次操作可以覆盖掉之前的操作, 所以需要保证 d[m-1] 在 b 中. 然后只需考虑 a 和 b 序列之间的差异, 这些差异应当都包含在 d 中即可.

void solve()
{
    int n, m;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    cin >> m;
    vector<int> d(m);
    for (int i = 0; i < m; i++)
        cin >> d[i];
    bool flag = true;
    
    if (find(b.begin(), b.end(), d[m - 1]) == b.end()) {
        flag = false;
    }
    multiset<int> p(d.begin(), d.end());
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) {
            if (p.find(b[i]) == p.end())
                flag = false;
            p.extract(b[i]);
        }
    }
    if (flag) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

D. GCD-sequence

题解: 删除 $a_i$ 等价于删除 $b_{i-1}, b_{i}$, 添加一个新的数 $g=\operatorname{gcd}(a_{i-1}, a_{i+1})$, 保证删改前后 $b$ 非递减, 只需要考虑左边/右边/中间满足非递减即可. 左边和右边的单调性可以用前缀/后缀数组维护.

注意下表和边界的处理.

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1), l(n + 1), r(n + 1);
    b[n] = INF, l[0] = 1, r[n] = 1;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
    {
        b[i] = gcd(a[i], a[i + 1]);
        l[i] = (l[i - 1] && (b[i] >= b[i - 1]));
    }
    for (int i = n - 1; i >= 1; i--)
        r[i] = (r[i + 1] && (b[i] <= b[i + 1]));
    int ans = 0;
    if (r[2])
        ans = 1;
    if (l[n - 2])
        ans = 1;
    for (int i = 2; i < n; i++)
    {
        int g = gcd(a[i - 1], a[i + 1]);
        if (l[i - 2] && r[i + 1] && b[i - 2] <= g && g <= b[i + 1])
            ans = 1;
    }
    cout << ((ans) ? "YES" : "NO") << '\n';
}

Codeforces Global Round 26

A. Strange Splitting

无解只可能是单一元素的情形. 然后可以构造 n-1/1 的分组, 保证一个分组的 Range 为 0 而另一个不为 0, 只需要让单独分组的放到中间就可以了, 例如 1 1 2 分成 R B R. 题目保证了 $n>2$.

void solve()
{
    int n;
    cin >> n;
 
    set<int> st;
 
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        st.insert(x);
    }
    if (st.size() == 1) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
        for (int i = 0; i < n; i++) {
            cout << (i == 1 ? 'R' : 'B');
        }
        cout << '\n';
    }
}

B. Large Addition

猜结论: 首位必须为 1, 最后一位不为 9, 中间位不为 0.

void solve()
{
    string x;
    cin >> x;
    int n = x.size();
    int ans = 1;
    if (x[0] != '1')
        ans = 0;
    for (int i = 1; i < n - 1; i++) {
        if (x[i] == '0')
            ans = 0;
    }
    if (x[n - 1] == '9')
        ans = 0;
    if (ans)
        cout << "YES\n";
    else
        cout << "NO\n";
}

C1. Magnitude (Easy Version)

void solve()
{
    int n;
    cin >> n;
    LL mx = 0, mn = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mn += x;
        mx += x;
        mx = max(mx, abs(mn));
    }
    cout << mx << '\n';
}

C2. Magnitude (Hard Version)

求方案数.

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    map<LL, mint> dp;
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        map<LL, mint> ndp;
        for (auto &[x, y] : dp) {
            ndp[x + a[i]] += y;
            ndp[abs(x + a[i])] += y;
        }
        dp.clear();
        for (auto [x, y] : ndp) {
            if (x == ndp.begin()->first || x == ndp.rbegin()->first)
                dp[x] = y;
        }
    }
    cout << dp.rbegin()->second << '\n';
}