第二章:枚举与模拟

给出一串数字,要求找出所有符合条件的组合;给出一串操作,要求算出最终结果。这两类任务都能从很直接的做法开始:前者把候选逐个试过,后者把过程一步步执行。前者称为枚举,后者称为模拟。

“逐个试”仍需要设计。枚举三个数,究竟枚举数值还是位置?两个顺序不同的选择算一组还是两组?模拟一次行动,先判断结束还是先更新?这些选择决定了程序是否与题意一致。本章从数位计数开始,每次只引入一种新的处理困难,直到把“枚举一种规则,再模拟规则下的过程”连起来。

阅读前需要掌握循环、数组、字符串和函数。每段 C++ 代码都是独立完整程序,分别对应本节题目的输入输出;同名变量不需要跨程序合并。数组容量由各题数据范围确定。

1. 确定枚举对象与范围

1.1 枚举整数与数位

例题:NOIP 2013 普及组·计数问题。

简易题面:统计整数 11 至 nn 的十进制表示中,数字 xx 总共出现了多少次。

数据范围:1≤n≤1061\le n\le 10^6,0≤x≤90\le x\le 9。

题目统计出现次数,例如 1111 中的两个 11 都要计入答案。因此,直接枚举每个整数,再逐位检查。对 1010 取余得到个位,整除 1010 去掉个位;例如 101101 依次拆出 1,0,11,0,1,顺序不影响计数。

先只处理一个数 101101,目标数字取 11。每一轮先查看个位,再删去已经查看过的个位:

轮次处理前的 ttt mod 10t\bmod10本轮增加次数整除后 tt
1110110111111010
221010000011
3311111100

三个位置处理完后,t=0t=0,循环结束。这里每个位置都能贡献一次,所以不能在发现第一个 11 后停止。外层再让 ii 依次取 11 至 nn,便能检查整个范围。拆位会改变数值,需把循环变量 ii 复制到 tt;否则外层循环的计数也会被破坏。ansans 在主函数中初始化为 00。

#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';
}

每个整数的每一位恰好检查一次。设最大整数有 DD 位,时间复杂度为 O(nD)O(nD),额外空间为 O(1)O(1)。本题至多七百万次拆位,直接枚举足够。若枚举范围包含整数 00,需单独统计它的一位数字 00,因为 while (t > 0)\texttt{while (t > 0)} 不会执行。

1.2 用唯一表示避免重复枚举

候选对象表示方式范围或去重规则
一个整数数值 xx枚举给定闭区间
两个不同位置组成的无序数对下标 i,ji,j1≤i<j≤n1\le i<j\le n
一个非空连续区间左右端点 l,rl,r1≤l≤r≤n1\le l\le r\le n
网格中的定长线段起点、方向和长度检查边界,按题意区分正反方向

任意无序位置对都能把较小下标放在前面,得到唯一的 i<ji<j,因此枚举全部这样的下标对就能不重不漏。连续区间同理由唯一的左右端点确定。

以三个位置为例,无序位置对恰好是 (1,2),(1,3),(2,3)(1,2),(1,3),(2,3)。若同时枚举 (2,1)(2,1),它和 (1,2)(1,2) 指向同一个无序对象;若允许 (1,1)(1,1),又会加入“选择同一位置两次”的对象。条件 i<ji<j 同时排除了这两类多余候选。

三个位置的数对矩阵:只访问对角线上方的三个格子

连续区间也可以这样检查。长度为 33 的数组有 [1,1],[1,2],[1,3],[2,2],[2,3],[3,3][1,1],[1,2],[1,3],[2,2],[2,3],[3,3] 六个非空区间。每个区间只由端点确定,不能把它与任意挑出的非连续位置集合混为一类。

位置与数值不能混淆。数组 2,2,32,2,3 中,两个 22 分别与 33 配对,是两个不同的位置对;只有题目要求按数值去重时才能合并。

2. 利用等式减少枚举变量

