额？难道不用剪枝么，难道是数据太弱了么- -！

判断素数，直接写个函数来就好~~

然后我是这么想的。。读数的时候就记录各项之和，然后如果k>n/2的时候就反过来搜（这样可以大大减小搜索量）

编译通过...

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

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

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

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

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

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

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

点击查看代码

菜鸟弱弱的写 水题 题解。。。

用DFS

或者 就是 回朔

void dfs(int A, int sum, int select)

{

if(select

var

n,k,i,j,t,ans:longint; flag:boolean;

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

zs:array[0..50000]of longint;

function check(x:longint):boolean;

var i:longint;

begin

for i:=1 to t do

if(x mod zs[i]=0)and(xzs[i])then exit(false);

exit(true);

end;

procedure search(x,y,z:longint);

var i:longint;

begin

for i:=y+1 to n do search(x+a[i],i,z+1);

if(z=k)and(check(x))then inc(ans);

end;

begin

readln(n,k); ans:=0;

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

t:=1; zs[1]:=2;

for i:=3 to 50000 do

begin

flag:=true;

for j:=1 to t do

if i mod zs[j]=0 then begin flag:=false; break; end;

if flag then

begin inc(t); zs[t]:=i; end;

end;

search(0,0,0); writeln(ans);

end.

史上最短的搜索，不过生成质数多了点……

一次AC就是爽!!

先搜索所有可能,再判断素数即可.

program P1128;

var n,k,ans,i:longint;

s,a:array[0..21] of longint;

function pd:boolean;

var sum,i:longint;

begin

sum:=0;

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

pd:=true;

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

if sum mod i=0 then

begin

pd:=false;

break;

end;

end;

procedure work(l:longint);

var i:longint;

begin

if l=k then

begin

if pd then ans:=ans+1;

end

else

begin

for i:=s[l]+1 to n do

begin

s[l+1]:=i;

work(l+1);

end;

end;

end;

begin

readln(n,k);

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

ans:=0;

for i:=1 to n-k+1 do

begin

s[1]:=i;

work(1);

end;

writeln(ans);

end.

编译通过...

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

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

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

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

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

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

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

我终于过了！庆祝一下！贴个程序！

program vijos_1128;

const

maxn=500000;

var

p:array[0..maxn] of boolean;

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

n,k,ans:longint;

procedure jurgde(s:longint);

var i,g:longint;

begin

if sk then

begin

//writeln(s);

jurgde(s);

exit;

end;

if t>n then exit;

so(s,j,t+1);

so(s+a[t],j+1,t+1);

end;

procedure main;

var i,j:longint;

begin

readln(n,k);

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

fillchar(p,sizeof(p),1);

p[1]:=false;

for i:=2 to maxn do

if p[i] then

begin

j:=i+i;

while j

编译通过...

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

Miller-Rabin算法，选择2,7,61为底数，和在longint范围内秒杀，且正确率100%

只不过由于选择了2,7,61为底数，所以对于61以内的素数要进行特判（还是很划算）

第三个测试点就是这种情况

小弟编的不是程，是水…………

编译通过...

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

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

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

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

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

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

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

妈的，居然不要考虑重复情况，题目又不说清楚，害得我下降了一个百分点，我的AC率啊~！

#include

#include

#include

long n,m,ans=0;

short b[5000000]={0},c[30]={0};

long a[30];

short sushu(long x)//是素数返回1，否则返回0

{

long j,t;

if (x==2) return 1;

if (x

编译通过...

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

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

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

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

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

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

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

"要求你计算出和为素数共有多少种"

题主语文还要多下功夫啊，和为素数的情况.....而不是素数和的种类个数.....

我还死去活来地加哈希表判重....

郁闷死，死在水题上

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

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

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

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

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

var

n,k,i,ans:longint;

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

function js:boolean;

var

i,t:longint;

begin

t:=0;

for i:=1 to k do

t:=t+x[y[i]];

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

if t mod i =0 then exit(false);

exit(true);

end;

procedure search(v:integer);

var i:integer;

begin

if v>k then

begin

if js then inc(ans); exit;

end;

for i:=y[v-1]+1 to n do

begin y[v]:=i;search(v+1);end;

end;

begin

readln(n,k);ans:=0;

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

fillchar(y,sizeof(y),0);

search(1);

writeln(ans);

end.

PS: ！组合算法+素数尝试！

编译通过...

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

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

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

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

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

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

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

program ex;

var i,j,n,k,ans:longint;

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

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

procedure init;

var i,j:longint;

begin

readln(n,k);

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

end;

function check(a:longint):boolean;

var i,j:longint;

begin

if a=2 then exit(true);

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

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

exit(true);

end;

procedure dfs(step,t,tol:longint);

var i,j:longint;

begin

if step=k then

begin

if check(tol) then inc(ans);

exit;

end;

if t

不用判断重复？

var

n,k,i,ans:longint;

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

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

function check(p:longint):boolean;

var

t:longint;

begin

if p=2 then exit(true);

for t:=2 to trunc(sqrt(p)) do

if (p mod t)=0 then exit(false);

exit(true);

end;

procedure dfs(p,k,tol:longint);

var

i,t:longint;

flag:boolean;

begin

if k=0 then

begin

flag:=true;

if (flag)and(check(tol)) then

begin

inc(a[0]);

a[a[0]]:=tol;

end;

end

else

begin

for i:=p to n-k+1 do

dfs(i+1,k-1,tol+x[i]);

end;

end;

begin

readln(n,k);a[0]:=0;

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

dfs(1,k,0);

write(a[0]);

end.

诶。为楼下多数人感到杯具啊。就最底下几楼有牛用米勒拉宾素数检索法来过这题....

var

n,k,i,j,s,tot,tt:longint;

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

procedure sushu(k:longint);

var i:integer;

begin

for i:=2 to trunc(sqrt(k))+2 do

if k mod i=0 then break;

if i=trunc(sqrt(k))+2 then tot:=tot+1;

end;

procedure search(t:integer);

var i:integer;

begin

if s=k then begin sushu(tt); exit; end;

for i:=t to n do

begin

tt:=tt+a[i];

s:=s+1;

search(i+1);

tt:=tt-a[i];

s:=s-1;

end;

end;

begin

read(n);

readln(k);

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

search(1);

writeln(tot);

end.

很简单的搜索

这题难度是2？