我也是
by dfmz @ 2017-07-15 12:34:54
@[东方明珠](/space/show?uid=49276) 我试了试反过来(枚举未知位上的数时从 n-1 到 0),多 A 了一个点,时间真的快了不少,不过倒数第二个点还是TLE。
by piggy @ 2017-07-16 11:39:01
还是TLE一个点,求大犇帮忙修改一下……(注释由于从IDE上复制下来后成了乱麻,就删掉了)
···
```cpp
#include <cstdio>
#define A(xx,yy) (f[a[xx][yy]]-1)
int f[30],a[3][30],g[30],jw[30],n,ok,boo;
char ch;
void dfs(int x,int y){
if (ok) return;
if (y==0){
if (A(0,1)+A(1,1)+jw[2]==A(2,1)){
for (int i=0; i<n; i++) printf("%d ",f[i]-1);
ok=1;
}
return;
}
if (x<2){
int k=1-x;
if (!f[a[x][y]]){
if (f[a[k][y]] && f[a[2][y]]){
if (!g[(A(2,y)-A(k,y)-jw[y+1]+n)%n]){
f[a[x][y]]=(A(2,y)-A(k,y)-jw[y+1]+n)%n+1;
g[A(x,y)]=1;
dfs(x+1,y);
if (ok) return;
g[A(x,y)]=0;
f[a[x][y]]=0;
}
return;
}
for (int i=n-1; i>=0; i--) if (!g[i]){
f[a[x][y]]=i+1;
g[A(x,y)]=1;
dfs(x+1,y);
g[A(x,y)]=0;
f[a[x][y]]=0;
}
return;
}
dfs(x+1,y);
return;
}
if (x==2){
if (!f[a[x][y]]){
f[a[x][y]]=(A(0,y)+A(1,y)+jw[y+1])%n+1;
if (!g[A(x,y)]){
g[A(x,y)]=1;
jw[y]=(jw[y+1]+A(0,y)+A(1,y))/n;
dfs(0,y-1);
g[A(x,y)]=0;
}
f[a[x][y]]=0;
return;
}
if ((A(0,y)+A(1,y)+jw[y+1])%n==A(2,y)){
jw[y]=(jw[y+1]+A(0,y)+A(1,y))/n;
dfs(0,y-1);
}
return;
}
}
int main(){
scanf("%d",&n);
for (int i=0; i<3; i++){
while (ch<'A' || ch>'Z') ch=getchar();
for (int j=1; j<=n; j++) a[i][j]=ch-'A',ch=getchar();
}
dfs(0,n);
}
···
```
by piggy @ 2017-07-16 11:54:35
说一个悲伤的故事,我在找到答案后没有强制退出程序。。。。
( PS:就这样也能过9个点。。。是数据太水了吗?)
我差点都放弃了搜索
你能看懂Pascal吗(我的程序经过一周的乱改,已经面目全非)
不过速度挺快
by dfmz @ 2017-08-13 18:44:32
```cpp
var n,i:longint;s1,s2,s3:string;
a:array['A'..'Z'] of integer;
f:array[0..26] of boolean;
procedure dfs(step,d:longint);
var i,x,y,z,j,k:longint;
begin
if step=0 then
begin
if d=0 then
begin
for i:=1 to n do write(a[chr(i+64)],' ');writeln;halt;
end;
exit;
end;
for i:=1 to step-1 do
begin
x:=a[s1[i]];y:=a[s2[i]];z:=a[s3[i]];
if (x>-1)and(y>-1)and(z>-1)and((x+y+1) mod n<>z)and((x+y) mod n<>z) then exit;
end;
x:=a[s1[step]];y:=a[s2[step]];z:=a[s3[step]];
if (x=-1)and(y=-1)and(z=-1) then
begin
for i:=n-1 downto 0 do
if (f[i])and(((i+d) mod n=0)or(s2[step]<>s3[step])) then
for j:=n-1 downto 0 do
if (f[j])and((i=j)=(s1[step]=s2[step]))and(((j+d) mod n=0)or(s1[step]<>s3[step])) then
begin
k:=(i+j+d) mod n;
if not f[k] then continue;
if (i=k)<>(s1[step]=s3[step]) then continue;
if (j=k)<>(s2[step]=s3[step]) then continue;
f[i]:=false;f[j]:=false;f[k]:=false;
a[s1[step]]:=i;a[s2[step]]:=j;a[s3[step]]:=k;
dfs(step-1,(i+j+d) div n);
f[i]:=true;f[j]:=true;f[k]:=true;
a[s1[step]]:=-1;a[s2[step]]:=-1;a[s3[step]]:=-1;
end;
exit;
end;
if (x=-1)and(y=-1) then
begin
if s1[step]=s2[step] then
begin
if (not odd(z-d))and(f[(z-d) div 2]) then
begin
i:=(z-d) div 2;f[i]:=false;a[s1[step]]:=i;
dfs(step-1,0); f[i]:=true;a[s1[step]]:=-1;
end;
if (not odd(z+n-d))and(f[(z+n-d) div 2]) then
begin
i:=(z-d+n) div 2;f[i]:=false;a[s1[step]]:=i;
dfs(step-1,1); f[i]:=true;a[s1[step]]:=-1;
end;
exit;
end;
for i:=n-1 downto 0 do
if f[i] then
begin
j:=(z-i-d+n) mod n;
if (i=j)or(not f[j]) then continue;
f[i]:=false;f[j]:=false;
a[s1[step]]:=i;a[s2[step]]:=j;
dfs(step-1,(i+j+d) div n);
f[i]:=true;f[j]:=true;
a[s1[step]]:=-1;a[s2[step]]:=-1;
end;
exit;
end;
if (x=-1)and(z=-1) then
begin
if s1[step]=s3[step] then
begin
if (d=0)and(y<>0) then exit;
if (d=1)and(y<>n-1) then exit;
end;
for i:=n-1 downto 0 do
if f[i] then
begin
k:=(i+y+d) mod n;
if not f[k] then continue;
if (i=k)<>(s1[step]=s3[step]) then continue;
f[i]:=false;f[k]:=false;
a[s1[step]]:=i;a[s3[step]]:=k;
dfs(step-1,(i+y+d) div n);
f[i]:=true;f[k]:=true;
a[s1[step]]:=-1;a[s3[step]]:=-1;
end;
exit;
end;
if (y=-1)and(z=-1) then
begin
if s2[step]=s3[step] then
begin
if (d=0)and(x<>0) then exit;
if (d=1)and(x<>n-1) then exit;
end;
for j:=n-1 downto 0 do
if f[j] then
begin
k:=(x+j+d) mod n;
if not f[k] then continue;
if (j=k)<>(s2[step]=s3[step]) then continue;
f[j]:=false;f[k]:=false;
a[s2[step]]:=j;a[s3[step]]:=k;
dfs(step-1,(x+j+d) div n);
f[j]:=true;f[k]:=true;
a[s2[step]]:=-1;a[s3[step]]:=-1;
end;
exit;
end;
if (x=-1) then
begin
i:=(z-y-d+n) mod n;
if not f[i] then exit;
a[s1[step]]:=i;f[i]:=false;
dfs(step-1,(i+y+d) div n);
a[s1[step]]:=-1;f[i]:=true;
exit;
end;
if (y=-1) then
begin
j:=(z-x-d+n) mod n;
if not f[j] then exit;
a[s2[step]]:=j;f[j]:=false;
dfs(step-1,(x+j+d) div n);
a[s2[step]]:=-1;f[j]:=true;
exit;
end;
if (z=-1) then
begin
k:=(x+y+d+n) mod n;
if not f[k] then exit;
a[s3[step]]:=k;f[k]:=false;
dfs(step-1,(x+y+d) div n);
a[s3[step]]:=-1;f[k]:=true;
exit;
end;
if (x+y+d) mod n=z then dfs(step-1,(x+y+d) div n);
end;
begin
readln(n);readln(s1);readln(s2);readln(s3);
fillchar(f,sizeof(f),true);
for i:=1 to n do a[chr(i+64)]:=-1;dfs(n,0);
end.
```
by dfmz @ 2017-08-13 18:44:56
分点信息(鼠标移到方块上有详细信息)
#1
AC
0ms/1468kB
#2
AC
0ms/1410kB
#3
AC
0ms/1199kB
#4
AC
0ms/1148kB
#5
AC
0ms/1402kB
#6
AC
0ms/1402kB
#7
AC
4ms/1343kB
#8
AC
0ms/1191kB
#9
AC
16ms/1402kB
#10
AC
0ms/1164kB
by dfmz @ 2017-08-13 18:46:36
你只需把每一篇题解都认真看一遍,
所有剪枝全部写上,是肯定能过的
(除非像我一样犯了低级错误)
by dfmz @ 2017-08-13 18:54:03
一个点怎么办
by Mystic_czy @ 2017-10-06 11:37:10
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
char s1[27],s2[27],s3[27];
int w1[27],w2[27],w3[27];
int q[27]={0}/*数字出现了没*/,n,qq[27]={0}/*代表字母出现过没*/;
void Print()
{
printf("%d",q[1]);
for(int a=2;a<=n;a++)
printf(" %d",q[a]);
exit(0);
}
int dfs(int k,int jw){
if(k==0&&jw==0) Print();
else
{
if(q[w1[k]]==-1)
{
for(int a=n-1;a>=0;a--)
if(!qq[a])
{
qq[a]=1;q[w1[k]]=a;
if(q[w2[k]]==-1)
{
for(int b=n-1;b>=0;b--)
if(!qq[b])
{
qq[b]=1;q[w2[k]]=b;
if(q[w3[k]]==-1)
{
q[w3[k]]=(q[w1[k]]+q[w2[k]]+jw)%n;qq[q[w3[k]]]=1;
dfs(k-1,(q[w1[k]]+q[w2[k]]+jw)/n);
qq[q[w3[k]]]=0;q[w3[k]]=-1;
}
else
{
if(q[w3[k]]==(q[w2[k]]+q[w1[k]]+jw)%n)
{
dfs(k-1,(q[w1[k]]+q[w2[k]]+jw)/n);
}
}
q[w2[k]]=-1;qq[b]=0;
}
}
else
{
if(q[w3[k]]==-1)
{
q[w3[k]]=(q[w1[k]]+q[w2[k]]+jw)%n;qq[q[w3[k]]]=1;
dfs(k-1,(q[w1[k]]+q[w2[k]]+jw)/n);
qq[q[w3[k]]]=0;q[w3[k]]=-1;
}
else
{
if(q[w3[k]]==(q[w2[k]]+q[w1[k]]+jw)%n)
{
dfs(k-1,(q[w1[k]]+q[w2[k]]+jw)/n);
}
}
}
q[w1[k]]=-1;qq[a]=0;
}
}
else
{
if(q[w2[k]]==-1)
{
for(int b=n-1;b>=0;b--)
if(!qq[b])
{
qq[b]=1;q[w2[k]]=b;
if(q[w3[k]]==-1)
{
q[w3[k]]=(q[w1[k]]+q[w2[k]]+jw)%n;qq[q[w3[k]]]=1;
dfs(k-1,(q[w1[k]]+q[w2[k]]+jw)/n);
qq[q[w3[k]]]=0;q[w3[k]]=-1;
}
else
{
if(q[w3[k]]==(q[w2[k]]+q[w1[k]]+jw)%n)
{
dfs(k-1,(q[w1[k]]+q[w2[k]]+jw)/n);
}
}
q[w2[k]]=-1;qq[b]=0;
}
}
else
{
if(q[w3[k]]==-1)
{
q[w3[k]]=(q[w1[k]]+q[w2[k]]+jw)%n;qq[q[w3[k]]]=1;
dfs(k-1,(q[w1[k]]+q[w2[k]]+jw)/n);
qq[q[w3[k]]]=0;q[w3[k]]=-1;
}
else
{
if(q[w3[k]]==(q[w2[k]]+q[w1[k]]+jw)%n)
{
dfs(k-1,(q[w1[k]]+q[w2[k]]+jw)/n);
}
}
}
}
}
}
int main()
{
scanf("%d",&n);
scanf("%s%s%s",s1,s2,s3);
for(int a=1;a<=n;a++){
q[a]=-1;
w1[a]=s1[a-1]-'A'+1;
w2[a]=s2[a-1]-'A'+1;
w3[a]=s3[a-1]-'A'+1;
}
dfs(n,0);
return 0;
}
```
by Mystic_czy @ 2017-10-06 11:37:28
@管理员 这个染色出bug了把
by Mystic_czy @ 2017-10-06 11:38:21