题解：P3921 小学数学题

· · 题解

题目

题目链接

P3921 小学数学题

有 n 个人需要过河，编号从 1 到 n，有一传送器，且这个传送器每次只能载 r 个人（传送器可以同时把两侧的人分别运到对岸，但每次运送的总人数不能超过 r）。

另外，在任意时刻，有一些条件需要满足，其中第一种条件有 m_1 个，第二种条件有 m_2 个。

第一种: a 和 b 必须要在湖的同一侧；

第二种 : 当 a 在一侧时，b 和 c 不能同时在湖的另一侧。

求： 至少需要传送器几次到对岸；在保证次数最少的前提下，求方案数。

对于 30 \% 的数据，n \leq 10；

对于另外 10 \% 的数据，m_1=m_2=0；

对于 100 \% 的数据，a,b,c \leq n \leq 15， m_1,m_2 \leq 50，r \leq 10^9。

解析

0~10 分做法

直接输出 -1 0。

30~70 分做法

由于对于 30 \% 分的数据 1 \leq n \leq 10 ，想到状态压缩dp。

设 dp_i 表示到达对面的状态，对于 r > n 的情况，将 r 重新取为 n。

此时只需枚举每次通过传送门的人，bfs即可。

常数卡的好可以拿到 70 分。

代码此处不展示了。

100 分做法

似乎其他题解有更方便的做法，需要的可以看其他人的题解。

此处提供一种做法:

首先，对于 30~70 分的做法，因为其状态转移的次数过多所以使得其超时。

对于状态转移过多的情况，可以重新设计状态进行转移。

