当前位置: 首页 > news >正文

搜索选讲

前言

我太菜了,如有没写清楚的地方大家轻喷.

爆搜

P4467 k短路

Hint:沿用次短路的思路(P1491).

不能经过重复的点是一个很强的限制,直接搜无论怎么剪枝都会被卡爆. 由于没有负权边,最短路必然不会经过重复的点,所以我们可以通过每次从最短路的第一条边开始,删掉一条边重新跑最短路,就可以得到字典序最小的次短路.

将这个思路推广到 \(k\) 短路,用优先队列维护字典序,每次更新拿出字典序最小的路径,从之前删过的前缀的下一条边开始继续删,跑出来的最短路都加到优先队列里,重复 \(k-1\) 次就可以得到字典序最小的 \(k\) 短路.

P1979 华容道

Hint:时过境迁,直接爆搜可以通过所有数据. 图论建模后跑最短路.

最终贡献分为两部分,首先空白格子走到初始棋子的某个方向,然后空白格子和初始棋子一起移动到目标位置. 前者可以直接 \(bfs\),后者考虑图论建模,\(bfs\) 预处理出每个格子四周状态之间的最短路,然后连边建图. 特别的,左右和上下状态之间的边权为 \(1\). 暴力枚举空白格到初始格的方向和最终空白格的方向,取最小值即可.

时间复杂度 \(O(n^2m^2+qnm\log nm)\).

P9169 过河卒

Hint:有向图博弈,建新图跑 bfs.

三个棋子的位置不同代表不同状态,也就是说状态总数大约是 \(2(nm)^3\),可以支持我们把所有状态存下来. 然而直接搜代码极其繁琐,分讨情况过多,于是考虑根据性质建出新图先再搜.

转换成有向图博弈,每走一步交换先后手,不能移动者输. 考虑当前这一步必胜或必败的条件,必胜当且仅当后继状态存在必败,必败当且仅当所有后继状态都为必胜. 这启发我们用 bfs 来遍历状态,每次把非平局状态压入队列,若当前必败,把所有前驱标记为必胜;当前必胜就检查是否有前驱所有后继状态都是必胜,把这个前驱标记为必败;未遍历到的节点均为平局. 时间复杂度是 \(O(n^3m^3)\).

考虑上述过程的操作步数怎么更新. 由于状态是倒着更新的,所以必胜在队列中的第一个后继更新状态,必败在队列中的最后一个后继更新状态. 剩下的就是模拟了.

口胡一下,给每个状态标个序号,枚举三个点的状态,枚举方向,后继状态向当前状态连有向边,顺便维护入度(倒着的出度)、胜负状态以及步数. 然后 bfs 即可.

ID-A*

P2324 骑士精神

移动马到空格比较难搞,将一次移动视为空格走日字与一个马交换.

每步至多还原一个马,所以容易想到把当前状态与目标状态不同的位置数直接作为估价函数.

这样做存在一个致命的问题:存在实际的步数比估价小 \(1\) 的状态,这违反了可采纳性;最后一步必然会使估价 \(-2\),这违反了一致性.

所以我们修正估价函数为:当前局面与目标局面相等时,估价为 \(0\). 其余情况估价为对应位置不同的数量 \(-1\). 现在估价函数就符合了可采纳性和一致性,直接 ID-A* 即可.

P2534 铁盘整理

每次 reverse 一个前缀 \(1\sim i\),前缀中每个位置圆盘之间的相对顺序没有改变,本质上改变的只有 \(i\)\(i+1\) 两个位置上的圆盘.

那么可以想到,对离散化后的半径,如果相邻两圆的半径差不为 \(1\),说明两圆之间至少要操作一次. 不妨先令这个东西为估价函数.

如果你在实现这个估价函数时顺便把 \(r_0\)\(r_1\) 的差也考虑进去了那么你会惊喜地发现挂了大量的分数.

原因与上一个题类似,可能使估价减小 \(2\). 将 \(r_{n+1}\) 设为 \(n+1\) 即可避免这种情况.


后面若干题只会讲估价函数是啥,不再讲具体实现,大家可以大胆口胡.

UVA1604 立方的 8-谜

跟骑士精神几乎一样.

UVA1343 自转游戏

最终数字认为是当前出现次数最多的数字,一次操作至多增加一个.

