搜索题目 专项题解

P4206 [NOI2005] 聪聪与可可

题意简述

给定无向图，以及聪聪和可可的初始位置。

聪聪要抓可可，聪聪先走，可可后走。聪聪一个单位时间内可以走一到两步，每次都是选择最靠近可可的点走，如果有多个距离可可相同的点则选择标号最小的。

可可单位时间只能走一步，并且等概率的选择附近相邻的点或者呆在原地不动。

问平均聪聪走多少个单位时间可以追到可可。

解题报告

考虑爆搜改记搜。

爆搜：需要记住当前聪聪的位置、可可的位置，每次枚举可可下一步走哪（也可以不走），然后让聪聪走两步，继续搜索（此处需要预处理聪聪应该往哪走）。退出条件是聪聪和可可重合 / 一步抓到 / 两步抓到。

改记搜：模板记搜，直接存状态 dp[i][j] 表示聪聪在 i 点，可可在 j 点的期望步数。

预处理跑 n 遍 bfs 得到任意两点间距离即可。

代码实现

// memsearch

const int MAXN = 1000 + 10;

int n, e, c, m;
int sdis[MAXN][MAXN];
int nxtnode[MAXN][MAXN]; // i -> j 最短路要走的下一个点

std::vector<int> G[MAXN];

void bfs(int st, int *dist) {
    static bool vis[MAXN];
    memset(vis, 0, sizeof vis);
    std::queue<int> q; q.push(st); dist[st] = 0; vis[st] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = false;
        forall (G[u], i) {
            int v = G[u][i];
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                if (!vis[v]) { q.push(v); vis[v] = true; }
            }
        }
    }
}

double dp[MAXN][MAXN];

double search(int cat, int mouse) {
    if (dp[cat][mouse] != 0) return dp[cat][mouse];
    double &ans = dp[cat][mouse];
    if (cat == mouse) return ans = 0;
    if (nxtnode[cat][mouse] == mouse) return ans = 1;
    if (nxtnode[nxtnode[cat][mouse]][mouse] == mouse) return ans = 1;
    forall (G[mouse], i) {
        int nv = G[mouse][i];
        ans += search(nxtnode[nxtnode[cat][mouse]][mouse], nv) + 1;
    } ans = (ans + 1 + search(nxtnode[nxtnode[cat][mouse]][mouse], mouse)) / (double) (G[mouse].size() + 1);  //不走的情况
    // 也可以写成
    // ans += search(nxtnode[nxtnode[cat][mouse]][mouse], nv); 
    // ans = (ans + search(nxtnode[nxtnode[cat][mouse]][mouse], mouse)) / (double) (G[mouse].size() + 1) + 1
    // 区别就在于把循环里的 +1 拿出来
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> e >> c >> m;
    rep (i, 1, e) {
        int u, v; cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }
    memset(sdis, 0x3f, sizeof sdis);
    rep (i, 1, n) bfs(i, sdis[i]);
    memset(nxtnode, 0x3f, sizeof nxtnode);
    for (int u = 1; u <= n; ++u) {
        forall (G[u], i) {
            int v = G[u][i];
            for (int d = 1; d <= n; ++d) {
                if (u == d) continue;
                if (sdis[u][d] == sdis[v][d] + 1) {
                    nxtnode[u][d] = std::min(nxtnode[u][d], v);
                }
            }
        }
    } 
    cout << std::fixed << std::setprecision(3) << search(c, m) << endl;
    return 0;
}

P3205 [HNOI2010]合唱队

题意简述

imp

解题报告

手玩发现，原序列中最后一个人会到理想队伍的1位置或者n位置，倒数第二个会到2或n-1

于是设 f[l][r][0/1] 表示理想队伍 [l,r] 中的人还没有确定原序列位置的原序列方案数，且当前放置的人是 l(0)还是r(1)

转移就看看当前人和上一个人是往哪放的

代码实现

const int MAXN = 1000 + 10;
const int HA = 19650827;

int n;
int aa[MAXN];

int f[MAXN][MAXN][2];
// 设 `f[l][r][0/1]` 表示理想队伍 `[l,r]` 中的人还没有确定原序列位置的原序列方案数
// 且本次放置的人是 `l(0)` 还是 `r(1)`

int search(int l, int r, int p) {
    // [^v.........v^]
    // 当前插入^，上次插入v
    if (f[l][r][p] != -1) return f[l][r][p];
    int &ans = f[l][r][p] = 0;
    if (l == r) return ans = 1;
    if (l + 1 == r) return ans = (aa[l] < aa[r]);
    if (p == 0) {
        // [^v.........]
        if (aa[l] < aa[l + 1]) ans += search(l + 1, r, 0);
        // [^.........v]
        if (aa[l] < aa[r]) ans += search(l + 1, r, 1);
    } else {
        // [v.........^]
        if (aa[r] > aa[l]) ans += search(l, r - 1, 0);
        // [.........v^]
        if (aa[r] > aa[r - 1]) ans += search(l, r - 1, 1);
    } ans %= HA;
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    rep (i, 1, n) cin >> aa[i];
    memset(f, -1, sizeof f);
    cout << (search(1, n, 0) + search(1, n, 1)) % HA << endl;
    return 0;
}

P2473 [SCOI2008] 奖励关

题意简述

k 次发钱，有 n 种金额（正数发钱，负数扣钱），每次等概率选一种金额发钱，可以拿也可以不拿。每种金额都有依赖，即拿一些金额必须之前拿过特定的金额。求期望最大钱数。

解题报告

一个长得比较像爆搜的记搜。

状态：当前发了 k 次，拿钱的状态如何（状压）

转移：枚举当前发哪种钱

代码实现

把数组开大了才过。。

const int MAXK = 1000 + 10;
const int MAXN = 17;

int k, n;
double aa[MAXN]; int pre[MAXN];
double dp[MAXK][(1 << MAXN) + 10];
bool vis[MAXK][(1 << MAXN) + 10];

double search(int tm, int stat) {
    if (tm == k + 1) return 0;
    if (vis[tm][stat]) return dp[tm][stat];
    double &ans = dp[tm][stat]; vis[tm][stat] = true;
    for (int i = 1; i <= n; ++i) {
        if ((stat & pre[i]) == pre[i]) ans += std::max(search(tm + 1, stat | (1 << (i - 1))) + aa[i], search(tm + 1, stat)) / (double) n;
        else ans += search(tm + 1, stat) / (double) n;
    } 
    return ans;
}

int main() {
    k = read(); n = read();
    for (int i = 1; i <= n; ++i) {
        aa[i] = read(); int fx = read();
        while (fx != 0) {
            pre[i] |= (1 << (fx - 1));
            fx = read();
        }
    }
    printf("%0.6lf", search(1, 0));
    return 0;
}