标签：10 num int Day4 2024 蓝润 pad return bool

知识总结

搜索算法

剪枝

剪枝是指在搜索树的构造过程中，对某些分支不必继续探索，从而减少搜索树的大小，提高搜索效率。

启发式搜索

启发式搜索是指根据某种启发式函数对搜索树进行排序，使得搜索树中优先扩展那些有可能产生最优解的分支。

迭代加深搜索

迭代加深搜索是指在搜索树的构造过程中，每一步都对当前的搜索树进行扩展，直到搜索树中所有可行解都被找到为止。

A*搜索算法

A*搜索算法是一种启发式搜索算法，它在搜索树的构造过程中，同时考虑了启发式函数和路径长度。

IDA*搜索算法

IDA*搜索算法是一种迭代加深搜索算法，它在搜索树的构造过程中，使用启发式函数来对搜索树进行排序，并对那些分支的扩展进行限制，从而减少搜索树的大小。

题目

这些题目基本都是模拟

T1 蚂蚁

题目描述

在二维平面坐标轴里面，有 N 只蚂蚁，第 i 只蚂蚁所在的点的坐标是(xi, yi)，坐标都是整数。所有蚂蚁的移动速度都相等，都是每秒移动 1 个单位。每只蚂蚁都有一个固定的移动方向，是如下 4 种方向之一，都是平行于坐标轴的：
? N 表示向北（即朝上），则 y 坐标正方向。
? E 表示向东（即朝右），则 x 坐标正方向。
? S 表示向南（即向下），则 y 坐标负方向。
? W 表示向西（即向左），则 x 坐标负方向。
当 2 只或多只蚂蚁在某个时刻碰（不一定是整数时刻）撞到一起，那么这些蚂蚁都会立即消失。例如蚂蚁 A 的初始位置是(0, 0)且方向是向东，蚂蚁 B 的初始位置是(1, 0)且方向是向西，那么 0.5 秒后，两只蚂蚁会在点（0.5, 0）处碰撞，两只蚂蚁瞬间都消失。当所有的碰撞结束后，还有多少只蚂蚁存在？不管蚂蚁最终移动到哪里，只要没有消失，都算是存在。

思路解析

由于蚂蚁碰撞的地点坐标可能是小数，因此读入数据把坐标值乘以 2，那么碰撞后的点的坐标肯定是整数。蚂蚁数量较少，N<= 50，而且坐标值范围是【-2000,2000】，因此蚂蚁碰撞的时刻不会超过 8000，因此可以逐一时刻的模拟蚂蚁爬到了什么位置，然后判断如果在某个特定时刻有两只或多只蚂蚁爬到同一点，那么这些蚂蚁都会消失。可以用 active 数组表示目前还有哪些蚂蚁是活的，然后按照上面的模拟，蚂蚁消失就设 active 为 false。但 8000 个时刻过后，再统计一遍，看还有多少只蚂蚁是活的，输出答案。用 C++的 STL 库减少代码量，当时时间复杂度会差些。本题还有更高效率的算法，请读者思考。如下程序的时间复杂度是：O(800050Log50)。

代码实现

#include <bits/stdc++.h>

using namespace std;

ifstream fin("ant.in");

ofstream fout("ant.out");

const int maxn = 60;

int n, type[256], dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};

string dir;

struct Tant {
    int x, y;
} ant[maxn];

map<pair<int, int>, vector> Map;

bool active[maxn];

int main()

{
    type['N'] = 0;
    type['S'] = 1;
    type['W'] = 2;
    type['E'] = 3;

    fin >> n >> dir;

    for (int i = 1; i <= n; i++)

    {
        fin >> ant[i].x >> ant[i].y;

        ant[i].x *= 2;
        ant[i].y *= 2;
    }

    for (int i = 1; i <= n; i++)
        active[i] = true;

    for (int t = 1; t <= 8001; t++)

    {
        Map.clear();

        for (int j = 1; j <= n; j++)
            if (active[j])

            {
                int x = ant[j].x + t * dx[type[dir[j - 1]]];

                int y = ant[j].y + t * dy[type[dir[j - 1]]];

                Map[make_pair(x, y)].push_back(j);
            }

        map<pair<int, int>, vector>::iterator it;

        for (it = Map.begin(); it != Map.end(); it++)

        {
            vector vec = it->second;

            int s = vec.size();

            if (s <= 1)
                continue;

            for (int k = 0; k < s; k++)
                active[vec[k]] = false;
        }
    }

    int ans = 0;

    for (int i = 1; i <= n; i++)
        if (active[i])
            ans++;

    fout << ans << endl;

    return 0;
}

