P1128选数Accepted
记录信息
评测状态 Accepted
题目 P1128 选数
递交时间 2015-07-28 21:33:32
代码语言 C++
评测机 VijosEx
消耗时间 0 ms
消耗内存 280 KiB
评测时间 2015-07-28 21:33:36
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 280 KiB, score = 10
Accepted, time = 0 ms, mem = 280 KiB, score = 50
代码
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
int a[25];
int n,k;
int ans=0;
bool is_prime(int a)
{
for(int i=2;i<=sqrt(a);i++)
if(a%i==0)return false;
return true;
}
void work(int now,int total,int where)
{
if(where>n+1)return;
if(now==k)
{
if(is_prime(total)) ans++;
return;
}
work(now+1,total+a[where],where+1);
work(now,total,where+1);
}
int main()
{ scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
work(0,0,1);
printf("%d",ans);
return 0;
}

我竟然自己做出来了！~
评测状态 Accepted
题目 P1128 选数
递交时间 2015-06-27 21:42:01
代码语言 C++
评测机 VijosEx
消耗时间 15 ms
消耗内存 276 KiB
评测时间 2015-06-27 21:42:06

评测结果

编译成功

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

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

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

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

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

Accepted, time = 15 ms, mem = 276 KiB, score = 50

代码

#include <iostream>
using namespace std;
int n,k,s=0,x[21];
int pd(int num)
{
if((num==1)||(num==0))return 0;
for(int i=2;i<num;i++)
{
if((num%i)==0)return 0;
}
s++;
return 1;
}
int repeat(int j,int t,int ans)
{
ans+=x[j];
if(t<k)
{
for(int i=j+1;i<=(n-k+t+1);i++)
repeat(i,t+1,ans);
}
else pd(ans);
return 0;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>x[i];
for(int i=1;i<=(n-k+1);i++)
repeat(i,1,0);
cout<<s;
return 0;
}

入门级的搜索

#include<cstdio>
#include<cmath>
using namespace std;
int a[21],n,k,ans;
bool Judge(int x){
if (x<1) return false;
if (x<=2) return true;
for(int i=2;i<=sqrt(x);i++)
if (x%i==0) return false;
return true;
}
void DFS(int x,int num,int sum){
if (x==n+1){
if ((num==k)&&(Judge(sum))) ans++;
return;
}
DFS(x+1,num,sum);
DFS(x+1,num+1,sum+a[x]);
}
int main(){
//freopen("p1.in","r",stdin);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
ans=0;
DFS(1,0,0);
printf("%d",ans);
return 0;
}

打表is not necessary.
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
int prime[5000];
int primeSize = 0;
void init(){
bool a[10000];
memset(a, 1, sizeof(a));
for (int i = 2; i < 10000; i++){
if (a[i])prime[primeSize++] = i;
for (int j = 0; j < primeSize&&i*prime[j] < 10000; j++){
a[prime[j] * i] = false;
if (i%prime[j] == 0)break;
}
}
}
int a[21];
int ans = 0;
int size;
bool isPrime(int n){
for (int i = 0; i < primeSize&&prime[i]*prime[i]<=n; i++){
if (n%prime[i] == 0)return false;
}
return true;
}
void go(int from, int choose,int now){
if (choose == 0){
if (isPrime(now))
ans++;
return;
}
if (from >= size)return;
int i, j;
for (i = from; i < size; i++){
go(i + 1, choose - 1, now + a[i]);
}
}
int main(){
freopen("in.txt", "r", stdin);

init();
int choose;
cin >> size >> choose;
int i;
for (i = 0; i < size; i++)cin >> a[i];
go(0, choose,0);
cout << ans << endl;
return 0;
}

#include <iostream>

using namespace std;

int a = 0;

void pd(int ab)//判断是否为素数
{
int c = 0;
for (int b = 2; b < ab / 2; b++)
{
if (ab % b == 0)
{
c++;
}
}
if (c == 0)
{
a++;
}
}

void gyc(int m[20],int n,int ans,int k,int j)//递归列出所有可能
{
if (0 == k)
{
pd(ans);
}
else
{
for (int i = n; i<=j - k; i++)
{
gyc(m, i+1, ans+m[i], k-1, j);
}
}
}
int main()
{
int m[20];
int n = 0,k = 0;
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> m[i];
}
gyc(m, 0, 0, k, n);
cout << a;
return 0;
}
这个方法在想递归的时候比较烦，但写起来很方便

