点击查看程序源码+详细题解

0ms AC

var

a,b,c:array[0..26]of char; find:boolean;

val:array['A'..'Z']of integer; n,i:longint;

used:array[0..26]of boolean;

procedure print;

var q:longint;

begin

for q:=0 to n-2 do

write(val[chr(ord('A')+q)],' ');

writeln(val[chr(ord('A')+n-1)]);

find:=true;

end;

function check:boolean;

var i:longint;

begin

check:=true;

for i:=1 to n do if (val[a[i]]-1)and(val[b[i]]-1)and(val[c[i]]-1)

then if ((val[a[i]]+val[b[i]])mod nval[c[i]])

and((val[a[i]]+val[b[i]]+1)mod nval[c[i]])

then exit;

check:=false;

end;

procedure dfs(k,jin:longint);

var i,j:longint;ifa,ifb,ifc:boolean;

begin

if k=0 then begin

if jin=0 then print;

exit;end;

if check then exit;

if val[a[k]]-1 then ifa:=true else ifa:=false;

for i:=n-1 downto 0 do

if ((ifa)and(val[a[k]]=i)) or ((ifa=false)and(used[i]=false))then

begin

used[i]:=true;val[a[k]]:=i;

if val[b[k]]-1 then ifb:=true else ifb:=false;

for j:=n-1 downto 0 do

if ((ifb)and(val[b[k]]=j)) or ((ifb=false)and(used[j]=false))then

begin

used[j]:=true;val[b[k]]:=j;

if val[c[k]]-1 then ifc:=true else ifc:=false;

if ((ifc)and((i+j+jin)mod n=val[c[k]]))

or ((ifc=false)and(used[(i+j+jin)mod n]=false))then

begin

used[(i+j+jin)mod n]:=true;val[c[k]]:=(i+j+jin)mod n;

dfs(k-1,(i+j+jin)div n);if find then exit;

if ifc=false then begin val[c[k]]:=-1;used[(i+j+jin)mod n]:=false;end;

end;

if ifb=false then begin val[b[k]]:=-1;used[j]:=false;end;

end;//if j

if ifa=false then begin val[a[k]]:=-1;used[i]:=false;end;

end;//if i

end;

begin

readln(n);

fillchar(used,sizeof(used),false);fillchar(val,sizeof(val),-1);

for i:=1 to n do read(a[i]);readln;

for i:=1 to n do read(b[i]);readln;

for i:=1 to n do read(c[i]);

find:=false; while not find do begin dfs(n,0);end;

end.

倒着搜就是快，noip搜索题数据向来这样

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 619ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：619ms

高斯居然比搜索还慢。。

VJ_MD5.com.cn这是什么。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 322ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：322ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 338ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：338ms

神啊

。。。

终于秒杀了

反向＋强效搜索＋Evolution SmdCn（很高效么？不知道）＝秒杀。。

还是看了题解的。虽啊

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

哦啦啦~

我Cheat了一个点 。。。 第八点……

鬼晓得……就第八点超时了。。。

大家都第九点

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：150ms

虽然是1A，但是样例wa了不下20次。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

若原本是初值,则结束后改为初值,若不是,则不变.c数组亦是.

orz ,,强大的剪枝

判断还未枚举到的列，若有一列3个字母都确定了，但有无进位都不满足，说明当前的字母顺序错误，直接EXIT.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我开始少考虑了一种情况，那就是同一列中可能有相同且不确定的数字，纠结了半天。另外求教神牛们这题的高斯消元算法。

编译通过...

├ 测试数据 01：运行超时|无输出...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：运行超时|无输出...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：0ms

诡异啊，哪位神牛能帮帮我呢？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 103ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：103ms

var a:array['A'..'Z'] of integer;

b:array[0..26] of boolean;

n:longint;

si,sj,sx:string;

procedure sousuo(x:longint);

forward;

procedure init;

var ch:char;

begin

readln(n);

readln(si);

readln(sj);

readln(sx);

for ch:='A' to 'Z' do

a[ch]:=-1;

end;

function panduan(x:longint):boolean;

var i,js:longint;

begin

panduan:=true;

js:=0;

for i:=n downto x do

begin

if (a[si[i]]+a[sj[i]]+js) mod na[sx[i]] then

begin

panduan:=false;

exit;

end;

js:=(a[si[i]]+a[sj[i]]+js) div n;

end;

for i:=1 to n do

if (a[si[i]]-1)and(a[sj[i]]-1)and(a[sx[i]]-1) then

if not(((a[si[i]]+a[sj[i]]+1)mod n=a[sx[i]])or((a[si[i]]+a[sj[i]])mod n=a[sx[i]])) then