T2 士兵训练

题目描述

N 个士兵排成一队进行军事训练，每个士兵的等级用 1...K 范围内的数来表示，长官每隔 1 小时就随便说出 M 个等级 a1,a2…am（1≤ai≤K，M 个等级中允许有重复），如果这 M 个等级组成的序列是排成一队的 N 个士兵等级序列的子序列，那么训练继续；否则训练结束。长官想知道，M 至少为多少时，训练才有可能结束。
例：士兵等级序列为 1 5 3 2 5 1 3 4 4 2 5 1 2 3，长官说出的等级序列为 5 4，那么训练继续，如果长官说出的等级序列为 4 4 4，那么训练结束。

思路解析

解题分析：方法很简单，只要从 1 扫到 n，一旦 tot 个等级都至少有一个了，就清空统计数组，同时把 tot + 1，最终答案是 tot + 1。下面我们来证明这为什么是最少的。通过上面的扫描，把士兵分成了 tot 个区域 A1、A2、A3……An。无论长官怎么报，第 i 个等级必然处于 A1~Ai 当中，故最终至少需要 tot + 1 个等级才能使训练结束。
时间复杂度：O(n)
空间复杂度：O(n)

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, k, a[N], ans, cnt;
bool vis[N];
signed main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (vis[a[i]]) {
            continue;
        }
        cnt++;
        vis[a[i]] = true;
        if (cnt == k) {
            cnt = 0;
            ans++;
            memset(vis, 0, sizeof(vis));
        }
    }
    printf("%lld", ans + 1);
    return 0;
}

T3 JLOI2010 世界杯租房

题目描述

南非世界杯组委会指定了在此期间可提供的一些旅馆供球迷租赁，名为阿凡达的即是其中一所。因为阿凡达旅馆房子的数目不超过 26，所以它们可以用 26 个大写字母表示。
有一天，刘经理的电话响了，他接到了一个租赁房屋的请求，要求从 6 月 12 日晚起租到 6 月 19 日中午。于是他察看了预定表，但是并没有发现一间房屋能够直接满足要求。比如房主可能因为一些私人原因需要留在自己的房子中，所以这个游客不得不在其中的一间先住上几天再搬到另一间住上几天。他详细检查了预定表后，对旅客说：“我将你先在 B 安置 3 天，再将你安排到 F 去度过剩余的旅途。”
　　你的目标是使得游客从一间房屋搬到另一间房屋的次数最少。
　　注意在旅馆的计费中，总是将某一天的晚上到第二天的中午视作一天。

思路解析

状压 dp

代码实现

#include <bits/stdc++.h>
using namespace std;
int f[110][30], d[110][30];
char a[110][30];
int n, m, s, t, i, j, k, ans, T;
void print(int s, int i, int j) {
    if (i == t)
        return;
    if (d[i][j] != j) {
        printf("%c: %d-%d\n", 'A' + j - 1, s, i + 1);
        print(i + 1, i + 1, d[i][j]);
    } else {
        print(s, i + 1, j);
    }
    return;
}
int main() {
    while (cin >> m >> n && n) {
        for (i = 1; i <= m; i++)
            scanf("%s", a[i] + 1);
        cin >> s >> t;
        memset(f, 0x3f, sizeof(f));
        f[t][0] = 0;
        for (i = t - 1; i >= s; i--)
            for (j = 1; j <= n; j++)
                if (a[i][j] == 'O')
                    for (k = 0; k <= n; k++)
                        if (f[i + 1][k] + (j != k) < f[i][j]) {
                            f[i][j] = f[i + 1][k] + (j != k);
                            d[i][j] = k;
                        }
        ans = 0x3f3f3f3f;
        for (i = 1; i <= n; i++)
            if (f[s][i] < ans)
                ans = f[s][i], j = i;
        printf("Case %d:\n\n", ++T);
        if (ans == 0x3f3f3f3f) {
            printf("Not available\n");
        } else
            print(s, s, j);
        puts("");
    }
    return 0;
}

T4 ZJOI2002Reading 阅览室

题目描述

