我一直怀疑这道题能用dfs做吗……

我还是试试吧……

编译通过...

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

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

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

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

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

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

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

……貌似是可以的……但我更喜欢BFS……这样的话可以减少状态数……

一次AC

编译通过...

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

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

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

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

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

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

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

var n,k,a,b,rs,c,d,e,p,k2:longint;

x:array[1..20] of longint;

s:string;

procedure huan(var a,b:char);

var c:char;

begin

c:=a;

a:=b;

b:=c;

end;

function iszs(a:longint):boolean;

var b:longint;

begin

for b:=2 to round(sqrt(a))+1 do

if a mod b=0 then exit(false);

exit(true);

end;

begin

readln(n,k);

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

c:=0;

setlength(s,n);

for a:=1 to n-k do s[a]:='0';

for a:=n-k+1 to n do s[a]:='1';

p:=n;

while p>0 do

begin

rs:=0;

for a:=1 to n do

if s[a]='1' then rs:=rs+x[a];

if iszs(rs) then c:=c+1;

p:=n-1;

while s[p]>=s[p+1] do dec(p);

if p>0 then

begin

k2:=n;

while s[k2]

var

a:array[1..20] of longint;

p:array[1..20] of boolean;

i,f,n,max,s:longint;

function pd(x:longint):boolean;

var i:longint;

begin

for i:=2 to trunc(sqrt(x)) do

if x mod i=0 then

exit(false);

pd:=true;

end;

procedure dfs(i,k:integer);

var j:integer;

begin

for j:=k+1 to n do

begin

s:=s+a[j];

p[j]:=false;

if i=f then

begin

if pd(s) then

inc(max);

end

else

dfs(i+1,j);

s:=s-a[j];

p[j]:=true;

end;

end;

begin

fillchar(p,sizeof(p),true);

readln(n,f);

for i:=1 to n do

read(a[i]);

s:=0;

max:=0;

dfs(1,0);

writeln(max);

end.

#include

#include

using namespace std;

int n,sum=0,n1,a[200];

bool sushu (int x)

