T1 拼数

题意概括

给定一个长度为 $L$ ($1 \le L \le 10^6$) 的字符串 $s$，它由小写字母和数字组成，且至少包含一个 $1 \sim 9$ 的数字。要求从 $s$ 中选取任意多个数字字符（每个字符最多使用一次），按任意顺序拼接成一个正整数。求能拼成的最大正整数。

题目分析

这是一个经典的贪心问题。我们的目标是构造一个值最大的正整数。一个整数的值由两个核心因素决定：它的位数（长度）和高位上的数字大小。

1. 位数最大化： 为了使数值尽可能大，我们应该使用 $s$ 中所有可用的数字字符。如果舍弃任何一个数字，构成的数位数必然 $\le$ 使用所有数字构成的数，因此其值通常更小（除非舍弃的是 $0$，但保留 $0$ 总是优于或等于不保留 $0$）。

2. 高位优先： 在位数相同（即使用所有 $K$ 个可用数字）的前提下，要使数值最大，必须将越大的数字放在越靠前（越高）的数位上。

设 $D$ 为从 $s$ 中提取出的所有数字字符构成的多重集（multiset）。我们的目标是用 $D$ 中的所有元素 $d_1, d_2, \dots, d_k$ (其中 $k = |D|$) 构造一个 $k$ 位数 $N$，使其值最大。

根据贪心策略，我们应该将 $D$ 中的元素按非递增（降序）排列，得到序列 $d'_1, d'_2, \dots, d'_k$，满足 $d'_1 \ge d'_2 \ge \dots \ge d'_k$。

构造的数 $N = d'_1d'_2\dots d'_k$ (这里表示字符串拼接) 即为最大值。

合法性（正整数）： 题目保证 $s$ 至少包含一个 $1 \sim 9$ 的数字。因此，提取出的数字集合 $D$ 必然包含至少一个非 $0$ 字符。当我们将 $D$ 降序排序后，最大的元素 $d'_1$ 必然 $\ge \text{'1'}$ (即 $d'_1 \ne \text{'0'}$)。因此，拼接得到的数 $N$ 绝不会有前导 $0$（除非 $N=0$，但本题保证 $D$ 不全为 $0$），且 $N$ 必然是正整数。

算法流程：

1. 遍历输入字符串 $s$。
2. 将所有数字字符（'0' 到 '9'）提取到一个新的字符串 $d$ 中。
3. 将字符串 $d$ 按降序排序。
4. 输出排序后的字符串 $d$。

复杂度分析： 设 $N = |s|$，$K$ 为 $s$ 中数字的个数 ($K \le N$)。

• 时间复杂度：$O(N)$ 遍历 $s$ 提取数字 + $O(K \log K)$ 排序数字。由于 $K \le N$，总时间复杂度为 $O(N \log N)$。
• 空间复杂度：$O(K)$ 存储提取的数字。最坏情况 $K=N$，空间复杂度为 $O(N)$。

---

代码

#include<bits/stdc++.h> 

using namespace std;using ll=long long;

void sol() {
    string s; 
    cin >> s;
    
    string d; 
    
    // 遍历s，提取所有数字字符
    for (char c : s) {
        if (c >= '0' && c <= '9') { // 判断是否为数字
            d.push_back(c);
        }
    }
    
    // 贪心策略：要使数字最大，必须将大的数字放在高位
    // 故对所有提取的数字进行降序排序
    sort(d.rbegin(), d.rend());
    
    // 输出拼接成的最大整数
    cout << d << '\n';
}

int main() {

    ios::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
    
    sol();
    
    return 0;
}

T2 座位

题意概括

给定 $n \times m$ 个互不相同的分数 $a_1, \dots, a_{nm}$。将它们按降序排名 $s_1 > \dots > s_{nm}$。座位按列蛇形分配：第 1 列从 $s_1$ 到 $s_n$（行 $1 \to n$），第 2 列从 $s_{n+1}$ 到 $s_{2n}$（行 $n \to 1$），第 3 列从 $s_{2n+1}$ 到 $s_{3n}$（行 $1 \to n$），以此类推。求分数 $a_1$ 所在的座位 $(c, r)$（列, 行）。 数据范围：$1 \le n, m \le 10$, $1 \le a_i \le 100$。

题目分析

