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

感谢voyagec2牛提供剪枝

程序只要80行不到 大家要想简单点 不要受楼下题解的干扰

高斯消元+进位枚举.

反正挺猥琐的.我差点要cheat了

有效耗时：525ms

十分感谢楼下voyagec2牛提供的剪枝……

第九个点的关键剪枝..

for i:=1 to l do

if (vis[a[i]])and(vis[b[i]])and(vis[c[i]]) then

if ((key[a[i]]+key[b[i]]+1) mod nkey[c[i]])

and((key[a[i]]+key[b[i]]) mod nkey[c[i]]) then

begin flag:=false;break;end;

if flag=false then exit;

虫食算解题报告

（alpha.pas）

By Withflying

2009-1-30

问题描述：

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：

43#9865#045 + 8468#6633 = 44445506678 其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。

现在，我们对问题做两个限制：首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表示的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。

BADC + CBDA = DCCC 上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解.

输入格式 Input.txt

输入包含4行。第一行有一个正整数N(N

var

n,len,i:integer;

f:array['A'..'Z'] of integer;

a:array['A'..'Z'] of boolean;

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

s:array[1..3,1..30] of char;

list:array[1..26] of char;

m:char;

procedure finish;

var i:char;

begin

for i:='A' to m do

write(f[i],' ');

writeln;

halt;

end;

function check:boolean;

var

tt,t,i,d:integer;

b:boolean;

begin

b:=true;

for i:=n downto 1 do

begin

if b then b:=false

else if d0 then d:=0;

if a[s[1][i]] and a[s[2][i]] and a[s[3][i]] then

begin

t:=f[s[1][i]]+f[s[2][i]];

if t>=n then

begin

dec(t,n);

b:=true;

d:=1;

end;

if (f[s[3][i]]=0)

then if (t0)and(t+1n)

then exit(false)

else t:=0

else t:=f[s[3][i]]-t;

if (t>1)or(t=n then dec(t,n);

if tt>=n then dec(tt,n);

if u[t] and u[tt] then exit(false);

end;

if a[s[1][i]] and a[s[3][i]]and(not a[s[2][i]]) then

begin

t:=f[s[3][i]]-f[s[1][i]];

tt:=t-1;

if t=n then

begin

dec(t,n);

d:=1;

end else d:=0;

if tf[s[3][i]] then exit(false);

end;

if d=0 then judge:=true

else judge:=false;

end;

procedure search(d:byte);

var

i:integer;

begin

if dn then

if judge then finish

else exit;

a[list[d]]:=true;

for i:=n-1 downto 0 do

if not u[i] then

begin

u[i]:=true;

if check then

search(succ(d));

u[i]:=false;

end;

a[list[d]]:=false;

end;

begin

readln(n);

m:=chr(n+64);

readln(s[1]);

readln(s[2]);

readln(s[3]);

len:=0;

fillchar(a,sizeof(a),0);

for i:=n downto 1 do

begin

if not a[s[1][i]] then

begin

inc(len);

list[len]:=s[1][i];

a[s[1][i]]:=true;

end;

if not a[s[2][i]] then

begin

inc(len);

list[len]:=s[2][i];

end;

if not a[s[3][i]] then

begin

inc(len);

list[len]:=s[3][i];

a[s[3][i]]:=true;

end;

end;

fillchar(a,sizeof(a),0);

fillchar(u,sizeof(u),0);

search(1);

end.

编译通过...

├ 测试数据 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：答案正确... 0ms

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

127 lines

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

#include

using namespace std;

char ss[5][30];

int n,ans[30];

bool vis[30];

void print()

{

for (int i = 0; i=0 && nn >=0 && dd >= 0)

{if (((tt + nn + carry) % n )!= dd) return;}

int now = ss[k][t] - 'A';

if (ans[now] < 0)

{

if (tt >= 0 && dd >= 0)

{

int bb = dd - tt - carry;

if (bb < 0) bb+= n;

if (vis[bb]) return;

ans[now] = bb;

vis[bb] = true;

dfs(t,k+1,carry);

vis[bb] = false;

ans[now] = -1;

}

else

for (int i = n - 1; i>-1; i--)

if (!vis[i])

{

ans[now] = i;

vis[i] = true;

dfs(t, k+1 , carry);

vis[i] = false;

}

ans[now] = -1;

}

else dfs(t, k+1 ,carry);

}

int main()

{

scanf("%d",&n);

for (int i = 0; i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

付上程序，刷屏专用

不长，250行而已

program p1099;

var

a1,b1,c1:array[1..26]of longint;

a,b,c,a2,b2,c2:string[30];

f:array[0..26]of longint;

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

x,y,z,n,i,j,k:longint;

bb:boolean;

procedure work(r:longint);

var z,x,y,i,j,k:longint;

bb:boolean;

begin

if r>n then begin

for i:=0 to n-2 do write(f[i],' ');

writeln(f[n-1]);

halt;

end

else begin

x:=ord(a[r])-65;

y:=ord(b[r])-65;

if (f[x]-1) and (f[y]-1) then

begin

k:=f[x]+f[y];

bb:=false;

if (r=n) and (k>=n) then exit

else begin

a1[r]:=f[x];

b1[r]:=f[y];

c1[r]:=c1[r]+k;

if c1[r]>=n then

begin

inc(c1[r+1]);

bb:=true;

c1[r]:=c1[r] mod n;

end;

z:=ord(c[r])-65;

if f[z]-1 then

begin

if f[z]=c1[r] then

work(r+1);

end

else begin

if not ff[c1[r]] then

begin

f[z]:=c1[r];

ff[c1[r]]:=true;

work(r+1);

f[z]:=-1;

ff[c1[r]]:=false;

end;

end;

if bb then begin dec(c1[r+1]); c1[r]:=c1[r]+n-k;end

else begin c1[r]:=c1[r]-k;end;

end;

end

else if (f[x]=-1)and(f[y]-1) then

begin

for i:=0 to n-1 do

if not ff[i] then

begin

f[x]:=i;

ff[i]:=true;

k:=f[x]+f[y];

if (rn)or((r=n)and(k=n then

begin

bb:=true;

inc(c1[r+1]);

c1[r]:=c1[r] mod n;

end;

z:=ord(c[r])-65;

if f[z]-1 then

begin

if f[z]=c1[r] then

work(r+1);

end

else begin

if not ff[c1[r]] then

begin

f[z]:=c1[r];

ff[c1[r]]:=true;

work(r+1);

f[z]:=-1;

ff[c1[r]]:=false;

end;

end;

if bb then begin dec(c1[r+1]); c1[r]:=c1[r]+n-k;end

else begin c1[r]:=c1[r]-k;end;

end;

f[x]:=-1;

ff[i]:=false;

end;

end

else if (f[y]=-1)and(f[x]-1) then

begin

for i:=0 to n-1 do

if not ff[i] then

begin

f[y]:=i;

ff[i]:=true;

k:=f[x]+f[y];

if (rn)or((r=n)and(k=n then

begin

bb:=true;

inc(c1[r+1]);

c1[r]:=c1[r] mod n;

end;

z:=ord(c[r])-65;

if f[z]-1 then

begin

if f[z]=c1[r] then

work(r+1);

end

else begin

if not ff[c1[r]] then

begin

f[z]:=c1[r];

ff[c1[r]]:=true;

work(r+1);

f[z]:=-1;

ff[c1[r]]:=false;

end;

end;

if bb then begin dec(c1[r+1]); c1[r]:=c1[r]+n-k;end

else begin c1[r]:=c1[r]-k;end;

end;

f[y]:=-1;

ff[i]:=false;

end;

end

else begin

if xy then

begin

for i:=0 to n-1 do

for j:=0 to n-1 do

if (ij)and(not ff[i])and(not ff[j]) then

begin

f[x]:=i;

f[y]:=j;

ff[i]:=true;

ff[j]:=true;

k:=f[x]+f[y];

if (rn)or((r=n)and(k=n then

begin

bb:=true;

inc(c1[r+1]);

c1[r]:=c1[r] mod n;

end;

z:=ord(c[r])-65;

if f[z]-1 then

begin

if f[z]=c1[r] then work(r+1);

end

else begin

if not ff[c1[r]] then

begin

f[z]:=c1[r];

ff[c1[r]]:=true;

work(r+1);

f[z]:=-1;

ff[c1[r]]:=false;

end;

end;

if bb then begin dec(c1[r+1]); c1[r]:=c1[r]+n-k;end

else begin c1[r]:=c1[r]-k;end;

end;

f[x]:=-1;

f[y]:=-1;

ff[i]:=false;

ff[j]:=false;

end;

end

else begin

for i:=0 to n-1 do

begin

if not ff[i] then

begin

f[x]:=i;

ff[i]:=true;

k:=2*i;

if (rn)or((r=n)and(k=n then

begin

bb:=true;

inc(c1[r+1]);

c1[r]:=c1[r] mod n;

end;

z:=ord(c[r])-65;

if f[z]-1 then

begin

if f[z]=c1[r] then work(r+1);

end

else begin

if not ff[c1[r]] then

begin

f[z]:=c1[r];

ff[c1[r]]:=true;

work(r+1);

f[z]:=-1;

ff[c1[r]]:=false;

end;

end;

if bb then begin dec(c1[r+1]);c1[r]:=c1[r]+n-k;end

else c1[r]:=c1[r]-k;

end;

f[x]:=-1;

ff[i]:=false;

end;

end;

end;

end;

end;

end;

begin

readln(n);

readln(a2);

readln(b2);

readln(c2);

for i:=1 to n do a:=a2[i]+a;

for i:=1 to n do b:=b2[i]+b;

for i:=1 to n do c:=c2[i]+c;

for i:=0 to n do f[i]:=-1;

fillchar(ff,sizeof(ff),0);

work(1);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一次.剪枝.只是每次判断和的那一位是否已经做过.是但不符合两数和就退出

从低位做起

C++/C 从n-1 to 0

当年考试的测试数据都过了， 就第九个点过不了，尴尬。。。。

有点恶心

全0

ms

VAR

a:array[1..3,1..26] of longint;

n:longint;

hashl,d:array[0..26] of longint;

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

fuck:array[0..100,1..2] of longint;

tot:longint;

Procedure init;

var

i,j:longint;

c:char;

begin

readln(n);

for j:=1 to 3 do

begin

for i:=1 to n do

begin

read(c);

a:=ord(c)-ord('A')+1;

end;

readln;

end;

end;

Function check(X:longint):boolean;

var

i,j:longint;

begin

check:=false;

for i:=1 to x-1 do

if (hashl[a]>-1) and (hashl[a]>-1) and(hashl[a]>-1) then

if ((hashl[a]+hashl[a])mod nhashl[a]) and

((hashl[a]+hashl[a]+1) mod n hashl[a]) then exit;

check:=true;

end;

Procedure ttry(x,y:longint);

var

i,t,temp:longint;

begin

if y=3 then if not(check(x)) then exit;

if x=0 then

begin

for i:=1 to n-1 do write(hashl[i],' ');writeln(hashl[n]);

halt;

end;

if y=1 then t:=2 else t:=1;

if y=3 then if hashl[a[x,3]]>-1 then

if (hashl[a[x,1]]+hashl[a[x,2]]+d[x+1]) mod n hashl[a[x,3]] then exit;

if hashl[a[x,y]]>-1 then

begin

if y=3 then

begin

d[x]:=(hashl[a[x,1]]+hashl[a[x,2]]+d[x+1]) div n;

ttry(x-1,1);

d[x]:=0;

end else ttry(x,y+1);

end else

if (hashl[a[x,t]]>-1) and (hashl[a[x,6-y-t]]>-1) then

begin

if y=3 then

begin

temp:=hashl[a[x,1]]+hashl[a[x,2]]+d[x+1];

if (hashl[a[x,y]]=-1) and (hashu[temp mod n]) then exit;

hashl[a[x,y]]:=temp mod n;

hashu[temp mod n]:=true;

d[x]:=temp div n;

ttry(x-1,1);

hashl[a[x,y]]:=-1;

hashu[temp mod n]:=false;

end else

begin

temp:=hashl[a[x,3]]-d[x+1]-hashl[a[x,t]];

if temp=n then exit;

hashl[a[x,y]]:=temp;

hashu[temp]:=true;

ttry(x,Y+1);

hashl[a[x,y]]:=-1;

hashu[temp]:=false;

end;

end else

begin

for i:=n-1 downto 0 do

if not(hashu[i]) then

begin

hashl[a[x,y]]:=i;

hashu[i]:=true;

if y=3 then

begin

d[x]:=hashl[a[x,1]]+hashl[a[x,2]];

ttry(x-1,1);

end else ttry(x,y+1);

hashu[i]:=false;

hashl[a[x,y]]:=-1;

end;

end;

end;

Procedure main;

var

i:longint;

begin

for i:=1 to n do hashl[i]:=-1;

ttry(n,1);

end;

begin

fillchar(hashl,sizeof(hashl),0);

fillchar(hashu,sizeof(hashu),0);

fillchar(a,sizeof(a),0);

init;

main;

end.

庆祝100题 倒序搜0MS

var

a,b,c:array[1..26] of char;

num:array['A'..'Z'] of integer;

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

n,i,j,k:integer;

ch:char;

procedure print;

var i:integer;

begin

for i:=0 to n-2 do write(num[chr(ord('A')+i)],' ');

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

halt;

end;

function panduan:boolean;

var k:integer;

begin

panduan:=true;

for k:=1 to n do if (num[a[k]]-1)and(num[b[k]]-1)and(num[c[k]]-1) then

if ((num[a[k]]+num[b[k]])mod nnum[c[k]])

and((num[a[k]]+num[b[k]]+1) mod nnum[c[k]]) then exit;

panduan:=false;

end;

procedure try(k,jin:integer);

var

ia,ib,ic:integer;

pa,pb,pc:boolean;

begin

if k=0 then begin if jin=0 then print;exit;end;

if panduan then exit;

pa:=false;

if num[a[k]]-1 then pa:=true;

for ia:=n-1 downto 0 do

if ((num[a[k]]=ia)and(pa=true))or((pa=false)and(use[ia]=false)) then

begin

num[a[k]]:=ia;use[ia]:=true;

pb:=false;

if num[b[k]]-1 then pb:=true;

for ib:=n-1 downto 0 do

if ((num[b[k]]=ib)and(pb=true))or((pb=false)and(use[ib]=false)) then

begin

num[b[k]]:=ib;use[ib]:=true;

pc:=false;

if num[c[k]]-1 then pc:=true;

ic:=(ia+ib+jin) mod n;

if ((pc=true)and(num[c[k]]=ic))or((pc=false)and(use[ic]=false)) then

begin

num[c[k]]:=ic;use[ic]:=true;

try(k-1,(ia+ib+jin) div n);

if pc=false then begin num[c[k]]:=-1;use[ic]:=false;end;

end;

if pb=false then begin num[b[k]]:=-1;use[ib]:=false;end;

end;

if pa=false then begin num[a[k]]:=-1;use[ia]:=false;end;

end;

end;

begin

readln(n);

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]);readln;

fillchar(use,sizeof(use),false);

for ch:='A' to 'Z' do begin num[ch]:=-1;end;

try(n,0);

end.

搜索时一定要n-1 downto 0，快了很多

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

爽啊！！

140行啊！！！

按从右到左的顺序搜索很有效果！

确实

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

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

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

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

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

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

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

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

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

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

按从右到左的顺序搜索很有效果！

C/C++

输出解之后立刻 exit()，这样能快一点

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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