/ Vijos / 题库 / 选数 /

题解

184 条题解

  • 3
    @ 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;
}
  • 1
    @ 2021-02-26 08:36:49 
    #include<bits/stdc++.h>
using  namespace  std;
int n,k,i,j,sum,tot,a[21],x[21];
bool c(int x)
{
    if(x==1)return false;
    for(int i=2;i<=sqrt(x);i=i+1)
     if(x%i==0)return false;
     return true;
}
 
int  main()
{
  cin>>n>>k;
  for(i=1;i<=n;i=i+1)
   cin>>x[i];
   for(i=0;i<=k;i=i+1)a[i]=i;
    while(a[0]==0)
    {
        sum=0;
        for(i=1;i<=k;i=i+1)
        sum=sum+x[a[i]];
        if(c(sum))tot++;
        j=k;
        while(a[j]==n+j-k)j--;
        a[j]=a[j]+1;
        for(i=j+1;i<=k;i=i+1)
        a[i]=a[i-1]+1;
    }
   cout<<tot;
}
  • 1
    @ 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(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    dfs(1,0,0); printf("%d\n",ans);
    return 0;
}
  • 1
    @ 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
    readln(n,k);
    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
    Linking foo.exe
    39 lines compiled, 0.1 sec , 28336 bytes code, 1628 bytes data

  • 0
    @ 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;
    }

  • 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;
}
  • 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){
    if(choose_left_num==0)return isprime(already_sum);
    int sum=0;
    for(int i=start;i<=end;i++){
    sum+=rule(choose_left_num-1,already_sum+x[i],i+1,end);
    }
    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;
    }

  • 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
    readln(n,k);
    for i:=1 to n do
    read(a[i]);
    for i:=1 to n-k+1 do
    begin
    num:=1;
    sum:=a[i];
    doit(i);
    end;
    writeln(ans);
    end.

  • 0
    @ 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;
}
  • 0
    @ 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;
    }

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

  • 0
    @ 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
    readln(n,k);
    for i:=1 to n do begin
    read(a[i]);
    end;
    readln;
    fillchar(b,sizeof(b),true);
    dfs(1,1);
    writeln(ans);
    end.

  • 0
    @ 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暴搜

  • 0
    @ 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;
    }
    有人能告诉我这个搜索为什么是错的吗

  • 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
    readln(n,k);
    fillchar(f,sizeof(f),false);
    fillchar(a,sizeof(a),0);
    for i:=1 to n do
    read(a[i]);
    tot:=0; l:=0; ans:=0;
    search(1,1);
    writeln(ans);
    end.

  • 0
    @ 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;
    }
    求大神指教

  • 0
    @ 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;
    }

  • 0
    @ 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;
    readln(n,k);
    for p:=1 to n do
    read(s[p]);
    search(1);
    writeln(num);
    end.

选数

信息

ID
1128
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
5816
已通过
2645
通过率
45%
被复制
28
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1