P1036 [NOIP2002 普及组] 选数

梦里梦外; 2023-01-22 12:51 237阅读 0赞

# 原题：[https://www.luogu.com.cn/problem/P1036][https_www.luogu.com.cn_problem_P1036] #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]

深度优先搜索找到排列，然后用一个求质数函数返回1和0，用一个sum在循环中累加，搜索结束返回sum，正好就是结果。

#include <iostream>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    int *a = new int[50];
    bool isprime(int aNum)
    { 
        int cnt = 0;
        for (int i = 1; i * i <= aNum; i++)
        { 
            if (aNum % i == 0)
                cnt++;
        }
        if (cnt == 1)
            return true;
        else
            return false;
    }
    int dfs(int k, int aNum, int start, int end)
    { 
        if (k == 0)
        { 
            return isprime(aNum);
        }
    	int sum = 0; // important
        for (int i = start; i < end; i++)
        { 
            sum += dfs(k - 1, aNum + a[i], i + 1, end);
        }
        return sum;
    }
    int main()
    { 
        ios::sync_with_stdio(false);
        int n, k;
        cin >> n >> k;
        for (int i = 0; i < n; i++)
        { 
            cin >> a[i];
        }
    
        // int sum = 0, cnt = 0;
        // do
        // { 
        // for (int i = 0; i < k; i++)
        // { 
        // // sum += a[i];
        // cout << a[i] << " ";
        // }
        // cout << endl;
        // if (isprime(sum))
        // { 
        // cnt++;
        // }
        // } while (next_permutation(a, a + k));
        cout << dfs(k, 0, 0, n)
             << endl;
        return 0;
    }

[https_www.luogu.com.cn_problem_P1036]: https://www.luogu.com.cn/problem/P1036
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/3098dfec6f294c3c83a83312baf4338c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221020/5ea4564976cb4458b6cfacfba12927fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221020/670c7a68e7f3430c98c64d22aa7083ae.png