设出现次数最多的数字出现次数为 \(cnt\),估价函数定义为 \(8-cnt\).

UVA11212 编辑一本书

剪切一个区间粘贴到一个位置,至多可以改变三个位置的后继.

一个合法的估价函数是所有位置 \(i\),位置 \(i+1\) 不是 \(a_i+1\) 的数量除以三(本题可以比较 \(a_0\)\(a_1\)).

可以通过不等式两边同时乘以 \(3\) 来避免精度问题.

UVA10181 15-谜 问题

考虑估价函数为所有数字到目标状态的曼哈顿距离之和,因为一次移动只能改变一个数字的位置.

一个剪枝是可以直接根据初始状态来判断是否无解.

对于 \(n\times m\) 的方格存在一个对于任何操作都不发生改变的恒量. 具体的,设把方格去掉空白格拉成一个序列,逆序对个数的奇偶性为 \(M\),空白格到目标状态空白格距离的奇偶性为 \(N\),有结论:

  • \(m\) 为偶数,恒量为 \(M\oplus N\).
  • \(m\) 为奇数,恒量为 \(M\).

考虑证明,将空白格下移,相当于将空白格下面的数上移,也就是在序列中的位置从 \(i\) 变化到 \(i-m+1\). 逆序对的变化量为 \(m-1\),易得上述结论.

所以直接判断初始状态的这个恒量是否为 \(0\) 即可.

记忆化

CF1593F Red-Black Number

折半肯定能做,但是值域很小没有必要. 记状态 \(f_{i,a,b,c}\) 表示考虑前 \(i\) 个数,红色拼起来的数 \(\bmod A=a\),黑色拼起来的数 \(\bmod B = b\),选了 \(c\) 个红色是否合法,直接记搜即可.

P4547 随机二分图

Hint:把一组中的两条边拆开,考虑额外的贡献.

小清新记搜题.

首先期望的完美匹配数量可以转化为出现一组完美匹配的概率的和;计算一组完美匹配出现的概率,只需要考虑最终这组完美匹配里面的边.

考虑状压 DP. 如果只有 \(t=0\) 的情况,可以设 \(f_{i,s}\) 表示考虑左部点前 \(i\) 个点,匹配了右边状态为 \(s\) 点的概率. 转移直接乘上 \({1\over2}\) 即可.

扩展到 \(t=1,t=2\),我们把两条边拆开,以 \(t=1\) 为例,考虑新贡献:

  • 当最终匹配中只有 \((u_1,v_1)\) 时,概率是 \({1\over2}\).
  • 当最终匹配中只有 \((u_2,v_2)\) 时,概率还是 \({1\over2}\).
  • \((u_1,v_1),(u_2,v_2)\) 都在匹配中时(要求没有重复出现的点),原本概率是 \({1\over2}\),但是被算成了 \({1\over 4}\),要额外加上 \({1\over4}\) 的概率.

类似的,\(t=2\) 时两边同时取到的概率是 \(0\),但是被算成了 \({1\over4}\),要减掉.

搜索时,为了不算重,我们强制要求找到左部编号最小的没有匹配的点来匹配. 时间复杂度看起来是 \(O(2^{2n}\cdot n^2)\) 的,但是每次匹配前后两部 \(1\) 的个数是相等的,所以状态数大概是 \(\sum_{i=0}^n{n\choose i}^2={2n\choose n}\approx1.5\times10^8\),记搜轻松通过.

折半

P12371 【模板】最大团/最大独立集

Hint:最大独立集等于补图上的最大团.

大家还记得 \(O(\sqrt m2^{\sqrt{2m}\over2})\) 的稀疏图最大团算法吗?

将度数从小到大排序,当找度数为 \(d\) 的最大团时,符合条件的点度数 \(\ge d\),这里就带上了一个自然根号. 跑与 \(O(2^{n\over2})\) 相同的搜索即可.

然后介绍一个 \(O(1.3803^n)\) 的最大独立集算法,在完全图更加优秀.

按度数从大到小排序,每次搞出最大的度数 \(d_u\),如果 \(d_u\le2\) 可以直接 \(O(n)\) 算剩下的图的最大独立集大小. 否则把 \(u\) 放到独立集里面或删除 \(u\) 和直接相连的点. 由于后者 \(d_u\ge3\),所以时间复杂度满足递推式 \(T(n)=T(n-1)+T(n-4)\),即 \(O(1.3803^n)\).

