UVa 517 Word

题目描述题目要求模拟一个长度为nnn的循环单词的演化过程。单词由字母a和b组成循环意味着首尾相邻。每个位置iii的下一状态由该位置及其左右邻居位置i−2i-2i−2、iii、i1i1i1的当前字母共同决定共有2382^3 8238种可能组合每种组合对应一个输出字母a或b。给定初始单词和演化步数ssssss可达2×1092 \times 10^92×109输出经过sss步后字典序最小的循环等价单词。输入格式每个数据块包含第一行整数nnn2n162 n 162n16。第二行长度为nnn的字符串由a和b组成。接下来888行每行一个长度为444的字符串c1c2c3c4c_1c_2c_3c_4c1​c2​c3​c4​表示规则若模式c1c2c3c_1c_2c_3c1​c2​c3​匹配则输出c4c_4c4​。最后一行整数sss0≤s≤2×1090 \le s \le 2 \times 10^90≤s≤2×109。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个数据块输出一行即sss步后字典序最小的循环等价单词。样例输入5 aaaaa aaaa aaab aabb abab abbb baab bbab bbbb 1输出bbbbb题目分析本题的核心是模拟循环单词的演化并利用状态循环加速。状态表示由于n16n 16n16每个单词可以用一个161616位整数表示000表示a111表示b。总状态数最多216655362^{16} 6553621665536可以存储。演化规则对于每个位置iii需要获取三个位置的字母i−2i-2i−2、iii、i1i1i1模nnn。这三个位组成一个333位二进制数kkk然后根据规则表rules[k]\textit{rules}[k]rules[k]得到新位。所有位置同时更新。循环检测由于状态数有限经过一定步数后必然进入循环。使用数组steps[state]\textit{steps}[state]steps[state]记录每个状态首次出现的步数。模拟过程中若当前状态已出现过则进入循环可直接计算出sss步后的状态。否则继续模拟。输出最终状态表示为二进制字符串生成所有循环移位取字典序最小的输出ab。复杂度分析预处理规则O(1)O(1)O(1)模拟最多655366553665536步之后查询O(1)O(1)O(1)可接受。代码实现// Word// UVa ID: 517// Verdict: Accepted// Submission Date: 2016-12-24// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN116;intrules[8],steps[MAXN],indexer[MAXN];intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,s;string word,rule;while(cinn){cinword;intw0;for(inti0;iword.length();i){w*2;if(word[i]b)w;}for(inti1;i8;i){cinrule;intr0;for(intj0;jrule.length()-1;j){r*2;if(rule[j]b)r;}rules[r]rule.back()-a;}cins;memset(steps,-1,sizeof(steps));for(inti0;is;i){if(steps[w]0){intt(s-i)%(i-steps[w]);windexer[steps[w]t];break;}else{steps[w]i;indexer[i]w;intww0;for(intj0;jn;j){intk0;if((1(j2)%n)w)k4;if((1j)w)k2;if((1((j-1n)%n))w)k1;ww|(rules[k]j);}www;}}wordbitset16(w).to_string().substr(16-n);setstringwords;string wordwordwordword;for(inti0;iword.length();i)words.insert(wordword.substr(i,word.length()));word*(words.begin());for(inti0;iword.length();i){if(word[i]0)couta;elsecoutb;}cout\n;}return0;}