2019牛客暑期NOIP真题班提高组5-DFS

1. 传染病控制

来源：NOIP2003提高组 https://ac.nowcoder.com/acm/contest/251/D

算法知识点: 搜索

复杂度： $O(2^n)$

解题思路：

由于这道题目的数据较弱，且贪心算法均有反例，因此直接暴搜出所有切割方案，保留最小值即可。

首先预处理出每一层的节点集合，以及每棵子树的大小。

然后从第一层开始，依次枚举每一层中删除哪棵子树，枚举之后通过深度优先遍历，将整棵子树中的边全部标记为不可选，再递归到下一层继续枚举。递归结束时需要再次深度优先遍历整棵子树，将每条边的状态恢复为可选。

当枚举到最后一层时，更新最小值。

暴力枚举过程中需要维护当前已经删除的节点总数。

C++ 代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; const int N = 310,
    M = 610;

int n, m;
int h[N], e[M], ne[M], c[M], idx;
int size[N];
vector<int> level[N];

int ans = N, max_depth;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs_level(int u, int depth, int father)
{
    size[u] = 1;
    max_depth = max(max_depth, depth);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father)
        {
            level[depth].push_back(i);
            size[u] += dfs_level(j, depth + 1, u);
        }
    }
    return size[u];
}

void dfs_draw(int i, bool color)
{
    c[i] = color;
    for (int j = h[e[i]]; j != -1; j = ne[j])
        if (j != (i ^ 1))
            dfs_draw(j, color);
}

void dfs(int u, int s)
{
    ans = min(ans, n - s);

    if (u == max_depth) return;

    for (auto i: level[u])
        if (!c[i])
        {
            dfs_draw(i, true);
            dfs(u + 1, s + size[e[i]]);
            dfs_draw(i, false);
        }
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs_level(1, 0, -1);

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}

2. 靶形数独

来源：NOIP2009提高组 https://ac.nowcoder.com/acm/contest/257/D

算法知识点: 搜索，剪枝

复杂度： $O(9^{81})$

解题思路：

在搜索时分别记录每行、每列、每个九宫格内当前未填写的数字有哪些。
这里采用位运算来加速：

每行、每列、每个九宫格内，分别用一个9位的二进制数来表示哪些数字可填。
每个空格内所有可选的数字就是其所在行、列、九宫格内可选数字的交集，这里直接将三个9位二进制数按位与(&)即可求出交集，然后通过lowbit运算可以快速枚举出所有是1的位。

另外还需要优化搜索顺序，每次选择分支最少的空格来枚举。

C++ 代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 9;

int ones[1 << N], map[1 << N];
int row[N], col[N], cell[3][3];
int g[N][N];
int ans = -1;

inline int lowbit(int x)
{
    return x &-x;
}

void init()
{
    for (int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cell[i][j] = (1 << N) - 1;
}

// 求可选方案的交集
inline int get(int x, int y)
{
    return row[x] &col[y] &cell[x / 3][y / 3];
}

inline int get_score(int x, int y)
{
    return min(min(x, 8 - x), min(y, 8 - y)) + 6;
}

bool dfs(int cnt, int score)
{
    if (!cnt)
    {
        ans = max(ans, score);
        return false;
    }

    // 找出可选方案数最少的空格
    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (!g[i][j])
            {
                int t = ones[get(i, j)];
                if (t < minv)
                {
                    minv = t;
                    x = i, y = j;
                }
            }

    for (int i = get(x, y); i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];

        // 修改状态
        row[x] -= 1 << t;
        col[y] -= 1 << t;
        cell[x / 3][y / 3] -= 1 << t;
        g[x][y] = t + 1;

        if (dfs(cnt - 1, score + get_score(x, y) *(t + 1))) return true;

        // 恢复现场
        row[x] += 1 << t;
        col[y] += 1 << t;
        cell[x / 3][y / 3] += 1 << t;
        g[x][y] = 0;
    }

    return false;
}