值得一提的是,最大独立集的个数上界为 \(3^{n\over3}\),虽然随机图远远小于这个上界,但是注意空间要开够.

P12904 平衡点

Hint:爆搜一半的括号序列,枚举最终是哪两端拼起来.

分别考虑斜向上走和斜向下走的重心怎么变的,简单推式子.

两段括号可以拼起来当且仅当相邻高度一样,暴力枚举每个高度的括号拼起来,判断一下即可.

状态数是卡特兰数 \(H({n\over2})\),大约 \(4\times10^8\).

CF1601F 二次排序

Hint:把 \(i\) 换成字典序排名 \(rk_i\),可以拆贡献,折半预处理.

值接近的两个数字典序相差很大,难以预处理. \(i\)\(rk_i\) 显然构成双射,将式子调整为:

\[\left(\sum_{i=1}^n\Big((rk_i-i)\bmod998244353\Big)\right)\bmod10^9+7 \]

字典序排名是连续的,值域想到折半,可以考虑拆式子.

\(i=10^6x+y\),有:

\[\begin{aligned} &\left(\sum_{i=10^6x+y}^n\Big(\left((rk_{10^6x}-10^6x)+(rk_y-y)\right)\bmod998244353\Big)\right)\bmod10^9+7\\ =&\left(\Big(\sum_{i=10^6x+y}^n(rk_{10^6x}-10^6x)+\sum_{i=10^6x+y}^n(rk_y-y)\Big)-p\times998244353\right)\bmod10^9+7\\ \end{aligned} \]

其中 \(p\)\(rk_i-i\ge998244353\)\(i\) 的个数.

第二个和式可以爆搜 \(y\) 预处理,然后枚举 \(x\) 统计答案. \(p\) 的维护稍麻烦,需要对于每个十进制位维护 \((rk_y-y)\bmod998244353\) 的具体值,二分第一个与 \((rk_{10^6x}-10^6x)\) 相加大于等于 \(998244353\) 的位置.

剪枝

P1526 智破连环阵

Hint:每个炸弹能造成的影响一定是一个确定的武器区间,相当于每个炸弹与武器区间做二分图匹配.

由于炸弹爆炸持续 \(5\) 分钟,所以一定可以摧毁所有能摧毁的武器.
\(f_{i,j}\) 为炸弹 \(i\) 炸到武器 \(j\) 时,最远能炸到的武器编号,\(g_i\) 为炸到武器 \(i\) 消耗的最少炸弹数,都可以递推预处理. \(g_i\) 可以用来进行可行性剪枝,类似于 A-star.

考虑深搜状态 dfs(int x, int y) 表示从第 \(x\) 个武器开始炸,已经用了 \(y\) 个炸弹.

  • 可行性剪枝,当 \(g_x+y>ans\) 直接返回.
  • 递归边界 \(x>m\),更新 \(ans=y\).

根据 Hint,我们要搞出 \(y\) 匹配的炸弹,并且跑增广路判断是否合法.
枚举炸弹至少炸到武器 \(j\),设 \(p_{i,y}\) 表示炸弹 \(i\)\(y\) 是否可以匹配. 可以匹配当且仅当 \(f_{i,x}\ge j\).
当存在增广路时,我们就往 dfs(j, y + 1) 继续搜索.

由于每次增广是在前面所有匹配的基础上进行的,当前匹配不一定最优,所以需要在搜索完之后进行回溯.

由于保证数据随机,所以这样剪枝已经可以轻松通过了.

P4631 选圆圈

Hint:从判断一个圆与最大圆相交/相切的条件入手,尝试缩小检查的范围.

神仙剪枝题!

首先我们把圆按照半径从大到小排序,依次遍历每个圆. 判断两圆相交的条件是:

\[(x_1-x_2)^2+(y_1-y_2)^2\le(r_1+r_2)^2 \]

我们认为 \((x_1,y_1,r_1)\) 是目前最大的圆,那么 \(r_2\le r_1\),所以 \((x_2,y_2)\) 被限制在 \((x_1,y_1)\) 周围一圈的某个范围里面. 具体的,我们对平面分块,划分成若干 \(L=2r_1\) 为边长的正方形,那么这个范围就是 \((x_1,y_1)\) 所在块以及周围 \(8\) 连通的块.