例题:三连击(升级版)。

简易题面:将数字 11 至 99 各使用一次,组成三个三位数 x,y,zx,y,z,使 x:y:z=A:B:Cx:y:z=A:B:C。按 xx 递增输出全部方案;无解时输出 No!!!。

数据范围:0≤A<B<C≤9990\le A<B<C\le 999,三个结果均为三位正整数。

分别枚举三个三位数需要检查 9003900^3 组候选。比例关系可以减少枚举变量:当 A>0A>0 时,确定 xx 就唯一确定了

y=xBA,z=xCA.y=\frac{xB}{A},\qquad z=\frac{xC}{A}.

因此只枚举 xx,先检查 xB,xCxB,xC 能否被 AA 整除,再检查 y,zy,z 是否为三位数,以及九个数位是否恰好使用 11 至 99 各一次。例如比例为 1:2:31:2:3 时,192,384,576192,384,576 合法,123,246,369123,246,369 因数位重复而不合法。若 A=0A=0,第一个数只能为 00,直接判定无解。

用比例 1:2:31:2:3 手算三个候选,可以看出检查的先后顺序:

首数 xx等式确定的 y,zy,z数位情况结论
123123246,369246,3692,3,62,3,6 重复舍弃
192192384,576384,57611 至 99 各一次输出
400400800,1200800,1200zz 不是三位数不必继续拆位

代码的 cnt[d]cnt[d] 表示当前候选九个数位中数字 dd 出现的次数;它必须在每个候选开始时清零。foundfound 只表示到目前为止是否输出过方案,不随候选清零。两个变量服务于不同范围的工作,重置时机也不同。

#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!!!");
}

程序最后检查 foundfound,仍为假时输出 No!!!。每个合法方案都有唯一的首数,枚举会按递增顺序访问它,因此输出不重不漏。共检查 900900 个首数,每次处理九个数位;乘积不超过 9992999^2,使用 int\texttt{int} 足够。

同理,方程 ax+by=nax+by=n 在 a,b>0a,b>0、x,y≥0x,y\ge0 时,可枚举 0≤x≤⌊n/a⌋0\le x\le\lfloor n/a\rfloor,再通过整除检查确定 yy。减少变量的依据是等式约束。

3. 调整枚举顺序

例题:NOIP 2011 提高组·铺地毯。

简易题面:按编号依次铺放 nn 张矩形地毯,后铺的盖住先铺的。求覆盖查询点的最上面一张地毯的编号,无覆盖时输出 −1-1,边界也算覆盖。

数据范围:0≤n≤1040\le n\le10^4,左下角坐标和边长均在 00 至 10510^5 之间。

设第 ii 张地毯左下角为 (ai,bi)(a_i,b_i),横向、纵向边长分别为 gi,kig_i,k_i。题目只查询一个点 (x,y)(x,y),无需逐格铺设,只需检查

ai≤x≤ai+gi,bi≤y≤bi+ki.a_i\le x\le a_i+g_i,\qquad b_i\le y\le b_i+k_i.

从前往后检查时,每遇到覆盖就更新答案,最终留下最后一张。既然答案是覆盖该点的最大编号,改成从后往前检查,遇到第一张覆盖就能停止。

例如共有 55 张地毯,其中编号 2,42,4 覆盖查询点。从编号 55 开始:55 不覆盖,继续;44 覆盖,答案已经确定。未检查的 1,2,31,2,3 即使覆盖,也必然在第 44 张下面。这个提前停止的理由来自“编号越大越靠上”,并不来自地毯面积或离查询点的距离。

程序按原输入顺序保存四组参数,循环结束后输出一次答案。

#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';
}

例如覆盖编号为 2,5,72,5,7,逆序首先找到 77;没有覆盖则保留 −1-1。两种顺序的最坏时间均为 O(n)O(n),逆序只是允许提前结束。

4. 按规则维护过程状态

例题:NOIP 2003 普及组·乒乓球。