核心任务是确定 $a_1$（小 R 的分数）在所有 $n \times m$ 个分数中的降序排名 $k$。我们可以读入 $a_1$，然后读入其余 $n \times m - 1$ 个分数，统计其中大于 $a_1$ 的数量 $cnt$，则 $a_1$ 的 $1$-based 排名 $k = cnt + 1$。得到 $k$ 后，我们分析座位分配规律。

座位分配以 $n$ 个人（一整列）为一个周期。我们将排名 $k$ 转换为 $0$-based 索引 $k' = k - 1$。$0$-based 列索引 $c'$ 可以通过 $c' = \lfloor \frac{k'}{n} \rfloor$ 计算得到。在 $c'$ 列中的 $0$-based 行偏移 $r_{off}$ (从该列的起始方向算起) 为 $r_{off} = k' \pmod n$。蛇形分配的规律取决于列索引 $c'$ 的奇偶性：1. 如果 $c'$ 为偶数（$c' = 0, 2, 4, \dots$），分配方向为自顶向下（行 $0 \to n-1$）。此时 $0$-based 行索引 $r' = r_{off}$。2. 如果 $c'$ 为奇数（$c' = 1, 3, 5, \dots$），分配方向为自底向上（行 $n-1 \to 0$）。

此时 $0$-based 行索引 $r' = (n - 1) - r_{off}$。最后，将 $0$-based 的 $(c', r')$ 转换为 $1$-based 的 $(c, r)$，即 $c = c' + 1$，$r = r' + 1$。由于 $n, m \le 10$，总人数 $nm \le 100$。计算排名 $k$ 的时间复杂度为 $O(nm)$，计算 $(c, r)$ 的时间复杂度为 $O(1)$。总时间复杂度 $O(nm)$，空间复杂度 $O(1)$。

#include <bits/stdc++.h> 

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    int my;
    cin >> my; // 小 R 的分数

    int k = 1; // 1-based 排名
    int tot = n * m;

    for (int i = 1; i < tot; ++i) {
        int x;
        cin >> x;
        if (x > my) {
            k++; // 统计有多少人分数比小 R 高
        }
    }

    k--; // 转换为 0-based 排名 (k')

    int c = k / n; // 0-based 列 (c')
    int r = k % n; // 0-based 行偏移 

    if (c % 2 == 1) { 
        // 如果是奇数列 (c' = 1, 3, ...)，方向自底向上
        r = n - 1 - r; 
    }
    
    // 输出 1-based 结果
    cout << c + 1 << " " << r + 1 << '\n';

    return 0;
}

T3 异或和

题意概括

给定一个长度为 $n$ 的非负整数序列 $a$ 和一个非负整数 $k$。你需要选择序列中尽可能多的不相交的区间 $[l, r]$，使得每个区间的异或和 $a_l \oplus a_{l+1} \oplus \dots \oplus a_r$ 均等于 $k$。求这个最大数量。 数据范围：$1 \leq n \leq 5 \times 10^5$, $0 \leq k < 2^{20}$, $0 \leq a_i < 2^{20}$。

题目分析

本题要求最大数量的不相交区间，是典型的动态规划 (DP) 问题。 我们定义 $s_i = \bigoplus_{t=1}^i a_t$ 为序列 $a$ 的前缀异或和，并令 $s_0 = 0$。根据异或的性质，区间 $[l, r]$ 的异或和为 $s_r \oplus s_{l-1}$。 我们要找的区间 $[l, r]$ 满足 $s_r \oplus s_{l-1} = k$，这等价于 $s_{l-1} = s_r \oplus k$。

定义 $dp[i]$ 表示考虑序列的前 $i$ 个元素 $a_1, \dots, a_i$，能选出的满足条件的不相交区间的最大数量。 计算 $dp[i]$ 时，我们有两种决策：

1. 不选择以 $i$ 结尾的区间。这种情况下，最优解与 $a_1, \dots, a_{i-1}$ 的最优解相同，即 $dp[i] = dp[i-1]$。
2. 选择一个以 $i$ 结尾的区间 $[l, i]$，且其异或和为 $k$。为了使区间总数最大，我们应在 $a_1, \dots, a_{l-1}$ 中也取最优解。设 $j = l-1$，则我们需要找到 $j < i$ 且 $s_j = s_i \oplus k$，使得 $dp[j] + 1$ 最大。

综合两种情况，DP 转移方程为：