当圆的半径都在一个数量级时,这样的剪枝十分高效. 观察到:每个圆在被删除前最多被检查 \(O(1)\) 次. 证明就是考虑在一个圆所在的九宫格填比它半径更大的圆,最多只能填 \(O(1)\) 个,而且很难对每个圆都卡满.

对于更一般的情况,我们希望根据圆的半径和当前格子边长对块进行重构来保证复杂度. 具体的,当 \(2r_2\le\lfloor{L\over2}\rfloor\) 时,我们以 \(L=2r_2\) 对格子进行重构. 重构最多进行 \(O(\log R)\) 次,并且一次重构可以做到 \(O(n)\). 重构可以保证上述构造的正确性,所以总复杂度理论可以做到 \(O(n\log n)\).

实现可以用 map 维护每个格子还没有被删去的点集,第一维用 pair 记格子坐标,第二维用 vector 记点集.

点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 3e5 + 10;
int n, pri[maxn], ans[maxn];struct Circle{int x, y, r;} c[maxn];
inline bool cmp(int i, int j) {return c[i].r == c[j].r ? i < j : c[i].r > c[j].r;}inline ll pow2(const int &x) {return 1ll * x * x;} 
inline bool check(int i, int j) {return pow2(c[i].x - c[j].x) + pow2(c[i].y - c[j].y) <= pow2(c[i].r + c[j].r);}map<array<int, 2>, vector<int> > q;int main() {ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++) cin >> c[i].x >> c[i].y >> c[i].r, pri[i] = i;sort(pri + 1, pri + n + 1, cmp);for(int i = 1, id, L = 0; i <= n; i++) {id = pri[i];if(ans[id]) continue;if(!L || c[id].r * 2 < L / 2) {L = c[id].r * 2; map<array<int, 2>, vector<int> >().swap(q);for(int j = 1; j <= n; j++) if(!ans[j]) q[{c[j].x / L, c[j].y / L}].push_back(j);}int px = c[id].x / L, py = c[id].y / L;for(int j = px - 1; j <= px + 1; j++) {for(int k = py - 1; k <= py + 1; k++) {if(q.find({j, k}) != q.end()) {vector<int> nw;for(auto p : q[{j, k}]) {if(check(id, p)) ans[p] = id;else nw.push_back(p); }q[{j, k}] = nw;}}}}for(int i = 1; i <= n; i++) cout << ans[i] << " ";return 0;
}

P1763 埃及分数

Hint:迭代加深,最后两项通过韦达定理构造一元二次方程来求解.

\({a\over b}={1\over x}+{1\over y}\),可得

\[\begin{cases} ka=x+y\\ kb=xy \end{cases}\]

根据此式可以构造一元二次方程反解出 \(x,y\). 所以我们可以枚举 \(k\),取最优的答案.

P10788 分数

Hint:首先发现集合中的数具有唯一的操作方法还原回 \((1,0)\). 考虑一次操作相当于 \((a,b)\rightarrow(b,a+2k_i\times b)\),优化对 \(k_i\) 序列的计数.