其次，使用类似 dijkstra 的方法进行搜索，枚举第 $k$ 个人是否被选中通过传送门，对 $i$ 直接异或即可，不过因为图中的边的权值只有 $0$ 或 $1$，所以可以用双端队列进行优化。 最后，在得到 dp 的值后，我们对其进行类似拓扑排序的方法+dp统计方案数量即可。 （注意:直接在求值的过程中求方案时可能会 WA） 例如以下的转移构成的图： ![图](https://cdn.luogu.com.cn/upload/image_hosting/jewgss86.png) 可能方案由点 $1$ 加到点 $2$ 时，点 $2$ 已经被访问过了，若加到点 $3$ 上，照此操作，对于大数据可能会 TLE，否则会 WA。 时间和空间复杂度都为 $O(n^22^n)$，可以通过本题。 更多细节可以看代码的注释。 ~~（拓扑排序懒得写了，让豆包帮我写了一下 。）~~ ~~（数据太水了，别人暴力优化一下就过了。）~~ ### $Code 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const long long INF = 1e18;

struct State {
    int x, y, z;
    State(int x_, int y_, int z_) : x(x_), y(y_), z(z_) {}
};

int n, m1, m2, r;
long long dp[1 << MAXN][MAXN + 1][MAXN + 1]; // dp[mask][y][z]
long long cnt[1 << MAXN][MAXN + 1][MAXN + 1]; // 方案数
bool can[1 << MAXN]; // 状态mask是否合法
bool vis[1 << MAXN][MAXN + 1][MAXN + 1]; // 是否访问过该状态
vector<State> Bucket[1 << MAXN][MAXN + 1]; // 桶排序降低时间复杂度

// 约束条件
int a[55], b[55]; // 第一种条件：a和b必须同侧
int c[55], d[55], e[55]; // 第二种条件：a在一侧时，b和c不能同时在另一侧

int main() {
    memset(can, true, sizeof(can));
    cin >> n >> m1 >> m2 >> r;

    // 读取第一种约束
    for (int i = 0; i < m1; ++i) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--; // 转为0基
    }

    // 读取第二种约束
    for (int i = 0; i < m2; ++i) {
        cin >> c[i] >> d[i] >> e[i];
        c[i]--; d[i]--; e[i]--; // 转为0基
    }

    // 预处理can数组：检查每个mask是否满足所有约束
    for (int mask = 0; mask < (1 << n); ++mask) {
        // 检查第一种约束
        for (int i = 0; i < m1; ++i) {
            bool a_in = (mask >> a[i]) & 1;
            bool b_in = (mask >> b[i]) & 1;
            if (a_in != b_in) {
                can[mask] = false;
                break;
            }
        }
        if (!can[mask]) continue;

        // 检查第二种约束
        for (int i = 0; i < m2; ++i) {
            bool c_in = (mask >> c[i]) & 1;
            bool d_in = (mask >> d[i]) & 1;
            bool e_in = (mask >> e[i]) & 1;
            // 若c在一侧，d和e都在另一侧，则不合法
            if (d_in != c_in && e_in != c_in) {
                can[mask] = false;
                break;
            }
        }
    }

    // 初始化DP
    for (int mask = 0; mask < (1 << n); ++mask) 
        for (int y = 0; y <= n; ++y) 
            for (int z = 0; z <= n; ++z) 
                dp[mask][y][z] = INF;
    dp[0][0][0] = 0;

    // 0-1 BFS计算最少次数
    deque<State> q;
    q.emplace_back(0, 0, 0);

    while (!q.empty()) {
        State s = q.front();
        q.pop_front();

        int mask = s.x;
        int y = s.y;
        int z = s.z;

        if (vis[mask][y][z]) continue;
        if (dp[mask][y][z] > dp[(1 << n) - 1][0][0]) continue;
        vis[mask][y][z] = true;

        // 当传送器在原岸（y=0），当前状态必须合法
        if (y == 0 && !can[mask]) continue;

        // 若所有妖精都处理完毕（z == n），可以传送一次
        if (z == n) {
            int new_mask = mask;
            int new_y = 0;
            int new_z = 0;
            if (dp[new_mask][new_y][new_z] > dp[mask][y][z] + 1) {
                dp[new_mask][new_y][new_z] = dp[mask][y][z] + 1;
                q.emplace_back(new_mask, new_y, new_z);
            }
        } else {
            // 不选第z只妖精
            int new_mask = mask;
            int new_y = y;
            int new_z = z + 1;
            if (dp[new_mask][new_y][new_z] > dp[mask][y][z]) {
                dp[new_mask][new_y][new_z] = dp[mask][y][z];
                q.emplace_front(new_mask, new_y, new_z); // 0 cost，放前面
            }

            // 选第z只妖精（如果传送器还能装）
            if (y < r) {
                new_mask = mask ^ (1 << z);
                new_y = y + 1;
                new_z = z + 1;
                if (dp[new_mask][new_y][new_z] > dp[mask][y][z]) {
                    dp[new_mask][new_y][new_z] = dp[mask][y][z];
                    q.emplace_front(new_mask, new_y, new_z); // 0 cost，放前面
                }
            }
        }
    }

    // 目标状态：所有妖精到对岸（mask=(1<<n)-1），传送器在原岸（y=0），处理完毕（z=0）
    int target_mask = (1 << n) - 1;
    long long min_steps = dp[target_mask][0][0];
    if (min_steps >= INF) {
        cout << "-1 0" << endl;
        return 0;
    }

    // 统计方案数：反向拓扑排序
    memset(cnt, 0, sizeof(cnt));
    cnt[target_mask][0][0] = 1;

    // 收集所有有效状态，并按dp值从大到小排序，同一dp值按z从大到小排序
    vector<State> states;
    for (int mask = 0; mask < (1 << n); ++mask) 
        for (int y = 0; y <= n; ++y) 
            for (int z = 0; z <= n; ++z) 
                if (vis[mask][y][z] && dp[mask][y][z] <= min_steps) 
                    Bucket[dp[mask][y][z]][z].emplace_back(mask, y, z);

    // 排序：先按dp值降序，再按z降序
    for (int i = min_steps; i >= 0; --i)
        for (int j = n; j >= 0; --j)
            for (int k = Bucket[i][j].size() - 1; k >= 0; --k)
                states.push_back(Bucket[i][j][k]);

    // 处理每个状态，计算方案数
    for (const State& s : states) {
        int mask = s.x;
        int y = s.y;
        int z = s.z;
        long long current_cnt = cnt[mask][y][z];
        if (current_cnt == 0) continue;

        // 情况1：当前状态是由"不选第z-1只妖精"转移而来
        if (z > 0) {
            int prev_z = z - 1;
            int prev_y = y;
            int prev_mask = mask;
            if (vis[prev_mask][prev_y][prev_z] && dp[prev_mask][prev_y][prev_z] == dp[mask][y][z]) {
                cnt[prev_mask][prev_y][prev_z] += current_cnt;
            }
        }

        // 情况2：当前状态是由"选第z-1只妖精"转移而来
        if (z > 0 && y > 0) {
            int fairy = z - 1;
            int prev_mask = mask ^ (1 << fairy);
            int prev_y = y - 1;
            int prev_z = z - 1;
            if (prev_y < r && vis[prev_mask][prev_y][prev_z] && dp[prev_mask][prev_y][prev_z] == dp[mask][y][z]) {
                cnt[prev_mask][prev_y][prev_z] += current_cnt;
            }
        }

        // 情况3：当前状态是由"传送"步骤转移而来（即当前状态是传送后的状态）
        if (y == 0 && z == 0) {
            int prev_z = n;
            int prev_mask = mask;
            for (int prev_y = 1; prev_y <= n; ++prev_y) { // 传送时至少有1只妖精
                if (prev_y > r) continue; // 传送时数量不超过r
                if (vis[prev_mask][prev_y][prev_z] && dp[prev_mask][prev_y][prev_z] == dp[mask][y][z] - 1) {
                    cnt[prev_mask][prev_y][prev_z] += current_cnt;
                }
            }
        }
    }

    // 初始状态的方案数
    long long total = cnt[0][0][0];
    cout << min_steps << " " << total << endl;

    return 0;
}