笔记01-最优字典序「efzoi」

- AC日期：2018.08.16 - 网址：https://efzoi.tk/contest/30/4 ------------ # 2018暑假集训Day14.D # 最优字典列 - ## 题目描述: n 个格子排成一列，一开始，你在第一个格子，目标为跳到第 n 个格子。在每个格子 i 里面你可以做出两个选择: 选择「a」：向前跳 a_i ​ ​​ 步。 选择「b」：向前跳 b_i ​ ​​ 步。 把每步的选择写成一个关于字符 a 和 b的字符串。求到达格子 n 的方案中，字典序最小的字符串。当做出某个选择时，你跳出了这n个格子的范围，则这个选择是不合法的。 当没有合法的选择序列时，输出 No solution!。 当字典序最小的字符串无限长时，输出 Infinity!。 否则，输出这个选择字符串。 - ## 输入格式 输入有三行。 第一行输入一个整数 n。 第二行输入 n 个整数，分别表示 a_i 。 第三行输入 n 个整数，分别表示 b_i。 - ## 输出格式 输出一行字符串表示答案。 - ## 样例 ### 样例输入 7 5 -3 6 5 -5 -1 6 -6 1 4 -2 0 -2 0 ### 样例输出 abbbb - ## 数据范围与提示 1≤n≤10^5 −n≤ai,bi≤n ------------ - ## 思路 1. 看题面就知道是搜索题（虽然是听见旁边的巨佬说的搜索想都没想）， 既然要判断是否有环就要用dfs而不是bfs了啦。 2. 特殊的地方在于需要判断 No Answer 以及 Infinity! 两种情况。 注意到出现Infinity：当且仅当1~(n-2)中一点可以通过a方式重复到达本身，且通过b方式到达终点。 _字典序：空格>字典序（>长度）_ 3. 正常dfs时需要一个数组判断当前路径是否到达某一点，结束后得重置。 此题则不一样，到达一次后还可以再次到达（成环），但到达最多两次以后不论哪次循环到该点都不再进入，所以说使用int数组，每次循环到x点就把used[x]++，最多加到2，并且不进行used[x]--操作。 4. 那问题又来了，若是到达了终点，怎么知道当前路径有没有环呢（可能是由于其他废掉的路径导致某一个used[x]==2） 所以要引入circ数组，circ与used同时进行++操作，在一次dfs结束后进行--操作，在最终到达n-1点时判断是否有circ[i]>2，若有，则有环。 就是酱紫w ------------ - ## 代码 ```cpp #include<bits/stdc++.h> using namespace std; int n; int a[100000]; int b[100000]; string ans; int used[100000]; int circ[100000]; int dfs(int node){ circ[node]++; used[node]++; if(node==(n-1)){ int r=2; for(int i=0; i<n; i++) if(circ[i]==2) r=1; return r; } int r=0; if((node+a[node])>=0&&(node+a[node])<n){ if(used[node+a[node]]<2) r=dfs(node+a[node]); if(r==1) return 1; if(r==2){ ans="a"+ans; return 2; } } if((node+b[node])>=0&&(node+b[node])<n){ if(used[node+b[node]]<2) r=dfs(node+b[node]); if(r==1) return 1; if(r==2){ ans="b"+ans; return 2; } } circ[node]--; //used[node]--; return 0; } int main(){ int r=0; ans=""; scanf("%d",&n); for(int i=0; i<n; i++) used[i]=0; for(int i=0; i<n; i++) circ[i]=0; for(int i=0; i<n; i++) scanf("%d",&a[i]); for(int i=0; i<n; i++) scanf("%d",&b[i]); r=dfs(0); if(r==0) cout<<"No solution!"<<endl; if(r==1) cout<<"Infinity!"<<endl; if(r==2) cout<<ans<<endl; return 0; } ```