2024年马蹄杯专科组第三场初赛 解题报告 | 珂学家-题解

VP了这场比赛，整体还是偏简单，最难的题是数论相关，算一道思维题。

也看了赛时榜单，除了数论，大模拟和图论题也是拦路虎。

---

---

打工人

有趣的一道数学题，有点绕

很像数列和

$$\sum _{i=1}^{i=n}i=n\ast (n+1)/2$$

从公式结合时间复杂度，可以$\sqrt{n}$求解单次查询，时间复杂度$O(q\ast \sqrt{n})$是可行的。

对于区间$[L,R]$问题，转化为函数差

$$f(x)=[1,x]的累加和$$
$$g(l,r)=f(r)-f(l-1)$$

关键在于如何求解这个函数$f(x)$

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

// 时间复杂度为O(\sqrt n)
int64 f(int v) {
    int64 r = 0;
    int acc = 0;
    for (int i = 1; acc <= v; i++) {
        r += (i * min(v - acc, i));
        acc += i;
    }
    return r;
}

int main() {
    int q;
    cin >> q;
    while (q-- > 0) {
        int l, r;
        cin >> l >> r;
        int64 r1 = f(l - 1);
        int64 r2 = f(r);
        cout << r2 - r1 << endl;
    }
    return 0;
}

当然这题是可以把单次查询优化为$O(1)$的

---

P序列

其实是一道思维题。

可以从构造的角度，去解这道题，就会发现很容易。

因为其是一种山峰状的数组, 左侧非严格递增，右侧非严格递减。

对数进行分组，按值排序，然后放置于数组。

1. 最大值先放于中间
2. 按序依次放置其他数$v_i$，若个数为$cn{t}_{v_i}$，其放置左右侧的方案数总共为$cn{t}_{v_i}+1$

根据乘法原理，最终的总方案数为

$$\prod (cn{t}_{v_i}+1),v_i\ne v_{max}$$

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int64 mod = 998244353l;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    map<int, int> hp;

    int mz = -0x3f3f3f3f;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        hp[x]++;
        mz = max(mz, x);
    }

    long long res = 1l;
    for (auto &[k, v] : hp) {
        if (k != mz) {
            res = res * (v + 1) % mod;
        }
    }
    cout << res << endl;

    return 0;
}

---