P1036 [NOIP2002 普及组] 选数

题目描述：P1036 [NOIP2002 普及组] 选数

---

解题思路

---

• 解题思路

  1、由于数据范围较小，所以可猜测该题使用搜索算法
  2、DFS 搜索的参数需要记录当前层位置、当前选择的数字个数、当前的和这三项信息
  3、作为递归搜索出口，当选择了 $k$ 个数时，判断当前和是否为质数(质数判断函数)；当当前层数大于 $n$ 时，返回 $0$
  4、对于每次搜索，都有两种向下递归的可能，可以不选当前数，也可以选择当前数，递归处理

---

代码实现

---

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 30;
  int a[30], n, k;
  
  bool is_prime(int x)
  {
      if (x == 2)
          return true;
      if (x < 2)
          return false;
  
      for (int i = 2; i <= x / i; i++)
          if (x % i == 0)
              return false;
      return true;
  }
  
  // dep 表示当前在第几层，cnt 表示当前一共选了几个数字，sum 表示当前的和
  int DFS(int dep, int cnt, int sum)
  {
      // 如果已经选到 k 个数，判断和是否是质数
      if (cnt == k)
          return (int)is_prime(sum);
      // 如果层数超过 n，直接返回 0
      if (dep > n)
          return 0;
  
      int res = 0;                                // 统计满足的种类数
      res += DFS(dep + 1, cnt, sum);              // 不选当前数
      res += DFS(dep + 1, cnt + 1, sum + a[dep]); // 选了当前数
      return res;
  }
  
  void solve()
  {
      cin >> n >> k;
      for (int i = 1; i <= n; i++)
          cin >> a[i];
  
      cout << DFS(1, 0, 0);
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---