【題目鏈接】

ybt 1919：【02NOIP普及組】選數
洛谷 P1036 [NOIP2002 普及組] 選數

【題目考點】

1.排列組合

2.深搜（子集樹）

3.質數

【解題思路】

深搜（子集樹），每次確定要不要選擇某個數字。選擇該數字，則加和增加，然后看下一個數字。不選擇，則直接看下一個數字。如果選擇的數字個數達到k個，那么看加和是不是質數，如果是，計數加1。最后輸出計數。

看數據范圍k,n都小于等于20，從n個數中找k個數的組合數$C_n^k$最大值為$C_{20}^{10}=184756$，可以通過深搜搜索所有可能的組合看加和為質數有多少種情況。
如果直接判斷一個數是否是質數，復雜度為$O(\sqrt{x})$，x為待判斷的數字。x的最大可以是$10$個$5?10^6$相加即$5?10^7$，$\sqrt{5?10^7}\approx 7?10^3$這個數再乘以184756，結果接近$10^9$。
以上只是對時間復雜度最壞情況的理論上的分析，實際每次判斷質數多數情況下不會循環$O(\sqrt{x})$次，應該不會超時，實際也沒有超時。

【題解代碼】

解法1：

#include <bits/stdc++.h> using namespace std; #define N 25 int n, k, x[N], sum, ct;//sum:加和 bool isPrime(int n)//判斷n是不是質數 {for(int i = 2; i <= sqrt(n); ++i){if(n % i == 0)return false;}return true; } //看要不要選擇第i個數字，現在還需要選擇m個數字（深搜子集樹） void dfs(int i, int m) {if(m == 0)//找到解，已經選擇了k個數字 {if(isPrime(sum))//如果num是質數 ct++;//計數加1 return;}if(n-i+1 < m)//剪枝 若 剩余的數字個數 小于 要選擇的數字個數 就退出 return;dfs(i+1, m);//第i數字不加入sum += x[i];//狀態更新 dfs(i+1, m-1);//第i數字加入sum -= x[i];//狀態還原 } int main() {cin >> n >> k;for(int i = 1; i <= n; ++i)cin >> x[i];dfs(1, k);cout << ct;return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1919：【02NOIP普及组】选数 | 洛谷 P1036 [NOIP2002 普及组] 选数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。