2 条题解

  • 0
    @ 2023-7-5 13:26:31
    #include <bits/stdc++.h>
    using namespace std;
    int n, k;
    int a[10005];
    // f[i][j] 前 i 个数,组合出来 %k 之后能否为 j
    bool f[10005][105];
    int main()
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        f[0][0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= k - 1; j++)
            {
                int pre1 = ((j + a[i]) % k + k) % k;
                int pre2 = ((j - a[i]) % k + k) % k;
                f[i][j] = f[i - 1][pre1] || f[i - 1][pre2];
            }
        }
        if (f[n][0])
            cout << "YES\n";
        else
            cout << "NO\n";
        return 0;
    }
    
    • 0
      @ 2023-7-4 23:14:27
      #include <bits/stdc++.h>
      using namespace std;
      #define int long long
      #define endl '\n'
      #define pii pair<int, int>
      const int N = 1e4 + 5;
      int n, k;
      int a[N];
      bool dp[N][105]; // dp[i][j] -> 当前做到第i个数 存不存在 sum % k == j 的方案
      signed main()
      {
          ios::sync_with_stdio(false);
          cin.tie(0);
          cin >> n >> k;
          for (int i = 1; i <= n; i++)
              cin >> a[i];
          dp[0][0] = 1;
          for (int i = 1; i <= n; i++)
          {
              for (int j = 0; j < k; j++)
              {
                  if (dp[i - 1][j]) // 如果前一位存在 % k == j  那么可以在此基础上继续加当前的数
                  {
                      int now = (j + a[i]) % k;         // 加上 a[i] % k 是多少
                      dp[i][now] = true;                // 更新答案
                      now = (j - a[i] + k * 10001) % k; // 减去 a[i] % k 是多少  注意: now 应当大于等于0
                      dp[i][now] = true;                // 更新答案
                  }
              }
          }
          cout << (dp[n][0] ? "YES" : "NO") << endl; // 如果做到第n位时 有 sum % k == 0 则证明存在一种方案 否则不存在
      }
      
      • 1

      信息

      ID
      415
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      (无)
      递交数
      42
      已通过
      12
      上传者