{

int i,j;

if (x==1)

return false;

if (x==2)

return true;

for (i=2;in)

{

if (sushu(i))

++sum;

return ;

}

for (i1=k+1;i1>n1>>n;

for (i=1;i>a[i];

dfs(0,1,0);

cout

program lt;

var

a:array[1..20]of longint;

sum,s,i,n,m:integer;

function pan(n:longint):boolean;

var

i:integer;

begin

pan:=true;

for i:=2 to n div 2 do

if n mod i=0 then begin

pan:=false;

exit;

end;

end;

procedure try(n,k,s:integer);

begin

if (n=0)and(k=m)or(k=m)

then begin

if pan(s) then inc(sum);

exit;

end;

if (n=0)then exit;

try(n-1,k+1,s+a[n]);

try(n-1,k,s);

end;

begin

readln(n,m);

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

sum:=0;

try(n,0,0);

writeln(sum);

end.

回溯！！！！！

用int64就可以AC了

爽

program jj;

var n,m,i,j,k,l:integer;

a:array[1..10000] of integer;{比较吝啬}

b:array[1..10000] of integer;

function sfs(n:integer):boolean;

var i:integer;

begin

sfs:=true;

for i:=2 to trunc(sqrt(n)) do

if n mod i=0 then begin sfs:=false; break end;

end;

procedure search(x,y:integer);

VAR i,j,l:integer;

begin

l:=0;

if x=k+1 then begin

for j:=1 to k do begin l:=l+a[j]; end;

if sfs(l)=true then m:=m+1;

end

else for i:=y to n do

begin

a[x]:=b[i];

search(x+1,i+1);

a[x+1]:=0;

end;

end;

begin

readln(n,k);

for i:=1 to n do

read(b[i]);

search(1,1);

writeln(m);

end.

一个搜索AC了

这题好难啊,做不出来

要注意：if m=k then if check(s) then inc(ans)

else try(x+1); 这句话这么写是有问题的

要写成 if m=k then begin if check(s) then inc(ans) end

else try(x+1);

两个if在一起的时候，嵌套要小心

...dfs (...)

{

.

.

.

for (...) dfs (...);

}

var

t,i,n,k,s:integer;

a,b:array[0..20] of integer;

procedure dg(x:integer);

var

i,j:integer;

f:boolean;

begin

if x=k+1 then begin

s:=0;

f:=true;

for i:=1 to k do s:=s+b[i];

for i:=2 to trunc(sqrt(s)) do begin

if s mod i=0 then f:=false;

end;

if f then inc(t);

end else begin

for i:=1 to n do begin

f:=true;

for j:=1 to n do if a[i]=b[j] then f:=false;

if a[i]>b[x-1] then begin

if f then begin

b[x]:=a[i];

dg(x+1);

b[x]:=0;

end;

end;

end;

end;

end;

begin

readln(n,k);

fillchar(b,sizeof(b),0);

b[0]:=0;

a[0]:=0;

t:=0;

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

dg(1);

writeln(t);

end.

我的程序有一个点没过，请各位指点指点

program ll;

var

s,zong,m,p,k,n,i:longint;

a:array[0..100000] of longint;

function pan(q:longint):boolean;

var

j:integer;

begin

for j:=2 to trunc(sqrt(q)) do

if q mod j = 0 then exit(false);

exit(true);

end;

procedure run(x:longint);

begin

if x>n then exit

else

begin

s:=s+a[x];

inc(m);

if m

var a:array[0..21]of integer;

b:array[1..21]of int64;

n,k:integer;

h,i:integer;

he:int64;

function panduan(x:int64):boolean;

var i:longint;

begin

panduan:=true;

for i:=1 to trunc(sqrt(x)) do

if x mod i=0 then

begin panduan:=false; break; end;

end;

procedure jisuan;

begin

he:=0;

for i:=1 to k do

he:=he+b[a[i]];

if panduan(he) then inc(h);

end;

procedure run(x:integer);

begin

for i:=a[x-1] to n-(k-x)do

begin

a[i]:=i;

if x=k then jisuan

else run(x+1);

end;

end;

begin

readln(n,k);

h:=0;

a[0]:=0;

run(1);

writeln(h);

readln;

end.

怎么会超时呢？郁。。。。。。

一颗星纪念

————————————

呵呵，继续努力啊

50题通过，庆祝一下

我 晕死了

这题的输出要求 -.-

我一直认为和是一样的 只算一个的

编译通过...

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

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

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

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

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

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

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

program p1128;

var n1, j,s1,i,n,k,z:longint; b,a:array[1..10000]of longint;

procedure su(s:longint);

var i0,k:longint;

begin

k:=0;

for i0:=2 to trunc(sqrt(s)) do

if s mod i0=0 then k:=1;

if (s=0)or (s=1) then k:=1;

if (k=0) then inc(s1);

end;

procedure work(s,k1,fale:longint);

var i1:longint;

begin

if k=k1 then

for i1:=fale to n-k+k1 do

begin

s:=s+a[i1];

b[z]:=s;

inc(z);

su(s);

s:=s-a[i1];

end

else for i1:=fale to n-k+k1 do

begin s:=s+a[i1];

work(s,k1+1,i1+1);

s:=s-a[i1];end;

end;

begin

readln(n,k);

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

z:=1;

work(0,1,1);

writeln (s1);

end.

第一次用回溯调试到吐血

编译通过...

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

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

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

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

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

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

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

program p1128;

var m,n,p,q,i,j,k,l,r,su:longint;

d:array[1..5000000] of qword;

hash:array[1..5000000] of longint;

c:array[1..5000000] of longint;

v:array[1..20] of longint;

pp:array[1..5000000] of longint;

function chick(o:longint):longint;

var ti,tj,tk,tl,tr:longint;

begin

chick:=0;

for ti:=2 to trunc(sqrt(o)) do

if o mod ti=0 then begin chick:=1; break; end;

end;

procedure bfs;

var ii,jj,kk,ll,rr:longint;

begin

ll:=1;

rr:=n;

repeat

for i:=1 to n do

if pp[hash[ll] or v[i]]=0 then

begin

inc(rr);

d[rr]:=d[ll]+d[i];

hash[rr]:=hash[ll] or v[i];

c[rr]:=c[ll]+1;

pp[hash[ll] or v[i]]:=1;

if (c[rr]=k) and (chick(d[rr])=0) then inc(su);

end;

inc(ll);

until ll>rr;

end;

begin

read(n,k);

for i:=1 to n do

begin

read(d[i]);

hash[i]:=hash[i] or (1 shl (i-1));

v[i]:=hash[i];

c[i]:=1;

pp[hash[i]]:=1;

end;

bfs;

write(su);

end.

无聊滴用BFS+位运算 AC

program p1128;

var m,n,p,q,i,j,k,l,r,su,max:longint;

te:qword;

a,b:array[1..1000] of longint;

function chick(o:longint):longint;

var ti,tj,tk,tl,tr:longint;

begin

chick:=0;

for ti:=2 to trunc(sqrt(o)) do

if o mod ti=0 then begin chick:=1; break; end;

end;

procedure try(o,oo:longint);

var ii,jj,kk,ll,rr,tt,lo:longint;

begin

for ii:=1 to n do

if (b[ii]=0) and (moo) then

begin

lo:=ii;

b[ii]:=1;

te:=te+a[ii];

inc(m);

if m=k then begin if chick(te)=0 then inc(su) end else try(o+1,lo);

te:=te-a[ii];

b[ii]:=0;

dec(m);

end;

end;

begin

read(n,k);

for i:=1 to n do

read(a[i]);

try(1,0);

write(su);

end.

简单dfs。。。。

欢迎大牛小菜们到寒舍指点学习：http://hi.baidu.com/x50946702