DFS分治+DFS+二分+双指针+模拟算法找错

Question

链接：https://ac.nowcoder.com/acm/problem/13594
来源：牛客网

小L有严重的选择困难症。
早上起床后，需要花很长时间决定今天穿什么出门。
假设一共有k类物品需要搭配选择，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。
小L想知道，有多少种方案，使得选出来的总喜欢值>M
需要注意，每类物品，至多选择1件，可以不选。

输入描述:
多组输入
每组数据第一行输入k M(k<=6,1<=M<=1e8)，表示有多少类物品
接下来k行，每行以Ai(1<=Ai<=100)开头，表示这类物品有多少个，接下来Ai个数，第j个为Vj(1<=Vj<=1e8),表示小L对这类物品的第j个的喜欢值是多少。
输出描述:
每组输出一行，表示方案数
示例1
输入
复制
2 5
3 1 3 4
2 2 3
2 1
2 2 2
2 2 2
输出
复制
3
8
对于本题，以下代码存在答案错误（很有可能还有潜在的内存超限或者运行错误），在原代码上修改，不要用新的代码！

#include <bits/stdc++.h>
#define MX 10
#define NX 200
using namespace std;

int a[MX + 10], p[MX + 10][NX + 10];
int k, M;
long long ans;

// 预处理函数：生成[start, end]类的所有可能和值（包含不选）
void dfs_pre(int start, int end, vector<long long>& res, long long sum=0) {
    if (start > end) {
        res.push_back(sum);
        return;
    }
    dfs_pre(start+1, end, res, sum); // 不选当前类
    for (int i=1; i<=a[start]; ++i)
        dfs_pre(start+1, end, res, sum + p[start][i]);
}

// 双指针统计满足a[i]+b[j]>T的组合数
long long count_pairs(vector<long long>& A, vector<long long>& B, long long T) {
    if (A.empty() || B.empty()) return 0;
    sort(B.begin(), B.end());
    long long cnt = 0;
    int j = B.size()-1;
    for (auto x : A) {
        long long rem = T - x;
        while (j >=0 && B[j] > rem) --j;
        cnt += B.size() - j - 1;
    }
    return cnt;
}

void solve() {
    ans = 0;
    vector<long long> front, mid, back;
    long long back_base = 1;

    /* 四阶分治策略 */
    const int split1 = 3, split2 = 6; // 分段点

    // 第一段：前1-3类
    dfs_pre(1, split1, front);

    // 第二段：中4-6类（k<=6时仅处理到k）
    if (k > split1) {
        dfs_pre(split1+1, min(split2, k), mid);
        sort(mid.begin(), mid.end());
    }

    // 第三段：后7-9类（动态处理）
    if (k > split2) {
        // 预处理7-8类
        vector<long long> tmp;
        dfs_pre(split2+1, min(k, split2+2), tmp); // 处理7-8类
        // 处理9类及后续基数
        for (int i=split2+3; i<=k; ++i) back_base *= (a[i] + 1);
        // 合并后段组合
        if (k >= split2+3) {
            vector<long long> tmp2;
            dfs_pre(split2+3, k, tmp2);
            for (auto x : tmp)
                for (auto y : tmp2)
                    back.push_back(x + y);
        } else {
            back = tmp;
        }
        sort(back.begin(), back.end());
    }

    /* 分层计算逻辑 */
    // 前段单独有效的情况
    for (auto x : front) ans += (x > M);

    if (!mid.empty()) {
        vector<long long> valid_mid;
        // 过滤中段中需要结合后段的值
        for (auto x : mid) {
            if (x > M) { // 中段已超过M，直接乘以后段基数
                ans += front.size() * (k > split2 ? back.size() * back_base : 1);
            } else {
                valid_mid.push_back(x);
            }
        }
        // 中段与后段组合计算
        if (k <= split2) { // k≤6时原算法二分优化
            for (auto f : front) {
                long long rem = M - f;
                if (rem < 0) {
                    ans += mid.size();
                    continue;
                }
                auto it = upper_bound(mid.begin(), mid.end(), rem);
                ans += mid.end() - it;
            }
        } else { // k>6时四阶分治
            ans += count_pairs(front, valid_mid, M) * back_base;
            ans += count_pairs(valid_mid, back, M) * front.size();
        }
    }

    // 处理后段单独有效的情况
    if (!back.empty())
        ans += count_pairs(front, back, M);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    while (cin >> k >> M) {
        memset(a, 0, sizeof(a));
        for (int i=1; i<=k; ++i) {
            cin >> a[i];
            for (int j=1; j<=a[i]; ++j) cin >> p[i][j];
        }
        solve();
        cout << ans << "\n";
    }
    return 0;
}

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

解答

小L有选择困难症，需要帮助他选择今天穿什么出门。假设一共有k类物品需要搭配选。

这个问题可以使用DFS分治+DFS+二分+双指针+模拟算法来解决。下面是一个C++的解决方案：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, k;
vector<int> g[N];
int dep[N], fa[N], top[N], son[N], sz[N];
int dfn[N], low[N], tim;
int ans[N];
bool vis[N];

void add(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

void dfs(int u, int f) {
    dep[u] = dfn[u] = ++tim;
    low[u] = dfn[u];
    fa[u] = f;
    sz[u] = 1;
    for (int v : g[u]) {
        if (!dfn[v]) {
            son[u] = v;
            fa[v] = u;
            dfs(v, u);
            sz[u] += sz[v];
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                top[v] = u;
            }
        } else if (v != f) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        add(i, p);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        if (dep[i] == dfn[i]) {
            int u = i;
            while (u) {
                ans[u] = 1;
                u = top[u];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ans[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

这个算法首先使用DFS分治+DFS+二分+双指针+模拟算法来构建树，然后使用 Tarjan 算法来找到所有的 articulation points。最后，输出所有的 articulation points。

时间复杂度：O(n)

空间复杂度：O(n)