第二章:枚举与模拟

给出一串数字,要求找出所有符合条件的组合;给出一串操作,要求算出最终结果。这两类任务都能从很直接的做法开始:前者把候选逐个试过,后者把过程一步步执行。前者称为枚举,后者称为模拟。
“逐个试”仍需要设计。枚举三个数,究竟枚举数值还是位置?两个顺序不同的选择算一组还是两组?模拟一次行动,先判断结束还是先更新?这些选择决定了程序是否与题意一致。本章从数位计数开始,每次只引入一种新的处理困难,直到把“枚举一种规则,再模拟规则下的过程”连起来。
阅读前需要掌握循环、数组、字符串和函数。每段 C++ 代码都是独立完整程序,分别对应本节题目的输入输出;同名变量不需要跨程序合并。数组容量由各题数据范围确定。
1. 确定枚举对象与范围
1.1 枚举整数与数位
简易题面:统计整数 至 的十进制表示中,数字 总共出现了多少次。
数据范围:,。
题目统计出现次数,例如 中的两个 都要计入答案。因此,直接枚举每个整数,再逐位检查。对 取余得到个位,整除 去掉个位;例如 依次拆出 ,顺序不影响计数。
先只处理一个数 ,目标数字取 。每一轮先查看个位,再删去已经查看过的个位:
| 轮次 | 处理前的 | 本轮增加次数 | 整除后 | |
|---|---|---|---|---|
三个位置处理完后,,循环结束。这里每个位置都能贡献一次,所以不能在发现第一个 后停止。外层再让 依次取 至 ,便能检查整个范围。拆位会改变数值,需把循环变量 复制到 ;否则外层循环的计数也会被破坏。 在主函数中初始化为 。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,x,ans=0;
cin>>n>>x;
for(int i=1;i<=n;++i){
int t=i;
while(t>0){
if(t%10==x)++ans;
t/=10;
}
}
cout<<ans<<'\n';
}
每个整数的每一位恰好检查一次。设最大整数有 位,时间复杂度为 ,额外空间为 。本题至多七百万次拆位,直接枚举足够。若枚举范围包含整数 ,需单独统计它的一位数字 ,因为 不会执行。
1.2 用唯一表示避免重复枚举
| 候选对象 | 表示方式 | 范围或去重规则 |
|---|---|---|
| 一个整数 | 数值 | 枚举给定闭区间 |
| 两个不同位置组成的无序数对 | 下标 | |
| 一个非空连续区间 | 左右端点 | |
| 网格中的定长线段 | 起点、方向和长度 | 检查边界,按题意区分正反方向 |
任意无序位置对都能把较小下标放在前面,得到唯一的 ,因此枚举全部这样的下标对就能不重不漏。连续区间同理由唯一的左右端点确定。
以三个位置为例,无序位置对恰好是 。若同时枚举 ,它和 指向同一个无序对象;若允许 ,又会加入“选择同一位置两次”的对象。条件 同时排除了这两类多余候选。
连续区间也可以这样检查。长度为 的数组有 六个非空区间。每个区间只由端点确定,不能把它与任意挑出的非连续位置集合混为一类。
位置与数值不能混淆。数组 中,两个 分别与 配对,是两个不同的位置对;只有题目要求按数值去重时才能合并。
2. 利用等式减少枚举变量
例题:三连击(升级版)。
简易题面:将数字 至 各使用一次,组成三个三位数 ,使 。按 递增输出全部方案;无解时输出 No!!!。
数据范围:,三个结果均为三位正整数。
分别枚举三个三位数需要检查 组候选。比例关系可以减少枚举变量:当 时,确定 就唯一确定了
因此只枚举 ,先检查 能否被 整除,再检查 是否为三位数,以及九个数位是否恰好使用 至 各一次。例如比例为 时, 合法, 因数位重复而不合法。若 ,第一个数只能为 ,直接判定无解。
用比例 手算三个候选,可以看出检查的先后顺序:
| 首数 | 等式确定的 | 数位情况 | 结论 |
|---|---|---|---|
| 重复 | 舍弃 | ||
| 至 各一次 | 输出 | ||
| 不是三位数 | 不必继续拆位 |
代码的 表示当前候选九个数位中数字 出现的次数;它必须在每个候选开始时清零。 只表示到目前为止是否输出过方案,不随候选清零。两个变量服务于不同范围的工作,重置时机也不同。
#include <bits/stdc++.h>
using namespace std;
int cnt[10],v[3];
int main(){
int A,B,C;
bool found=0;
cin>>A>>B>>C;
if(A>0){
for(int x=100;x<=999;++x){
if(x*B%A!=0||x*C%A!=0)continue;
int y=x*B/A,z=x*C/A;
if(y<100||y>999||z<100||z>999)continue;
for(int d=0;d<=9;++d)cnt[d]=0;
v[0]=x;
v[1]=y;
v[2]=z;
for(int i=0;i<3;++i){
int t=v[i];
while(t>0){
++cnt[t%10];
t/=10;
}
}
bool ok=cnt[0]==0;
for(int d=1;d<=9;++d){
if(cnt[d]!=1)ok=0;
}
if(ok){
cout<<x<<' '<<y<<' '<<z<<'\n';
found=1;
}
}
}
if(!found)puts("No!!!");
}
程序最后检查 ,仍为假时输出 No!!!。每个合法方案都有唯一的首数,枚举会按递增顺序访问它,因此输出不重不漏。共检查 个首数,每次处理九个数位;乘积不超过 ,使用 足够。
同理,方程 在 、 时,可枚举 ,再通过整除检查确定 。减少变量的依据是等式约束。
3. 调整枚举顺序
简易题面:按编号依次铺放 张矩形地毯,后铺的盖住先铺的。求覆盖查询点的最上面一张地毯的编号,无覆盖时输出 ,边界也算覆盖。
数据范围:,左下角坐标和边长均在 至 之间。
设第 张地毯左下角为 ,横向、纵向边长分别为 。题目只查询一个点 ,无需逐格铺设,只需检查
从前往后检查时,每遇到覆盖就更新答案,最终留下最后一张。既然答案是覆盖该点的最大编号,改成从后往前检查,遇到第一张覆盖就能停止。
例如共有 张地毯,其中编号 覆盖查询点。从编号 开始: 不覆盖,继续; 覆盖,答案已经确定。未检查的 即使覆盖,也必然在第 张下面。这个提前停止的理由来自“编号越大越靠上”,并不来自地毯面积或离查询点的距离。
程序按原输入顺序保存四组参数,循环结束后输出一次答案。
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N],b[N],g[N],k[N];
int main(){
int n,x,y;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i]>>b[i]>>g[i]>>k[i];
cin>>x>>y;
int ans=-1;
for(int i=n;i>=1;--i){
if(a[i]<=x&&x<=a[i]+g[i]&&b[i]<=y&&y<=b[i]+k[i]){
ans=i;
break;
}
}
cout<<ans<<'\n';
}
例如覆盖编号为 ,逆序首先找到 ;没有覆盖则保留 。两种顺序的最坏时间均为 ,逆序只是允许提前结束。
4. 按规则维护过程状态
简易题面:W、L 分别表示双方得分,E 表示记录结束,其后内容忽略。分别按 分制和 分制输出各局比分;一方达到规定分数且领先至少两分才结束一局。最后还要输出当前局比分,两种分制之间空一行。
数据范围:每行至多 个字符,原题至多 行;洛谷保留的一组数据有 行。
每个字符只改变一方得分,按顺序处理即可。当前局用 记录比分:先得分,再判断是否满足
其中 为规定分数。例如 分制的 尚未结束, 才结束;结束时先输出,再清零。两种分制的分局位置不同,应分别从 开始处理同一份记录。
把比分状态和操作顺序写成一张局部表。假定正在按 分制比赛,当前已到 :
| 新得分 | 加分后 | 是否结局 | 留给下一条记录的状态 |
|---|---|---|---|
W | 分差为 ,否 | ||
L | 否 | ||
W | 否 | ||
W | 是,输出比分 |
读到 E 时直接停止收集,既不加分,也不再读取它后面的内容。 会跳过行间空白,因此换行不会变成一次得分。数组开到 ,覆盖题面所述记录规模; 保存实际收集的字符数。
#include <bits/stdc++.h>
using namespace std;
const int N=63010;
char s[N];
int n;
void play(int lim){
int a=0,b=0;
for(int i=0;i<n&&s[i]!='E';++i){
if(s[i]=='W')++a;
else if(s[i]=='L')++b;
if(max(a,b)>=lim&&abs(a-b)>=2){
printf("%d:%d\n",a,b);
a=b=0;
}
}
printf("%d:%d\n",a,b);
}
int main(){
char c;
while(cin>>c){
if(c=='E')break;
s[n++]=c;
}
play(11);
puts("");
play(21);
}
分别调用 、,中间输出空行。循环结束后仍需输出当前比分:即使开头就是 E,或恰好在一局结束后终止,也要输出 0:0。设记录长度为 ,两次扫描总时间为 ,保存记录需要 空间。
5. 网格枚举与状态更新
5.1 按坐标枚举邻居
简易题面:给出 行 列的网格,* 表示地雷,? 表示空格。保留地雷,将每个空格改为周围八个相邻位置中的地雷数量。
数据范围:。
每个空格只需检查八个邻居。它们的行、列增量均在 中,排除同时为 即可。边缘邻居可能越界,必须先判断坐标是否合法,再读取数组。
以原图 *? / ?? 为例,斜线这里只用于分隔两行。右下角 枚举出的九组增量中, 指向自己,必须跳过;若新坐标是 ,必须因为越界跳过;增量 到达 ,读到地雷,计数加一。最终输出 *1 / 11。
下面原图存于 ,结果存于 ,行号为 至 ,列号为 至 。每行字符串从下标 读入;全局结果数组的行末仍为零字符,可以直接用 输出。
#include <bits/stdc++.h>
using namespace std;
char g[105][105],b[105][105];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>(g[i]+1);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(g[i][j]=='*'){
b[i][j]='*';
continue;
}
int cnt=0;
for(int dx=-1;dx<=1;++dx){
for(int dy=-1;dy<=1;++dy){
if(dx==0&&dy==0)continue;
int x=i+dx,y=j+dy;
if(x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]=='*')++cnt;
}
}
b[i][j]=char('0'+cnt);
}
}
for(int i=1;i<=n;++i)puts(b[i]+1);
}
只有左上角为雷的 网格,其余三格都应显示 ,因为斜角也相邻。每格至多检查八次,时间、存图空间均为 。
5.2 枚举起点与固定方向
例题:单词方阵。
简易题面:在字母方阵中找出所有沿同一直线连续排列的 yizhong,方向可以是上、下、左、右或四个斜向,单词可以交叉。保留属于这些单词的字母,其余位置输出 *。
数据范围:方阵大小为 ,,目标单词长度为 。
先把每个格子作为单词开头,检查能否连续读出七个字母。题目要求整个单词方向不变,因此确定起点 和方向增量 后,剩余位置就全部确定:
枚举每个起点和八个方向,沿该方向逐字比较;越界或字母不符就放弃,全部匹配后再标记七个位置。必须先检查完整个单词,避免留下失败候选的部分标记;标记也不能改动原图,否则会影响交叉单词。
例如第一行从第一列开始恰好是 yizhong,起点 、方向 会依次访问 至 ,七次比较全部成功后才标记。若这一行是 yizhonx,前六次虽然成功,第七次失败,整条候选都不能留下标记。若另一个单词从交叉处穿过,读取的仍是原字母,因此不会被已经成功的候选破坏。
代码把“检查完整候选”和“提交候选结果”分成两个循环。 存原图,下标从 开始;布尔数组 初始为假,只回答某个格子是否属于至少一个完整单词。
#include <bits/stdc++.h>
using namespace std;
char g[105][105];
bool vis[105][105];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>(g[i]+1);
char s[]="yizhong";
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
for(int d=0;d<8;++d){
bool ok=1;
for(int t=0;t<7;++t){
int x=i+t*dx[d],y=j+t*dy[d];
if(x<1||x>n||y<1||y>n||g[x][y]!=s[t]){
ok=0;
break;
}
}
if(ok){
for(int t=0;t<7;++t)vis[i+t*dx[d]][j+t*dy[d]]=1;
}
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)putchar(vis[i][j]?g[i][j]:'*');
puts("");
}
}
最后按 输出原字母或 *。每个单词的起点、方向都在枚举范围内,因此不会遗漏;交叉位置重复标记不影响结果。时间为 ,空间为 。若改为统计无向线段且正反算同一条,则只枚举一半方向,避免重复计数。
5.3 区分旧状态与新状态
扫雷只读取地雷标记,将 ? 原地改成数字不会影响后续计数;单词方阵则需要保留全部原字母。能否原地更新,取决于是否会覆盖后续仍需读取的旧值。
例如旧数组为 ,首项不变,其余项同时变成“旧的左邻项与自身之和”,应得到 。从左往右原地更新会让第三项误用新的第二项,得到 。
| 写入次序 | 写完第二项后的数组 | 写第三项所用左邻值 | 最终结果 |
|---|---|---|---|
| 从左到右原地写入 | 新值 | ,错误 | |
| 从右到左原地写入 | 第三项先变为 | 旧值 | ,正确 |
| 从旧数组读、向新数组写 | 旧数组保持 | 旧值 | ,正确 |
双数组是通用做法:从旧数组 计算 ,全部完成后再替换;未重新计算的位置需保留旧值。本例也可从右往左原地更新,使所需的左邻项仍是旧值。关键是保存必要的旧状态,而非必须使用两个数组。
6. 日期合法性与候选构造
简易题面:日期写成八位整数,依次为四位年、两位月、两位日。统计给定闭区间内有多少个合法日期,其八位表示是回文。
数据范围:起止日期合法且起始不晚于结束,年份为 至 。
直接逐日模拟并检查回文,需要遍历所有日期、处理月末和年末进位。回文的后四位由前四位唯一确定,而前四位正是年份,因此每年只需构造一个候选。例如 生成 ,但 生成的 月份非法。
构造后先检查月份,再检查当月天数和区间。闰年二月有 天,闰年条件为
例如 年是闰年, 年不是。构造候选本身不能保证它是真实日期:
| 年份 | 回文候选 | 拆出的月、日 | 合法性 |
|---|---|---|---|
| 合法 | |||
| 合法 | |||
| 月份非法 |
月份必须先验证,否则拿 当下标访问月长数组已经越界,之后再判断日数也来不及。合法性通过后仍要判断整个八位数是否在 内,因为区间的第一年和最后一年可能只包含一部分日期。以下 为起止日期, 初始为 ,平年月长存于 。
#include <bits/stdc++.h>
using namespace std;
int main(){
int l,r,ans=0;
cin>>l>>r;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
for(int y=l/10000;y<=r/10000;++y){
int x=y,t=y;
for(int i=0;i<4;++i){
x=x*10+t%10;
t/=10;
}
int m=x/100%100,d=x%100;
if(m<1||m>12)continue;
bool leap=y%400==0||(y%4==0&&y%100!=0);
int lim=days[m]+(m==2&&leap);
if(d>=1&&d<=lim&&x>=l&&x<=r)++ans;
}
cout<<ans<<'\n';
}
每个合法回文日期都由其年份唯一构造,因此不重不漏。设区间含 个年份,时间为 ,额外空间为 ,本题至多检查 个候选。
需要逐日模拟时,应按当前年月确定天数,再处理进位;跨年后重算闰年。时刻计算可先统一单位,例如将 时 分转为 分钟,运算后用整除、取余还原。
7. 按字符串规则划分处理对象
简易题面:给出目标单词和一行只含英文字母、空格的文章。忽略大小写,统计完整单词的匹配次数及首次出现的下标;下标从 开始,空格也占位置,无匹配时输出 。
数据范围:单词长度为 至 ,文章长度为 至 。
逐字符尝试匹配,还需检查左右边界:To 能匹配 ,today 的前两个字母却不算。既然空格已划分单词,可先取出完整单词再比较,省去额外的边界判断。
扫描时跳过空格,记录起点 ,走到空格或文章末尾,得到单词区间 。长度相同才逐字比较,用 忽略大小写。例如目标为 ,文章为 To today TO。跳过下标 的空格,得到单词区间 ,匹配;下一个区间 的长度为 ,不匹配;最后一个区间 匹配,答案为 次、首次位置 。这里右端点不属于单词,所以长度是右端减左端。
以下目标 长度为 ,文章 长度为 ,均从下标 开始;两行均用 读入,保留文章的全部空格。题目仅含英文字母和空格,传入 的字符都在相应有效范围内。
#include <bits/stdc++.h>
using namespace std;
int main(){
string s,t;
getline(cin,t);
getline(cin,s);
int n=s.size(),m=t.size(),ans=0,first=-1,i=0;
while(i<n){
while(i<n&&s[i]==' ')++i;
if(i==n)break;
int l=i;
while(i<n&&s[i]!=' ')++i;
if(i-l!=m)continue;
bool ok=1;
for(int j=0;j<m;++j){
if(tolower(s[l+j])!=tolower(t[j])){
ok=0;
break;
}
}
if(ok){
if(ans==0)first=l;
++ans;
}
}
if(ans==0)puts("-1");
else printf("%d %d\n",ans,first);
}
无匹配时输出 ,否则输出 、。例如 To today TO 匹配 两次,首次下标为 。扫描和比较的字符总量为 ;最后一个单词在到达文章末尾时同样结算,不能只在遇到空格时处理。
8. 环形位置与周期序列
8.1 用取余代替逐个移动
简易题面:玩具按逆时针顺序围成一圈,各有名字和朝向。从第一个开始,执行“向左或右数 个”的指令,左右以当前玩具朝向为准,输出最终玩具的名字。
数据范围:,,名字长度不超过 。朝内、朝外分别记为 ,向左、向右分别记为 。
逐个移动最坏需要 时间。一条指令的方向由起点玩具确定,途中不会改变,因此可直接计算终点。按输入顺序编号为 至 ,下标增加表示逆时针移动。为了确定左右与编号的关系,可以把当前玩具想象在圆的最上方:朝内时它面向下,左手指向图的右侧,也就是沿圆顺时针移动,下标减少;右手方向相反。朝外时面向上,左右对应的圆周方向互换。旋转整张图不会改变这个关系,因此其他位置也适用:
| 当前朝向 | 指令方向 | 下标变化 |
|---|---|---|
| 朝内 | 向左 | 减少 |
| 朝内 | 向右 | 增加 |
| 朝外 | 向左 | 增加 |
| 朝外 | 向右 | 减少 |
两个编码相同时减,不同时加,再对 取余处理绕圈。这个相同与不同的规律应从四种情况表中总结,不能先猜一个异或表达式再尝试套题。
例如有 个玩具,从下标 的朝内玩具向左走 个,到下标 。若下标 的玩具朝外,下一条向左走 个就会增加下标,到 。两条指令都写“左”,实际编号方向却相反,因为第二条读取的是新起点的朝向。以下 初始为 , 为当前朝向, 为当前指令。
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int dir[N];
char name[N][15];
int main(){
int n,m,pos=0;
cin>>n>>m;
for(int i=0;i<n;++i)cin>>dir[i]>>name[i];
while(m--){
int a,s;
cin>>a>>s;
if(dir[pos]==a)pos=(pos-s+n)%n;
else pos=(pos+s)%n;
}
puts(name[pos]);
}
例如 ,从下标 减少 ,到达 。本题 ,加一个 即可保证非负;若允许更大步数,应先对 取余。下一条指令读取新位置的朝向。处理指令的时间为 ,保存玩具需要 空间。
8.2 维护多个周期的当前位置
简易题面:双方循环使用各自的出拳序列,比赛 轮。每轮胜者得一分,败者和平局不得分,求双方总分。手势关系如下。
| 编号与手势 | 能战胜的手势 |
|---|---|
| :剪刀 | 布、蜥蜴人 |
| :石头 | 剪刀、蜥蜴人 |
| :布 | 石头、斯波克 |
| :蜥蜴人 | 布、斯波克 |
| :斯波克 | 剪刀、石头 |
数据范围:, 为双方周期长度,手势编号为 至 。
逐轮模拟时,无需复制出拳序列:从第 轮开始,第 轮的下标分别为 、。胜负组合只有 种,用二维表 保存前者得分,反查 得到后者得分。例如甲循环出 ,乙循环出 。前三轮分别为 、、,结果是甲胜、乙胜、平局,总分 。第四轮甲回到下标 ,乙回到下标 ,不能把双方都强行重置到第一个手势。以下序列 从下标 开始。
#include <bits/stdc++.h>
using namespace std;
int a[210],b[210];
int main(){
int N,p,q;
cin>>N>>p>>q;
for(int i=0;i<p;++i)cin>>a[i];
for(int i=0;i<q;++i)cin>>b[i];
int win[5][5]={
{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}
};
int sa=0,sb=0;
for(int i=0;i<N;++i){
int x=a[i%p],y=b[i%q];
sa+=win[x][y];
sb+=win[y][x];
}
cout<<sa<<' '<<sb<<'\n';
}
若 ,双方下标组合依次为
只有双方下标都复原,后续过程才整体重复。原题逐轮处理的时间为 ,空间为 。若轮数很大,可模拟至组合首次回到 ,求出周期长度 和得分,再计算 个整周期及 轮余数的贡献。
9. 用有限状态判断过程是否终止
简易题面:农夫和牛群均朝北,每分钟同时行动:前方可走则前进一步,否则原地顺时针转 度。求首次在某分钟结束时位于同一格的时间,永不相遇输出 ,途中交错不算相遇。
数据范围:地图固定为 ,含空地、障碍和双方各一个起点,起点不同。
直接按分钟模拟,可能因永不相遇而无法结束。固定地图上,下一步由位置和朝向决定,因此需记录双方各自的“行、列、朝向”。只记录位置会混淆不同朝向,只记录一方也无法确定另一方的动作。
完整状态再次出现时,之后的变化必然重复;此前未相遇,以后也不会相遇。每方至多有 种状态,可编码为
行、列从 开始,上、右、下、左编号为 。例如位置 朝北的编号为 ,同一位置朝东则为 ;两个状态的位置相同,下一步却可能不同。完整状态是一对编号 ,最多有 种。
在一张全为空地的地图上,农夫从 朝北、牛从 朝北出发。第一分钟两者都因北侧越界而向右转,位置不变;第二分钟分别到 、。第一分钟结束时位置与初始相同,但方向不同,不能仅凭位置断定进入循环。
每轮开始先判断是否已经相遇,再判断这个完整状态是否见过;未见过就登记,然后双方各执行一次行动,时间增加一。以下 、 为双方位置, 初始为 , 初始为假,地图 中 * 表示障碍。
#include <bits/stdc++.h>
using namespace std;
char g[10][11];
int x[2],y[2],d[2];
bool vis[400][400];
int main(){
for(int i=0;i<10;++i){
cin>>g[i];
for(int j=0;j<10;++j){
if(g[i][j]=='F'){
x[0]=i;
y[0]=j;
}
if(g[i][j]=='C'){
x[1]=i;
y[1]=j;
}
}
}
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int ans=0;
while(x[0]!=x[1]||y[0]!=y[1]){
int u=(x[0]*10+y[0])*4+d[0],v=(x[1]*10+y[1])*4+d[1];
if(vis[u][v]){
ans=0;
break;
}
vis[u][v]=1;
for(int k=0;k<2;++k){
int nx=x[k]+dx[d[k]],ny=y[k]+dy[d[k]];
if(nx<0||nx>=10||ny<0||ny>=10||g[nx][ny]=='*')d[k]=(d[k]+1)%4;
else{
x[k]=nx;
y[k]=ny;
}
}
++ans;
}
cout<<ans<<'\n';
}
双方只读取自身状态和固定地图,因此依次计算也符合同时行动;相遇在双方都更新后判断。转向已经消耗一分钟,不能立即再走一步。设完整状态数为 ,每个状态最多处理一次,时间、标记空间均为 。
有限状态过程可能先经过一段前缀再进入循环,如 。计算远期状态时,应先扣除前缀,再对循环长度取余,不能从起点直接套用周期。
10. 枚举规则,再执行模拟
例题:Codeforces 908B·New Year and Buggy Bot。
简易题面:地图含起点 S、终点 E、障碍 #。指令由 0 至 3 组成,四个数字与四个方向一一对应,但关系未知。统计能到达终点的完整对应关系数;撞墙或越界立即失败,到达终点立即成功,均停止后续指令。
数据范围:,指令长度为 至 ,起点和终点各一个。
对应关系确定后,就能逐条模拟指令;未知的关系则放在外层枚举。四个数字依次有 种选择,共 种。题目统计对应关系,即使产生相同路线也不能合并。
先看只有两行两列的空地图,起点为左上角,终点为右上角,指令是 00。只要数字 0 对应向右,第一条指令就到达终点,立即成功;不能继续执行第二条再以越界判失败。其余三个数字没有出现,但它们仍必须与剩余三个方向一一对应,共有 种,因此答案为 。
令 为数字 对应的方向,方向数组沿用上一节的上、右、下、左定义。外层用三层循环选出不同的 ;方向编号总和为 ,所以 取剩余编号。每次 都从起点恢复位置,不能接着上一个对应关系的终点继续走。下面给出枚举与模拟合在一起的完整程序。
#include <bits/stdc++.h>
using namespace std;
int n,m,sx,sy,len,p[4];
char g[55][55],s[105];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool check(){
int x=sx,y=sy;
for(int i=0;i<len;++i){
int d=p[s[i]-'0'];
x+=dx[d];
y+=dy[d];
if(x<0||x>=n||y<0||y>=m||g[x][y]=='#')return 0;
if(g[x][y]=='E')return 1;
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;++i){
cin>>g[i];
for(int j=0;j<m;++j){
if(g[i][j]=='S'){
sx=i;
sy=j;
}
}
}
cin>>s;
len=strlen(s);
int ans=0;
for(p[0]=0;p[0]<4;++p[0]){
for(p[1]=0;p[1]<4;++p[1]){
if(p[1]==p[0])continue;
for(p[2]=0;p[2]<4;++p[2]){
if(p[2]==p[0]||p[2]==p[1])continue;
p[3]=6-p[0]-p[1]-p[2];
ans+=check();
}
}
}
cout<<ans<<'\n';
}
成功、失败均立即返回,避免后续指令改变已确定的结果。 累加的是成功的对应关系数;没有用过的数字的不同映射也分别计数。
每种对应关系由前三个编号唯一确定,枚举不重不漏。设指令长度为 ,总时间为 ,空间为 。
11. 把过程写成可检查的规则
枚举程序可以逐项核对三件事:每个合法对象是否有表示,循环是否会访问这个表示,同一对象是否产生多份输出。模拟程序则要明确初始状态、一步转移和停止时刻;“同时发生”还要求判断计算新状态时能否读取已更新的值。
这两种方法并不互斥。三连击先由一个候选推导其余数值,再检查数位;机器人先枚举方向对应关系,再执行整条指令。遇到规模过大时,应先定位反复做的工作或可用的等式,而不是因为方法名字叫枚举就认定一定超时。
12. 作业
巩固练习
提高训练
- CSP-J 2021·网络连接
- NOIP 2004 普及组·花生采摘
- NOIP 2007 普及组·守望者的逃离:还需证明行动选择的最优性,建议学完第八章贪心或第十二章 DP 后完成。
留言
可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。
正在加载留言区…