简易题面:W、L 分别表示双方得分,E 表示记录结束,其后内容忽略。分别按 1111 分制和 2121 分制输出各局比分;一方达到规定分数且领先至少两分才结束一局。最后还要输出当前局比分,两种分制之间空一行。

数据范围:每行至多 2525 个字符,原题至多 25002500 行;洛谷保留的一组数据有 25012501 行。

每个字符只改变一方得分,按顺序处理即可。当前局用 a,ba,b 记录比分:先得分,再判断是否满足

max⁡(a,b)≥L且∣a−b∣≥2.\max(a,b)\ge L\quad\text{且}\quad |a-b|\ge2.

其中 LL 为规定分数。例如 1111 分制的 11:1011:10 尚未结束,12:1012:10 才结束;结束时先输出,再清零。两种分制的分局位置不同,应分别从 0:00:0 开始处理同一份记录。

把比分状态和操作顺序写成一张局部表。假定正在按 1111 分制比赛,当前已到 10:1010:10:

新得分加分后是否结局留给下一条记录的状态
W11:1011:10分差为 11,否11:1011:10
L11:1111:11否11:1111:11
W12:1112:11否12:1112:11
W13:1113:11是,输出比分0:00:0

读到 E 时直接停止收集,既不加分,也不再读取它后面的内容。cin >> c\texttt{cin >> c} 会跳过行间空白,因此换行不会变成一次得分。数组开到 6301063010,覆盖题面所述记录规模;nn 保存实际收集的字符数。

#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);
}

分别调用 play(11)\texttt{play(11)}、play(21)\texttt{play(21)},中间输出空行。循环结束后仍需输出当前比分:即使开头就是 E,或恰好在一局结束后终止,也要输出 0:0。设记录长度为 TT,两次扫描总时间为 O(T)O(T),保存记录需要 O(T)O(T) 空间。

5. 网格枚举与状态更新

5.1 按坐标枚举邻居

例题:NOIP 2015 普及组·扫雷游戏。

简易题面:给出 nn 行 mm 列的网格,* 表示地雷,? 表示空格。保留地雷,将每个空格改为周围八个相邻位置中的地雷数量。

数据范围:1≤n,m≤1001\le n,m\le100。

每个空格只需检查八个邻居。它们的行、列增量均在 −1,0,1-1,0,1 中,排除同时为 00 即可。边缘邻居可能越界,必须先判断坐标是否合法,再读取数组。

以原图 *? / ?? 为例,斜线这里只用于分隔两行。右下角 (2,2)(2,2) 枚举出的九组增量中,(0,0)(0,0) 指向自己,必须跳过;若新坐标是 (3,2)(3,2),必须因为越界跳过;增量 (−1,−1)(-1,-1) 到达 (1,1)(1,1),读到地雷,计数加一。最终输出 *1 / 11。

下面原图存于 gg,结果存于 bb,行号为 11 至 nn,列号为 11 至 mm。每行字符串从下标 11 读入;全局结果数组的行末仍为零字符,可以直接用 puts\texttt{puts} 输出。

#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);
}

只有左上角为雷的 2×22\times2 网格,其余三格都应显示 11,因为斜角也相邻。每格至多检查八次,时间、存图空间均为 O(nm)O(nm)。

5.2 枚举起点与固定方向

例题:单词方阵。

简易题面:在字母方阵中找出所有沿同一直线连续排列的 yizhong,方向可以是上、下、左、右或四个斜向,单词可以交叉。保留属于这些单词的字母,其余位置输出 *。

数据范围:方阵大小为 n×nn\times n,7≤n≤1007\le n\le100,目标单词长度为 77。

先把每个格子作为单词开头,检查能否连续读出七个字母。题目要求整个单词方向不变,因此确定起点 (x,y)(x,y) 和方向增量 (dx,dy)(d_x,d_y) 后,剩余位置就全部确定:

