因为一天机房都是断网状态，校内的小V评测这道题总显示Unaccept，所以下午放学后就和xiaoyimi晚上回家自习，来做一做这道题。
搜索+剪枝优化：
一开始我是顺着低位向高位填数，这么暴力在Vijos上有90分，如果NOIP能得这么多分我也甘心就写这个暴力吧
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int s1[27], s2[27], an[27], ans[27], n;
bool vis[27], pd = 0;
inline void dfs1(int, int);
inline void dfs3(int tmp, int delta) {
int c = an[tmp];
if (ans[c] == -1) {
int num = (ans[s1[tmp]] + ans[s2[tmp]] + delta), mo = num % n;
if (!vis[mo]) {
vis[mo] = 1;
ans[c] = mo;
dfs1(tmp + 1, num / n);
if (pd) return;
vis[mo] = 0;
ans[c] = -1;
}
} else {
int num = (ans[s1[tmp]] + ans[s2[tmp]] + delta);
if (ans[c] == num % n)
dfs1(tmp + 1, num / n);
if (pd) return;;
}
}
inline void dfs2(int tmp, int delta) {
int c = s2[tmp];
if (ans[c] == -1) {
for(int i = 0; i < n; ++i)
if (!vis[i]) {
vis[i] = 1;
ans[c] = i;
dfs3(tmp, delta);
if (pd) return;
vis[i] = 0;
ans[c] = -1;
}
} else {
dfs3(tmp, delta);
if (pd) return;
}
}
inline void dfs1(int tmp, int delta) {
if (tmp > n){
if (delta == 0)
pd = 1;
return;
}
int c = s1[tmp];
if (ans[c] == -1) {
for(int i = 0; i < n; ++i)
if (!vis[i]) {
vis[i] = 1;
ans[c] = i;
dfs2(tmp, delta);
if (pd) return;
vis[i] = 0;
ans[c] = -1;
}
} else {
dfs2(tmp, delta);
if (pd) return;
}
}
int main() {
scanf("%d
", &n);
char c;
for(int i = n; i > 0; --i) {
c = getchar();
s1[i] = c - 'A';
}
scanf("
");
for(int i = n; i > 0; --i) {
c = getchar();
s2[i] = c - 'A';
}
scanf("
");
for(int i = n; i > 0; --i) {
c = getchar();
an[i] = c - 'A';
}
for(int i = 0; i < n; ++i)
ans[i] = -1;
dfs1(1, 0);
for(int i = 0; i < n; ++i)
printf("%d ",ans[i]);
return 0;
}
正解：先扫出字母出现的先后顺序，在这个扫出的序列上暴力，每次暴力后简单的扫一遍整个等式进行$check$，这是我写的唯一的也是最重要的剪枝，能过掉那组T掉的数据：
输入
20
NLHFIEASBRQJOGKMDPCT
NQGPSIIGKDMFDCBFMQSO
PNKNTOLHEIJHFGJKHJGG
输出
18 14 0 9 15 17 7 13 12 16 1 10 4 2 8 5 11 3 6 19
AC代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int s1[27], s2[27], an[27], ans[27], n, tb[27], tn = 0;
bool vis[27], pan = 0;
inline void mktb(int x) {
if (!vis[x]){
vis[x] = 1;
tb[++tn] = x;
}
}
inline bool pd() {
bool p = 0;
int delta = 0;
for(int i = 1; i <= n; ++i){
int a = ans[s1[i]], b = ans[s2[i]], c = ans[an[i]];
if (a == -1 || b == -1) {
p = 1;
} else {
if (c == -1) {
if (p) {
if (a + b == n-1)
p = 1;
else
p = 0, delta = (a + b) / n;
} else {
p = 0;
delta = (a + b + delta) /n;
}
} else {
if (p) {
if ((a + b) % n == c) {
p = 0;
delta = (a + b) / n;
} else if ((a + b + 1) % n == c) {
p = 0;
delta = (a + b + 1) / n;
} else
return 1;
} else {
if ((a + b + delta) % n != c)
return 1;
else {
p = 0;
delta = (a + b + delta) / n;
}
}
}
}
}
if (!p && delta == 1)
return 1;
else
return 0;
}
inline void dfs(int tmp) {
if (pd())
return;
if (tmp > n) {
pan = 1;
return;
}
for(int i = 0; i < n; ++i)
if (!vis[i]) {
vis[i] = 1;
ans[tb[tmp]] = i;
dfs(tmp + 1);
if (pan)
return;
vis[i] = 0;
ans[tb[tmp]] = -1;
}
}
int main() {
scanf("%d
", &n);
char c;
for(int i = n; i > 0; --i) {
c = getchar();
s1[i] = c - 'A';
}
scanf("
");
for(int i = n; i > 0; --i) {
c = getchar();
s2[i] = c - 'A';
}
scanf("
");
for(int i = n; i > 0; --i) {
c = getchar();
an[i] = c - 'A';
}
for(int i = 1; i <= n; ++i) {
mktb(s1[i]);
mktb(s2[i]);
mktb(an[i]);
}
for(int i = 0; i < n; ++i)
vis[i] = 0, ans[i] = -1;
dfs(1);
for(int i = 0; i < n; ++i)
printf("%d ",ans[i]);
return 0;
}
没了，，，xyx和我玩了一下午的棋盘类游戏，SG什么的真的不会啊，省选要爆0了TwT