Problem:1008 新建题解

Solution_ID:32893            选数

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>

#include<cmath>

#include<iostream>

using namespace std;

typedef long long ll;

ll a[105],n,k,total=0;

bool prime(ll n)

{

ll i;

for(i=2;i<=sqrt(n);i++)

{

if(n%i==0)

return 0;

}

return 1;

}

void dfs(ll s,ll i,ll j)

{

if(j==k)

{

if(prime(s))

total++;

return;

if(i>n)

return;

dfs(s+a[i],i+1,j+1);

dfs(s,i+1,j);

}

int main()

{

cin>>n>>k;

for(int i=1;i<=n;i++)

cin>>a[i];

dfs(0,1,0);

cout<<total;

}


by 84201 七月 16, 2019, 2:50 p.m.

Solution_ID:32667            简单粗暴,建议使用

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
#include<cmath>
using namespace std;
int n,m,a[100],s;
int ZS(int d){
 for(int i=2;i<=sqrt(d);i++){
  if(d%i==0)return 0;
 }
 return 1;
}
void dfs(int y,int x,int z){
 if(x==m){
 if(ZS(z)==1){
  s++;
 }
 return;
 }
 if(y>n)return;
 dfs(y+1,x+1,z+a[y]);
 dfs(y+1,x,z);
}
int main(){
 cin>>n>>m;
 for(int i=1;i<=n;i++)cin>>a[i];
 dfs(1,0,0);
 cout<<s;
 return 0;
}


by 85057 四月 24, 2019, 9:44 p.m.

Solution_ID:32648            递归搜索 同采药

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cmath>

using namespace std;

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

int prime(int a){

    int i;

    if(a<2)return 0;

    if(a==2)return 1;

    for(i=2;i*i<=a;i++)

        if(a%i==0)return 0;

    return 1;

}

void add(int x,int g,int z){

if(g==m){

if(prime(z)==1)

ans++;

return;

}

if(x>n)return;

add(x+1,g+1,z+a[x]);

add(x+1,g,z);

}


int main(){

cin>>n>>m;

for(int i=1;i<=n;i++){

cin>>a[i];

}

    add(1,0,0);

cout<<ans<<endl;



return 0;

}



by 90097 四月 14, 2019, 5:31 p.m.

Solution_ID:32328            递归搜索

                   时间复杂度:Θ(o( )) 空间复杂度:Θ(o(n))

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int a[101],n,k,t;

int pd(int x)

{

if(x==1||x==0) return 0;

    for(int i=2;i<=sqrt(x);i++)

    if(x%i==0) return 0;

return 1;

}

void zh(int p,int s,int x)

{

    if(p==n+1||x==k)

    {

    if(x==k) if(pd(s)) t++;

        return;

    }

    zh(p+1,s+a[p],x+1);

    zh(p+1,s,x);

return;

}

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)

scanf("%d",&a[i]);

    zh(1,0,0);

    printf("%d",t);

    return 0;

}


by 86517 一月 16, 2019, 5:47 p.m.

Solution_ID:32277            递归生成组合(深搜)

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <stdio.h>

#include <stdlib.h>
int count,N,K,Array[20];
int IsPrime(int Num)
{
    int i;
    if(Num%2==0)
        return 0;
    for(i=3;i*i<=Num;i+=2)
        if(Num%i==0)
            return 0;
    return 1;
}
void Input()
{
    int i;
    scanf("%d%d",&N,&K);
    for(i=0;i<N;i++)
        scanf("%d",&Array[i]);
}
void CreateCombination(int Left,int Right,int Sum)
{
    int i;
    if(Right==N)
    {
        if(IsPrime(Sum))
            count++;
        return ;
    }
    for(i=Left;i<=Right;i++)
        CreateCombination(i+1,Right+1,Sum+Array[i]);
    return ;
}
int main()
{
    Input();
    CreateCombination(0,N-K,0);
    printf("%d\n",count);
    return 0;
}