$$dp[i] = \max(dp[i-1], \max_{j < i, \text{s.t. } s_j = s_i \oplus k} \{dp[j] + 1\}) $$

直接计算 $\max_{j < i}$ 会导致 $O(n^2)$ 的复杂度，需要优化。 我们发现，在 $i$ 递增的过程中，对于 $s_i \oplus k$ 这个值，我们只需要找到一个 $j < i$ 使得 $s_j = s_i \oplus k$ 且 $dp[j]$ 最大。 我们可以使用一个辅助数组（或哈希表） $mp$，其中 $mp[x]$ 存储 $\max \{dp[j]\}$，其中 $j$ 满足 $s_j = x$ 且 $j$ 在当前 $i$ 之前。 在遍历 $i$ 从 $1$ 到 $n$ 的过程中，我们维护 $s_i$：

1. 令 $s = s \oplus a[i]$（$s$ 初始为 $0$）。
2. 计算 $dp[i] = dp[i-1]$ （对应决策 1）。
3. 计算目标前缀和 $v = s \oplus k$。
4. 在 $mp$ 中查找 $v$。如果 $mp[v]$ 存在（例如，我们用 $-1$ 初始化 $mp$，则检查 $mp[v] \ne -1$），说明存在 $j < i$ 使得 $s_j = v$。我们用决策 2 更新 $dp[i]$：$dp[i] = \max(dp[i], mp[v] + 1)$。
5. 更新 $mp$：$mp[s] = \max(mp[s], dp[i])$。将 $dp[i]$ 存入 $mp[s_i]$，供后续的 $i' > i$ 使用。

由于 $a_i$ 和 $k$ 均小于 $2^{20}$，所有的 $s_i$ 和 $v$ 也都小于 $2^{20}$。因此 $mp$ 可以是一个大小为 $2^{20}$ 的数组。 时间复杂度：$O(n + M)$，其中 $M = 2^{20}$ (用于 $mp$ 的初始化和访问)。 空间复杂度：$O(n + M)$，用于 $dp$ 数组和 $mp$ 数组。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, k;
int a[500005]; // 存储序列a
int dp[500005]; // dp[i] 表示前i个元素的最大区间数
int mp[1 << 20]; // 映射：mp[x] = max(dp[j]) s.t. s[j] = x

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 初始化 mp 数组，-1 表示该前缀和尚未出现
    memset(mp, -1, sizeof(mp));

    // s[0] = 0, dp[0] = 0
    mp[0] = 0; 

    int s = 0; // 当前的前缀异或和 s[i]
    for (int i = 1; i <= n; i++) {
        s ^= a[i]; // 计算 s[i]

        // 决策1：不选以 i 结尾的区间
        dp[i] = dp[i - 1];

        // 决策2：选择以 i 结尾的区间 [l, i]
        int v = s ^ k; // 寻找目标 s[l-1]，即 s[j]

        if (mp[v] != -1) {
            // 如果存在这样的 j = l-1
            dp[i] = max(dp[i], mp[v] + 1);
        }

        // 更新 mp[s[i]] 为 dp[i] 的最大值
        // 供 i 之后的 j' (j' > i) 使用
        mp[s] = max(mp[s], dp[i]);
    }

    cout << dp[n] << '\n';

    return 0;
}

T4 多边形

题意概括

给定 $n$ 根木棍，长度分别为 $a_1, a_2, \dots, a_n$。需要选出一个下标子集 $S \subseteq \{1, \dots, n\}$，设 $L = \{a_i \mid i \in S\}$ 且 $m = |S|$。该子集 $S$ 能构成多边形的条件是：$m \ge 3$ 且 $\sum_{l \in L} l > 2 \times \max_{l \in L} l$。 求有多少个这样的下标子集 $S$ 满足条件，答案对 998,244,353 取模。

数据范围：$3 \leq n \leq 5,000$，$1 \leq a_i \leq 5,000$。

题目分析

我们考虑使用总方案数减去不合法的方案数。总方案数为 $2^n$。不合法的方案分为两类：

1. 选出的木棍数 $m < 3$。这类方案数

   $$\binom{n}{0} + \binom{n}{1} + \binom{n}{2} = 1 + n + \frac{n(n-1)}{2} $$

