2 条题解

  • 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 则证明存在一种方案 否则不存在
    }
    

    信息

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