前者的证明有深刻的数论背景,因为一个连分数的表示唯一对应一个 Stern-Brocot Tree 上的节点. 感性理解可以考虑当 \(n=1\),对于两个完美正分数 \(x_1={1\over 2+2k_1}\)\(x_1'={1\over2+ 2k_1'}\),由于 \(k_1,k_1'\) 为整数,显然有 \(k_1=k_1'\)\(x_1=x_1'\). 所以一个的序列 \(k_i\) 唯一对应一个完美正分数,考虑对序列计数.

现在我们有一个 \(O(ans)\) 的暴力枚举做法,但是剪枝非常困难.

非常人类智慧的一步:我们想到用求方程解的个数来统计答案,那么每一个分数可以表示成形如 \({ax+b\over cx+d}\),此时的 \(x\) 是一个未知数,若干次操作后得到的分数仍然是这个形式. 满足题目条件的 \(x\) 的个数是 \(\min(\lfloor{n-b\over a}\rfloor, \lfloor{m-d\over c}\rfloor)\). 若我们对每个爆搜出来的系数 \((a,b,c,d)\) 都统计一遍答案,显然会有大量重复统计的情况.

考虑通过钦定避免这种情况,我们在爆搜完美分数 \({a\over b}\) 的时候维护 \(v=\max\{k_i\}\),对于每个 \((a,b,v)\),统计 \(\ge v\)\(x\). 这样符合正确性,因为当完美分数被 \(v\) 操作一次后,再操作若干次仍然可以保留 \(av+b\over cv+d\) 的形式,这与上面提到过的 \(x\) 的性质一样. 现在我们已经统计了所有序列 \(k_1,k_2,\cdots,v\) 的答案,在此基础上继续爆搜维护系数 \((a,b,c,d)\),并更新 \(v\) 继续统计答案. 可以说明状态数减小到大约 \(10^8\),可以通过.

点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll ans;
int n, m;void dfs0(int a, int b, int c, int d, int v) {if(1ll * a * v + b > n) return;ans += max(0, min(!a ? m : (n - b) / a, (m - d) / c) - v + 1);ans += max(0, (n - d) / c - v + 1);for(int u = 1; ; u++) {int A = 2 * c * u + a, B = 2 * d * u + b;if(1ll * A * max(v, u + 1) + B > m) break;dfs0(c, d, A, B, max(v, u + 1));} return;
}
void dfs(int a, int b, int v) {for(int u = 1; ; u++) {int c = 2 * u * b + a;if(2ll * max(v, u) * c + b > m) break;dfs(b, c, max(u, v));} dfs0(0, b, 2 * b, a, v);
}int main() {ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m; if(n > m) swap(n, m);dfs(0, 1, 1); cout << ans;return 0;
}

P9483 合并书本

由于这道题性质太多了,将采用分步 Hint.

Hint 1:将操作序列视为建树,贡献拆开考虑.

Hint 2:尝试自底向上建树.

Hint 3:对于所有非叶子节点 \(u\)\(h(ls_u)\le h(rs_u)\).

Hint 4:自顶向下建树,用左深度表示儿子,逐层分裂.

Hint 5:观察性质,对树高的可重集剪枝.

http://www.hskmm.com/?act=detail&tid=27497

相关文章:

  • vue打包的项目,从根目录进去路由可访问,浏览器直接打开这个路由不可访问
  • IObit Uninstaller一款强大的卸载工具!IObit Uninstaller卸载工具,IObit Uninstaller下载安装教程
  • 网络配置不再难:4G/Wi-Fi/以太网/虚拟网卡全指南
  • 计算几何
  • 2025开关按钮厂家最新推荐榜:开关按钮,带灯开关按钮,防水开关按钮,防爆开关按钮,防腐开关按钮等全种类覆盖,高品质设计与卓越性能口碑之选
  • 一种排查java.lang.OutOfMemoryError: Metaspace的方法
  • First Blog Post
  • 本站点即将在2025年改变研究方向和目标
  • 实用指南:12_OkHttp初体验
  • (AE)Adobe After Effects 2025 视频后期制作软件!安装包永久免费免激H解锁版下载与图文详细安装教程!!
  • Postgresql主从配置
  • 乒乓球
  • 2025年工程管理软件系统推荐榜:交付管理/工程协同/工程管理/智慧工地管理系统
  • 《程序员修炼之道》 阅读笔记一
  • 大型行为模型LBM超越语言模型的技术解析
  • 2025工程管理软件系统推荐榜:技术赋能下的场景化解决方案全景
  • 【LVS入门宝典】LVS-TUN模式原理与配备:跨越网络界限的负载均衡解决方案
  • Java基础-Eclipse工具-面向对象(1)
  • Avalonia UI 投资 Wilderness Labs
  • BLE开发新体验:四种模式全解析,源码免费开放
  • JBoltAI V4 - 那年-冬季
  • 【EI检索】2025年智能决策与机器学习国际学术会议 (ICIDML 2025)
  • 10月9号
  • Qwen3技术报告
  • 赋能智慧监管:国标GB28181平台EasyGBS在明厨亮灶场景中的深度应用
  • CFD与FDM, FEM, FVM的关系?
  • 央国企高管团队为何频繁流失?揭示薪酬结构失衡的深层原因与优化策略
  • 在Ubuntu 22.04系统上安装libimobiledevice的步骤
  • Redis sentinal模式,master挂了的 选举过程
  • 软件技术基础第一次