(x+tdx,y+tdy),0≤t<7.(x+td_x,y+td_y),\qquad 0\le t<7.

枚举每个起点和八个方向,沿该方向逐字比较;越界或字母不符就放弃,全部匹配后再标记七个位置。必须先检查完整个单词,避免留下失败候选的部分标记;标记也不能改动原图,否则会影响交叉单词。

例如第一行从第一列开始恰好是 yizhong,起点 (1,1)(1,1)、方向 (0,1)(0,1) 会依次访问 (1,1)(1,1) 至 (1,7)(1,7),七次比较全部成功后才标记。若这一行是 yizhonx,前六次虽然成功,第七次失败,整条候选都不能留下标记。若另一个单词从交叉处穿过,读取的仍是原字母,因此不会被已经成功的候选破坏。

代码把“检查完整候选”和“提交候选结果”分成两个循环。g[105][105]g[105][105] 存原图,下标从 11 开始;布尔数组 vis[105][105]vis[105][105] 初始为假,只回答某个格子是否属于至少一个完整单词。

#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("");
    }
}

最后按 visvis 输出原字母或 *。每个单词的起点、方向都在枚举范围内,因此不会遗漏;交叉位置重复标记不影响结果。时间为 O(8n2⋅7)=O(n2)O(8n^2\cdot7)=O(n^2),空间为 O(n2)O(n^2)。若改为统计无向线段且正反算同一条,则只枚举一半方向,避免重复计数。

5.3 区分旧状态与新状态

扫雷只读取地雷标记,将 ? 原地改成数字不会影响后续计数;单词方阵则需要保留全部原字母。能否原地更新,取决于是否会覆盖后续仍需读取的旧值。

例如旧数组为 1,2,31,2,3,首项不变,其余项同时变成“旧的左邻项与自身之和”,应得到 1,3,51,3,5。从左往右原地更新会让第三项误用新的第二项,得到 66。

同时更新的依赖:新第三项必须读取旧第二项 2,而不能读新第二项 3

写入次序写完第二项后的数组写第三项所用左邻值最终结果
从左到右原地写入1,3,31,3,3新值 331,3,61,3,6,错误
从右到左原地写入第三项先变为 55旧值 221,3,51,3,5,正确
从旧数组读、向新数组写旧数组保持 1,2,31,2,3旧值 221,3,51,3,5,正确

双数组是通用做法:从旧数组 aa 计算 bb,全部完成后再替换;未重新计算的位置需保留旧值。本例也可从右往左原地更新,使所需的左邻项仍是旧值。关键是保存必要的旧状态,而非必须使用两个数组。

6. 日期合法性与候选构造

例题:NOIP 2016 普及组·回文日期。

简易题面:日期写成八位整数,依次为四位年、两位月、两位日。统计给定闭区间内有多少个合法日期,其八位表示是回文。

数据范围:起止日期合法且起始不晚于结束,年份为 10001000 至 99999999。

直接逐日模拟并检查回文,需要遍历所有日期、处理月末和年末进位。回文的后四位由前四位唯一确定,而前四位正是年份,因此每年只需构造一个候选。例如 20102010 生成 2010010220100102,但 20232023 生成的 2023320220233202 月份非法。

构造后先检查月份,再检查当月天数和区间。闰年二月有 2929 天,闰年条件为

y mod 400=0或(y mod 4=0 且 y mod 100≠0).y\bmod400=0\quad\text{或}\quad(y\bmod4=0\ \text{且}\ y\bmod100\ne0).

例如 20002000 年是闰年,19001900 年不是。构造候选本身不能保证它是真实日期:

年份回文候选拆出的月、日合法性
2010201020100102201001021,21,2合法
2020202020200202202002022,22,2合法
20232023202332022023320232,232,2月份非法

月份必须先验证,否则拿 3232 当下标访问月长数组已经越界,之后再判断日数也来不及。合法性通过后仍要判断整个八位数是否在 [l,r][l,r] 内,因为区间的第一年和最后一年可能只包含一部分日期。以下 l,rl,r 为起止日期,ansans 初始为 00,平年月长存于 daysdays。

