Music Problem

Music Problem

https://ac.nowcoder.com/acm/contest/5203/B

@[TOC]
传送

时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld

题目描述

Listening to the music is relax, but for obsessive(强迫症), it may be
unbearable. HH is an obsessive, he only start to listen to music at
12:00:00, and he will never stop unless the song he is listening ends
at integral points (both minute and second are 0 ), that is, he can
stop listen at 13:00:00 or 14:00:00,but he can't stop at 13:01:03 or
13:01:00, since 13:01:03 and 13:01:00 are not an integer hour time.
Now give you the length of some songs, tell HH whether it's possible
to choose some songs so he can stop listen at an integral point, or
tell him it's impossible. Every song can be chosen at most once.

输入描述:

The first line contains an positive integer T(1≤T≤60), represents
there are T test cases. For each test case: The first line
contains an integer n(1≤n≤105), indicating there are n songs. The
second line contains n integers a1,a2…an (1≤ai≤109 ), the ith integer
ai indicates the ith song lasts ai seconds.

输出描述:

For each test case, output one line "YES" (without quotes) if HH is
possible to stop listen at an integral point, and "NO" (without
quotes) otherwise.

示例1
输入

3
3
2000 1000 3000
3
2000 3000 1600
2
5400 1800

输出

NO
YES
YES

说明
In the first example it's impossible to stop at an integral point.
In the second example if we choose the first and the third songs, they cost 3600 seconds in total, so HH can stop at 13:00:00
In the third example if we choose the first and the second songs, they cost 7200 seconds in total, so HH can stop at 14:00:00

题意:

给你n个数,这些数自由组合能不能凑出3600的倍数

题解:

我一开始想到的是前缀和,后来感觉dp最直接
dp[x]=1表示能组成x这个数
dp = 0表示组不了
cnt是中间数组,暂时存储本轮的数值
因为求能不能组成3600,可以用mod,3600的倍数mod后都是0,直接求dp[0]是否等于1
每读取一个a,就把a与之前所求的值进行相加存在cnt里,然后再给dp[],cnt就是工具人

#include<bits/stdc++.h>
#define mem(a) memset(a,0,sizeof(a))

using namespace std;
const int maxn=1e5+3;
bool dp[maxn],cnt[maxn];
const int mod=3600;
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
            mem(dp);
        mem(cnt);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int a;
            cin>>a;
            a%=3600;
            if(!dp[0])
            {
                for(int j=0;j<3600;j++)
                {
                    if(dp[j]>0||j==0)
                    {
                        cnt[(a+j)%3600]=1;
                    }

                }
                for(int j=0;j<3600;j++)
                {
                    if(cnt[j])dp[j]=1;
                    if(cnt[j]==1)cnt[j]=0;
                }
            //    mem(cnt);
            }
        }
        if(!dp[0])cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

有个很玄学的地方我把读入n放在两个mem之前,数据就过了一半,放后面就ac了,不知道为什么
在这里插入图片描述看来卡时间卡的太紧了(笑哭)

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:10
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
MinJerous:虽然我一直说 计算机不怎么卡学历 但是至少得一本
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务