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

2025-03-28 打得还行的一集，赛时写了四题，但是全是很简单的题啊。下一题我就刚才看题解都看得很难受。看大佬代码强行理解一下

今天是周一，03-31，不仅刚补这篇题解，还有VP的区域赛的也等着我。先把这篇整了，回去学个算法，然后VP一场EDU。

感觉像这种还是干脆就在Vscode写可能还比较舒服，不然有点麻烦，就得用两个软件，切文件还不方便，而且Vscode还更流畅一些。

1001

比较简单的模拟题，但是我把题目看错了。。。弘文了。题目说的是第二次及以后收到的伤害是 \(\frac{u}{2}\) ，但是我以为每次受到的伤害是上一次受到的伤害除以2。。。后来重新看了一下发现了。

void ChatGptDeepSeek()
{
    long long n, u, k, hq;
    cin >> n >> u >> k >> hq;
    vector<int> cnt(n + 1);
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    vector<int> time(n + 1), lst(n + 1, 2 * u);
    multiset<int> st;
    for (int i = 1; i <= n; i++)
    {
        int a, h;
        cin >> a >> h; // 攻击 血量
        //  血量 攻击 下标
        pq.push({h, a, i});
        st.insert(a);
    }
    int ans = 0;
    while (!pq.empty())
    {
        auto [h, a, i] = pq.top();
        // assert(h >= 0 && time[i] <= k);
        pq.pop();
        // assert(i <= n);

        if (time[i] == 0)
        {
            h -= u;
            lst[i] = u;
        }
        else
        {

            h -= u / 2;
        }
        if (h <= 0)
        {
            ans++;
            st.erase(st.lower_bound(a));
        }
        if (st.empty())
            break;
        int hurt = *st.rbegin();

        time[i]++;

        hq -= hurt;
        if (hq <= 0)
        {
            break;
        }
        if (time[i] < k && h > 0)
        {
            pq.push({h, a, i});
        }
    }
    cout << n - st.size() << '\n';
}

1003

刚补（抄）的，感觉能看懂一点的。。大概强行理解吧。

我只能说还是不太懂，已经看了很久了。或许以后再回来看看吧。

void ChatGptDeepSeek()
{
    ll k, b, c, v;
    cin >> k >> b >> c >> v;
    ll led = 0;
    // p^c <=v
    ll ans = 0;
    for (int i = 60; i >= 0; i--)
    {
        if (v >> i & 1)
        {
            ll u = (led ^ c) & ((1LL << 61) - (1LL << i));
            ll L = u - 1, R = u + (1LL << i) - 1;
            // [u,R] 是 i全为0的区间，在这之后 i 这个地方全会为1了
            // 那么我们后面其实会漏掉 p=v 的情况
            if (R >= b)
                ans += (R - b) / k + 1;
            if (L >= b)
                ans -= (L - b) / k + 1;
            led |= 1LL << i;
        }
    }
    if ((v ^ c) >= b && ((v ^ c) - b) % k == 0)
        ans++;
    cout << ans << '\n';
}

1005

水题。。

void ChatGptDeepSeek()
{
    int P, n, k;
    cin >> P >> n >> k;
    vector<double> p1(1, 1);
    vector<int> p2(1, 0);
    // priority_queue<int, vector<int>, greater<>> p1;
    // priority_queue<int> p2;
    for (int i = 1; i <= n; i++)
    {
        int t, p;
        cin >> t >> p;
        if (!t)
            p1.push_back(p / 10.0);
        else
            p2.push_back(p);
    }
    sort(p1.begin() + 1, p1.end());
    sort(p2.begin() + 1, p2.end(), greater<>());
    for (int i = 1; i < p1.size(); i++)
        p1[i] = p1[i - 1] * p1[i];
    //  cerr << p1[i] << " \n"[i + 1 == p1.size()];
    for (int i = 1; i < p2.size(); i++)
        p2[i] = p2[i - 1] + p2[i];
    //  cerr << p2[i] << " \n"[i + 1 == p2.size()];

    double ans = P;

    int s1 = p1.size() - 1, s2 = p2.size() - 1;
    for (int i = max(0, k - s2); i <= min(k, s1); i++)
    {
        if (k - i > s2)
            ans = min(ans, P * p1[i]);
        else
            ans = min(ans, P * p1[i] - p2[k - i]);
        // cerr << "P*p1 :" << P * p1[i] << " p2[k-i]: " << p2[k - i] << '\n';
        // cerr << i << " " << k - i << " " << ans << '\n';
    }
    ans = max(ans, 0.0);
    cout << ans << '\n';
}

1006

树状数组模板题。

struct Fenwick
{
    vector<ll> b;
    Fenwick(int n)
    {
        b = vector<ll>(n + 1);
    }
    int lowbit(int x) { return (x) & (-x); }
    void add(int i, int x)
    {
        while (i && i < b.size())
        {
            b[i] += x;
            i += lowbit(i);
        }
    }
    ll query(int i)
    {
        ll res = 0;
        while (i)
        {
            res += b[i];
            i -= lowbit(i);
        }
        return res;
    }
};
void ChatGptDeepSeek()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    Fenwick C(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        C.add(i, a[i]);
    }
    int tot = 1;
    ll ans = 0;
    while (q--)
    {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1)
        {
            C.add(x, y - a[x]);
            a[x] = y;
        }
        else
        {
            ll res = C.query(y) / 100 - C.query(x - 1) / 100;
            ans = ans ^ (res * tot);
            tot++;
        }
    }
    cout << ans << '\n';
}

1008

基础的一个DP，但是感觉我写得不够流畅，还是写了一会才写出来的。

void ChatGptDeepSeek()
{
    int n, k;
    cin >> n >> k;
    vector<vector<int>> dp(n + 1, vector<int>(k + 1)), a(n + 1, vector<int>(k + 1));
    /* 到i 分了j段 */
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i][j]);
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            // cerr << dp[i][j] << " \n"[j == k];
        }
    }
    cout << dp[n][k] << '\n';
}