题解：P11703 [ROIR 2025] 个人 OI 比赛的原则

ELECTRODE_kaf · 2025-02-16 11:32:00 · 题解

01 背包板子+DFS 拼凑目标值。用 bitset 可通过。很模板的题，评蓝虚高。

设 dp_{i,j}=0/1 表示考虑前 i 个题目，得到恰好 j 分是否可行。转移：dp_{i,j}=dp_{i,j-k}\lor dp_{i-1,j-k}。

const ll N = 1e5 + 10, GOAL = 1e5 + 10;
ll n, goal;
bitset<GOAL> dp[N];
vector<ll> v[N], ans[N];

void dfs(ll p, ll rem, ll lst) {
    if (p == 0) {
        if (rem == 0) {
            rep(i, 1, n) {
                cout << ans[i].size() << '\n';

                for (ll j : ans[i])
                    cout << j + 1 << ' ';

                endl;
            }

            exit(0);
        }
    } else {
        if (lst + 1 <= v[p].size() - 1) {
            rep(i, lst + 1, v[p].size() - 1) {
                if (rem >= v[p][i] and dp[p][rem - v[p][i]]) {
                    ans[p].pb(i);
                    dfs(p, rem - v[p][i], i);
                    ans[p].pop_back();
                }

                if (rem >= v[p][i] and dp[p - 1][rem - v[p][i]]) {
                    ans[p].pb(i);
                    dfs(p - 1, rem - v[p][i], -1);
                    ans[p].pop_back();
                }
            }
        }
    }
}

int main() {
    cin >> n >> goal;

    rep(i, 1, n) {
        ll m;
        cin >> m;

        count(m) {
            ll in;
            cin >> in;
            v[i].pb(in);
        }
    }

    dp[0][0] = 1;

    rep(i, 1, n) {
        for (ll j : v[i]) {
            rep_(k, goal, j) dp[i][k] = dp[i][k] or dp[i][k - j] or dp[i - 1][k - j];
        }
    }

    if (dp[n][goal]) {
        cout << "Yes\n";
        dfs(n, goal, -1);
    } else
        cout << "No";
}