挖土机 CSP-J 模拟赛 ~ 第一场

33DAI2024年12月24日大约 10 分钟

A. 不要三个一

显然要尽可能把 $1$ 往高位放，如果放了两个 $1$ 就来一个 $0$ 来避免非法，所以 $1$ 应该放在从左往右第 $1, 2, 4, 5, 7, 8, \dots$ 个，这些除以 $3$ 余 $1, 2$ 的位置中。所以可以根据是否还有 $1$ 来决定怎么输出。

子任务 1：只有一个 $1$ ，那直接输出 $1$ 个 $1$ 和 $n - 1$ 个 $0$ 即可。
子任务 2：显然这个子任务的输出是 $11, 11011, 11011011, \dots$ 这样的格式。
子任务 3：凑数给愿意写 $6$ 个 if 打表的同学送的分数。

满分参考代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
    freopen("three.in", "r", stdin);
    freopen("three.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        if (m > 0)
        {
            if (i % 3 == 1 || i % 3 == 2)
            {
                cout << 1;
                m--;
            }
            else
                cout << 0;
        }
        else
            cout << 0;
    }
    return 0;
}

B. 猜数字作弊

60 分

显然这是段二分的代码，输出的是在 $l \sim r$ 中找几次能找到 $x$ （虽然这件事本身挺无聊）。

题目问几个数可以得到最大的输出，显然一个暴力枚举的做法就是对 $l \rim r$ 范围内的每个数都跑一遍这段代码看看输出是几。

但有不少同学这个写错了，主要原因是这段代码会修改 $l, r$ 的值，所以外面枚举 $x$ 的时候不能也用变量 $l, r$ 来做了。可以把题目描述给的代码打包成一个函数，或者备份一份即可。

子任务 1,2 送了可以口算出来的 $30$ 分。

60 分参考代码：