var
su,s:array[1..1000000] of longint;
e,n,k,p,max,num:longint;
function pd(a:longint):boolean;
var
i:longint;
begin
for i:=2 to trunc(sqrt(a)) do
if a mod i=0 then
begin
pd:=true;
exit;
end;
pd:=false;
end;
procedure search(a:longint);
var
o:boolean;
i,z:longint;
begin
if a>k then
begin
if pd(max)=false then begin
o:=true;
for i:=1 to num do
if max=su[i] then
begin
o:=false;
break;
end;
if o=true then
begin
num:=num+1;
su[num]:=max;
end;
end;
exit;
end;
for i:=e to n do
begin
max:=max+s[i];
z:=e;
e:=i+1;
search(a+1);
max:=max-s[i];
e:=z;
end;
end;
begin
e:=1;
readln(n,k);
for p:=1 to n do
read(s[p]);
search(1);
writeln(num);
end.

DFS。

Pascal Code

var
n,k,i,ans,j:longint;
x:array[1..20] of longint;
t:array[1..10000] of boolean;
prime:array[1..10000] of longint;
max,maxp:longint;
function isprime(x:longint):boolean;
var i,t1:longint;
begin
i:=0;
t1:=trunc(sqrt(x));
repeat
inc(i);
if x mod prime[i]=0 then exit(false);
until prime[i]>=t1;
exit(true);
end;
procedure dfs(d,p,s:longint); //p表示上一次选的数的位置
var i,t2:longint;
begin
if d=k
then begin
if isprime(s) then inc(ans);
exit;
end;
if n<n-k+d+1 then t2:=n
else t2:=n-k+d+1; //筛选掉达不到k个数的状态
for i:=p+1 to t2 do
dfs(d+1,i,s+x[i]);
end;
begin
readln(n,k);
max:=0;
for i:=1 to n do
begin
read(x[i]);
max:=max+x[i];
end;
fillchar(t,sizeof(t),1);
maxp:=trunc(sqrt(max));
t[1]:=false;
for i:=2 to maxp do //计算1——maxp范围内的素数
if t[i] then
for j:=2 to maxp div i do
t[i*j]:=false;
j:=0;
for i:=1 to maxp do
if t[i]
then begin
inc(j);
prime[j]:=i;
end;
ans:=0;
dfs(0,0,0);
writeln(ans);
end.

program P1128;
var data:array[1..20] of longint;
op:array[1..20] of boolean;
n,i,k,num,ans:longint;
ps:boolean;
function sushu(x:longint):boolean;
var i:longint;
begin
for i:=2 to (x div 2) do
if x mod i=0 then
exit(true);

exit(false);
end;

procedure main(step,xx,y:longint);
var i,sum:longint;
begin
if step=k+1 then
begin
ps:=sushu(xx);
if ps=false then
begin
inc(ans);
exit;
end
else
exit;
end;

sum:=xx;
for i:=y to n do
if op[i]=true then
begin
sum:=sum+data[i];
op[i]:=false;
main(step+1,sum,i);
op[i]:=true;
sum:=sum-data[i];
end;

end;

begin //main
ans:=0;
fillchar(op,sizeof(op),true);
read(n); read(k);
for i:=1 to n do
begin
read(num);
data[i]:=num;
end;

main(1,0,1);
write(ans);

end.

回溯枚举所有组合，由于排列组合的原理，选的数要想不重复，肯定是在这个数之后的数里选。剪枝的话因为数据小不考虑，否则当选了一个数后，如果后面数数量小于需要的数的数目，就退出（我这里没做）；
选出数后判断素数，素数定理知道，一个数N不被2到N/2的数整除就是素数，然后ans+1

举例 1 2 3 4 4个数选3个，当选了2以后，要想出现不一样的组合，肯定在3 4里选数，因为之前的话1的组合已经选完了，所以如果剩下的数少于3个。比如第一个数选了3，就没必要再做回溯了。

大致题目就是这样。

另外的思路自己找其他大牛的题解看吧，这是最简单的思路应该

数据水的要死，我还写了个hash 后来发现没hash也能过

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=21;
int x[maxn];
int ans;
int i,k,n;
void func(int m)
{
int flag1=0;
int p=sqrt(m);
for(int q=2;q<=p+1;q++) if(m%q==0) {flag1=1; break;};
if(flag1==0) ans++;
}

void dfs(int num,int place,int sum)
{
if(num==k) func(sum);
else
{
for(int z=place+1;z<=n;z++)
{dfs(num+1,z,sum+x[z]);}
}
}

int main()
{
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++) scanf("%d",&x[i]);
dfs(0,0,0);
printf("%d",ans);
return 0;
}

唉，还是第一次用这个编辑器，先兴奋下^_^
水题。思路是用搜索搜出所有情况，计算总数，并判断和是否为素数。（可以先预处理，这里使用筛法）
#include<cstring>
#include<cstdio>

