179

A - Partition

给你整数 $N$ 和 $K$ 。

长度为 $N$ 的整数序列 $X = (X_{1}, X_{2}, \dots, X_{N})$ 的累积和定义为长度为 $N + 1$ 的序列 $Y = (Y_{0}, Y_{1}, \dots, Y_{N})$ 如下：

$Y_{0} = 0$
$Y_{i} = \sum_{j = 1}^{i} X_{j} (i = 1, 2, \dots, N)$

长度为 $N$ 的整数序列 $X = (X_{1}, X_{2}, \dots, X_{N})$ 如果且仅当它满足以下条件时，才称为良序列：

在 $X$ 的累积和中，任何小于 $K$ 的值都出现在任何不小于 $K$ 的值之前。
- 形式上，对于 $X$ 的累积和 $Y$ ，对于任意一对整数 $(i, j)$ ，若 $0 \leq i, j \leq N$ ，若 $(Y_{i} < K$ 和 $Y_{j} \geq K)$ ，则 $i < j$ 。

给你一个长度为 $N$ 的整数序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 。请判断 $A$ 中的元素能否重新排列成一个好的序列。如果可以，请打印一个这样的重排结果。

本题的突破点在 $Y_{0} = 0$ 上面。

当 $k \geq 1$ 时：由于 $Y_{0} < k$ 满足，若将 $X$ 数组按照升序排列，则一定能满足左边 $< k$ ，右边 $\geq k$

当 $k \leq 0$ 时：由于 $Y_{0} \geq k$ 满足，这时后面的数字都要满足 $pre[i] \geq k$ ，不然就无解，要尽量满足 $pre[i] \geq k$ ，则按照降序排列能满足。

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1), pre(n + 1);

    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end());

    if (k <= 0) {
        reverse(a.begin() + 1, a.end());
        for (int i = 1;i <= n;i++)pre[i] = pre[i - 1] + a[i];
        for (int i = 1;i <= n;i++) {
            if (pre[i] < k) {
                cout << "No\n";return;
            }
        }
    }
    cout << "Yes\n";
    for (int i = 1;i <= n;i++)cout << a[i] << " ";
}

B - Between B and B

给你一个长度为 $M$ 的序列 $(X_{1}, X_{2}, \dots, X_{M})$ ，由介于 $1$ 和 $M$ 之间的整数（包括首尾数）组成。

请求模为 $998244353$ 的序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 的个数。

之间的整数组成的长度为 $N$ 的序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 的个数：

对于每个 $B = 1, 2, \dots, M$ ，在 $A$ 中 $B$ 的任意两个不同出现点（包括两端）之间存在值 $X_{B}$ 。(包括两端）。

更正式地说，对于每个 $B = 1, 2, \dots, M$ ，必须满足以下条件：

对于每一对整数 $(l, r)$ ，即 $1 \leq l < r \leq N$ 和 $A_{l} = A_{r} = B$ ，都存在一个整数 $m$ （ $l \leq m \leq r$ ），即 $A_{m} = X_{B}$ 。

Solution

状压DP

本题的空间其实有点紧张的，可以像 jiangly 一样滚动数组优化。

#define int long long
constexpr int mod = 998244353;
int f[10010][1 << 11];
void solve() {
    int m, n;cin >> m >> n;
    vector<int> mask(m + 1);
    for (int i = 1;i <= m;i++) {
        int x;cin >> x;
        mask[x] |= (1 << (i - 1));
    }
    f[0][(1 << m) - 1] = 1;
    for (int i = 0;i < n;i++) {
        for (int j = 1;j <= m;j++) {
            for (int k = 0;k < 1 << m;k++) {
                if ((k >> j - 1) & 1) {
                    f[i + 1][(k ^ (1 << j - 1)) | mask[j]] += f[i][k];
                    f[i + 1][(k ^ (1 << j - 1)) | mask[j]] %= mod;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0;i < 1 << m;i++) {
        ans += f[n][i];ans %= mod;
    }
    cout << ans << '\n';
}

Q: 如何化简为无 $\oplus$ 的形式？如何得到的？(挖坑...)

然后是补昆明邀请赛和西安邀请赛，然后百度之星+ABC 板刷+CF 板刷

鉴于时间紧张 C 题先不补(挖坑...)