题解 | #Music Problem#

Music Problem

https://ac.nowcoder.com/acm/contest/24213/1022

Music Problem

题意

给n个数字，判断这n个数字是否存在任意个数字之和是3600的倍数

解法一（背包）

分析

状态表示

f[i][j]表示在前i个中选，余数为j的情况，用1表示有这样的情况，0表示没有这样的情况

状态计算

首先进行初始化，f[i][a[i] % 3600] = 1，其次，如果f[i][j] = 1，那么f[i + 1][j]必定为1，也满足f[i + 1][(j + a[i + 1]) % 3600]为1

Note 这道题给的范围是1≤T≤60，1≤n≤105，那么这样做的时间复杂度就是O(T * n * 3600)，这样做肯定会超时，这时我们可以对他进行优化，但是实际上当n >= 3600时，一定可以输出"YES"，这是为什么呢？大家可以看一下一位大佬对此的解析： alt

当n >= 3600时，如果不存在sum[i] == 0，那么在1 ~ 3599这3599个余数中一定有重复的，假设sum[x] == sum[y](y > x)，那么sum[y] == sum[x] + sum[x + 1,y](表示从a[x + 1]到a[y]的前缀和),要满足这个条件必须满足sum[x + 1,y]对3600取余等于0，综上所述我们可以发现当n >= 3600时，一定可以输出YES

代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 7;
typedef long long ll;
int t,n,k,f[3610][3610],a[N];

int main()
{
    cin >> t;
    while(t --){
        cin >> n;
        //f[i][j]表示在前i个中选，余数为j的情况
        for(int i = 1;i <= n;i ++){
            cin >> a[i];
            a[i] %= 3600;
        }
        if(n >= 3600){
            cout << "YES\n";
            continue;
        }
        memset(f,0,sizeof(f));
        for(int i = 0;i < n;i ++){
            f[i + 1][a[i + 1] % 3600] = 1;
            for(int j = 0;j < 3600;j ++){
                if(f[i][j]){
                    f[i + 1][j] = 1;
                    f[i + 1][(j + a[i + 1]) % 3600] = 1;
                }
            }
        }
        if(f[n][0]) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

解法二（bitset优化）

分析

如果不了解bitset的用法大家可以先去看一下bitset的用法转载：https://blog.csdn.net/TopTom1234/article/details/108472174?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165810640916781432910483%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165810640916781432910483&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-108472174-null-null.142^v32^pc_rank_34,185^v2^control&utm_term=bitset&spm=1018.2226.3001.4187

bitset<7500>f;

其中f[i] = 1表示存在余数为i的情况我来给大家解释一下这段代码的含义：

f |= (f << x) | (f >> (mod - x));

f << x表示f左移x位，因为如果如果第i位是1，那么第i + x位就一定是1

例如如果余数是5，现在的f是10001（可以看到存在值为4的余数，因为f[4] = 1），x = 3，那么一定存在4 + 3 = 7的余数，左移x位变成10001000，右移mod- x位变成100，然后10001000和100相或变成10001100，这时存在值为2，3，7的余数，再与原本的f相或，就是最终所有的余数，如果f[0] = 1，就输出YES

代码

#include <bits/stdc++.h>

using namespace std;
const int mod = 3600;
typedef long long ll;
int t,n,x;

int main()
{
    cin >> t;
    while(t --){
        cin >> n;
        bitset<7500>f;
        for(int i = 1;i <= n;i ++){
            cin >> x;
            x %= mod;
            f |= (f << x) | (f >> (mod - x));
            f[x] = 1;
        }
        if(f[0] == 1) cout << "YES\n";
        else cout << "NO\n";
        
    }
    return 0;
}

alt