using namespace std;

bool isPrime[10000001],visit[10000001];
int ans=0,a[21],N,K;

void DFS(int t,int pre,int sum)
{
if (t==K)
{
if (isPrime[sum]&&!visit[sum])
ans++;
return;
}
for(int i=pre+1;i<=N;i++)
DFS(t+1,i,sum+a[i]);
}

int main()
{
memset(isPrime,1,sizeof(isPrime));
memset(visit,0,sizeof(visit));
isPrime[1]=0;
for(int i=2;i<=10000000;i++)
if (isPrime[i])
for(int j=2;i*j<=10000000;j++)
isPrime[i*j]=0;
scanf("%d%d",&N,&K);
for(int i=1;i<=N;i++)
scanf("%d",a+i);
DFS(0,0,0);
printf("%d",ans);
return 0;
}

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 868 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 868 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 868 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 864 KiB, score = 10
Accepted, time = 15 ms, mem = 868 KiB, score = 50

• -代码 var i,j,n,m,k:longint;
  ans,num:longint; p:boolean;
  a:array[0..20] of longint;
  d:array[0..20] of longint;
  b:array[0..10000] of longint;
  c:array[0..10000] of boolean;
  begin
  k:=trunc(sqrt(20000000));
  for i:=2 to k do
  for j:=2 to k div i do c[i*j]:=true;
  j:=0;
  for i:=2 to k do if not c[i] then begin
  inc(j); b[j]:=i;
  end;
  readln(n,m);
  k:=n; num:=0;
  for i:=1 to n do read(a[i]);
  for i:=1 to m do d[i]:=i;
  while k<>0 do begin
  ans:=0;
  for i:=1 to m do ans:=ans+a[d[i]];
  j:=1; k:=trunc(sqrt(ans)); p:=true;
  while b[j]<=k do begin
  if ans mod b[j]=0 then begin
  p:=false; break;
  end;
  inc(j);
  end;
  if p then inc(num);
  k:=m;
  while (d[k]=n+k-m) and (k>0) do dec(k);
  if k<>0 then begin
  d[k]:=d[k]+1;
  for i:=k+1 to m do d[i]:=d[i-1]+1;
  end;
  end;
  writeln(num);
  end.

var ts,f,n,k,i,j,z,t,s,num:longint;
a:array [0..20] of byte;
b:array [0..20] of longint;
c:array [0..10000] of boolean;
d:array [0..5000] of integer;
begin
readln(n,k);z:=0;
for i:=1 to n do read(b[i]);readln;
c[1]:=false;for i:=2 to 10000 do c[i]:=true;
for i:=2 to 10000 do begin
if c[i] then begin
inc(z);d[z]:=i;
for j:=1 to 10000 div i do c[i*j]:=false;
end
end;
{for i:=1 to z do write(d[i],' ');}
for i:=0 to k do a[i]:=i;dec(a[k]);
num:=0;
repeat
t:=k;inc(a[t]);
while a[t]+(k-t)>n do begin
a[t]:=1;dec(t);inc(a[t]);
for i:=t+1 to k do a[i]:=a[i-1]+1;
end;
if a[0]=1 then break;
s:=0;
for i:=1 to k do s:=s+b[a[i]];
f:=0;i:=0;ts:=trunc(sqrt(s));
repeat
inc(i);
if s mod d[i]=0 then begin
f:=1;break;
end;
until d[i+1]>ts;
if f=0 then inc(num);
until a[0]=1;
writeln(num);
end.

var ts,f,n,k,i,j,z,t,s,num:longint;
a:array [0..20] of byte;
b:array [0..20] of longint;
c:array [0..10000] of boolean;
d:array [0..5000] of integer;
begin
readln(n,k);z:=0;
for i:=1 to n do read(b[i]);readln;
c[1]:=false;for i:=2 to 10000 do c[i]:=true;
for i:=2 to 10000 do begin
if c[i] then begin
inc(z);d[z]:=i;
for j:=1 to 10000 div i do c[i*j]:=false;
end
end;
{for i:=1 to z do write(d[i],' ');}
for i:=0 to k do a[i]:=i;dec(a[k]);
num:=0;
repeat
t:=k;inc(a[t]);
while a[t]+(k-t)>n do begin
a[t]:=1;dec(t);inc(a[t]);
for i:=t+1 to k do a[i]:=a[i-1]+1;
end;
if a[0]=1 then break;
s:=0;
for i:=1 to k do s:=s+b[a[i]];
f:=0;i:=0;ts:=trunc(sqrt(s));
repeat
inc(i);
if s mod d[i]=0 then begin
f:=1;break;
end;
until d[i+1]>ts;
if f=0 then inc(num);
until a[0]=1;
writeln(num);
end.