begin

panduan:=false;

exit;

end;

end;

procedure fx(x:longint);

var i:longint;

begin

if a[sx[x]]=-1 then

begin

for i:=n-1 downto 0 do

if not b[i] then

begin

a[sx[x]]:=i;

b[i]:=true;

if panduan(x) then

sousuo(x-1);

b[i]:=false;

end;

a[sx[x]]:=-1;

end;

if a[sx[x]]-1 then

if panduan(x) then

sousuo(x-1);

end;

procedure fj(x:longint);

var i:longint;

begin

if a[sj[x]]=-1 then

begin

for i:=n-1 downto 0 do

if not b[i] then

begin

a[sj[x]]:=i;

b[i]:=true;

fx(x);

b[i]:=false;

end;

a[sj[x]]:=-1;

end;

if a[sj[x]]-1 then

fx(x);

end;

procedure fi(x:longint);

var i:longint;

begin

if a[si[x]]=-1 then

begin

for i:=n-1 downto 0 do

if not b[i] then

begin

a[si[x]]:=i;

b[i]:=true;

fj(x);

b[i]:=false;

end;

a[si[x]]:=-1;

end;

if a[si[x]]-1 then

fj(x);

end;

procedure print;

var i:char;

begin

for i:='A' to chr(ord('A')+n-1) do

write(a[i],' ');

writeln;

end;

procedure sousuo(x:longint);

begin

if x=0 then

begin

print;

halt;

end;

fi(x);

end;

begin

init;

sousuo(n);

end.

0 to n-1不比n-1 downto 1慢

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

附上程序：program P1099;var a:array[1..3,1..26] of char; b:array['A'..'Z'] of longint; c:array[0..25] of boolean; d:array[0..26] of longint; n,i,j:longint; ch:char;function check(p:longint):boolean;var i:longint;begin for i:=p downto 1 do if (b[a[1,i]]>=0) and (b[a[2,i]]>=0) and (b[a[3,i]]>=0) then if ((b[a[1,i]]+b[a[2,i]]) mod nb[a[3,i]]) and ((b[a[1,i]]+b[a[2,i]]+1) mod nb[a[3,i]]) then exit(false); exit(true);end;procedure dfs(p:longint);var i,j:longint;begin if (p=0 then if b[a[2,p]]>=0 then if b[a[3,p]]>=0 then begin if (b[a[1,p]]+b[a[2,p]]+d[p]) mod n=b[a[3,p]] then begin d[p-1]:=(b[a[1,p]]+b[a[2,p]]+d[p]) div n; if check(p) then dfs(p-1); d[p-1]:=0; end; end else begin j:=b[a[1,p]]+b[a[2,p]]+d[p]; if c[j mod n] then begin c[j mod n]:=false; d[p-1]:=j div n; b[a[3,p]]:=j mod n; if check(p) then dfs(p-1); d[p-1]:=0; b[a[3,p]]:=-1; c[j mod n]:=true; end; end else if b[a[3,p]]>=0 then begin if b[a[3,p]]=0 then if b[a[3,p]]>=0 then begin if b[a[3,p]]

剪枝弄不好，所以就。。

用生成法生成从小到大的排列：

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 41ms

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：40 有效耗时：41ms

从大到小排列：

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：30 有效耗时：0ms

有秒了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

+---|--+

|/ |

| |

| +-+ |

| | | |

+-+-+-+

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：72ms

数据问题而已啊！

n年之前我从小到大枚举，怎么优化都差那么0.2秒，我就郁闷啊！！

n年后我突发奇想从大到小，然后奇迹就发生了：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

。。居然从小到大枚举就超，从大到小就秒了。。。

。。居然先填第3位再第2位再第1位可以多过几个点。。。

猜想：从大到小枚举有数学理论依据。。。直觉上就觉得先大在小会剪的比较多。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：166ms

评测机 vijos easy 王道啊！！！！！

（虽然没秒………………）

编译通过...

├ 测试数据 01：答案正确... 999ms

├ 测试数据 02：答案正确... 999ms

├ 测试数据 03：答案正确... 999ms

├ 测试数据 04：答案正确... 999ms

├ 测试数据 05：答案正确... 999ms

├ 测试数据 06：答案正确... 999ms

├ 测试数据 07：答案正确... 999ms

├ 测试数据 08：答案正确... 999ms

├ 测试数据 09：答案正确... 999ms

├ 测试数据 10：答案正确... 999ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9990ms

真是稳定的算法

（完全PS痕迹）