by 65190 一月 6, 2019, 12:14 p.m.

Solution_ID:31844            二进制解法,不用dfs

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
bool isprime(int n)
{
 for(int i=2;i<=sqrt(n);++i)
 if(!(n%i)) return false;
 return true;
}
int count_one(int n)
{
 int ct=0;
 while(n) n&=n-1,ct++;
 return ct;
}
int main()
{
 int n,k,res=0;
 cin>>n>>k;
 vector<int> v(n);
 for(int i=0;i<n;++i) cin>>v[i];
 int bs=(1<<k)-1;
 while(bs<(1<<n))
 {
  if(count_one(bs)==k) 
  {
   int t=0;
   for(int i=0;i<n;++i) if(bs&(1<<i)) t+=v[i];
   if(isprime(t)) res++;
  }
  ++bs;
 }
 cout<<res;
 return 0;
}


by 68279 九月 11, 2018, 8:05 p.m.

Solution_ID:31449            写一个题解

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<bits/stdc++.h>
using namespace std;
int cnt = 0,sum = 0,ans = 0;
int a[100],n,k;
int isprime(int x)
{
  int i;
  if(x<2) return 0;
  else if(x == 2) return 1;
  if(x%2 == 0) return 0;
  for(i = 3;i*i<=x;i+=2)
   if(x%i == 0) return 0;
  return 1;
}
void dfs(int x)
{
  if(ans>=k)
  {
    if(isprime(sum))
     cnt++;
     return ;
  }
  for(int i =x;i<=n;i++)
  {
    sum += a[i];
    ans++;
    dfs(i+1);
    sum -= a[i];
    ans--;
  }
}
int main ()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>n>>k;
  for(int i= 1;i<=n;i++)
   cin>>a[i];
  dfs(1);
  cout<<cnt<<endl;
  return 0 ;
}




by 73734 七月 18, 2018, 12:24 p.m.

Solution_ID:31316            先求质数再晦朔

                   时间复杂度:Θ() 空间复杂度:Θ()

先求出一个质数列表,本题目最大和为1E,也就是需要求出10000附近的质数;求法从5,7,9,11.。。。(2,3手动加到列表中),判断的话不用从(3,5,sqrt),直接从质数列表里去整除判断;

然后就是一个回溯了……基本上是遍历所有组合(注意k个索引不能重复后在检测)


by 74728 五月 20, 2018, 4:11 p.m.

Solution_ID:31080            递归搜索

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <stdio.h>

#define M 21

 

int n=0,k=0;  //n个整数中选择k个 

int count=0;


int judge(int num);

void arrange(int *num,int current,int address,int sum);


int main(void)

{

int i=0;

int num[M]={0};  //num数组接收n个整数

scanf("%d %d",&n,&k);

for(i=0;i<n;i++)

{

scanf("%d",num+i);

}

arrange(num,0,0,0);

printf("%d",count); 

return 0;

}

//对num数组进行搜索,赋值加入sum,current为当前确定sum已经加入多少个数

//sum每次加入的值只从num数组中address开始取 

void arrange(int *num,int current,int address,int sum)

{

int i=0;

if(current>=k) 

{

if(judge(sum)) count++;

return;

}

for(i=address;i<n;i++)

{

sum+=num[i];

arrange(num,current+1,i+1,sum);

sum-=num[i];

}

}

//判断num是否为素数 

int judge(int num)

{

int i=0;

for(i=2;i*i<=num;i++)

{

if(num%i==0) return 0;

}

return 1;

}


by 68872 三月 15, 2018, 3:09 p.m.