#include <bits/stdc++.h>
using namespace std;
int f(int l, int r, int x)
{
    int cnt = 0;
    while (l <= r)
    {
        cnt++;
        int mid = (l + r) / 2;
        if (mid == x)
            return cnt;
        if (mid < x)
            l = mid + 1;
        if (mid > x)
            r = mid - 1;
    }
}
int main()
{
    freopen("guess.in", "r", stdin);
    freopen("guess.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int l, r;
    cin >> l >> r;
    int maxX = 0;
    for (int i = l; i <= r; i++)
        maxX = max(maxX, f(l, r, i));
    int ans = 0;
    for (int i = l; i <= r; i++)
        if (f(l, r, i) == maxX)
            ans++;
    cout << ans;
    return 0;
}

满分

实际上手动模拟一下，可以算出来每个数是第几次被 $m i d$ 命中的。比如 $l = 3, r = 10$ 时：

第一次被 $m i d$ 命中的是 $⌊ \frac{3 + 10}{2} ⌋ = 6$
然后第二次被 $m i d$ 命中的有两个，左半边是 $3 \sim 5$ 中间的 $4$ ，和右半边的 $7 10$ 中间的 $8$ 。

这个过程显然可以用深搜或者广搜跑完，时间复杂度 $O (n)$ 。

还有一个做法，实际上容易发现 $l r$ 的答案可以等价对应到 $1 \sim r - l + 1$ 或者 $2 \sim r - l$ 。然后其实是可以数学方法, $\log n$ 算算哪些数字最后一次被命中。但我懒得推了，作为第二题直接爆搜就好了。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int l, r, maxCnt;
int f[100'000'000 + 5];
void dfs(int l, int r, int cnt)
{
    if (l > r)
        return;
    int mid = (l + r) / 2;
    f[mid] = cnt;
    maxCnt = max(maxCnt, cnt);
    dfs(l, mid - 1, cnt + 1);
    dfs(mid + 1, r, cnt + 1);
}
int main()
{
    freopen("guess.in", "r", stdin);
    freopen("guess.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int l, r;
    cin >> l >> r;
    maxCnt = 0;
    dfs(l, r, 1);
    int ans = 0;
    for (int i = l; i <= r; i++)
        if (f[i] == maxCnt)
            ans++;
    cout << ans;
    return 0;
}

C. 再次抓住牛

这道题我觉得最好的是我这个配图用 ppt 画得真好看。

60 分

首先显然直接 dfs 爆搜能跑出来子任务 1，但大胆一点搜搜会发现子任务 3 的 $20$ 的范围也跑的飞快，所以直接 dfs 是能拿到 $40$ 分的。

子任务 1、3 参考代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXN = 1'000'000;
int n, a, b;
int ans;
bool vis[MAXN + 5];
int dx[] = {1, -1, 2, -2};
void dfs(int now)
{
    if (now == b)
    {
        ans = (ans + 1) % MOD;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nxt = now + dx[i];
        if (nxt < 0 || nxt > n || vis[nxt])
            continue;
        vis[nxt] = true;
        dfs(nxt);
        vis[nxt] = false;
    }
}
int main()
{
    freopen("cow.in", "r", stdin);
    freopen("cow.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    ans = 0;
    vis[a] = true;
    dfs(a);
    vis[a] = false;
    cout << ans;
    return 0;
}

很多同学就止步于此了，实际上能拿到 $40$ 分之后，子任务 2 的 $20$ 分就在嘴边了。用这个代码来跑一跑 1 0 1、2 0 2、3 0 3 这些数据，会发现其实是有规律的，n 0 n 的答案等于前三个答案之和（实际上这个规律也是我出完题目之后才发现的）。所以子任务 1,2 直接一个递推就好了。两个代码总结在一起就是个 $60$ 分了。

子任务 1,2 参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXN = 1'000'000;
int n, a, b;
int f[MAXN + 5];
signed main()
{
    freopen("cow.in", "r", stdin);
    freopen("cow.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    f[0] = 1;
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; i++)
        f[i] = (f[i - 1] + f[i - 2] + f[i - 3]) % MOD;
    cout << f[n];
    return 0;
}

100 分

首先要注意到，n a b 和 n b a 的答案一样，所以可以先把人调整到左边，牛调整到右边。

然后抓牛得情况看上去很多，但是仔细想想会发现一旦某个地方回头了，就不可能再折返回去了。所以只有三种情况：

直接往右精准抵达
往右跳过牛，然后回头精准抵达
往左一段，然后往右精准抵达
往左一段，然后往右跳过牛，再回头精准抵达

是否往左一段

如果往左一段然后回头，那么必然是 -2 -2 -2 -2 -1 +2 +2 +2... 这样或者 -2 -2 -2 -2 +1 +2 +2 +2 ...。前面的两步走几次有多种情况，但是一旦开始回头了，就是唯一的一种走法了。

所以从 $a$ 走到 $a + 1$ 其实就看左边从哪儿开始往右走，一共有 $0 \sim a$ 这些折返点，共 $a + 1$ 个方案能“走到 $a + 1$ 这个位置且能继续往右”。

往右狂奔或者折返回到牛

后半部分就两种结果了，要么精准往右到 $b$ ，要么跳过了 $b$ 到达 $b + 1$ 再回头。我一开始没发现子任务 2 那个规律，所以我是 dp 写的。

$f_{i}$ 表示往右走到了 $i$ 且 $i - 1$ 被走过了， $g_{i}$ 表示往右走到了 $i$ 且 $i - 1$ 没走（跳过去了）。然后状态转移方程其实很好退出来。

那么精准抵达 $b$ 的方案是就是 $f_{b} + g_{b}$ ，跳过 $b$ 到达 $b + 1$ 的方案就是 $g_{b + 1}$ 。

我们可以惊喜得发现，从 $b + 1$ 回头到 $b$ 的方案数和前部分从 $a$ 到 $a + 1$ 的计算方法一样。这道题就这么做完了。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXN = 1'000'000;
int n, a, b;
int f[MAXN + 5]; // 往右走到 i，且 i-1 走过了，i 右面都没走过
int g[MAXN + 5]; // 往右走到 i，且 i-1 没走过，i 右边都没走过
signed main()
{
    freopen("cow.in", "r", stdin);
    freopen("cow.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    if (a > b)
        swap(a, b);
    f[a] = 0, f[a + 1] = a + 1;
    g[a] = 1, g[a + 1] = 0;
    for (int i = a + 2; i <= n; i++)
    {
        // 左边走过
        f[i] = (f[i - 1] + g[i - 1]) % MOD; // 直接左边往右走一步
        f[i] = (f[i] + g[i - 1]) % MOD;     // 左边回撤一步再往前
        // 左边没走过
        g[i] = (f[i - 2] + g[i - 2]) % MOD; // 只能从 i-2 一次两步过去
    }
    int ans1 = (f[b] + g[b]) % MOD; // 左边直达
    int ans2 = 0;
    if (b != n)
        ans2 = (g[b + 1] * (n - (b + 1) + 1)) % MOD;
    cout << (ans1 + ans2) % MOD;
    return 0;
}

D. 合法哈夫曼

其实这题是为了给初赛服务的。为了给大家科普下 J 组初赛常考的哈夫曼编码。

所以可以先学学咋求哈夫曼编码。核心就是每次贪心选两个权值最小的节点，合到一个节点上。拿个优先队列建树就好，这题数据范围小也可以直接纯暴力找俩权值小的节点建树就好了。

然后从根节点开始 dfs 往下跑就能得到每节点的编码了，这题我给的数据范围的编码直接用一个 long long 就能存，我用两个数组分别存了编码长度和编码，当然直接用字符串存左子树 +"0" 右子树 +"1" 也能造出来的。

满分参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[60 + 5];
string s[60 + 5];

// huffman 建树
priority_queue<pair<int, int>> q;
int tot, l[60 * 2 + 5], r[60 * 2 + 5];
// 算 huffman 编码
int len[60 * 2 + 5], code[60 * 2 + 5];
void dfs(int x, int nowLen, int nowCode)
{
    if (x <= n)
    {
        len[x] = nowLen;
        code[x] = nowCode;
        return;
    }
    dfs(l[x], nowLen + 1, nowCode * 2);
    dfs(r[x], nowLen + 1, nowCode * 2 + 1);
}

signed main()
{
    freopen("huffman.in", "r", stdin);
    freopen("huffman.out", "w", stdout);
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    // 算输入的文章总长度
    int inf_ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        inf_ans += s[i].size() * a[i];
    }

    // 特判
    if (n == 1)
    {
        if (s[1].size() == 1)
            cout << "Yes\n"
                 << inf_ans << "\n";
        else
            cout << "No\n1\n";
        return 0;
    }

    // 构建一个哈夫曼编码
    tot = n;
    for (int i = 1; i <= n; i++)
        q.push(make_pair(-a[i], i));
    while (q.size() > 1)
    {
        tot++;
        pair<int, int> x = q.top();
        q.pop();
        pair<int, int> y = q.top();
        q.pop();
        q.push(make_pair(x.first + y.first, tot));
        l[tot] = x.second;
        r[tot] = y.second;
    }
    dfs(tot, 0, 0);

    // 检查
    bool flag = true;
    // 检查文章总长度
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += a[i] * len[i];
    if (inf_ans != ans)
        flag = false;
    // 检查前缀问题
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        if (s[i] > s[i + 1])
            continue;
        bool now = true; // 是否为前缀
        for (int j = 0; j < s[i].size(); j++)
            if (s[i][j] != s[i + 1][j])
            {
                now = false;
                break;
            }
        if (now)
        {
            flag = false;
            break;
        }
    }

    // 输出
    if (flag)
    {
        cout << "Yes\n";
        cout << ans << "\n";
    }
    else
    {
        cout << "No\n";
        for (int i = 1; i <= n; i++)
        {
            for (int j = len[i] - 1; j >= 0; j--)
                cout << ((code[i] >> j) & 1);
            cout << "\n";
        }
    }
    return 0;
}

挖土机 CSP-J 模拟赛 ~ 第一场

A. 不要三个一

B. 猜数字作弊

60 分

满分

C. 再次抓住牛

60 分

100 分

是否往左一段

往右狂奔或者折返回到牛

D. 合法哈夫曼

子任务 1（10 分）

子任务 2（20 分）

子任务 3（30 分）

子任务 4（40 分）