跳至主要內容

20240810比赛题解

Andy Shen2024/8/9大约 8 分钟Solution比赛题解

前言

本次比赛题目 T1，T2，T3 的题目背景均使用了陀思妥耶夫斯基的著作中的句子，与该题目有关联也蕴含一定哲理。（详见附注）

本次比赛题目，分别为 20230225 比赛 T3，2023 年暑期四中出题活动第 1 题，20230311 比赛 T3（出自腐朽阁内部赛 R2T3），20230114 比赛 T3。

题目难度顺序并不单调递增，难度排列大约为 2>3>4>1。（那些不读完整套题就放弃的同学请长长记性）

勾股

签到题，模拟即可。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long m, n;
    cin >> m >> n;
    vector<long long> temp = { 2 * m * n, m * m - n * n, m * m + n * n };
    sort(temp.begin(), temp.end());
    cout << temp[0] << ' ' << temp[1] << ' ' << temp[2] << endl;
    return 0;
}
import Data.List

main = do
    [m, n] <- fmap (map read . words) getLine
    putStrLn $ foldl (\acc x -> acc ++ show x ++ " ") [] $ sort [2 * m * n, m * m - n * n, m * m + n * n]

T2 贴标签 题解

这题有很多做法，我介绍一个珂朵莉树的做法。

显然的，有modn在，那么只要考虑最后n个就行（因为前面的都会被最后n次操作覆盖掉）。

然后考虑有什么数据结构能够区间修改，区间查询的。显然的，线段树能够完成这个任务，但是我不想写线段树，于是 std 用的是 ODT（珂朵莉树）。

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int l = 0, r = 0;
    mutable int val = 0;
    Node(int a, int b, int c)
    {
        l = a;
        r = b;
        val = c;
    }
    explicit Node(int a)
    {
        l = a;
    }
    bool operator<(const Node& a) const
    {
        return l < a.l;
    }
};

set<Node> ct;

typedef set<Node>::iterator tit;

tit split(int pos)
{
    auto it = ct.lower_bound(Node(pos));
    if (it != ct.end() && it->l == pos) {
        return it;
    }
    --it;
    int l = it->l, r = it->r;
    int val = it->val;
    ct.erase(it);
    ct.insert(Node(l, pos - 1, val));
    return ct.insert(Node(pos, r, val)).first;
}

void assign(int l, int r, int val)
{
    auto it2 = split(r + 1), it1 = split(l);
    ct.erase(it1, it2);
    ct.insert(Node(l, r, val));
}

int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m, p, q;
    cin >> n >> m >> p >> q;
    ct.insert({ 0, n - 1, 0 });
    int fir = (p + q) % n, sec = fir;
    int s = max(0, (m / n - 1) * n);
    for (int i = s + 1; i <= m; i++) {
        if (fir > sec) {
            assign(sec, fir, i);
        } else {
            assign(fir, sec, i);
        }
        fir = (fir + p) % n;
        sec = (sec + q) % n;
    }
    for (auto it : ct) {
        for (int i = it.l; i <= it.r; i++) {
            cout << it.val << ' ';
        }
    }
    cout << endl;
    return 0;
}

这题是白雪皑皑改编而来，代码几乎相同。可以考虑白雪皑皑原题的题解里面用的并查集，链表法。但是由于这题很明显的可以用珂朵莉，所以我当时的做法就是珂朵莉，而且珂朵莉的做法在原来的题解列表里面并不存在（

原题中有这样几种做法：链表+优先队列；并查集；线段树；暴力+优化。我个人认为，这题还有两种做法：珂朵莉树，分块。最后我用他们的题解实测了一下，暴力+优化的办法被我卡掉了（防止暴力碾标算），其他方法改一下输出格式都能成功 AC 该题。

原题当中的题解有更多做法，可供各位参考。

T3 金钱游戏 题解

原题，摘自国际大学生程序设计竞赛亚洲区域赛杭州站 D 题

首先，我们会发现这个轮数是非常的多，那么就说明这题肯定没法暴力或者其他什么办法，那么我们可以猜测，在一定的轮数过后，接下来继续进行操作是对原序列不会出现什么变化。

循着这个思路，很显然我们可以先去“蒙”答案，就是编写一个暴力程序进行模拟，对于小数据进行极大的次数的模拟（比如几千次甚至几万次），然后观察序列的变化。我们会发现，序列变化到最后一定是2:1:1:⋯:1的样式。

暴力程序：

#include <cstdio>
#include <iostream>

using namespace std;

double a[100010];

int main()
{
    // freopen("data/test.txt", "w", stdout);
    freopen("data/data1.in", "r", stdin);
    freopen("data/data1.ans", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= 500000; i++) {
        for (int j = 1; j <= n - 1; j++) {
            a[j] /= 2;
            a[j + 1] += a[j];
        }
        a[n] /= 2;
        a[1] += a[n];
    }
    for (int j = 1; j <= n; j++) {
        cout << a[j] << ' ';
    }
    cout << endl;
    return 0;
}

接下来我们来解释一下为什么这样是对的：