Solution_ID:30991            特别的思路,AC时间有点久

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
#include<cmath>
using namespace std;
int sum = 0, n, k, num[21];
int is_Prime(int n)
{
  int ok = 1;
  for(int i = 2; i<= sqrt(n); i++)
	  if(n%i == 0) ok = 0;
  return ok;
}
void DFS(int count, int index, int cur)
{
   count += num[index];
   if(cur == k)
   {
	  if( is_Prime(count) ) sum++;
	  return ;
   }
   for(int i = index+1; i < n; i++)
	   DFS(count,i,cur+1);
}
int main()
{
  cin>>n>>k;
  for(int i = 0; i < n; i++)
	  cin>>num[i];
  for(int j = 0; j < n-k+1; j++)
	  DFS(0,j,1);
  cout<<sum<<endl;
  return 0;
}





by 53193 二月 27, 2018, 11:57 a.m.

Solution_ID:30297            用啥搜索,直接回溯就解决了

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <iostream>
using namespace std;

int N,M;
int a[30];
int vis[30];
int count;

int sumVis(){
int sum=0;
for(int i=0;i<N;i++){
sum+=vis[i];
}
return sum;
}

bool sushu(int num){
int div;
for(div = 2; (div * div) <= num;div++){
if(num % div == 0){
return false;
}
}
return true;
}

void judge(){
int sum=0;
for(int i=0;i<N;i++){
if(vis[i]==1){
sum+=a[i];
}
}
if(sushu(sum)){
count++;
}
}

void selectNum(int arg){
vis[arg]=1;
if(sumVis()==M) {
judge();
}else{
if(arg<(N-1)){
selectNum(arg+1);
}
}
vis[arg]=0;
if(arg<(N-1)){
selectNum(arg+1);
}
}

int main(){
cin>>N>>M;
for(int i=0;i<N;i++){
cin>>a[i];
}
for(int i=0;i<N;i++){
vis[i]=0;
}
count=0;
selectNum(0);
cout<<count<<endl;
return 0;
}

by 13199 十一月 29, 2017, 2:45 p.m.

Solution_ID:30265            用递归挺简单的

                   时间复杂度:Θ() 空间复杂度:Θ()

这个题很容易就能想到用递归来解决 不过就是有点难想 想了差不多快半个小时终于写出了这个递归函数 AC了还是很开心的  

代码如下:


#include <stdio.h>

#include <math.h>

int p[100]={0};

int sum ;

int count;

int n,k;

int susu (int n)

{

    if(n==1) return 0;

    int flag =1;

    for(int i=2;i<=(int) sqrt(n);i++)

    {

        if(n%i==0)

        {

            flag = 0;

            break;

        }

    }

    if(flag) return 1;

    return 0;

}

void digui(int a,int b)//b = n-k+1

{

    if(b==n)

    {

        for(int i=a;i<=b;i++)

        {

            int ans = sum;

            ans += p[i];

            if(susu(ans))

                count++;

            //printf("%d\n",ans);

        }

    }

    else

    {

        for(int i=a;i<=b;i++)

        {

            sum+=p[i];

            digui(i+1,b+1);

            sum -= p[i];

        }

    }

}

int main (void)

{

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)

        scanf("%d",&p[i]);

    int a = 1;

    int b = n-k+1;

    count = 0;sum = 0;

    digui(a,b);

    printf("%d\n",count);

    return 0;

}



by 66456 十一月 26, 2017, 8:54 p.m.

Solution_ID:29402            一种比较有趣的解法,没有用全排列

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <stdio.h>

#include <math.h>

#include <string.h>


int a[30],b[30];


bool zs(int x){

int cnt=0;

for(int j=2;j<=sqrt(x);j++) if(x%j==0) cnt++;

if(cnt==0) return true;

else return false;

}


int main(){

int n,k,cnt=0;

scanf("%d %d",&n,&k);

for(int i=0;i<n;i++) scanf("%d",&a[i]);

for(int i=0;i<k;i++) b[i]=i;

while(1){

int temp=0;

for(int i=0;i<k;i++){

temp+=a[b[i]];

}

if(zs(temp)) cnt++;

int i=0;

int flag=1;

while(i<k){

// if(b[k-i-1]==0){

// b[k-i-1]++;

// if(b[k-i-1]>n-k){

// flag=1;

// }

// }


if(flag==1){ 

                int temp_2=b[k-i-1]+1;

b[k-i-1]++;

for(int j=k-i-1;j<k;j++){

b[j]=temp_2++;

}

}

if(b[k-i-1]>n-i-1||b[k-i-1]<b[k-i-2]){

flag=1;

}

else {

flag=0;

break;

}

i++;

}

if(flag==1){

break;

}

}

printf("%d",cnt);

return 0;

}


