有人能写出这段代码吗？求解。难

好。
为了造福以后看到这道题的人。
这里为题目作出补充。。。。。
【题目描述好劲啊】
1.好。。。如果没有冗余的话最后要输出No redundant.
有句号。有句号。
2.ABCDE->ABC这种不算冗余。。你需要判一下orz

var pre,res,vis,ok,len:Array[0..101]of longint;
lin,ans:Array[0..101]of longint;
i,j,k,m,n,t,l,r,best:longint;
flag:Boolean;
s,st:String;
function bush(s:String):longint;
var i,j:longint;
begin
bush:=0;
for i:=1 to length(s) do
inc(bush,1 shl (ord(s[i])-ord('A')));
end;
procedure print(x,y:longint);
var i,j:longint;
begin
write('FD ');
write(x);
write(' is redundant using FDs:');
for i:=1 to y do write(' ',ans[i]);
writeln;
end;
function dfs(dep,now,goa:longint):Boolean;
var i,j,k:longint;
begin
if (now and goa = goa)and(best>dep) then begin
best:=dep;
ans:=lin;
exit;
end;
if dep >= best then exit;
for i:=1 to n do
if (vis[i]=0)and(now and pre[i] = pre[i] ) then begin
lin[dep+1]:=i;
vis[i]:=1;
dfs(dep+1,now or res[i],goa);
vis[i]:=0;
end;
end;
begin
readln(n);
for i:=1 to n do begin
readln(s);
st:=copy(s,1,pos('-',s)-1);
delete(s,1,pos('>',s));
pre[i]:=bush(st);
res[i]:=bush(s);
end;
for i:=1 to n do begin
fillchar(vis,sizeof(vis),0);
vis[i]:=1;
flag:=true;
t:=pre[i]; r:=res[i];
while flag do begin
if t and r = r then break;
flag:=false;
j:=1;
while j<=n do begin
if (vis[j]=0)and(pre[j] and t = pre[j]) then begin
t:=t or res[j];
vis[j]:=1;
inc(len[i]);
flag:=true;
end;
inc(j);
end;
end;
if flag then begin
ok[i]:=1;
inc(m);
end;
end;
fillchar(vis,sizeof(vis),0);
if m<>0 then begin
for i:=1 to n do
if ok[i]=1 then begin
best:=len[i]+1;
vis[i]:=1;
dfs(0,pre[i],res[i]);
print(i,best);
vis[i]:=0;
end;
end
else writeln('No redundant FDs.');
end.

var pre,res,vis,ok,len:Array[0..101]of longint;
lin,ans:Array[0..101]of longint;
i,j,k,m,n,t,l,r,best:longint;
flag:Boolean;
s,st:String;

function bush(s:String):longint;
var i,j:longint;
begin
bush:=0;
for i:=1 to length(s) do
inc(bush,1 shl (ord(s[i])-ord('A')));
end;

procedure print(x,y:longint);
var i,j:longint;
begin
write('FD ');
write(x);
write(' is redundant using FDs:');
for i:=1 to y do write(' ',ans[i]);
writeln;
end;

function dfs(dep,now,goa:longint):Boolean;
var i,j,k:longint;
begin
if (now and goa = goa)and(best>dep) then begin
best:=dep;
ans:=lin;
exit;
end;
if dep >= best then exit;
for i:=1 to n do
if (vis[i]=0)and(now and pre[i] = pre[i] ) then begin
lin[dep+1]:=i;
vis[i]:=1;
dfs(dep+1,now or res[i],goa);
vis[i]:=0;
end;
end;

begin
readln(n);

for i:=1 to n do begin
readln(s);
st:=copy(s,1,pos('-',s)-1);
delete(s,1,pos('>',s));
pre[i]:=bush(st);
res[i]:=bush(s);
end;

for i:=1 to n do begin
fillchar(vis,sizeof(vis),0);
vis[i]:=1;
flag:=true;
t:=pre[i]; r:=res[i];
while flag do begin
if t and r = r then break;
flag:=false;
j:=1;
while j<=n do begin
if (vis[j]=0)and(pre[j] and t = pre[j]) then begin
t:=t or res[j];
vis[j]:=1;
inc(len[i]);
flag:=true;
end;
inc(j);
end;
end;
if flag then begin
ok[i]:=1;
inc(m);
end;
end;

