跳转至

2025“钉耙编程”中国大学生算法设计春季联赛

我感觉自己水平就是莫名其妙很低，以前或许还能找借口说自己是大一的，现在呢，已经是大二了。还是比不过很多人捏。

哈哈哈，没必要想那么多，好好补题就行。🙌🙌😭😭😭🙌🙌

这场做了人最多的四个题，其实也还行了。1005是WA了15次过的，很不容易了。虽然很多都乱交的，但是这场对我表现还行了的。

1005一开始没想着用dijkstra的，就一堆循环乱搞，最后开始写最短路30分钟ac了，中间wa两发，没仔细检查。

值得一提的是，1006这个签到题都 WA 了四次。没必要那么急的。1007刚开始看到被吓到了，题目很久没看懂，后来看到很多问的，稍微放松了点，推了一下ac了很爽，普通博弈吧。

好好补题吧，慢慢看。先自己看看题试试。

其实很多时候，题目只是看起来很麻烦，其实没什么的，静下心来，慢慢看看题。

01

最签到的一集

void solve()
{
    int n;
    string p;
    cin>>n>>p;
    int ans=-1;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        if(s==p) ans=i;
    }
    cout<<ans<<'\n';
}

02

暴力的去写就是模拟每次比赛结束输赢的人是谁，看遇到赢得人的时候的概率是多少。

但其实如果 \(n\) 是 \(10^5\) 我也不太会，在没看题解之前应该不太能写出来，就是模拟的过程感觉不太会写。于是看了题解。

\(f_i\) 表示 \(i\) 位置是然然不喜欢的人的概率，那么若下一轮能遇到然然，那么答案需要更新为 \(ans(1-f_i)\) 。怎么去模拟这一过程呢？每次进行比赛人数都会减半，于是 第 \(i\) 位选手在下一轮将会变成第 \(i\) >> \(1\) 位 ，但是需要先把序号都 -1 ，在这里会方便很多 。否则就是除以二向上取整。

然后如果说这一轮里比赛的两个人都是不想遇到的人，那么 \(f_{\frac{i}{2}}\) 就是 \(\frac{f_i+f_{i+1}}{2}\) ，如果只有一个是不想遇到的人，那么 $f_{\frac{i}{2}}=\frac{f_i}{2} $ 。如果这一轮他不需要比赛，那么就直接等于 \(f_i\) 。

之后一次次更新就行，如果序号都 -1 了的话， \(i\) 的对手就是 \(i\oplus 1\) 。。当然这些思路我全是看的题解的，甚至代码也是抄的。。自己思考应该会很难。

using ll = long long;

constexpr int mod = 998244353;

