A. 不要三个一

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

  • 子任务 1：只有一个 11，那直接输出 11 个 11 和 n−1n-1 个 00 即可。
  • 子任务 2：显然这个子任务的输出是 11,11011,11011011,…11,11011,11011011,\dots 这样的格式。
  • 子任务 3：凑数给愿意写 66 个 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∼rl\sim r 中找几次能找到 xx（虽然这件事本身挺无聊）。

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

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

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

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;
}

满分

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

  • 第一次被 midmid 命中的是 ⌊3+102⌋=6\lfloor \frac{3+10}{2}\rfloor=6
  • 然后第二次被 midmid 命中的有两个，左半边是 3∼53\sim 5 中间的 44，和右半边的 7 107~10 中间的 88。

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

还有一个做法，实际上容易发现 l rl~r 的答案可以等价对应到 1∼r−l+11\sim r-l+1 或者 2∼r−l2\sim r-l。然后其实是可以数学方法,log⁡n\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 的 2020 的范围也跑的飞快，所以直接 dfs 是能拿到 4040 分的。

子任务 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;
}

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

子任务 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 ...。前面的两步走几次有多种情况，但是一旦开始回头了，就是唯一的一种走法了。

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

往右狂奔或者折返回到牛

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

fif_i 表示往右走到了 ii 且 i−1i-1 被走过了，gig_i 表示往右走到了 ii 且 i−1i-1 没走（跳过去了）。然后状态转移方程其实很好退出来。

那么精准抵达 bb 的方案是就是 fb+gbf_b+g_b，跳过 bb 到达 b+1b+1 的方案就是 gb+1g_{b+1}。

我们可以惊喜得发现，从 b+1b+1 回头到 bb 的方案数和前部分从 aa 到 a+1a+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" 也能造出来的。

子任务 1（10 分）

就一个单词，直接给这个单词编码 0 或 1 就好了，文章长度就是单词数量乘以 11 了。很多同学这部分分数没拿到有点可惜。

子任务 2（20 分）

既然给的就是个合法的哈夫曼编码，直接用这套编码算文章长度就好了。文章长度就是“每个单词数量乘以编码长度”之和。

子任务 3（30 分）

只要长度合法就行，所以这里就需要把哈夫曼编码给先求出来。然后输入不合法就输出你的方案就好，合法就输出就直接算算文章长度输出就好。

这个子任务保证了互不为前缀，所以只要文章长度对了就行。所以用自己的编码算一个文章长度，然后算算输入给的文章长度。如果一样就是 Yes，不一样就是 No。

子任务 4（40 分）

前面的基础上再加一个判断是否有前缀关系就好。这题数据范围小，直接 O(n2)O(n^2) 的枚举单词对，然后检查两个单词是否满足其中一个是不是另一个的前缀就好。

实际上也有更简单的方法。把所有单词按照字典序排序，那么如果存在前缀关系，必然存在相邻的前缀关系。且前一个是后一个的前缀。

满分参考代码

#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;
}

0 条评论

目前还没有评论...
18
已通过
0
题解被赞
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 29ms
  4. Powered by Hydro v5.0.0-beta.18 Community