Word
| Word |
Dr. R. E. Wright‘s class was studying modified L-Systems. Let us explain necessary details. As a model let us have words of length n over a two letter alphabet .
The words are cyclic, this means we can write one word in any of n forms we receive by cyclic shift, whereby the first and the last letters in the word are considered to be neighbours.
Rewriting rules rewrite a letter at a position i, depending on letters at the positions i - 2, i, i+1. We rewrite all letters of the word in one step. When we have a given starting word and a set of rewriting rules a natural question is: how does the word look after s rewriting steps?
Help Dr. R. E. Wright and write a program which solves this task.
Input
There are several blocks in the input file, each describing one system. There is an integer number n, 2 < n< 16 the length of the input word in the first line. There is a word in the next line. The word contains only lowercase letters a and b. There are four characters c1 c2 c3 c4 in the next eight lines. Each quadruple represents one rewriting rule with the following meaning: when the letter at the position i - 2 is c1 and the letter at the position i is c2 and the letter at the position i + 1 is c3 then the letter at the position i after rewriting will be c4. Rewriting rules are correct and complete. There is an integer numbers,Output
There is one line corresponding to each block of the input file. The line contains a word which we receive after s rewriting steps from the corresponding starting word using given rewriting rules. As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.Sample Input
5 aaaaa aaab aabb abab abbb baab babb bbab bbbb 1
Sample Output
bbbbb
题意：给定一个字符串，和8种变化方式，变化方式代表如果i - 2, i , i + 1位置字符对应的变化方式，把i位置变化为字符。所有字符只有a或b。给出s，问变化s次后的字符串是什么。
思路：s很大，但是n只有16，由于只有a和b，可以把a当成0，b当成1，这样就是一个二进制数，最多2^15种字符串，那么周期长度肯定不超过2^15，所以利用周期去查找。过程利用位运算。然后注意一个坑点，按字典序输出。因为题目给的是环形的字符串，所以比如bbbaaa是要输出aaabbb才对。
代码：位运算写得有点乱。。。不太熟练
#include <stdio.h>
#include <string.h>
#include <set>
#include <vector>
using namespace std;
int n, s, state, change, way[8], vis[(1<<16) + 10];
vector<int> zq;
void init() {
zq.clear();
memset(vis, -1, sizeof(vis));
state = 0;
char str[20];
scanf("%s", str);
for (int i = 0; i < n; i++)
state += (str[i] - ‘a‘) * (1<<i);
for (int j = 0; j < 8; j++) {
change = 0;
scanf("%s", str);
for (int k = 0; k < 3; k++)
change = (change<<1) + str[k] - ‘a‘;
way[change] = str[3] - ‘a‘;
}
}
void tra() {
int save[20], i;
for (i = 0; i < n; i++) {
int change = 0;
change = (change<<1) + ((state&(1<<((i - 2 + n)%n)))?1:0);
change = (change<<1) + ((state&(1<<i))?1:0);
change = (change<<1) + ((state&(1<<((i + 1)%n)))?1:0);
save[i] = way[change];
}
state = 0;
for (i = 0; i < n; i++)
state += save[i] * (1<<i);
}
void solve() {
int num = 0;
int len;
scanf("%d", &s);
while (1) {
if (vis[state] != -1) {
len = num - vis[state];
break;
}
zq.push_back(state);
vis[state] = num++;
tra();
}
int st;
if (s <= vis[state]) st = zq[s];
else st = zq[(s - vis[state]) % len + vis[state]];
char ans[20] = {"bbbbbbbbbbbbbbb"};
char save[20];
memset(save, 0, sizeof(save));
for (int i = 0; i < n; i++) {
for (int j = i; j < i + n; j++) {
if (st&(1<<(j%n))) save[j - i] = ‘b‘;
else save[j - i] = ‘a‘;
}
if (strcmp(save, ans) < 0) strcpy(ans, save);
}
printf("%s\n", ans);
}
int main() {
while (~scanf("%d", &n)) {
init();
solve();
}
return 0;
}