ll ksm(ll a, ll b)
{
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll inv(ll x) { return ksm(x, mod - 2); }

void ChatGptDeepSeek()
{
    int n, k, win;
    cin >> n >> k >> win;
    --win;
    vector<int> p(k), f(k, 1);
    for (int i = 0; i < k; i++)
        cin >> p[i], --p[i];
    sort(p.begin(),p.end());
    ll ans = 1;
    ll iv2 = inv(2);
    while (!p.empty()) {
        win >>= 1;
        vector<int> b, g;
        for (int i = 0; i < p.size(); i++) {
            if ((p[i] >> 1) == win) {
                ans = (ans * (1 - f[i])) % mod;
                ans = (ans + mod) % mod;
            } else {
                b.push_back(p[i] >> 1);
                if (i + 1 < p.size() && (p[i] >> 1) == (p[i + 1] >> 1)) {
                    g.push_back(1LL * (f[i] + f[i + 1]) * iv2 % mod);
                    i++;
                } else if ((p[i] ^ 1) < n) {
                    g.push_back(1LL * f[i] * iv2 % mod);
                } else {
                    g.push_back(f[i]);
                }
            }
        }
        p = b, f = g;
        n = (n + 1) / 2;
    }
    cout << ans << '\n';
}

05

把一个点拆成4个不同方向的点，然后进行求最短路的操作。

其实我本来是循环写的，然后WA了好多次，开始尝试用最短路写，之后就AC了。。

using ll = long long;
using ull = unsigned long long;
constexpr long long LNF = 1000000000000000000LL;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<ull>> t(n + 1, vector<ull>(m + 1));
    vector<vector<ull>> d(n + 1, vector<ull>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> t[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> d[i][j];
    vector<vector<vector<ull>>> f(n + 1, vector<vector<ull>>(m + 1, vector<ull>(4, LNF)));
    // 0123 LURD
    f[1][0][2] = 0;

    {
        priority_queue<array<ull, 4>, vector<array<ull, 4>>, greater<>> pq;
        f[1][1][2] = t[1][1];
        pq.push({ t[1][1], 1, 1, 2 });
        while (!pq.empty()) {
            auto [dis, i, j, dir] = pq.top();
            // cerr << i << " " << j << '\n';
            pq.pop();
            if (f[i][j][dir] < dis)
                continue;
            for (ull k = 0; k < 4; k++) {
                // 首先它原地的不同方向
                if (f[i][j][dir] + d[i][j] < f[i][j][k]) {
                    f[i][j][k] = f[i][j][dir] + d[i][j];
                    pq.push({ f[i][j][k], i, j, k });
                }
            }
            if (i == n && j == m)
                continue;
            // 看自己是哪个方向
            if (dir == 0 && j - 1 >= 1) {
                if (f[i][j][0] + t[i][j - 1] < f[i][j - 1][0]) {
                    f[i][j - 1][0] = f[i][j][0] + t[i][j - 1];
                    pq.push({ f[i][j - 1][0], i, j - 1, 0 });
                }
            } else if (dir == 1 && i - 1 >= 1) {
                if (f[i][j][1] + t[i - 1][j] < f[i - 1][j][1]) {
                    f[i - 1][j][1] = f[i][j][1] + t[i - 1][j];
                    pq.push({ f[i - 1][j][1], i - 1, j, 1 });
                }
            } else if (dir == 2 && j + 1 <= m) {
                if (f[i][j][2] + t[i][j + 1] < f[i][j + 1][2]) {
                    f[i][j + 1][2] = f[i][j][2] + t[i][j + 1];
                    pq.push({ f[i][j + 1][2], i, j + 1, 2 });
                }
            } else if (dir == 3 && i + 1 <= n) {
                if (f[i][j][3] + t[i + 1][j] < f[i + 1][j][3]) {
                    f[i + 1][j][3] = f[i][j][3] + t[i + 1][j];
                    pq.push({ f[i + 1][j][3], i + 1, j, 3 });
                }
            }
        }
        // 距离 i j 方向
    }

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

06

我赛时map erase错了。。。

如果删除了，it++就会出问题，所以用 it=mp.erase(it)

set删元素也同理。

如果是c++20及以上可以使用 erase_if 删除元素。

std::erase_if(mp, [&](const auto& pair) {
    return pair.second != num + 1;
});

然后就很简单了，只需要枚举每一种可能，然后输出就行了。

void solve()
{
    int n;
    cin >> n;
    vector<array<int, 3>> a(n, array<int, 3>());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++)
            cin >> a[i][j];
    }
    map<int, int> mp;
    auto work = [&](array<int, 3> x, int num) {
        vector<int> p { 0, 1, 2 };
        do {

            int u = x[p[0]], v = x[p[1]], w = x[p[2]];
            if (((w - v) % u != 0) || (w - v) / u < 0)
                continue;
            int X = (w - v) / u;
            if (num && mp.find(X)!=mp.end()) {
                if (mp[X] == num + 1)
                    continue;
                if (mp[X] == num)
                    mp[X]++;
            } else {
                if (mp.find(X)!=mp.end())
                    continue;
                mp[X] = 1;
            }
        } while (next_permutation(p.begin(), p.end()));
        for (map<int,int>::iterator it = mp.begin(); it != mp.end(); ) {
            if (it->second != num + 1)
                it=mp.erase(it);
            else ++it;
        }
    };
    for (int i = 0; i < n; i++) {
        work(a[i], i);
        if (mp.size() == 1) {
            for (auto [x, y] : mp)
                cout << x << '\n';
            return;
        }
    }
}

07

博弈题，我怎么半天没看懂题目描述。。。

但是后来看很多提问的，然后多看了会就差不多了。

我们从小到大考虑一下。

\(n=1\) ，第 \(1\) 个人同不同意无所谓，肯定不给他钱。

\(n=2\) ，第 \(2\) 个人肯定同意如果给他钱，否则第 \(1\) 个人当船长了他肯定拿不到钱，第 \(1\) 个人肯定会反对，所以只用给第 \(2\) 个人。

\(n=3\) ，第 \(1\) 个人当船长肯定只会给第 \(3\) 个人，所以他们两都会反对，只用给 \(2\) 钱。

\(n=4\) ，第 \(1\) 个人会给第 \(3\) 个人，所以我们给 \(2\) 和 \(4\) 。

... 后面基本同理了，\(1\) 当船长给谁钱，我们就给其他人钱。

发现 \(1\) 会给所有奇数的人钱，所以我们给所有的偶数的人。

constexpr int mod = 1e9 + 7;

void solve()
{
    // n=1 肯定没必要给
    // n=2 给第2个人不给第1个人，因为第2个人把我沙了就拿不到了

    // n=3 给第二个第三个，因为如果主人变成1 ，那么肯定会给3送金币
    // 所以2号会支持我如果我给他钱，
    // 所以只用给2

    // n=4 第一个人当主人会变成 (1,3)的情况，所以他只会给3钱
    // 所以如果给钱给2 4，它们会支持我 我正好也需要2个人

    // n=5 (1,4)
    // 3，5 ，
    // 它们肯定反对我 1也反对我

    // 所以我们继续给2 4

    // n=6 135反对我
    // 把钱给246

    auto get = [&](int l, int r) {
        if (l > r)
            return 0LL;
        return 1LL * (r - l + 2) / 2 * (l + r) / 2 % mod;
    };
    int n;
    cin >> n;
    cout << get(2, n - (n & 1)) << '\n';
}

直接求和就行。