一个阅览室每天都要接待大批读者。阅览室开门时间是 0，关门时间是 T。每位读者的到达时间都不一样，并且想要阅读的刊物不超过 5 本。每位读者心里对自己想看的刊物都有一个排位，到达之后他会先去找自己最想看的刊物，如果找不到则去找其次想看的刊物。如果找不到任何他想看的刊物，他会开始等待，直到有一本以上的他想看的刊物被人放回原处。当然，他会先去拿其中自己最想看的刊物。当他看完某一本刊物后，就把它放回原处，接着去找自己没看过的最想看的刊物。如此下去，直到看完所有他想看的刊物为止。矛盾出现在两个人同时想要拿同一本刊物的时候。阅览室为了避免读者之间出现争执，作了一个规定，读者每次在开始等待时先去服务台做一次登记。如果两个人都同时想要一本刊物，那么先登记的读者将得到这本刊物。如果两个人同时登记，那么先到达阅览室的读者将得到刊物。没得到的人就只能去找其他的刊物看。阅览室关门时，所有读者都将被强迫离开阅览室，不再允许继续阅读。

现在阅览室想做一个统计调查，你被要求写一个程序来模拟这个过程计算出所有刊物被阅读的总次数。当某个读者开始阅读某本刊物时，该刊物的被阅读次数就加 1，无论这本刊物最后有没有被读完。

思路解析