DFS

AC 40题
完美AC

记录信息
评测状态 Accepted
题目 P1128 选数
递交时间 2013-11-06 18:03:28
代码语言 C++
评测机 上海红茶馆
消耗时间 0 ms
消耗内存 564 KiB
评测时间 2013-11-06 18:03:29
评测结果

编译成功

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

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

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

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

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

Accepted, time = 0 ms, mem = 564 KiB, score = 50
代码

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <cstdlib>

using namespace std;

int n , k;
int i , j;
int total;
int a[20 + 2];

void DFS( int i , int num , int sum )
{
if( num == 0 )
{
if( sum % 2 == 0 )
return;
for( i = 3 ; i <= sqrt( sum ) ; i++ )
if( sum % i == 0 )
return;
total++;
return;
}
if( i < 0 )
return;
if( i < n )
DFS( i - 1 , num - 1 , sum + a[i] );
DFS( i - 1 , num , sum );
return;
}

int main()
{
while( scanf( "%d %d" , &n , &k ) != EOF )
{
total = 0;
memset( a, 0 , sizeof( a ) );
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &a[i] );
DFS( n , k , 0 );
cout << total << endl;
}
return 0;
}

program xx;
var
n,k,i,j,t,sum:longint;
p:boolean;
a:array[0..20]of longint;
b:array[0..20]of longint;
begin
t:=0;
p:=false;
read(n,k);
readln;
for i:=1 to n do read(a[i]);
readln;
for i:=1 to k do b[i]:=i;
b[0]:=0;
while(b[0]=0)do
begin
p:=false;
sum:=0;
j:=k;
while(b[j]=n-k+j)do dec(j);
b[j]:=b[j]+1;
for i:=j+1 to k do b[i]:=b[i-1]+1;
for i:=1 to k do sum:=sum+a[b[i]];
for i:=2 to trunc(sqrt(sum)) do
begin
if(sum mod i=0)then
begin
p:=true;
break;
end;
end;
if(not(p))then t:=t+1;
end;
writeln(t);
end.
O1枚举 拯救世界= =

var
i,j,k,m,ans,n:longint;
a:array[0..100] of longint;
f:array[1..20] of boolean;
function pan(i:longint):longint;
var j:longint;
begin
for j:=2 to trunc(sqrt(i)) do
if i mod j=0 then exit(0);
exit(1);
end;
procedure go(x,l,sum:longint);
var i,j:longint;
begin
if l=k then begin ans:=ans+pan(sum);exit;end;
for i:=x+1 to n do
begin
if f[i]=false then
begin
f[i]:=true;
go(i,l+1,sum+a[i]);
f[i]:=false;
end;
end;
end;

begin
readln(n,k);
for i:=1 to n do read(a[i]);
for i:=1 to n-k+1 do begin f[i]:=true; go(i,1,a[i]); f[i]:=false;end;
writeln(ans);
end.

#include <iostream>
#include <cstdio>
using namespace std;
int a[10001],ans=0,k,n;
bool flag[10001];
bool isprime(int x)
{
for(int i=2;i*i<=x;i++){
if(x%i==0) return false;
}
if(x==1) return false;
if(x!=1) return true;
}
void search(int k1,int s1,int sum)
{
int i;
if(k1>=k){
if(isprime(sum)==1) ans++;
}
else{
for(int i=s1+1;i<=n;i++){
if(!flag[i]){
flag[i]=1;
search(k1+1,i,sum+a[i]);
flag[i]=0;
}
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
search(0,0,0);
printf("%d\n",ans);
//system("pause");
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 516 KiB, score = 10

算法：dfs搜索+prime素数判断

编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 824 KiB, score = 10
Accepted, time = 0 ms, mem = 824 KiB, score = 50

我觉得这题就是背包，大家貌似想复杂了。。。。嗯。。。还是我太渣了、、、
CODE：
var n,k,i,m,s,p:longint;f:boolean;
a:array[1..20] of longint;b:array[1..20] of byte;
begin
read(n,k);fillchar(b,sizeof(b),0);m:=0;
for i:=1 to n do read(a[i]);
repeat
inc(b[n]);s:=0;p:=0;f:=true;
for i:=n downto 1 do begin //万能背包。。。。
if b[i]=2 then begin inc(b[i-1]);b[i]:=0;end;
if b[i]=1 then begin s:=s+a[i];inc(p);end;
end;
if p=k then begin //判断素数
for i:=2 to trunc(sqrt(s)) do if s mod i=0 then
begin f:=false;break;end;if f then inc(m);
end;
until p=n;
writeln(m);
end.