CSP2025 - 搜索，折半搜索专题
A. P1074 [NOIP2009 提高组] 靶形数独
搜就完了，一种比较好写的方式是把所有的 \(0\) 搞到一个 vector 里面，记录它在哪一行、哪一列、哪一九宫格，然后一个一个搜能填什么。
然后是优化问题，把所在行 \(0\) 的个数最少的行优先搜，用 stable_sort。
B. P4573 [CQOI2013] 新数独
弱智题，搜就完了，跑得嘎嘎快。
C. CF525E Anya and Cubes
容易观察到的是 \(a_i\le10^9\) 的值域是假的，如果要阶乘那么 \(a_i\) 必定不超过 \(18\)。于是对于一个 \(a_i\) 有三种情况：
- 不选；
- 选它本身，前提是加上它不超过 \(S\)；
- 选它的阶乘，前提是 \(!\) 够用且加上它不超过 \(S\)。
这样裸搜是 \(O(3^n)\) 的，会 T 得很惨。所以折半，先搜前一半，用一个 unordered_map 记录用了多少 \(!\)、总和为多少的答案，再搜后一半，和前一半拼凑答案即可。其实这都是折半搜索的套路了。
D. CF1276B Two Fairs
题意是求所有 \(u,v\) 使得 \(a,b\) 是 \((u,v)\) 的割点。于是只需搜 \(a,b\) 各自到不了对方的点的数目即可。最简单的一种搜法是分别从 \(a,b\) 搜能到达的，然后用 \(n\) 一减就是一边的答案，最后一乘即可。我一开始写的是依次搜 \(a,b\) 的相邻点，麻烦还调不出来。
E. CF58E Expression
首先需要明确，为了使最终的答案尽可能短，我们应该尽可能少地创造新的数位，所以盲目枚举左右两边加什么数是不可取的，我们应该从低位向高位依次判断。
搜到当前位时，分为两种情况：当前位满足要求、当前位不满足要求。若当前位满足要求，我们就不需要再考虑当前位了，开始考虑高位，所以我们给当前循环的 \(a,b,c\) 全部 \(\div10\)；若当前位不满足要求，我们再一一枚举 \(a,b,c\)，给 \(a,b,c\) 的最后一位加上一个数字然后继续搜。同样是因为我们应该尽可能少地创造新的数位，所以一旦我们给一个数的最后一位加上一个数字 \(i\)（即 \(a\gets a\times10+i\)，\(b,c\) 同理），这个 \(i\) 直接就是 \(c\) 和 \(b\) 的个位的差值。同理，如果是 \(b\) 就是 \(c\) 和 \(a\) 的个位的差值，\(c\) 就是 \(a\) 与 \(b\) 的个位的和。别忘了考虑进位。
需要特判的是当 \(c=0\) 时，这时我们只需要将 \(c\) 的最高位处理成 \(a+b+\text{进位}\) 即可。
F. CF293B Distinct Paths
容易发现的是 \(n,m\le1000\) 的范围显然是假的，如果 \(n+m-1>k\) 则根本不可能有解，又因为 \(k\le10\)，所以 \(n,m\) 的值域应该也是不超过 \(10\)，整张图的大小不超过 \(100\)，变成一个搜索题。
然而这样还是搜不出来。容易想到一个剪枝是若当前点在 \((x,y)\)，剩下 \(\mathit{cnt}\) 种颜色，则若 \(n+m-x-y+1>\mathit{cnt}\) 就直接 return；第二个剪枝是不好想的，我们发现若当前颜色从未出现，说明之前的颜色不会对它造成影响，那么不管用什么颜色都是等价的，不需要重新搜。
两个剪枝加起来就足矣通过这道题了。
G. CF679C Bear and Square Grid
傻逼题。傻逼之处在于，这道题让我认识了一个 CF 的标签叫做 \(\textbf{implementation}\)，名词，中文意思为
\[\Huge\textbf{实现。} \]思路是极其简单的，首先处理出每个点所在连通块和连通块大小，\(O(n^2)\) 枚举框所有的可能位置，这个位置的框所能造成的贡献就是它的大小 \(k^2\) 再加上它周围连通块的大小，这样复杂度是 \(O(n^2k)\) 的。
但是结果不对，因为有一些连通块会伸到框里面，所以我们应该做一个二维前缀和统计框内的 X 的个数。但是这样又有一个问题，框内可能有一些连通块被完全包裹着，这样计算就相当于把中间这些连通块漏了。
显然我们不能再扫一遍框内，那样复杂度就变成了 \(O(n^2k^2)\)。需要在 \(O(1)\) 的时间内查询被完全包裹的连通块。同样是做二维前缀和，只不过这个前缀和比较特殊。我们需要在统计连通块的时候一并计算每个连通块最上、下、左、右的位置，如果上下跨度或左右跨度超过 \(k\) 则显然不属于被全部包裹的一类。在这基础上，计算二维前缀和即可。
思路挺自然的，代码也就 \(2.3\,\text{KB}\)。放一下这个特殊前缀和的代码吧。\(a_{i,j}\) 是 \((i,j)\) 属于哪个连通块。
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(!vis[a[i][j]]){
vis[a[i][j]]=1;
int sht=a[i][j];
if(xmx[sht]-xmn[sht]<K&&ymx[sht]-ymn[sht]<K){
sum2[max(xmx[sht]-K+1,1)][max(ymx[sht]-K+1,1)]+=siz[sht];
sum2[xmn[sht]+1][max(ymx[sht]-K+1,1)]-=siz[sht];
sum2[max(xmx[sht]-K+1,1)][ymn[sht]+1]-=siz[sht];
sum2[xmn[sht]+1][ymn[sht]+1]+=siz[sht];
}
}
H. P2489 [SDOI2011] 迷宫探险
很好的搜索题，考察了概率、三进制状压、二进制状压、记搜，可惜数据水了。水到什么程度？初始化 01 颠倒都能过，使人不知如何是正解。
迷宫问题，一般都是搜索。但是针对这么复杂的题目描述，仅仅暴搜应该是捉襟见肘，不过题目提示了我们状压（陷阱种类数只有 \(5\)），那我们就考虑怎么压、怎么转移。
题目中其实有三种状态，未知的陷阱、已知无害陷阱、已知有害陷阱，我们可以分别把它们三进制状压为 \(0,1,2\)。初始状态显然是 \(0\)，然后我们就可以 DFS 了，DFS 里面含有四个参数 \(x,y,s,h\) 表示坐标、状态和剩余血量，遇到一个陷阱就分类讨论：如果是未知陷阱，就分有害和无害两种情况最终答案就是两种概率之和；如果是已知陷阱就正常遍历即可。
这两种概率怎么算？我们需要处理出在每一种状态下，每一种陷阱是有害陷阱的概率。这是容易预处理的，只需把所有情况下的 \(p_i\) 值加起来再除以总和即可。
这道题的思路就是这样的，但是直接照这样写理论上不能通过，不仅有复杂度方面的问题，还有正确性方面的问题。复杂度问题是好解决的，暴搜改记搜即可；正确性之所以有问题，是因为我们有可能一条分支的 DFS 出现了环，这时 DP 数组还没有处理好就被转移了。为此，我们可以先用一个 DFS 预处理出一个点所有能到达的出口、未知陷阱或已知有害陷阱，把它们全搞到一个 vector 里面就能解决这个问题。这样做的正确性在于，已知无害陷阱和空地一样，对状态、血量没有任何影响，所以从原点到空地和已知无害陷阱的这一过程我们可以忽略。
至此，我们就从理论和实践两方面通过了这道题。
如果想更优化，可以把预处理 vector 的过程中未知和已知有害的状态合并，从三进制状压变成二进制状压，实测能优化近 \(40\,\text{MB}\) 的空间和 \(800\,\text{ms}\) 的时间。
#include<bits/stdc++.h>
using namespace std;
constexpr int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},pw[]={1,3,9,27,81,243};
constexpr int MAXN=35,MAXM=300;
int n,m,K,H,p[MAXN],sx,sy;
string mp[MAXN];
// 三进制状态，0未知1无害2有害
// g[i][j]表示三进制状态i的条件下，陷阱j是有害的概率
double f[MAXN][MAXN][MAXM][6],g[MAXM][6];
vector<pair<int,int>>v[MAXN][MAXN][MAXM];
int vis[MAXN][MAXN],tot;
bool check(int s1,int s2){
for(int i=0;i<K;++i){
if(s1/pw[i]%3==1&&s2&1<<i) return 0;
if(s1/pw[i]%3==2&&!(s2&1<<i)) return 0;
}
return 1;
}
void dfs(int x,int y,int sta,int sx,int sy,int now){
vis[x][y]=now;
// 如果不是起点，且当前点是终点或有害点
if((x!=sx||y!=sy)&&(mp[x][y]=='@'||(isupper(mp[x][y])&&(sta/pw[mp[x][y]-'A']%3!=1)))){
v[sx][sy][sta].emplace_back(x,y);
return;
}
for(int i=0,xx,yy;i<4;++i){
xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m||mp[xx][yy]=='#'||vis[xx][yy]==now) continue;
dfs(xx,yy,sta,sx,sy,now);
}
}
double dp(int x,int y,int sta,int h){
if(f[x][y][sta][h]>-1) return f[x][y][sta][h];
if(!h) return f[x][y][sta][h]=0;
if(mp[x][y]=='@') return f[x][y][sta][h]=1;
double res=0;
for(auto vv:v[x][y][sta]){
int xx=vv.first,yy=vv.second;
if(mp[xx][yy]=='@') return f[x][y][sta][h]=1;
if(sta/pw[mp[xx][yy]-'A']%3==2) res=max(res,dp(xx,yy,sta,h-1));
else if(sta/pw[mp[xx][yy]-'A']%3==0){
// s1有害，s2无害
int s1=sta+pw[mp[xx][yy]-'A']*2,s2=sta+pw[mp[xx][yy]-'A'];
res=max(res,dp(xx,yy,s1,h-1)*g[sta][mp[xx][yy]-'A']+dp(xx,yy,s2,h)*(1-g[sta][mp[xx][yy]-'A']));
}
}
return f[x][y][sta][h]=res;
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin>>n>>m>>K>>H;
for(int i=1;i<=n;++i) cin>>mp[i],mp[i]=' '+mp[i];
for(int i=0;i<1<<K;++i) cin>>p[i];
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(mp[i][j]=='$'){
sx=i,sy=j;
goto byby;
}
byby:;
for(int i=0,tot;i<pw[K];++i){
tot=0;
for(int k=0;k<1<<K;++k){
// 判断k合不合理
if(!check(i,k)) continue;
tot+=p[k];
for(int j=0;j<K;++j){
if(i/pw[j]%3) continue;
if(k&1<<j) g[i][j]+=p[k];
}
}
for(int j=0;j<K;++j){
if(i/pw[j]%3==0) g[i][j]/=tot;
else if(i/pw[j]%3==1) g[i][j]=0;
else g[i][j]=1;
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
for(int k=0;k<pw[K];++k)
if(mp[i][j]!='#')
dfs(i,j,k,i,j,++tot);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
for(int k=0;k<pw[K];++k)
for(int l=0;l<=H;++l)
f[i][j][k][l]=-1;
printf("%.3f\n",dp(sx,sy,0,H));
return 0;
}
I. CF585D Lizard Era: Beginning
这题就很套路了，裸搜 \(O(3^n)\) 显然炸，所以折半搜，先搜前一半，再搜后一半。设前一半三个人得到的值是 \(a,b,c\)，后半部分是 \(a',b',c'\)，则由题得：
\[a+a'=b+b'=c+c' \]简单移项得：
\[a-b=b'-a',\quad b-c=c'-b' \]所以显然开一个 map<pair<int,int>,pair<int,string>>，搜前半部分时将 \((a-b,b-c)\) 作为 key 插入 map 当中，存储下当前的 \(a\) 值和操作序列；搜后半部分时直接用 \((b'-a',c'-b')\) 在 map 中找答案，用最大的 \(a+a'\) 更新答案和操作序列。
如果你会手写哈希函数，用 unordered_map 会优化近一半的时间。
Meet in the Middle 的题离不开 map。
J. CF1257F Make Them Similar
同样的套路题变了花样考你。其实更简单，配不上紫。
显然把 \(2^{30}\) 的值域分成两个 \(2^{15}\) 枚举，套路地，
\[\operatorname{pc}(a_1)+\operatorname{pc}(a_1)'=\operatorname{pc}(a_2)+\operatorname{pc}(a_2)' \]转化为
\[\operatorname{pc}(a_1)-\operatorname{pc}(a_2)=\operatorname{pc}(a_2)'-\operatorname{pc}(a_1)' \]可以推广到 \(a_n\)，所以搜前半部分时把 \(\operatorname{pc}(a_{2\dots n}\oplus x)-\operatorname{pc}(a_1\oplus x)\) 搞成一个 vector 作为 key 塞进 map，搜后半部分时直接查。
Meet in the Middle 的题离不开 map。
K. CF912E Prime Gift
这题不套路，但是好玩。
暴搜是容易的，枚举每个素数的次数，把枚举到的答案全搞到一个 vector 里面，最后排序去重，二分查找即可。顶满的时间复杂度是 \(O(\prod\log_{p_i}V)\)，爆炸。
折半搜索，一次搜一半的素数，分别搞到两个 vector（记为 \(v_1,v_2\)）里面排序去重。然后照例二分答案，判断当前二分到的答案前面有多少个结果，每个结果自然就是 \(v_1(i)\times v_2(j)\)。但如果 \(n^2\) 搞会 T 掉，观察到答案具有单调性，所以利用双指针的手法，\(i\) 从前往后，\(j\) 从后往前，之后就没什么问题了。
有几个小坑：
- 如果我们写：\(\operatorname{dfs_1}(1,\lfloor n/2\rfloor),\operatorname{dfs_2}(\lfloor n/2\rfloor+1,n)\)，如果 \(p\) 数组是有序的，那么 \(\operatorname{dfs_1}\) 就会炸掉（越小的素数 \(\log V\) 就越大）。此时要么将 \(p\) 数组 shuffle 一下，要么把两个 DFS 改成一个遍历奇数项、一个遍历偶数项。
- 用迭代器比用下标快。
- 二分不能写错！
int l=1,r=1e18;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<'\n';