#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';
}

每个合法回文日期都由其年份唯一构造,因此不重不漏。设区间含 YY 个年份,时间为 O(Y)O(Y),额外空间为 O(1)O(1),本题至多检查 90009000 个候选。

需要逐日模拟时,应按当前年月确定天数,再处理进位;跨年后重算闰年。时刻计算可先统一单位,例如将 hh 时 mm 分转为 60h+m60h+m 分钟,运算后用整除、取余还原。

7. 按字符串规则划分处理对象

例题:NOIP 2011 普及组·统计单词数。

简易题面:给出目标单词和一行只含英文字母、空格的文章。忽略大小写,统计完整单词的匹配次数及首次出现的下标;下标从 00 开始,空格也占位置,无匹配时输出 −1-1。

数据范围:单词长度为 11 至 1010,文章长度为 11 至 10610^6。

逐字符尝试匹配,还需检查左右边界:To 能匹配 toto,today 的前两个字母却不算。既然空格已划分单词,可先取出完整单词再比较,省去额外的边界判断。

扫描时跳过空格,记录起点 ll,走到空格或文章末尾,得到单词区间 [l,i)[l,i)。长度相同才逐字比较,用 tolower\texttt{tolower} 忽略大小写。例如目标为 toto,文章为 To today TO。跳过下标 0,10,1 的空格,得到单词区间 [2,4)[2,4),匹配;下一个区间 [5,10)[5,10) 的长度为 55,不匹配;最后一个区间 [11,13)[11,13) 匹配,答案为 22 次、首次位置 22。这里右端点不属于单词,所以长度是右端减左端。

以下目标 tt 长度为 mm,文章 ss 长度为 nn,均从下标 00 开始;两行均用 getline\texttt{getline} 读入,保留文章的全部空格。题目仅含英文字母和空格,传入 tolower\texttt{tolower} 的字符都在相应有效范围内。

#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);
}

无匹配时输出 −1-1,否则输出 ansans、firstfirst。例如 To today TO 匹配 toto 两次,首次下标为 22。扫描和比较的字符总量为 O(n+m)O(n+m);最后一个单词在到达文章末尾时同样结算,不能只在遇到空格时处理。

8. 环形位置与周期序列

8.1 用取余代替逐个移动

例题:NOIP 2016 提高组·玩具谜题。

简易题面:玩具按逆时针顺序围成一圈,各有名字和朝向。从第一个开始,执行“向左或右数 ss 个”的指令,左右以当前玩具朝向为准,输出最终玩具的名字。

数据范围:1≤n,m≤1051\le n,m\le10^5,1≤s<n1\le s<n,名字长度不超过 1010。朝内、朝外分别记为 0,10,1,向左、向右分别记为 0,10,1。

逐个移动最坏需要 O(nm)O(nm) 时间。一条指令的方向由起点玩具确定,途中不会改变,因此可直接计算终点。按输入顺序编号为 00 至 n−1n-1,下标增加表示逆时针移动。为了确定左右与编号的关系,可以把当前玩具想象在圆的最上方:朝内时它面向下,左手指向图的右侧,也就是沿圆顺时针移动,下标减少;右手方向相反。朝外时面向上,左右对应的圆周方向互换。旋转整张图不会改变这个关系,因此其他位置也适用:

当前朝向指令方向下标变化
朝内 00向左 00减少
朝内 00向右 11增加
朝外 11向左 00增加
朝外 11向右 11减少

两个编码相同时减,不同时加,再对 nn 取余处理绕圈。这个相同与不同的规律应从四种情况表中总结,不能先猜一个异或表达式再尝试套题。

