/ Vijos / 题库 / 选数 /

182 条题解

• @ 2018-02-06 09:50:50
#include<cstdio>
#include<cmath>
int a[100], n, k, ans;
int check(int x){
int i;
for (i = 2; i <= sqrt(x); i++)
if (x%i == 0) return 0;
return 1;
}
void dfs(int t, int s, int l)
{
int i;
if(t == k){
if (check(s))
ans++;
}
else
for (i = l; i <= n; i++)
dfs(t + 1, s + a[i], i + 1);
}
int main(){
int i;
scanf("%d%d", &n, &k);
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
dfs(0, 0, 1);
printf("%d", ans);
return 0;
}


• @ 2019-08-22 20:53:54

这道题目完全是全排的模板。并不难。

很多题目都是 看数据范围就知道了 ，一看$$n \leq 30$$

就是$$2^n+$$一些剪枝的$$dfs$$的算法。

代码并不难吧。

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a[21];
int ans=0;

inline bool ss(int n){
if(n<2) return 0;
if(n==2 || n==3) return 1;
if((n+1)%6 && (n-1)%6) return 0;
for(int i=2;i*i<=n;i++) if(n%i==0) return 0;
return 1;
}

inline int read(){char ch=getchar();while(ch<'0' || ch>'9') ch=getchar();
int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x;}

inline void dfs(int dep,int bs,int sum) {
if(bs==m) {ans+=ss(sum);return;}
if(dep>n) return;
dfs(dep+1,bs,sum);
dfs(dep+1,bs+1,sum+a[dep]);
}

int main(){
dfs(1,0,0); printf("%d\n",ans);
return 0;
}


• @ 2015-06-07 12:49:20

搜索入门，根本不用剪枝……不剪枝秒杀我也是醉了
注意：不用判断重复的和否则就错了
测试数据 #0: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #4: Accepted, time = 2 ms, mem = 768 KiB, score = 10
Accepted, time = 2 ms, mem = 772 KiB, score = 50

BLOCK code

代码
var
n,k:longint;
i:longint;
list:array[1..21] of longint;
chose:array[1..21] of boolean;
ans:Longint;
function check(num:Longint):boolean;
var i:longint;
begin
if num=2 then exit(true);
if num<=1 then exit(false);
for i:=2 to trunc(sqrt(num)) do
if num mod i=0 then exit(false);
exit(true);
end;
procedure calc(num:longint);
begin
if check(num) then inc(ans);
end;
procedure dfs(x,d,sum:Longint);
var i:Longint;
begin
if (x=k) then begin calc(sum); exit; end;
for i:=d+1 to n do
if chose[i] then
begin
chose[i]:=false;
dfs(x+1,i,sum+list[i]);
chose[i]:=true;
end;
end;
begin
fillchar(list,sizeof(list),0);
fillchar(chose,sizeof(chose),true);
for i:=1 to n do read(list[i]);
dfs(0,0,0);
writeln(ans);
end.

记录信息
评测状态 Accepted
题目 P1128 选数
递交时间 2015-06-07 12:41:07
代码语言 Pascal
评测机 VijosEx
消耗时间 2 ms
消耗内存 772 KiB
评测时间 2015-06-07 12:41:08
评测结果
编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
39 lines compiled, 0.1 sec , 28336 bytes code, 1628 bytes data

• @ 2018-11-04 11:08:26

c++代码
#include<bits/stdc++.h>
using namespace std;
int n,k,ans,a[21];
int pd(int n){
if(n<2) return 0;
for(int i=2;i*i<=n;i++)
if(n%i==0) return 0;
return 1;
}
void dfs(int x,int y,int z){
if(y==k){
if(pd(z)) ans++;
return;
}
if(k-y>n-x+1) return;
dfs(x+1,y,z);
dfs(x+1,y+1,z+a[x]);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(1,0,0);
printf("%d",ans);
return 0;
}

• @ 2018-09-23 16:57:05

这题数据真是水……亏我还特地写了个非递归形式的DFS，结果根本体现不出任何优势，码了这么长真不值……
本来还想用埃式筛法打表的，看来是没必要了……