如果我们把题面改一下，改成每个人都给下一个人他的全部，那么这个问题就会变的非常简单：所有钱在第一轮会叠罗汉一般的传递到最后一个人，最后一个人把钱在传给第一个人，那么一轮过去第一个人就拥有了全部的存款，接下来不管怎么传递，一轮结束后一定第一个人拥有全部的存款，那么这个时候就进入了一个稳态。

那么回到这个问题，这个问题是否存在稳态呢？事实上是存在的（数学证明极为复杂，此处不列）。接下来我们来构造一下这个稳态。对于我刚刚举的这个例子，进入稳态后就有一部分（例子中是全部）的钱像传花球一样的不断向下传递。这个问题中每次是有一半的钱在向下传递，那么我们可以先给所有人相同一部分的钱x，然后设定一个y，作为类似我们举的例子中的那个“花球”一样不断向后传递。那么显然要符合一个条件就是12(x+y)=x，只有这样才能够做到每个人向后传递存款之后能够达到自己手上的钱不变，一轮结束后仍然保持在这个稳态。解得前面那个方程的答案为y=x，所以稳态是所有人手上的钱的比例为：2:1:1:⋯:1时出现。

由于总钱数是保持不变的，所以只要算出总钱数sum，然后给第一个人sum×2n+1，其余的人sum×1n+1即可。

std:

#include <cstdio>
#include <iostream>

using namespace std;

double sum;

int main()
{
    // freopen("data/test.txt", "w", stdout);
    // freopen("data/data2.in", "r", stdin);
    // freopen("data/data2.out", "w", stdout);
    double n;
    cin >> n;
    double tmp;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        sum += tmp;
    }
    sum /= n + 1;
    printf("%.2lf ", sum * 2);
    for (int i = 1; i <= n - 1; i++) {
        printf("%.2lf ", sum);
    }
    printf("\n");
    return 0;
}

最后提一点反思：看到题面中如果有诸如20221204，20234101这种超大数出现，那么就可以将这个超大数看成无穷大，这类题目往往到最后会收敛到某个值，所以可以写一个暴力代码把过程打出来观察规律。

T4 分组 题解

二分图判定板子题。

如果不知道二分图是什么，请移步OIWiki

显然，不存在男男，女女之间的搭配以及除了男女之外的性别（至少在这里是这样），故搭配一定是男女。

很显然在二分图当中红色节点连接的一定是蓝色节点，蓝色节点连接的一定是红色节点。故我们从任意一个起点开始，将这个点标为红色，然后跑深搜进行红蓝染色。将遍历到的所有红色节点和蓝色节点分别加入两个 set 中，最后输出即可。

#include <bits/stdc++.h>

using namespace std;

constexpr int NOCOLOR = 0;
constexpr int RED = 1;
constexpr int BLUE = 2;
vector<int> G[100010];
int color[100010];
set<int> red;
set<int> blue;

void dfs(int x, int curcolor)
{
    if (curcolor == RED) {
        red.emplace(x);
        color[x] = RED;
    } else if (curcolor == BLUE) {
        blue.emplace(x);
        color[x] = BLUE;
    }
    for (auto it : G[x]) {
        if (!color[it]) {
            if (curcolor == RED) {
                dfs(it, BLUE);
            } else if (curcolor == BLUE) {
                dfs(it, RED);
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, RED);
    if (red.size() > blue.size()) {
        for (auto it : red) {
            cout << it << ' ';
        }
        cout << endl;
        for (auto it : blue) {
            cout << it << ' ';
        }
        cout << endl;
    } else {
        for (auto it : blue) {
            cout << it << ' ';
        }
        cout << endl;
        for (auto it : red) {
            cout << it << ' ';
        }
        cout << endl;
    }
    return 0;
}

附注

T1 使用了《地下室手记》中的选句。个人理解是：人如果真的找到了所谓的亘古不变的“真理”，也就是这里的“公式”，那么人的意志和主观能动性都会被磨灭，因为一切都是确定的，又有什么东西值得为之探索呢？人的生命过程本就是通过自己的“存在”去探索自己“本质”的过程，物质的运动性告诉我们，我们的“本质”是不断变化的，我们应当不断为探求自己的“本质”而努力。

T2 使用了《白痴》的选句。个人理解是：我们平时经常会为自己的性别，观点等等画上许多标签。这些标签虽然一般不会暴露在外面，但是他们会伴随着你的言行举止直到死去。我们应当拒绝死板的“标签”观点，动态的看问题。

T3 使用了《赌徒》的选句。此处和“金钱游戏”这个题名也相扣，赌博本就是一场金钱游戏。这句话反映的观点事实上是错误的，是一种典型的赌徒心理。你不应当把你的所有东西都押在某个很小的契机上（比如相信你在 CSP 的时候运气够好能够骗分过样例一样），你应当相信“不积跬步无以至千里，不积小流无以成江海”，从平时的老老实实地训练开始一步步的走向省一。

以上，祝大家 CSP RP++，NOIP RP++。

最近更新：
贡献者: AndyShen2006,Andy Shen