例如有 55 个玩具,从下标 00 的朝内玩具向左走 22 个,到下标 33。若下标 33 的玩具朝外,下一条向左走 11 个就会增加下标,到 44。两条指令都写“左”,实际编号方向却相反,因为第二条读取的是新起点的朝向。以下 pospos 初始为 00,dir[pos]dir[pos] 为当前朝向,a,sa,s 为当前指令。

#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]);
}

例如 n=5n=5,从下标 11 减少 33,到达 (1−3+5) mod 5=3(1-3+5)\bmod5=3。本题 s<ns<n,加一个 nn 即可保证非负;若允许更大步数,应先对 nn 取余。下一条指令读取新位置的朝向。处理指令的时间为 O(m)O(m),保存玩具需要 O(n)O(n) 空间。

8.2 维护多个周期的当前位置

例题:NOIP 2014 提高组·生活大爆炸版石头剪刀布。

简易题面:双方循环使用各自的出拳序列,比赛 NN 轮。每轮胜者得一分,败者和平局不得分,求双方总分。手势关系如下。

编号与手势能战胜的手势
00:剪刀布、蜥蜴人
11:石头剪刀、蜥蜴人
22:布石头、斯波克
33:蜥蜴人布、斯波克
44:斯波克剪刀、石头

数据范围:1≤N,p,q≤2001\le N,p,q\le200,p,qp,q 为双方周期长度,手势编号为 00 至 44。

逐轮模拟时,无需复制出拳序列:从第 00 轮开始,第 ii 轮的下标分别为 i mod pi\bmod p、i mod qi\bmod q。胜负组合只有 2525 种,用二维表 win[x][y]win[x][y] 保存前者得分,反查 win[y][x]win[y][x] 得到后者得分。例如甲循环出 [0,1][0,1],乙循环出 [2,4,0][2,4,0]。前三轮分别为 (0,2)(0,2)、(1,4)(1,4)、(0,0)(0,0),结果是甲胜、乙胜、平局,总分 1:11:1。第四轮甲回到下标 11,乙回到下标 00,不能把双方都强行重置到第一个手势。以下序列 a,ba,b 从下标 00 开始。

#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';
}

若 p=2,q=3p=2,q=3,双方下标组合依次为

(0,0),(1,1),(0,2),(1,0),(0,1),(1,2),(0,0).(0,0),(1,1),(0,2),(1,0),(0,1),(1,2),(0,0).

只有双方下标都复原,后续过程才整体重复。原题逐轮处理的时间为 O(N)O(N),空间为 O(p+q)O(p+q)。若轮数很大,可模拟至组合首次回到 (0,0)(0,0),求出周期长度 TT 和得分,再计算 ⌊N/T⌋\lfloor N/T\rfloor 个整周期及 N mod TN\bmod T 轮余数的贡献。

9. 用有限状态判断过程是否终止

例题:USACO 2.4·两只塔姆沃斯牛。

简易题面:农夫和牛群均朝北,每分钟同时行动:前方可走则前进一步,否则原地顺时针转 9090 度。求首次在某分钟结束时位于同一格的时间,永不相遇输出 00,途中交错不算相遇。

数据范围:地图固定为 10×1010\times10,含空地、障碍和双方各一个起点,起点不同。

直接按分钟模拟,可能因永不相遇而无法结束。固定地图上,下一步由位置和朝向决定,因此需记录双方各自的“行、列、朝向”。只记录位置会混淆不同朝向,只记录一方也无法确定另一方的动作。

完整状态再次出现时,之后的变化必然重复;此前未相遇,以后也不会相遇。每方至多有 10×10×4=40010\times10\times4=400 种状态,可编码为

id⁡(x,y,d)=(10x+y)×4+d.\operatorname{id}(x,y,d)=(10x+y)\times4+d.

行、列从 00 开始,上、右、下、左编号为 0,1,2,30,1,2,3。例如位置 (2,3)(2,3) 朝北的编号为 9292,同一位置朝东则为 9393;两个状态的位置相同,下一步却可能不同。完整状态是一对编号 (u,v)(u,v),最多有 4002=160000400^2=160000 种。