#include <iostream>
#include <cstdlib>
#include <stack>
using namespace std;

int ans=0;
struct node
{
int x[19];
int num;
node():num(0){}
};
stack<node> st;

bool isPrim(int a)
{
bool flag=true;
for(int i=2;i*i<=a;i++)
if(a%i==0)
{
flag=false;
break;
}
return flag;
}

void DFS(int n,int k,int a[])
{
node t;
st.push(t);
while(st.empty()==false)
{
t=st.top();
st.pop();
if(t.num==k)
{
int sum=0;
for(int i=0;i<t.num;i++)
sum+=a[t.x[i]];
if(isPrim(sum)==true)
ans++;
}
else
{
int temp;
if(t.num-1<0)
temp=-1;
else
temp=t.x[t.num-1];
for(int i=temp+1;i<n;i++)
{
node aot=t;
aot.x[aot.num]=i;
aot.num++;
st.push(aot);
}
}
}
}

int main()
{
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
DFS(n,k,a);
cout<<ans<<endl;
return 0;
}


• @ 2018-08-16 16:09:52

#include<iostream>
#include<math.h>
using namespace std;
int x[20],n,k;
bool isprime(int n){
int s=sqrt(double(n));
for(int i=2;i<=s;i++){
if(n%i==0)return false;
}
return true;
}
int rule(int choose_left_num,int already_sum,int start,int end){
int sum=0;
for(int i=start;i<=end;i++){
}
return sum;
}
int main(){
cin>>n>>k;
for(int i =0;i<n;i++)cin>>x[i];
cout<<rule(k,0,0,n-1);
return 0;
}

• @ 2017-07-13 22:40:17

深搜水过。。
var
a:array[1..20] of longint;
n,k,i,j,num,sum,ans:longint;
function check(x:longint):boolean;
var
bj,i:longint;
begin
bj:=0;
for i:=2 to trunc(sqrt(x)) do
if x mod i=0
then begin
bj:=1;
break;
end;
if bj=0
then exit(true)
else exit(false);
end;
procedure doit(t:longint);
var
j:longint;
begin
if num=k
then begin
if check(sum)
then inc(ans);
exit;
end;
for j:=t+1 to n do
begin
inc(num);
sum:=sum+a[j];
doit(j);
dec(num);
sum:=sum-a[j];
end;
end;
begin
for i:=1 to n do
for i:=1 to n-k+1 do
begin
num:=1;
sum:=a[i];
doit(i);
end;
writeln(ans);
end.

• @ 2017-06-25 16:43:04
#include<iostream>
#include<cmath>
using namespace std;
int a[100],n,k,ans;
int check(int x)
{
int i;
for(i=2;i<=sqrt(x);i++)
if(x%i==0) return 0;
return 1;
}
void dfs(int t,int s,int l)
{
int i;
if(t==k)
{
if(check(s))
ans++;
}
else
for(i=l;i<=n;i++)
dfs(t+1,s+a[i],i+1);
}
int main()
{
int i;
cin>>n>>k;
for(i=1;i<=n;i++)
cin>>a[i];
dfs(0,0,1);
cout<<ans;
return 0;
}

• @ 2017-10-02 08:09:51

调万能库的傻逼

• @ 2017-06-23 16:57:16

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<queue>
#define mian main
using namespace std;
int n,k;
int a[50];
int ans=0;
bool jc(int n)
{
for(int i=2;i<sqrt(n);i++)
if(n%i==0)
return false;
return true;
}
void search_DFS(int now,int w,int t)
{
if(w>n)
return;
if(now==k)
{
if(jc(t)==1)
++ans;
return;
}
search_DFS(now+1,w+1,t+a[w]);
search_DFS(now,w+1,t);
}
int main()
{
int Zoe,Forever,xzy,clxf,YBB;
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
search_DFS(0,0,0);
cout<<ans<<endl;

return 0;
}

• @ 2017-05-08 09:00:56

暴力打满？

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int a[24];
bool v[24];
long long f[25];
int n,k,ans;

bool check(int n)
{
for(int i=2;i<=sqrt(n);i++)
if(n%i==0)
return false;
return true;
}