by 59323 九月 27, 2017, 11:59 p.m.

Solution_ID:29070            题解

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

using namespace std;

inline int isPrime(const int& x)

{

    long long _x = ((long long)(x));

    if (_x == 0 || _x == 1)return 0;

    if (_x == 2)return 1;

    if (!(_x & 1))return 0;

    for (long long i = 3; i * i <= _x; i++)

    {

        if (!(_x%i))return 0;

    }

    return 1;

}

int numArr[21];

int k, n;

int ans;

void solve(int curValue, int depth, int beg)

{

    for (int i = beg; i <= n - k +depth; i++)

    {

        curValue += numArr[i];

        if (depth == k - 1)

        {

             ans += isPrime(curValue);

        }

        else

        {

            solve(curValue, depth + 1, i + 1);

        }

        curValue -= numArr[i];

    }

}


int main()

{

    cin >> n >> k;

    ans = 0;

    for (int i = 0; i < n; i++)cin >> numArr[i];

    solve(0, 0, 0);

    cout << ans << std::endl;

}



by 62931 九月 2, 2017, 11:44 a.m.

Solution_ID:28781            DFS 全排

                   时间复杂度:Θ() 空间复杂度:Θ()

一开始还想打素数表,没想到会超时。

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

int a[100],n,k,tot=0,tag[1000],s[1000];

void dfs(int dep,int pl){

int i,j,l,p;

if(dep==k+1){

int sum=0,j=0;

for(i=1;i<=k;i++) sum=sum+s[i];

for(i=2;i<=sqrt(sum);i++) if(sum%i==0) j=1;

if(j==0) tot++; 

}

else{

for(i=1;i<=n;i++){

if(tag[i]==0&&i>pl){

s[dep]=a[i];

tag[i]=1;

dfs(dep+1,i);

tag[i]=0;

}

}

}

}

int main(){

memset(tag,0,sizeof(tag));

int i,j,m=0;

cin>>n>>k;

for(i=1;i<=n;i++){

cin>>a[i];

m=m+a[i];

}

dfs(1,0);

cout<<tot;

}


by 59734 八月 18, 2017, 10:50 p.m.

Solution_ID:28521            应该比较短了吧献给我的多多

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream> 

#include<cmath>

using namespace std;

int m,p,s[22],ans=0;

bool pp[22];

void pd(int x)

{

for(int i=2;i<=sqrt(x);i++)

 if(x%i==0)return;

ans++;

}

void tyh(int n,int k,int zz,int zh)

{

    if(zz==m+1)zz=1;

if(k==0)pd(zh);

else

{

if(pp[zz]==0)

{

 pp[zz]=1;

 tyh(n-1,k-1,zz+1,zh+s[zz]);

          pp[zz]=0;

 if(n>k)

 tyh(n-1,k,zz+1,zh);

}

}

}

int main()

{

cin>>m>>p;

for(int i=1;i<=m;i++)

 cin>>s[i];

    tyh(m,p,1,0);

    cout<<ans<<endl;

return 0;

}


by 60937 八月 6, 2017, 7:33 p.m.

Solution_ID:28349            垃圾题解

                   时间复杂度:Θ() 空间复杂度:Θ()

这里#include<iostream>

#include<cmath>

using namespace std;

const int maxn=30;

int n,k,ans=0,sum=0,path[maxn]={0};

int a[maxn]={0};

int pos=0;

int prime(int m)

{

    for(int i=2;i<sqrt(m)+1;i++)

{

        if (m % i==0)return 0;

    }

    return 1;

}