在一张全为空地的地图上,农夫从 (0,0)(0,0) 朝北、牛从 (0,2)(0,2) 朝北出发。第一分钟两者都因北侧越界而向右转,位置不变;第二分钟分别到 (0,1)(0,1)、(0,3)(0,3)。第一分钟结束时位置与初始相同,但方向不同,不能仅凭位置断定进入循环。

完整状态必须同时记录双方的位置和朝向;重复后后续完全相同

每轮开始先判断是否已经相遇,再判断这个完整状态是否见过;未见过就登记,然后双方各执行一次行动,时间增加一。以下 x[0],y[0]x[0],y[0]、x[1],y[1]x[1],y[1] 为双方位置,d[0],d[1]d[0],d[1] 初始为 00,vis[400][400]vis[400][400] 初始为假,地图 gg 中 * 表示障碍。

#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';
}

双方只读取自身状态和固定地图,因此依次计算也符合同时行动;相遇在双方都更新后判断。转向已经消耗一分钟,不能立即再走一步。设完整状态数为 S≤160000S\le160000,每个状态最多处理一次,时间、标记空间均为 O(S)O(S)。

有限状态过程可能先经过一段前缀再进入循环,如 A,B,C,D,C,D,…A,B,C,D,C,D,\ldots。计算远期状态时,应先扣除前缀,再对循环长度取余,不能从起点直接套用周期。

10. 枚举规则,再执行模拟

例题:Codeforces 908B·New Year and Buggy Bot。

简易题面:地图含起点 S、终点 E、障碍 #。指令由 0 至 3 组成,四个数字与四个方向一一对应,但关系未知。统计能到达终点的完整对应关系数;撞墙或越界立即失败,到达终点立即成功,均停止后续指令。

数据范围:2≤n,m≤502\le n,m\le50,指令长度为 11 至 100100,起点和终点各一个。

对应关系确定后,就能逐条模拟指令;未知的关系则放在外层枚举。四个数字依次有 4,3,2,14,3,2,1 种选择,共 2424 种。题目统计对应关系,即使产生相同路线也不能合并。

先看只有两行两列的空地图,起点为左上角,终点为右上角,指令是 00。只要数字 0 对应向右,第一条指令就到达终点,立即成功;不能继续执行第二条再以越界判失败。其余三个数字没有出现,但它们仍必须与剩余三个方向一一对应,共有 3×2×1=63\times2\times1=6 种,因此答案为 66。

令 p[c]p[c] 为数字 cc 对应的方向,方向数组沿用上一节的上、右、下、左定义。外层用三层循环选出不同的 p[0],p[1],p[2]p[0],p[1],p[2];方向编号总和为 66,所以 p[3]p[3] 取剩余编号。每次 check()\texttt{check()} 都从起点恢复位置,不能接着上一个对应关系的终点继续走。下面给出枚举与模拟合在一起的完整程序。

#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';
}

成功、失败均立即返回,避免后续指令改变已确定的结果。ansans 累加的是成功的对应关系数;没有用过的数字的不同映射也分别计数。

每种对应关系由前三个编号唯一确定,枚举不重不漏。设指令长度为 LL,总时间为 O(nm+24L)O(nm+24L),空间为 O(nm+L)O(nm+L)。

11. 把过程写成可检查的规则

枚举程序可以逐项核对三件事:每个合法对象是否有表示,循环是否会访问这个表示,同一对象是否产生多份输出。模拟程序则要明确初始状态、一步转移和停止时刻;“同时发生”还要求判断计算新状态时能否读取已更新的值。

这两种方法并不互斥。三连击先由一个候选推导其余数值,再检查数位;机器人先枚举方向对应关系,再执行整条指令。遇到规模过大时,应先定位反复做的工作或可用的等式,而不是因为方法名字叫枚举就认定一定超时。

12. 作业

巩固练习

提高训练

留言

可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。