void dfs(int cur,int sum)
{
if(cur==k+1)
{
if(check(sum))
ans++;
}
else
{
for(int i=1;i<=n;i++)
if(!v[i])
{
v[i]=1;
dfs(cur+1,sum+a[i]);
v[i]=0;
}
}
}

int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0]=1;
for(int i=1;i<=k;i++)
f[i]=f[i-1]*i;
dfs(1,0);
cout<<ans/f[k]<<endl;
return 0;
}


• @ 2016-12-14 13:43:11
#include<bits/stdc++.h>
using namespace std;
int a[25];
int n,k,ans=0;
bool pd(int x)
{
for(int i=2;i*i<=x;++i)
if(x%i==0)return 0;
return 1;
}
void dfs(int now,int w,int t)
{
if(w>n)
return;
if(now==k){
if(pd(t)==1)
++ans;
return;
}
dfs(now+1,w+1,t+a[w]);
dfs(now,w+1,t);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;++i)scanf("%d",&a[i]);
dfs(0,0,0);
printf("%d\n",ans);
return 0;
}


• @ 2016-08-22 23:28:48

#include"stdio.h"
#include"stdlib.h"
#include"iostream"
#include"string.h"
#include"map"
using namespace std;
typedef long long ll;
ll mod(ll a,ll b,ll c)
{
if(!b) return 1;
return mod(a*a%c,b/2,c)*((b&1)?a:1)%c;
}

bool MR(ll x)
{
if(x==2) return true;
for(int i=1;i<=50;i++){
ll a=rand()%(x-2)+2;
if(mod(a,x-1,x)!=1)
return false;
}
return true;
}
int ans,n,k;
int a[40];
int visit[50];
void dfs(int pos,int num,int dep)
{
visit[pos]=1;
if(dep==k)
{
if(MR(num)) {ans++;}
return;
}
for(int i=pos+1;i<n;i++)
if(!visit[i])
{
dfs(i,num+a[i],dep+1); //dfs之后记得把标志更改回来
visit[i]=0;
}
return;
}
int main()
{
while(cin>>n>>k) //不要去重只要组合起来三个是素数就行
{
cnt.clear();
ans=0;
for(int i=0;i<n;i++)
cin>>a[i];
memset(visit,0,sizeof(visit));
for(int i=0;i<n-k+1;i++)
{
if(!visit[i])
{
dfs(i,a[i],1);
visit[i]=0;
}

}
cout<<ans<<endl;
}
}

• @ 2016-08-16 21:34:27

var
n,k,i,ans,sum:longint;
a:array[1..10000] of qword;
b:array[1..10000] of boolean;
function pd(i:longint):boolean;
var
flag:boolean;
j:longint;
begin
flag:=true;
if i=1 then flag:=false;
if i=2 then flag:=true;
if (i<>1) and (i<>2) then begin
for j:=2 to trunc(sqrt(i)) do begin
if i mod j=0 then flag:=false;
end;
end;
pd:=flag;
end;
procedure dfs(i,j:longint);
var
p:longint;
begin
if i=k+1 then begin
if (pd(sum)=true) then inc(ans);
end
else begin
for p:=j to n do begin
if b[p]=true then begin
sum:=sum+a[p];
b[p]:=false;
dfs(i+1,p+1);
b[p]:=true;
sum:=sum-a[p];
end;
end;
end;
end;
begin
for i:=1 to n do begin
end;
fillchar(b,sizeof(b),true);
dfs(1,1);
writeln(ans);
end.

• @ 2016-08-13 12:12:55

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int a[24];
bool v[24];
long long f[25];
int n,k,ans;

bool check(int n)
{
for(int i=2;i<=sqrt(n);i++)
if(n%i==0)
return false;
return true;
}

void dfs(int cur,int sum)
{
if(cur==k+1)
{
if(check(sum))
ans++;
}
else
{
for(int i=1;i<=n;i++)
if(!v[i])
{
v[i]=1;
dfs(cur+1,sum+a[i]);
v[i]=0;
}
}
}

int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0]=1;
for(int i=1;i<=k;i++)
f[i]=f[i-1]*i;
dfs(1,0);
cout<<ans/f[k]<<endl;
return 0;
}

