【2024年浙江工商大学程序设计竞赛新生赛（同步赛）部分题解】

比赛链接

C. 交换

题目大意

给定一个长度为 $n$ 的数组 $a$。一开始你有一个总和 $s=0$。

现在你需要做 $n$ 次操作，第 $i$ 次操作的流程如下（$1⩽i⩽n$)：

• 选择一个下标 $p\in [1,n)$，然后交换 $a[p],a[p+1]$（如果你不想选，这一小步可以跳过）；
• $s:=s+a[i]$；

求 $n$ 次操作结束后你能获得的最大的 $s$。

数据范围

• $2⩽n⩽500$；
• $1⩽a_i⩽10^6$；

Solution

我们观察这个数据范围，一眼 $O(n^3)$ 的解法，而且大概率 $dp$。只不过有可能是 $O(n^2)$ 的状态，$O(n)$ 的转移；还有可能是 $O(n^3)$ 的状态，以及需要优化成 $O(1)$ 的转移。

首先，我们的状态需要操作次数 $i$，因为每个操作次数要加的 $a[i]$ 不一样。其次，我们还要交换次数 $j$，因为每次操作可以不选下标 $p$ 进行交换。最后，我们还要知道交换后 $a[i]$ 变成了什么，即 $a[i]:=a[k]$，我们仅需记录这个 $k$。

这样就确定了我们的状态是 $O(n^3)$ 的，因此我们一定需要 $O(1)$ 的优化转移。

设 $dp[i][j][k]$ 表示进行了 $i$ 次操作，已经做了 $j$ 次交换，将 $a[i]:=a[k]$ 能得到的最大 $s$。

状态转移：

• $dp[i][j][k]=dp[i-1][j-1][k]+a[k]$，表示第 $i$ 次操作要交换 $a[i-1]$ 和 $a[i]$，而 $a[i-1]$ 在上一次操作中已经有 $a[i-1]:=a[k]$；
• $dp[i][j][k]=dp[i-1][j-|i-k|][k_1]+a[k],k_1<k$。
  • 满足的条件有 $j-|i-k|⩾0$，即 $\max (0,i-j)⩽k⩽\min (n,i+j)$；
  • $|i-k|$ 表示把 $a[k]$ 挪到 $a[i]$ 需要 $|i-k|$ 交换；
  • 除此之外，$k_1<k$ 表示第 $i-1$ 次操作可以交换到 $a[i-1]$ 的为 $a[k_1]$。原因如下：
    • 如果 $k_1>k$，说明它比 $a[k]$ 更值，才会花更大的代价（交换次数）将它换到前面来，这样的话应该是 $a[k_1]$ 一路平推后面的一段区间，那就只有 $k_1=k$ 的可能；
    • 但如果 $k_1=k$，按照表达式就是 $dp[i][j][k]=dp[i-1][j][k]+a[k]$，显然不对，这表示原先在 $i-1$ 的 $a[k]$ 凭空到了 $i$ 的位置。
  • 这个表达式如果枚举 $k_1\in [1,k]$，是 $O(n)$ 的转移，不符合我们的要求，因此需要优化。考虑到我们要 $dp[i][j][k]$ 最大，那只要选出最大的 $dp[i-1][j-|i-k|][k_1],k_1<k$ 即可，这就相当于求一个前缀最大值，用一个二维数组记录后两维的前缀最大值即可。

时间复杂度 $\mathcal{O}(n^3)$

• 这份代码跑了 $390ms$，按理来说 $500^3=1.25\times 10^8$，我们是需要卡点常的，但是牛牛机子比较厉害，再加上转移方程对 $k$ 的限制，大概率是 $O(\frac{n^3}{2})$ 这样的复杂度，常数自然少了一半，所以可以比较快速通过。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &a) {
    for (auto &x: a) {
        is >> x;
    }
    return is;
}

