WC2024 T1 题解

Register_int · 2024-02-02 09:40:29 · 题解

场外选手。

不妨算出每个题 i 在多少种方案中能被提交。题目中“将一道题状态改为结果不可见”显然只是将题目扔到末尾，所以：

• 当 i 结果可见时，他能否提交只跟编号比他小的题目有关。
• 当 i 结果不可见时，他能否提交只跟编号比他大的题目有关。

因此：

• 当 i 结果可见时，对于每一种选择在他之前的可见的题目 S，且满足 \sum_{j\in S} t_j\le T-t_i 的方案，a_i 会产生 2^{n-i} 的贡献。

• 当 i 结果不可见时，对于每一种选择在他之后的可见的题目 S，且满足 \sum_{j\in S}t_j\le T-\sum_{j\le i}t_j 的方案，a_i 会产生 2^{i-1} 的贡献。

相当于统计有多少个子集和 \le 一个数。上背包朴素转移，时间复杂度 O(nT)。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e2 + 10;
const int MAXM = 3e5 + 10;
const int mod = 998244353;

int n, m, a[MAXN], t[MAXN];

ll dp[MAXM], p2[MAXM], sum[MAXM], ans, tot;

int main() {
    scanf("%*d%d%d", &n, &m), *dp = *p2 = 1;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &t[i]), sum[i] = sum[i - 1] + t[i];
    for (int i = 1; i <= n; i++) p2[i] = p2[i - 1] * 2 % mod;
    for (int i = 1; i <= n; i++) {
        tot = 0;
        for (int j = 0; j <= m - t[i]; j++) tot = (tot + dp[j]) % mod;
        ans = (ans + tot * p2[n - i] % mod * a[i]) % mod;
        for (int j = m; j >= t[i]; j--) dp[j] = (dp[j] + dp[j - t[i]]) % mod;
    }
    for (int i = 0; i <= m; i++) dp[i] = 0; *dp = 1;
    for (int i = n; i; i--) {
        tot = 0;
        for (int j = 0; j <= m - sum[i]; j++) tot = (tot + dp[j]) % mod;
        ans = (ans + tot * p2[i - 1] % mod * a[i]) % mod;
        for (int j = m; j >= t[i]; j--) dp[j] = (dp[j] + dp[j - t[i]]) % mod;
    }
    printf("%lld", ans);
}

笑话：看到这题出了我直接去抢首 A，然后由于场外看题没记住数据范围，导致数组开小了两次。