枚举当前时刻 $t$
对于每个人，标记该时刻想要拿到的书
根据题目的要求判断冲突情况
对书进行分配

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5, K = 6;
struct reader {
    bool f[K];
    int num, k, ls, s[K], t[K];
    bool operator<(const reader& A) const {
        if (ls != A.ls) {
            return ls < A.ls;
        }
        return num < A.num;
    }
} a[N];
int T, n, ans, bk[N], cnt;
priority_queue<reader> q;
void init() {
    scanf("%d%d", &T, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].num, &a[i].k);
        a[i].ls = ++a[i].num;
        for (int j = 1; j <= a[i].k; j++) {
            scanf("%d%d", &a[i].s[j], &a[i].t[j]);
        }
    }
    return;
}
signed main() {
    init();
    for (int t = 1; t <= T; t++) {
        cnt = 0;
        for (int i = 1; i <= n; i++) {
            q.push(a[i]);
        }
        while (!q.empty()) {
            reader cur = q.top();
            a[n-cnt] = cur;
            q.pop();
            cnt++;
        }
        for (int i = 1; i <= n; i++) {
            if (a[i].ls <= t && a[i].num <= t) {
                for (int w = 1; w <= a[i].k; w++) {
                    if ((bk[a[i].s[w]] <= t) && (!a[i].f[w])) {
                        ans++;
                        a[i].f[w] = true;
                        a[i].ls = bk[a[i].s[w]] = t + a[i].t[w];
                        break;
                    }
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}

T5 NOIP2004-S-4-虫食算

题目描述

https://www.luogu.com.cn/problem/P1092

思路解析

首先我们倒序储存以方便判断是否可行时做的 A+B=C
先想一个暴力：枚举这 n 个字母分别对应哪个数字最后来个判断这样应该是过三个点 30
接着进行剪枝优化

首先定义 flag 若有可行解（一定有且只有一个）时 flag=1
dfs 时先看 flag 是否为 1 若 flag 为 1 则有找到可行解其后的 dfs 完全不需要。（记忆化）
我们不必等全枚举完这 n 个字母再进行判断可以从低位往高位枚举每完成一位后进行判断设上一位的进位为 t 判断是否 (A[i]+B[i]+t)%n==c 若不是 return 0 若是接着 i++
当枚举当前字母要对应哪一个数字时不要正着枚举要倒着枚举这一步可以从 80 分到 AC！！！！！！！（为了尽早用掉大数，防止最高位发生进位

代码实现

#include <bits/stdc++.h>
#pragma GCC optimize(3)  // 手开O3优化
#define N 30
using namespace std;
bool flag, used[N];
int n, a[5][N], num[N];
char s[5][N];
bool check() {
    int add = 0;
    for (int i = n; i >= 1; i--) {
        int A, B, C;
        A = num[a[1][i]], B = num[a[2][i]], C = num[a[3][i]];
        if ((A + B + add) % n != C)
            return false;
        add = (A + B + add) / n;
    }
    return true;
}
bool Prune() {
    if (num[a[1][1]] + num[a[2][1]] >= n)
        return true;
    for (int i = n - 1; i >= 0; i--) {
        int A = num[a[1][i]], B = num[a[2][i]], C = num[a[3][i]];
        if (A == -1 || B == -1 || C == -1)
            continue;
        if ((A + B) % n != C && (A + B + 1) % n != C)
            return true;
    }
    return false;
}
void Print() {
    for (int i = 1; i <= n; i++)
        printf("%d ", num[i]);
    return;
}
bool Check() {
    for (int i = 1; i <= n; i++)
        if (num[i] == -1)
            return false;
    return true;
}
void dfs(int x, int y, int t) {
    if (flag)
        return;
    if (Prune())
        return;
    if (Check()) {
        if (check()) {
            Print();
            flag = true;
        }
        return;
    }
    if (num[a[y][x]] == -1) {
        for (int i = n - 1; i >= 0; i--) {
            if (!used[i]) {
                if (y != 3) {
                    num[a[y][x]] = i;
                    used[i] = true;
                    dfs(x, y + 1, t);
                    used[i] = false;
                    num[a[y][x]] = -1;
                } else {
                    int z = num[a[1][x]] + num[a[2][x]] + t;
                    if (z % n != i)
                        continue;
                    used[i] = true;
                    num[a[y][x]] = i;
                    dfs(x - 1, 1, z / n);
                    used[i] = false;
                    num[a[y][x]] = -1;
                }
            }
        }
    } else {
        if (y != 3)
            dfs(x, y + 1, t);
        else {
            int z = num[a[1][x]] + num[a[2][x]] + t;
            if (Prune())
                return;
            dfs(x - 1, 1, z / n);
        }
    }
    return;
}
void Getid() {
    for (int i = 1; i <= 3; i++)
        for (int j = 0; j < n; j++)
            a[i][j + 1] = s[i][j] - 'A' + 1;
    return;
}
int main() {
    scanf("%d", &n);
    scanf("%s%s%s", s[1], s[2], s[3]);
    Getid();
    memset(num, -1, sizeof(num));
    dfs(n, 1, 0);
    return 0;
}

T6 CQOI2012 模拟工厂

题目描述

https://www.luogu.com.cn/problem/P3161

思路解析

n 只有 15，完全可以 2^n 暴力枚举打算完成哪些订单

问题转化为如何安排每天的策略才能满足枚举的所有订单？
每天的决策有两种：增加生产力、生产商品

显然我们希望第一种操作尽可能排在第二种操作之前
但由于前期的订单要求
可能存在先大量生产产品以满足较近的订单需求然后再提高生产力生产的情况

简单的贪心似乎都是错的

考虑单个订单的情况
显然所有提高生产力的操作排在生产操作之前

现在要求满足全部订单需求，于是可以从当前时刻开始，带上当前剩余的产品数量

逐个考虑 i_i+1，i+1i+2，i+2~i+3 等过程中是在什么时候开始生产的。

但这样的问题在于，可选的生产时间是一个范围，我们并不能确定哪个值对后续的订单最合适。

所以枚举后续所有订单，考虑在满足后续所有订单的基础上，最多可以花多少时间提高生产力。

取 min 即为在保证后续订单可以满足的前提下目前能提升的生产力最大值

总复杂度 O(2^n * n^2)

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
struct P {
    int t, c, p;
    friend bool operator<(P a, P b) {
        return a.t < b.t;
    }
} S[N], a[N];

int n;
int tot;
ll res;
ll js(ll Make, ll Time, ll Need) {
    ll a = 1;
    ll b = Make - Time;
    ll c = Need - Make * Time;
    ll derta = b * b - 4 * a * c;
    if (derta < 0)
        return -1;
    return floor((-b + sqrt(derta)) / 2 / a);
}
void solve(int Now) {
    tot = 0;
    ll num = 0;
    for (int i = 1; i <= n; i++)
        if (Now & (1 << i - 1))
            S[++tot] = a[i], num += a[i].p;
    ll Make = 1;
    ll Have = 0;
    for (int i = 1; i <= tot; i++) {
        ll t = S[i].t - S[i - 1].t;
        ll sum = 0;
        for (int j = i; j <= tot; j++) {
            sum += S[j].c;
            if (sum > Have)
                t = min(t, js(Make, S[j].t - S[i - 1].t, sum - Have));
        }
        if (t < 0)
            return;
        Make += t;
        Have += Make * (S[i].t - S[i - 1].t - t) - S[i].c;
    }
    res = max(res, num);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &a[i].t, &a[i].c, &a[i].p);
    sort(a + 1, a + 1 + n);
    for (int i = 0; i < (1 << n); i++)
        solve(i);
    printf("%lld\n", res);
    return 0;
}

T7 NOIP2011-S-DAY1-3-Mayan 游戏

题目描述

https://www.luogu.com.cn/problem/P1312

思路解析

首先，这题一看肯定是个暴力搜索，因为题目中的变换/操作略复杂，所以我们尽量分开写函数解决每块小操作

注：本文中的地图变量 [ i ][ j ] 均代表自下而上第 i 行，自左而右第 j 列

首先把图用二维数组表示出来，结构体，图方便

struct node{int pad[10][10];}
题目中总共满足三个操作： 1.掉落
当一个方块下方没有方块时，会往下掉，直到到底或下方有方块

实现[x][y]方块的掉落

void drop(int x, int y, node& u) {  // 同步修改掉，用地址，下同
    int r = x;                      // 用来记录当前掉落块，接下来有用
    if (u.pad[x][y] == 0)
        return;                            // 如果是个“空块”，不做了
    bool flag = 0;                         // 用来判定这个块有没有掉落
    while (u.pad[x - 1][y] == 0 && x > 0)  // 下方为空且不是最底层
    {
        flag = 1;
        swap(u.pad[x - 1][y], u.pad[x][y]);  // 掉落即交换
        x--;                                 // 自己的位置降低
    }
    if (flag)
        drop(r + 1, y, u);  // 如果自己掉了，自己上方也掉
}

2.横向拖动/交换
每个方块可以向左/右拖动，即与左/右交换方块，于是我们可以用简单的 swap 搞定

void move(int x, int y, int d, node& u) {
    swap(u.pad[x][y], u.pad[x][y + d]);  // d 是方向即 1 或-1，直接拿来用
    drop(x + 1, y, u);
    drop(x, y + d, u);  // 换来的可能是 0 ，换出去的一定不是零，会在宽搜时候保证
    // 我的上方方块可能会掉落，我过去的地方可能会使我掉落
}

消除
横向或纵向的三个连续相同块可以消掉，且可以共用块

因为有了共用块的性质，所以肯定不能无脑找到就消除，不妨打标记

void del(node& u) {
    bool need = 0;
    memset(vis, 0, sizeof(vis));                                                       // vis数组用来打标记
    for (int i = 0; i < 7; i++)                                                        // 从左下往右上搜
        for (int j = 0; j < 5; j++)                                                    // 只要考虑向右和向上的连续块即可
            if (u.pad[i][j] != 0) {                                                    // 存在方块
                if (u.pad[i + 1][j] == u.pad[i][j] && u.pad[i + 2][j] == u.pad[i][j])  // 纵向三个相连
                    vis[i][j] = vis[i + 1][j] = vis[i + 2][j] = 1;
                if (u.pad[i][j + 1] == u.pad[i][j] && u.pad[i][j + 2] == u.pad[i][j])  // 横向三个相连
                    vis[i][j] = vis[i][j + 1] = vis[i][j + 2] = 1;
            }

    for (int i = 6; i >= 0; i--)  // 消除的时候从上往下，可以同步drop操作
        for (int j = 0; j < 5; j++)
            if (vis[i][j]) {        // 被标记了要消除
                u.pad[i][j] = 0;    // 消掉
                drop(i + 1, j, u);  // 上方的方块下落
                need = 1;
            }
    if (need)
        del(u);
}

所以我们用一个 need 来判定有没有消除，如果有消除，那么再扫一遍，看在掉落后有没有新的可以消除的块

代码实现

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

struct G {
    int maps[10][10];
};

int n;

G now;

G last[10];

int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

struct Info {
    int x, y;
    int flag;

    Info(int dx, int dy, int flag) {
        x = dx;
        y = dy;
        this->flag = flag;
    }
    Info() {
    }
};

Info steps[10];

int cnt = 0;

bool visited[10][10];

bool checkp(int x, int y) {
    if (x >= 0 && y >= 0 && x < 5 && y < 7 && !visited[x][y] && now.maps[x][y])
        return true;
    return false;
}

bool marks[10][10];

bool updates[10][10];

int maxx, maxy;

int minx, miny;

void dfsupdate(int x, int y, int dire, int d) {
    visited[x][y] = true;
    maxx = max(maxx, x);
    minx = min(minx, x);
    maxy = max(maxy, y);
    miny = min(miny, y);
    if (dire == -1) {
        for (int i = 0; i < 4; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if (checkp(dx, dy))
                if (now.maps[x][y] == now.maps[dx][dy])
                    dfsupdate(dx, dy, i, d + 1);
        }
    } else {
        int dx = x + dir[dire][0];
        int dy = y + dir[dire][1];
        if (checkp(dx, dy))
            if (now.maps[x][y] == now.maps[dx][dy])
                dfsupdate(dx, dy, dire, d + 1);
    }
    visited[x][y] = false;
}

bool update(int x, int y) {
    maxx = maxy = 0;
    minx = miny = 100;
    dfsupdate(x, y, -1, 1);
    bool flag = false;
    if (maxx - minx + 1 >= 3) {
        for (int i = minx; i <= maxx; i++) {
            marks[i][y] = true;
            updates[i][y] = true;
        }
        flag = true;
    }
    if (maxy - miny + 1 >= 3) {
        for (int i = miny; i <= maxy; i++) {
            marks[x][i] = true;
            updates[x][i] = true;
        }
        flag = true;
    }
    return flag;
}

void updateall() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 7; j++)
            if (marks[i][j])
                now.maps[i][j] = 0, marks[i][j] = false;
        for (int j = 0; j < 7; j++)
            if (!now.maps[i][j]) {
                int ind = 0;
                for (int k = j + 1; k < 7; k++)
                    if (now.maps[i][k])
                        now.maps[i][j + ind] = now.maps[i][k], ind++, now.maps[i][k] = 0;
                break;
            }
    }
}

