题目链接：
http://soj.sysu.edu.cn/1016
题目大意：
给定一个字符串和256条规则，将某条规则应用于字符串，字符串将发生变化，给定一个数max，求出在max步内可以将字符串变为指定字符串的规则号以及步数。
题目分析：
既然只有256条规则，而且步数又有限制，那我们就暴力模拟，把所有情况都求出来就行了，但是如果用原始字符串来做是非常慢的，虽然题目的时间限制很宽松（10s），但也是会超时的。所以对于每个规则我用一个record的map来保存已经遇到过的字符串，这样就可以过了(虽然还是很慢)。
在网上看到的做法是用0，1分别代表白黑的，而且用到了很多位运算，虽然也是暴力，但是快很多，一样的测试，人家0.15s就过了。
代码：
// Problem#: 1016
// Submission#: 3585804
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <stdio.h>
#include <string.h> //
int rule[][], m[];
long long step, length;
char num[], target[];
int targetNum[], pro[][];
int answerNum, ans1[], ans2[]; int MAX() {
if (length < ) return m[length];
else return ;
} void init() {
for (int i = ; i < ; i++) {
int temp = i;
for (int j = ; j < ; j++) {
rule[i][j] = temp & ;
temp >>= ;
}
}
m[] = ;
for (int i = ; i < ; i++) m[i] = m[i - ] << ;
} bool check() {
length = strlen(target);
if (length < ) return false;
for (int i = ; i < length; i++) {
if (target[i] == 'W') targetNum[i] = ;
else if (target[i] == 'B') targetNum[i] = ;
else return false;
}
if ((targetNum[] == ) || (targetNum[length - ] == ) || (length & == )) return false;
return true;
} int main() {
init(); int caseNum = ; while () { scanf("%s%s", num, target); if (strcmp(num, "END") == ) break; printf("LINE %d ", caseNum++); if (!check()) {
printf("NONE\n");
continue;
} step = ;
for (int i = ; num[i] != '\0'; i++) step = step * + num[i] - '';
if (step > MAX()) step = MAX(); answerNum = ; for (int i = ; i < ; i++) {
memset(pro, , sizeof(pro));
int last = , now = ;
int s = ;
int jlength = length - , ruleNum;
pro[now][length / ] = ;
while () { if (s > step) break; bool isSame = true;
for (int k = ; k < length; k++) {
if (pro[now][k] != targetNum[k]) {
isSame = false;
break;
}
}
if (isSame) {
ans1[answerNum] = i;
ans2[answerNum] = s;
answerNum++;
break;
}
now ^= ;
last ^= ; s++;
for (int j = ; j < jlength; j++) {
ruleNum = pro[last][j];
ruleNum <<= ;
ruleNum += pro[last][j + ];
ruleNum <<= ;
ruleNum += pro[last][j + ];
pro[now][j + ] = rule[i][ruleNum];
}
pro[now][] = pro[now][length - ] = ;
}
}
if (answerNum) {
for (int i = ; i < answerNum; i++) printf("(%d,%d)", ans1[i], ans2[i]);
printf("\n");
} else printf("NONE\n");
}
return ;
}
这提示我以后能用int尽量不用字符串。多考虑效率。这道题要是时间限制到1s我就GG了。
我的代码：
#include <iostream>
#include <map>
#include <vector>
#include <string.h>
using namespace std; struct Ans {
int mo, t;
Ans(){}
Ans(int a, int b) {
mo = a;
t = b;
}
};
//0 for white, 1 for black
int model[];
map<string, int> transfer;
map<string, int> record;
vector<Ans> ans;
int Max;
string line;
string ary, dest, ary2;
int l; void addModel() {
int i = , j;
while (i >= && model[i]) {
i--;
}
for (j = i; j <= ; j++) {
model[j] = -model[j];
}
} int toInt(string tmp) {
int i, tot = ;
for (i = ; i < tmp.length(); i++) {
tot = tot* + tmp[i] - '';
}
return tot;
} void getData(int& n, string& r) {
string tmp1, tmp2;
tmp1 = tmp2 = "";
int i;
for (i = ; r[i] != ' '; i++) {
tmp1 += r[i];
}
for (i++; i<r.length(); i++) {
tmp2 += r[i];
}
n = toInt(tmp1);
dest = tmp2;
l = dest.length();
} bool cut(int f) {
string tmp;
int i;
for (i = ; i < ; i++) {
tmp += ary2[f+i];
}
return model[transfer[tmp]];
} void Do() {
int i;
ary2 = ary;
for (i = ; i < l-; i++) {
if (cut(i)) {
ary[i+] = 'B';
} else {
ary[i+] = 'W';
}
}
} bool equal(const string& a, const string& b) {
int i;
for (i = ; i < l; i++) {
if (a[i] != b[i]) {
return false;
}
}
return true;
} int main() {
transfer["BBB"] = ;
transfer["BBW"] = ;
transfer["BWB"] = ;
transfer["BWW"] = ;
transfer["WBB"] = ;
transfer["WBW"] = ;
transfer["WWB"] = ;
transfer["WWW"] = ;
int cnt = ;
while (getline(cin, line)) {
cnt++;
if (line == "END OF INPUT")
break;
ans.clear();
getData(Max, line);
int i, j, k;
for (i = ; i < ; i++) {
ary = "";
for (k = ; k < l; k++) {
ary += 'W';
}
ary[l/] = 'B';
record.clear();
for (j = ; j < Max; j++) {
if (record[ary]) {
break;
}
if (equal(ary, dest)) {
ans.push_back(Ans(i, j+));
break;
} else {
record[ary] = ;
}
Do();
}
addModel();
}
cout << "LINE " << cnt << " ";
for (i = ; i < ans.size(); i++) {
cout << "(" << ans[i].mo << "," << ans[i].t << ")";
}
if (!ans.size()) {
cout << "NONE";
}
cout << endl;
}
}