2. 选出的木棍数 $m \ge 3$，但不满足 $\sum l_i > 2 \times \max l_i$，即 $\sum l_i \le 2 \times \max l_i$。 设 $S$ 是选出的木棍集合，$l_{\max} = \max_{l \in S}$。令 $S' = S \setminus \{l_{\max}\}$（如果最大值有多个，任取其一）。不合法条件 $\sum l_i \le 2 l_{\max}$ 等价于 $(\sum_{l \in S'} l) + l_{\max} \le 2 l_{\max}$，即 $\sum_{l \in S'} l \le l_{\max}$。

为了不重不漏地统计第二类不合法方案，我们首先将 $n$ 根木棍按长度 $a_i$ 从小到大排序。 我们迭代 $i$ 从 $1$ 到 $n$，并假设 $a_i$ 是当前不合法集合 $S$ 中 下标最大 的那个最大值元素。 我们需要在 $a_i$ 之前（即下标 $j < i$）的元素 $\{a_1, \dots, a_{i-1}\}$ 中选取一个子集 $S'$，使得 $\sum_{l \in S'} l \le a_i$，并且 $m = |S'| + 1 \ge 3$，即 $|S'| \ge 2$。

这可以看作一个01背包计数问题。我们维护一个 $dp$ 数组，$dp[k]$ 表示从 $\{a_1, \dots, a_{i-1}\}$ 中选取子集，使其元素和恰好为 $k$ 的方案数。 当我们从 $i$ 迭代到 $i+1$ 时，$dp$ 数组需要被更新，以包含 $a_i$ 作为可选元素。 设 $A = \max(a_i)$。我们初始化 $dp$ 数组（大小 $A+1$），$dp[0] = 1$，其余为 $0$。 我们按 $i$ 从 $1$ 到 $n$ 循环：

1. 此时 $dp[k]$ 存储的是使用 $\{a_1, \dots, a_{i-1}\}$ 构成和为 $k$ 的方案数。

2. 我们计算 $T = \sum_{k=0}^{a_i} dp[k]$。$T$ 表示从 $\{a_1, \dots, a_{i-1}\}$ 中选取和 $\le a_i$ 的子集 $S'$ 的总方案数。

3. $T$ 包含了 $|S'|=0$ (空集，1种) 和 $|S'|=1$ (共 $i-1$ 种) 的情况。

4. 因此，满足 $\sum S' \le a_i$ 且 $|S'| \ge 2$ 的方案数为 $T - 1 - (i-1)$。我们将此计入不合法方案总数 $inv$。

5. 将 $a_i$ 加入背包，更新 $dp$ 数组，为下一次迭代 $i+1$ 做准备：

   $$dp[k] = (dp[k] + dp[k - a_i]) \pmod{MOD} \quad (\text{for } k \text{ from } A \text{ down to } a_i) $$

   总不合法方案数 $inv$ 即为 $m < 3$ 的方案数加上所有 $i$ 迭代中累加的 $T - i$。 最终答案为 $(2^n - inv) \pmod{MOD}$。

时间复杂度：排序 $O(N \log N)$，DP 过程 $N$ 次迭代，每次迭代 $O(A)$ 查询和 $O(A)$ 更新，总复杂度 $O(N \log N + N \cdot \max(a_i))$。 空间复杂度：$O(\max(a_i))$。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll mod = 998244353;

// 快速幂 p(a, b) = a^b % mod
ll p(ll a, ll b) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    // 总方案数 2^n
    ll ans = p(2, n);

    // 不合法方案数 m < 3
    ll inv = (1 + n + (ll)n * (n - 1) / 2 % mod) % mod;

    int m = a[n - 1]; // 最大ai
    vector<ll> dp(m + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < n; ++i) {
        int mx = a[i];
        
        // 计算 S' 子集和 <= mx 的方案数
        ll tot = 0;
        for (int k = 0; k <= mx; ++k) {
            tot = (tot + dp[k]) % mod;
        }

        // c1 是 |S'|=1 的方案数
        ll c1 = i; 
        // sub 是 |S'| >= 2 的方案数
        ll sub = (tot - 1 - c1 + mod + mod) % mod;

        // 计入不合法方案 (m >= 3 的情况)
        inv = (inv + sub) % mod;

        // 将 a[i] 加入背包
        for (int k = m; k >= a[i]; --k) {
            dp[k] = (dp[k] + dp[k - a[i]]) % mod;
        }
    }

    // (总方案 - 不合法方案) % mod
    cout << (ans - inv + mod) % mod << '\n';

    return 0;
}