[P13885]Music Problem

这道题让我明白了，取模运算效率低下

具体思路其他题解已经讲过了，这里不再赘述

这是一段超时的代码

//https://ac.nowcoder.com/acm/problem/13885
#include<cstdio>
#include<algorithm>
#include<cstring>

int a[100001];
bool dp[2][3600+10];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        std::fill_n(dp[0],2*3610,false);
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
        if(n>=3600){printf("YES\n");continue;}
        dp[1][a[1]%3600]=true;
        int filp;
        for(int i=2;i<=n;++i){
            filp=i&1;
            dp[filp][a[i]%3600]=true;
            for(int j=0;j<3600;++j){
                dp[filp][j]|=dp[filp^1][((j-a[i])%3600+3600)%3600]|dp[filp^1][j];
            }
            //if(dp[filp][0])break;
        }
        printf("%s\n",dp[filp][0]?"YES":"NO");
    }
    return 0;
}

简单修改后（大大减少取模运算的次数）即通过

//https://ac.nowcoder.com/acm/problem/13885
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>

int read(){//快读，在本题中不是影响运行时间的关键
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int a[100001];
bool dp[2][3600+10];//数组大小对时间有影响，但很多题解没有优化也都过了
int main(){
    int T=read();
    while(T--){
        int n=read();
        for(int i=1;i<=n;++i)a[i]=read()%3600;//关键在这里，原来超时的程序中取模运算在dp中进行
        if(n>=3600){printf("YES\n");continue;}
        std::fill_n(dp[0],2*3610,false);//fill_n和memset的耗时差不多，不是本题耗时的关键
        dp[1][a[1]]=true;
        int filp;
        for(int i=2;i<=n;++i){
            filp=i&1;
            dp[filp][a[i]]=true;
            for(int j=0;j<3600;++j){
                if(dp[filp^1][j]||dp[filp^1][(j-a[i]+3600)%3600])
                    dp[filp][j]=true;
            }
        }
        printf("%s\n",dp[filp][0]?"YES":"NO");
    }
    return 0;
}

所以特意提醒大家，取模运算效率低

取模运算效率低！

取模运算效率低！！