int main()
{
    for (int i = 0; i < N; i++) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i++)
    {
        int s = 0;
        for (int j = i; j; j -= lowbit(j)) s++;
        ones[i] = s; // i的二进制表示中有s个1
    }

    init();

    int cnt = 0, score = 0;
    for (int i = 0, k = 0; i < N; i++)
        for (int j = 0; j < N; j++, k++)
        {
            int x;
            scanf("%d", &x);
            g[i][j] = x;
            if (x)
            {
                row[i] -= 1 << x - 1;
                col[j] -= 1 << x - 1;
                cell[i / 3][j / 3] -= 1 << x - 1;
                score += get_score(i, j) *x;
            }
            else cnt++;
        }

    dfs(cnt, score);

    cout << ans << endl;

    return 0;
}

3. Mayan游戏

来源：NOIP2011提高组 https://ac.nowcoder.com/acm/contest/259/F

算法知识点: 搜索，剪枝

复杂度： $O((nm)^5)$

解题思路：

由于最多枚举 $5$ 步，数据范围很小，因此直接暴搜即可。

搜索顺序：依次枚举每一步选择哪个方块，向左右哪个方向移动。

剪枝情况有三种：

向右移动时，如果右侧的方块颜色和当前方块颜色相同，则剪枝。
向左移动时，如果左侧有方块，则直接减掉。
当某种颜色的方块数量大于0小于等于2时，一定无解，直接剪枝。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n;
int g[5][7];
int cnt[11];
int bg[5][5][7];
int bcnt[5][11];
bool st[5][7];

struct Move
{
    int x, y, d;
}
path[5];

void move(int j, int i, int k)
{
    swap(g[i][j], g[k][j]);

    while (true)
    {
        bool flag = false;
        memset(st, false, sizeof st);

        for (int x = 0; x < 5; x++)
        {
            int z = 0;
            for (int y = 0; y < 7; y++)
                if (g[x][y])
                    g[x][z++] = g[x][y];
            while (z < 7) g[x][z++] = 0;
        }

        for (int x = 0; x < 5; x++)
            for (int y = 0; y < 7; y++)
                if (g[x][y])
                {
                    int l = x, r = x;
                    while (l - 1 >= 0 && g[l - 1][y] == g[x][y]) l--;
                    while (r + 1 < 5 && g[r + 1][y] == g[x][y]) r++;
                    if (r - l + 1 >= 3)
                    {
                        st[x][y] = true;
                        flag = true;
                    }
                    else
                    {
                        l = y, r = y;
                        while (l - 1 >= 0 && g[x][l - 1] == g[x][y]) l--;
                        while (r + 1 < 7 && g[x][r + 1] == g[x][y]) r++;
                        if (r - l + 1 >= 3)
                        {
                            st[x][y] = true;
                            flag = true;
                        }
                    }
                }

        if (flag)
        {
            for (int x = 0; x < 5; x++)
                for (int y = 0; y < 7; y++)
                    if (st[x][y])
                    {
                        cnt[g[x][y]]--;
                        g[x][y] = 0;
                    }
        }
        else break;
    }
}

bool dfs(int u)
{
    if (u == n)
    {
        for (int i = 1; i <= 10; i++)
            if (cnt[i])
                return false;
        return true;
    }

    for (int i = 1; i <= 10; i++)
        if (cnt[i] && cnt[i] <= 2)
            return false;

    memcpy(bg[u], g, sizeof g);
    memcpy(bcnt[u], cnt, sizeof cnt);
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 7; j++)
            if (g[i][j])
            {
                int k = i + 1;
                if (k < 5 && g[i][j] != g[k][j])
                {
                    path[u] = {
                        i, j, 1
                    };
                    move(j, i, k);

                    if (dfs(u + 1)) return true;
                    memcpy(g, bg[u], sizeof g);
                    memcpy(cnt, bcnt[u], sizeof cnt);
                }

                k = i - 1;
                if (k >= 0 && !g[k][j])
                {
                    path[u] = {
                        i, j, -1
                    };
                    move(j, i, k);
                    if (dfs(u + 1)) return true;
                    memcpy(g, bg[u], sizeof g);
                    memcpy(cnt, bcnt[u], sizeof cnt);
                }
            }

    return false;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < 5; i++)
    {
        int j = 0, y;
        while (scanf("%d", &y), y)
        {
            cnt[y]++;
            g[i][j++] = y;
        }
    }

    if (!dfs(0)) puts("-1");
    else
    {
        for (int i = 0; i < n; i++) printf("%d %d %d\n", path[i].x, path[i].y, path[i].d);
    }

    return 0;
}

另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