constexpr int inf = 1E9;

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

    std::vector<int> a(n);
    std::cin >> a;

    std::vector dp(n + 1, std::vector(n, -inf));
    std::vector max(n + 1, std::vector(n + 1, 0));
    for (int i = 0; i < n; i++) {
        std::vector ndp(n + 1, std::vector(n, -inf));
        for (int j = 1; j <= i + 1; j++) {
            for (int k = 0; k < n; k++) {
                ndp[j][k] = dp[j - 1][k] + a[k];
            }
        }
        for (int j = 0; j <= i + 1; j++) {
            for (int k = 0; k < n; k++) {
                max[j][k + 1] = std::max(max[j][k], dp[j][k]);
            }
        }
        for (int j = 0; j <= i + 1; j++) {
            for (int k = std::max(i - j, 0); k <= i + j and k < n; k++) {
                ndp[j][k] = std::max(ndp[j][k], max[j - std::abs(i - k)][k] + a[k]);
            }
        }
        dp.swap(ndp);
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < n; j++) {
            ans = std::max(ans, dp[i][j]);
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

F. 感谢庆典的MEX

题目大意

给定一个长度为 $n$ 的非负整数数组 $a$，再给定一个正整数 $m$。

现在你可以进行任意次操作，使得 $mex(a)$ 最大化。每次操作如下：

• 选择下标 $i\in [1,n]$，然后 $a_i:=\lfloor \frac{a_i}{m}\rfloor$；

其中 $mex(a)$ 指的是数组 $a$ 中未出现的最小非负整数，例如 m e x ( { 0 , 1 , 3 } ) = 2 mex(\lbrace0, 1, 3\rbrace) = 2 mex({0,1,3})=2。

数据范围

• $1⩽n⩽10^5$；
• $1⩽m⩽10^{18}$；
• $0⩽a_i⩽10^{18}$；

Solution

首先讨论特殊情况 $m=1$。这种情况下怎么操作数组都不会发生变化，因此相当于直接求 $mex(a)$。这里我用的方式是将数组 $a$ 排序去重，然后 $O(n)$ 遍历 $a$ 看哪个没出现。

下面是 $m>1$ 的情况。

首先 $mex(a)\ne 0$，因为我们一定可以把 $\forall a_i$ 除以 $m$ 下取整除到 $0$。

其次 $mex(a)⩽n$，因为数组总共就 $n$ 个元素，最多 $0,1,\cdots ,n-1$ 全出现一遍。

再次就是 $mex(a)$ 具有二段性。假设现在我们构造了一个 $mex(a)=k$，那现在我们任选一个非负整数 $u(u<k)$，只要有 $a_i=u$，就令 $a_i:=\lfloor \frac{a_i}{m}\rfloor$。这样一来，就一定没有任何 $u$ 出现在 $a$ 里，这样 $mex(a)=u<k$。

综上，我们可以在 $[1,n]$ 内二分 $mex(a)$。下面我们讨论 $check$ 函数怎么写。

对于确定的 $mex$，若 $a_i⩾mex$ 就一直除以 $m$ 直到 $a_i<mex$。

• 若 $a_i=0$，直接记录；
• 否则 $a_i>0$，若 $a_i$ 出现过，就继续除以 $m$，直到 $a_i=0$ 或 $a_i$ 没出现过。

最后记录 $[0,mex)$ 内有多少数出现即可，若 $0,1,\cdots ,mex-1$ 均出现了，就可以尝试扩大 $mex$。

有个减小常数的技巧，就是如果有 $a_i⩾n$，就提前预处理不断除以 $m$ 直到 $a_i<n$。

时间复杂度 $\mathcal{O}(n\cdot \log n\cdot {\log }_m\max (a))$

• 算下来极限大约是 $9.6\times 10^7$ 的计算量，实际上跑出来是 $1365ms$，算是常数稍大了。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &a) {
    for (auto &x: a) {
        is >> x;
    }
    return is;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    i64 m;
    std::cin >> n >> m;

    std::vector<i64> a(n);
    std::cin >> a;

    std::ranges::sort(a);

    if (m == 1) {
        auto ua = std::ranges::unique(a);
        a.erase(ua.begin(), ua.end());
        int lst = 0;
        for (auto x: a) {
            if (x != lst) {
                break;
            }
            lst++;
        }
        std::cout << lst << "\n";
        return 0;
    }

    for (auto &x: a) {
        if (x >= n) {
            x /= m;
        }
    }
    auto check = [&](int mex) {
        std::vector<short> has(mex);
        for (auto x: a) {
            while (x >= mex or (x > 0 and has[x])) {
                x /= m;
            }
            has[x] = 1;
        }
        return std::accumulate(has.begin(), has.end(), 0) == mex;
    };

    int lo = 1, hi = n;
    while (lo < hi) {
        int mid = lo + hi + 1 >> 1;
        if (check(mid)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    std::cout << hi << "\n";
    
    return 0;
}

G. 约数和

题目大意

定义 $F(n)$ 表示正整数 $n$ 在 $[1,n]$ 的约数个数。

给定两个正整数 $n,m$，求 $\sum _{i=n}^{m}F(i)$，答案对 $998244353$ 取模。

数据范围

• $1⩽n<m⩽10^9$；

Solution

这种题显然是 $O(\sqrt{n})$ 的，要么是分解质因数，要么是整除分块。

首先用前缀和拆开，答案为$\sum _{i=1}^{m}F(i)-\sum _{i=1}^{n-1}F(i)$。然后考虑化简 $\sum _{i=1}^{n}F(i)$。

$$\begin{array}{rl}\sum _{i=1}^{n}F(i)& =\sum _{i=1}^n\sum _{j=1}^i[j\mid i]\\ & =\sum _{j=1}^n\sum _{i=j}^n[j\mid i]\\ & =\sum _{j=1}^n\sum _{i=1}^{\lfloor \frac{n}{j}\rfloor }1\\ & =\sum _{j=1}^{n}s\left(\lfloor \frac{n}{j}\rfloor \right)\end{array}$$

其中 $s(x)=\frac{x(x+1)}{2}$。

到这里就可以明显看到 整除分块 了，如果没学过可以先学一下。

时间复杂度 $\mathcal{O}(\sqrt{m}+\sqrt{n})$

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
     
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
 
template<>
int MInt<0>::Mod = 998244353;
 
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
 
constexpr int P = 998244353;
using Z = MInt<P>;

int next(int n, int x) {
    return n / (n / x);
}

Z s(int n) {
    return Z(n) * (n + 1) / 2;
}

Z calc(int n) {
    Z ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = next(n, l);
        ans += (r - l + 1) * s(n / l);
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;
    n--;

    std::cout << calc(m) - calc(n) << "\n";
    
    return 0;
}

I. 数字重组

题目大意

对于一个非负整数 $x$，你可以 任意重排 整数中每个数字的位置，允许有前导零。

对于重排后的数字 $x^{\prime }$，我们按照如下规则计算权值：

• 将这个数字 从低位到高位 每 $3$ 位分成一组，每组的权值为这组数字所表示的大小，总权值为所有组的权值之积；
• 若分组后组内数字不足 $3$ 位则在高位补 $0$；
• 若总位数是 $3$ 的倍数，就没有再补 $3k(k\in N^{+})$ 位高位 $0$ 的说法；

请计算通过重排能得到的最大总权值。

数据范围

• $0⩽x⩽10^9$；

Solution

模拟题。

只要把 $x$ 看成字符串，然后用 next_permutation 函数进行阶乘型枚举。对每个 $x^{\prime }$，我们从低到高三位三位枚举，用 $x^{\prime }.size()>i\times 3$ 判断是否要补高位 $0$，其中 $i\in [0,3]$。

时间复杂度 $\mathcal{O}(\lceil {\log }_{10}x\rceil !\times {\log }_{10}x)$

• 跑满四舍五入大约是 $4\times 10^7$ 的计算量，实测 $583ms$，可能我这写法常数稍大。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;
	
    std::vector<int> ord(s.size());
    // std::ranges::iota(ord, 0); C23 写法牛牛不支持
    std::iota(ord.begin(), ord.end(), 0);

    int ans = 0;
    do {
        std::string t;
        for (int i: ord) {
            t += s[i];
        }
        int res = 1;
        for (int i = 0; i <= 3 and t.size() > i * 3; i++) {
            while (t.size() < (i + 1) * 3) {
                t = '0' + t;
            }
            res *= std::stoi(t.substr(t.size() - (i + 1) * 3, 3));
        }
        ans = std::max(ans, res);
    } while (std::next_permutation(ord.begin(), ord.end()));

    std::cout << ans << "\n";
    
    return 0;
}