int search(int cur)

{

    for(int j=cur;j<n;j++)

{

        ans+=a[j];

        path[pos++]=a[j];

        if(pos==k)

{

sum += prime (ans);

}

        else search(j+1);

        ans-=a[j];

        pos--;

    }

}

int main()

{

    cin>>n>> k;

    for (int i = 0;i < n; i++)

{

        cin>>a[i];

    }

    search(0);

    cout<<sum<<endl;

}写题解


by 60488 七月 31, 2017, 12:08 p.m.

Solution_ID:27698            额。。。直接上题解

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cmath>

using namespace std;

int a[1410],n,k;

long long b[21],tot=0,ss=0,c[190000],zh=0,sss=0;

void build(){

int sum=0,kk;

for(int i=2;i<=11690;i++){

kk=1;

for(int j=2;j<=sqrt(i);j++){

if(i%j==0){

kk=0;break;

}

}

if(kk==1){

sum++;

a[sum]=i;

}

}

}

void check(long long x){

int kk,i;kk=1;i=1;

while(a[i]<=sqrt(x)){

if(x%a[i]==0) {

kk=0;

break;

}

i++;

}

if(kk==1) ss++;

}

void search(int xx,int yy,int zz){

if(xx>yy){

sss++;c[sss]=zh;return;

}

for(int i=zz;i<=n;i++){

zh=zh+b[i];

search(xx+1,yy,i+1);

zh=zh-b[i];

}

return ;

}

int main(){

build();

cin>>n>>k;

for(int i=1;i<=n;i++) {

cin>>b[i];

tot+=b[i];

}

if(n/2>=k) search(1,k,1);

else {

search(1,n-k,1);

for(int i=1;i<=sss;i++) c[i]=tot-c[i];

}

for(int i=1;i<=sss;i++){

check(c[i]);

}

cout<<ss;

return 0;

}


by 56263 七月 8, 2017, 9:57 p.m.

Solution_ID:27543            蒟蒻做法

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

int n,k,s=0;int a[30],w[30];bool f[30];

bool ss(int x)

{

if (x<2)

 return false;

for (int i=2;i<=sqrt(x);i++)

 if (x%i==0) return false;

return true;

}

void res()

{ int i,sum=0;

for (i=1;i<=k;i++)

 sum+=w[i];

  if (ss(sum))

    s++;

}

void sea(int i,int x)

{ int j;

if (i==k+1)

 res();

else

for (j=x+1;j<=n;j++)

 if (f[j]==false)

{w[i]=a[j];f[j]=true;sea(i+1,j);f[j]=false;}

}

int main()

{

scanf("%d%d",&n,&k);

int i;

memset(f,false,sizeof(f));

for (i=1;i<=n;i++)

 scanf("%d",&a[i]);

sea(1,0);

printf("%d",s); 

}


by 58027 七月 4, 2017, 8:37 p.m.

Solution_ID:27385            dfs练习题

                   时间复杂度:Θ(C(n,k)) 空间复杂度:Θ(n)

测试点#xs1.in  结果:<label>AC</label>    内存使用量:  256kB     时间使用量:  0ms     
测试点#xs2.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#xs3.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#xs4.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#xs5.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 13ms
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(int i=l;i<=r;++i)
int N,K,v[25],tot=0,co=0;
inline bool check(int p){
	if(p<2)return 0;
	for(int i=2;i*i<=p;i++)if(p%i==0)return 0;
	return 1;
}
void dfs(int pos,int dep){
	if(dep==K){
		if(check(tot))co++;
		return;
	}
	if(pos>N)return;
	dfs(pos+1,dep);
	tot+=v[pos];
	dfs(pos+1,dep+1);
	tot-=v[pos];
}
int main(){
	scanf("%d%d",&N,&K);
	FOR(i,1,N)scanf("%d",v+i);
	dfs(1,0);
	printf("%d\n",co);
} 

by 45271 六月 24, 2017, 2:08 p.m.