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 

Output 

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

UVA 517 - Word (周期规律+位运算)

原文：http://blog.csdn.net/accelerator_/article/details/18805899