fillchar(vis,sizeof(vis),0);
if m<>0 then begin
for i:=1 to n do
if ok[i]=1 then begin
best:=len[i]+1;
vis[i]:=1;
dfs(0,pre[i],res[i]);
print(i,best);
vis[i]:=0;
end;
end
else writeln('No redundant FDs.');
end.

强烈鄙视这题

如果遇到自己直接能到自己的，直接忽略，我去

比如：

2

ABCDE->ABC

A->ABC

上面的数据1是不冗余的

我x，强烈鄙视写标程的

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

成功压百

晕,同个人没有必要用"楼下"称呼吧

不用DFS,而是BFS.想法很简单。每次将该依赖屏蔽。之后把该依赖左边作为已知。

对剩下的边做BFS.用hash判重。hashsize = 2000003 足够。

注意。如楼下说的。不能用P的集合类型。我为此WA了很多次。用位运算很好。

不会吧。。。pascal的集合类型号难用。转为二进制后70->100!

弄懂这题的描述这道题就做出了90％。。。

意思就是：

要判断依赖i是不是冗余的

那么就以其左边的那些域为已知

然后通过这些已知和其余的n－1个依赖去得到新的确定的域

然后一直这样下去

直到最后没能确定新的值，或者依赖i的右边已经被确定了则停止。。。

一开始一直搞不懂题意思

看懂怎么操作后

直接ＤＦＳＩＤ

分支定界

高级本上的原题啊

用标程猥琐地AC了

关键是看懂“冗余”的概念。。如果第I个是冗余的，那么以第I个的左边作为已知，可以通过除I外的某几个依赖得到I的右边，那么I就是冗余的。先预判一下I是不是冗余的，如果不是的话等会儿搜索就不用搜它了。有三个点是无冗余的，起先忘看题目了。。5555~~~~

具体的看程序：

var pre,res,vis,ok,len:Array[0..101]of longint;

lin,ans:Array[0..101]of longint;

i,j,k,m,n,t,l,r,best:longint;

flag:Boolean;

s,st:String;

function bush(s:String):longint; //压缩成二进制处理

var i,j:longint;

begin

bush:=0;

for i:=1 to length(s) do

inc(bush,1 shl (ord(s[i])-ord('A')));

end;

procedure print(x,y:longint); //输出

var i,j:longint;

begin

write('FD ');

write(x);

write(' is redundant using FDs:');

for i:=1 to y do write(' ',ans[i]);

writeln;

end;

function dfs(dep,now,goa:longint):Boolean; //DFS搜索，每次都从第一

var i,j,k:longint; //个开始搜

begin

if (now and goa = goa)and(best>dep) then begin

best:=dep;

ans:=lin;

exit;

end;

if dep >= best then exit;

for i:=1 to n do

if (vis[i]=0)and(now and pre[i] = pre[i] ) then begin

lin[dep+1]:=i;

vis[i]:=1;

dfs(dep+1,now or res[i],goa);

vis[i]:=0;

end;

end;

begin

readln(n);

for i:=1 to n do begin

readln(s);

st:=copy(s,1,pos('-',s)-1);

delete(s,1,pos('>',s));

pre[i]:=bush(st);

res[i]:=bush(s);

end;

for i:=1 to n do begin //这里整个FOR都在预判

fillchar(vis,sizeof(vis),0);

vis[i]:=1;

flag:=true;

t:=pre[i]; r:=res[i];

while flag do begin

if t and r = r then break;

flag:=false;

j:=1;

while j

可以用位运算优化，有一个点要剪枝，不然会TLE.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

加一个很强的剪枝就可以AC：如果一路搜下去，第一次回溯的时候还没有出现解就可以判定无解了（因为无回溯的过程是加入了最大的条件个数）……

题目有错!!!!

No redundant FDs后面应该有个点!!!

No redundant FDs.

过的很委琐,看数据限定了深度为4.....

n

测试数据 #0: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 808 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 804 KiB, score = 10

Accepted, time = 0 ms, mem = 808 KiB, score = 100

完美水过