bool check() {
    for (int i = 0; i < 5; i++)
        if (now.maps[i][0] != 0)
            return false;
    return true;
}

bool move(int x, int y, int k) {
    int targetx, targety;
    if (k) {
        if (x == 4)
            return false;
        else {
            int t = now.maps[x][y];
            now.maps[x][y] = now.maps[x + 1][y];
            now.maps[x + 1][y] = t;
            steps[cnt++] = Info(x, y, 1);
            targetx = x + 1;
            targety = y;
            if (!now.maps[x][y]) {
                for (int i = x; i <= x + 1; i++)
                    for (int j = 0; j < 7; j++)
                        if (!now.maps[i][j]) {
                            int ind = 0;
                            for (int k = j + 1; k < 7; k++)
                                if (now.maps[i][k]) {
                                    if (i == x + 1 && y == k)
                                        targety = j + ind;
                                    now.maps[i][j + ind] = now.maps[i][k], ind++, now.maps[i][k] = 0;
                                }
                            break;
                        }
            }
        }
    } else {
        if (x == 0)
            return false;
        else {
            int t = now.maps[x][y];
            now.maps[x][y] = now.maps[x - 1][y];
            now.maps[x - 1][y] = t;
            steps[cnt++] = Info(x, y, -1);
            targetx = x - 1;
            targety = y;
            if (!now.maps[x][y]) {
                for (int i = x - 1; i <= x; i++)
                    for (int j = 0; j < 7; j++)
                        if (!now.maps[i][j]) {
                            int ind = 0;
                            for (int k = j + 1; k < 7; k++)
                                if (now.maps[i][k]) {
                                    if (i == x - 1 && y == k)
                                        targety = j + ind;
                                    now.maps[i][j + ind] = now.maps[i][k], ind++, now.maps[i][k] = 0;
                                }
                            break;
                        }
            }
        }
    }
    bool flag = false;
    if (update(x, y) | update(targetx, targety))
        flag = true;
    while (flag) {
        updateall();
        flag = false;
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 7 && now.maps[i][j] != 0; j++)
                if (updates[i][j]) {
                    updates[i][j] = false;
                    if (update(i, j))
                        flag = true;
                }
    }
    return true;
}