我是弱逼不会做啊，就直接sb暴搜

• @ 2016-08-04 20:55:18

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
int num[55]={0};
bool f[55]={0};
int tol=0,j=0,p,m;
int n,k,i;
int su(int zong)
{
for(m=2;m<=sqrt(zong);m++)
if(zong%m==0) return 0;
return 1;
}
int tj(int tal)
{
if(j==k)
{
if(su(tal)==1) tol++;
tal-=num[p];
j--;
return 0;
}
for(p=0;p<n;p++)
if(f[p]==0)
{
j++;
f[p]=1;
tal+=num[p];
printf("\n%d %d\n",j,tal);
tj(tal);

f[p]=0;
printf("\n%d %d\n",f[p],p);

}

return 0;
}
int main()
{
scanf("%d %d",&n,&k);
for(i=0;i<n;i++) scanf("%d",&num[i]);
tj(0);
printf("%d",tol);
getchar();
getchar();
return 0;
}
有人能告诉我这个搜索为什么是错的吗

• @ 2016-02-18 15:23:50

var
l,j,tot,ans,n,k,i:longint;
a:array[1..21] of longint;
f:array[1..21] of boolean;

procedure pd(c:longint);
begin
if c<2 then exit;
if c=2 then begin inc(ans); exit; end;
for i:=2 to round(sqrt(c)) do
if c mod i=0 then exit;
inc(ans); exit;
end;

procedure search(l,j:longint);
var i:longint;
begin
if l>k then pd(tot);
for i:=j to n do
if (not f[i])and(l<=k) then
begin
f[i]:=true;
inc(tot,a[i]);
search(l+1,i+1);
f[i]:=false;
dec(tot,a[i]);
end;
end;

begin
fillchar(f,sizeof(f),false);
fillchar(a,sizeof(a),0);
for i:=1 to n do
tot:=0; l:=0; ans:=0;
search(1,1);
writeln(ans);
end.

• @ 2015-10-04 17:21:29

测试数据 #0: Accepted, time = 0 ms, mem = 1056 KiB, score = 10
测试数据 #1: WrongAnswer, time = 0 ms, mem = 1060 KiB, score = 0
测试数据 #2: WrongAnswer, time = 15 ms, mem = 1056 KiB, score = 0
测试数据 #3: Accepted, time = 0 ms, mem = 1056 KiB, score = 10
测试数据 #4: WrongAnswer, time = 0 ms, mem = 1052 KiB, score = 0
WrongAnswer, time = 15 ms, mem = 1060 KiB, score = 20
代码
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

long long a[25],f[25],i,j,k,l,n,m,b[100000];
bool c[25];

bool p(long long y)
{
for (int i=2;i<=y-1;i++)
if (y%i==0) return false;
return true;
}

int find(int x)
{
if (x==k+1)
{
int s;s=0;
for (int i=1;i<=k;i++)
s+=f[i];
if (p(s) && b[s]==0) {
m++;b[s]=1;}
}
else
{
for (int i=1;i<=n;i++)
{
if (!c[i])
{
c[i]=true;
f[x]=a[i];
find(x+1);
c[i]=false;
}
}
}

}

int main()
{
cin >>n>>k;
for (i=1;i<=n;i++)
cin >>a[i];
find(1);
cout <<m;
}
求大神指教

• @ 2015-09-12 08:47:10

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int a[10005];
int n,k;
int s=0;
int isp(int x){
for (int i=2;i<=sqrt(x);i++)
if (x%i==0) return 0;
return 1;
}
int dfs(int nw,int w,int t){
if (w>n)
return 0;
if (nw==k){
if (isp(t)==1)
s++;
return 0;
}
dfs(nw+1,w+1,t+a[w]);
dfs(nw,w+1,t);
}
int main (){
cin>>n>>k;
for (int i=0;i<n;i++)
cin>>a[i];
dfs(0,0,0);
cout<<s;
}

• @ 2015-08-31 10:53:42

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;
for p:=1 to n do
search(1);
writeln(num);
end.

• @ 2015-08-14 21:14:08

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;
}

ID
1128

4

5685

2574

45%

3