void dfs(int d, int x, int y, int k) {
    if (d > n)
        return;
    last[d] = now;
    if (move(x, y, k)) {
        if (check()) {
            if (d == n) {
                for (int i = 0; i < cnt; i++)
                    cout << steps[i].x << " " << steps[i].y << " " << steps[i].flag << endl;
                exit(0);
            } else {
                bool flag = false;
                if ((d - n) % 2 == 0) {
                    for (int i = 0; i < 5; i++) {
                        for (int j = 0; j < 7; j++)
                            if (last[1].maps[i][j] && last[1].maps[i][j + 1]) {
                                for (int t = 0; t < (d - n); t++)
                                    cout << i << " " << j << " 1" << endl;
                                break;
                                flag = true;
                            }
                        if (flag)
                            break;
                    }
                    for (int i = 0; i < cnt; i++)
                        cout << steps[i].x << " " << steps[i].y << " " << steps[i].flag << endl;
                    exit(0);
                }
            }
        }
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 7 && now.maps[i][j] != 0; j++)
                if (i != 0 && !now.maps[i - 1][j])
                    for (int l = 1; l >= 0; l--)
                        dfs(d + 1, i, j, l);
                else
                    dfs(d + 1, i, j, 1);
        cnt--;
    }
    now = last[d];
}

int main() {
    cin >> n;
    for (int i = 0; i < 5; i++) {
        int x;
        int ind = 0;
        while (cin >> x) {
            if (x == 0)
                break;
            now.maps[i][ind] = x;
            ind++;
        }
    }
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 7 && now.maps[i][j] != 0; j++)
            if (i != 0 && !now.maps[i - 1][j])
                for (int k = 1; k >= 0; k--)
                    dfs(1, i, j, k);
            else
                dfs(1, i, j, 1);
    cout << -1 << endl;
}

T8 NOIP2009-S-4-靶形数独

题目描述

https://www.luogu.com.cn/problem/P1074

思路解析

下面主要讲填数独：

将数独划分为 9 个宫，如何知道一个坐标在哪个宫？

1。确定宫号

我们需要这个函数解决：

inline int get_id(int i, int j) {
    return (i - 1) / 3 * 3 + 1 + (j - 1) / 3;
}

i，j 是坐标，返回的就是所在的宫号。我们当然可以打表预先存储好宫号，这样还可以优化时间复杂度。所以上面这个函数可以废掉了

定义二维数组：

const int gong[10][10] =
    {
        {1, 1, 1, 2, 2, 2, 3, 3, 3},
        {1, 1, 1, 2, 2, 2, 3, 3, 3},
        {1, 1, 1, 2, 2, 2, 3, 3, 3},
        {4, 4, 4, 5, 5, 5, 6, 6, 6},
        {4, 4, 4, 5, 5, 5, 6, 6, 6},
        {4, 4, 4, 5, 5, 5, 6, 6, 6},
        {7, 7, 7, 8, 8, 8, 9, 9, 9},
        {7, 7, 7, 8, 8, 8, 9, 9, 9},
        {7, 7, 7, 8, 8, 8, 9, 9, 9},
        {7, 7, 7, 8, 8, 8, 9, 9, 9},
};

这样也是可以的。

2。设计数据结构

sdk 数组，用来存储数独

area 数组，用来标记宫

row 数组，用来标记行

col 数组，用来标记列

row_cnt 数组，用来记录行元素数

col_cnt 数组，用来记录列元素数

score 数组，用来表示分值

const int score[10][10] =
    {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
        {0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
        {0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
        {0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
        {0, 6, 7, 8, 9, 10, 9, 8, 7, 6},
        {0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
        {0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
        {0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
        {0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
};  // score list

我们还需要设计这样一个函数

inline int get_value() {
    int ret = 0;
    rep(i, 1, 9, 1)
        rep(j, 1, 9, 1)
            ret += score[i][j] * sdk[i][j];
    return ret;
}

用来每次计算总价值

返回总价值，跟 ans 作比较，选最大值

3。求解数独

可以用舞蹈链解决，但是这道题 dfs 足以

void dfs(int r, int c, int cpl)  // r row, c column
{
    if (cpl == 81)  // 81个代表填满了，填满了一定保证是正确的填法
    {
        ans = max(ans, get_value());  // 填满了之后，比较一次最大值
        return;
    }
    rep(k, 1, 9, 1)  // 这里改成for(register int k = 1; k <= 9; k++)之后同理
    {
        if (row[r][k] || col[c][k] || area[get_id(r, c)][k])
            continue;                  // 判断列不能重复，行不能重复，宫不能重复
        row[r][k] = true;              // 既然不重复，那现在就重复了
        col[c][k] = true;              // 同上
        area[get_id(r, c)][k] = true;  // 同上
        row_cnt[r]++;                  // 当前行中的元素数++
        col_cnt[c]++;                  // 当前列中的元素数++
        sdk[r][c] = k;                 // 填进去
        // 寻找下一个dfs的点
        int tmpr = -1, nxt_r = 0, tmpc = -1, nxt_c = 0;
        // nxt_r是下一个行，nxt_c是下一个列
        rep(i, 1, 9, 1) if (row_cnt[i] > tmpr && row_cnt[i] < 9)
            tmpr = row_cnt[i],
            nxt_r = i;
        rep(j, 1, 9, 1) if (col_cnt[j] > tmpc && (!sdk[nxt_r][j]))
            tmpc = col_cnt[j],
            nxt_c = j;
        dfs(nxt_r, nxt_c, cpl + 1);
        // 回溯解除标记↓
        row[r][k] = false;
        col[c][k] = false;
        area[get_id(r, c)][k] = false;
        row_cnt[r]--;
        col_cnt[c]--;
        sdk[r][c] = 0;
    }
}

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 10, inf = 0x3f3f3f3f;
struct f {
    int rank, sum;
} cou[N];
bool operator<(const f& a, const f& b) {
    return a.sum < b.sum;
}
bool r[10][10], c[10][10], g[10][10];
int a[10][10], s[100][4], u, ok, ans = -1, filled;
int palace(int y) {
    if (y <= 3) {
        return 1;
    } else if (y <= 6) {
        return 2;
    } else {
        return 3;
    }
}
int which(int x, int y) {
    if (x <= 3) {
        return palace(y);
    } else if (x <= 6) {
        return 3 + palace(y);
    } else {
        return 6 + palace(y);
    }
}

int point(int x, int y) {
    if (x == 1 || y == 1 || x == 9 || y == 9) {
        return 6;
    }
    if (x == 2 || y == 2 || x == 8 || y == 8) {
        return 7;
    }
    if (x == 3 || y == 3 || x == 7 || y == 7) {
        return 8;
    }
    if (x == 4 || y == 4 || x == 6 || y == 6) {
        return 9;
    }
    if (x == 5 && y == 5) {
        return 10;
    }
}
inline void dfs(int p, int score) {
    if (p == u) {
        ans = max(ans, score);
        return;
    }
    for (int i = 1; i <= 9; i++) {
        if (r[s[p][0]][i] || c[s[p][1]][i] || g[s[p][3]][i]) {
            continue;
        }
        r[s[p][0]][i] = c[s[p][1]][i] = g[s[p][3]][i] = true;
        dfs(p + 1, score + (s[p][2] * i));
        r[s[p][0]][i] = c[s[p][1]][i] = g[s[p][3]][i] = false;
    }
    return;
}
inline void init() {
    for (int i = 1; i <= 9; i++) {
        cou[i].rank = i;
    }
    return;
}
signed main() {
    init();
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] > 0) {
                r[i][a[i][j]] = c[j][a[i][j]] = g[which(i, j)][a[i][j]] = true;
                filled += a[i][j] * point(i, j);
            } else {
                cou[i].sum++;
            }
        }
    }
    sort(cou + 1, cou + 10);
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (a[cou[i].rank][j] == 0) {
                s[u][0] = cou[i].rank;
                s[u][1] = j;
                s[u][2] = point(cou[i].rank, j);
                s[u++][3] = which(cou[i].rank, j);
            }
        }
    }
    dfs(0, filled);
    printf("%d\n", ans);
    return 0;
}

标签：10,num,int,Day4,2024,蓝润,pad,return,bool
From： https://www.cnblogs.com/TangyixiaoQAQ/p/18300536

2024信友队蓝润暑期集训提高1班②Day4

知识总结

搜索算法

剪枝

启发式搜索

迭代加深搜索

A*搜索算法

IDA*搜索算法

题目

T1 蚂蚁

题目描述

思路解析

代码实现

T2 士兵训练

题目描述

思路解析

代码实现

T3 JLOI2010 世界杯租房

题目描述

思路解析

代码实现

T4 ZJOI2002Reading 阅览室

题目描述

思路解析

代码实现

T5 NOIP2004-S-4-虫食算

题目描述

思路解析

代码实现

T6 CQOI2012 模拟工厂

题目描述

思路解析

代码实现

T7 NOIP2011-S-DAY1-3-Mayan 游戏

题目描述

思路解析

代码实现

T8 NOIP2009-S-4-靶形数独

题目描述

思路解析

代码实现

相关文章

赞助商

阅读排行