首页 > 试题广场 >

Music Problem

[编程题]Music Problem

热度指数：46 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

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≤10⁵), indicating there are n songs. 
 The second line contains n integers a₁,a₂…a_n (1≤a_i≤10⁹ ), the i^th integer a_i indicates the i^th song lasts a_i 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

算法知识视频讲解

ksdg恍然大明白

发表于 2020-04-15 21:03:22

抽屉原理的应用：一个由n个数组成的数列一定能找出若干个连续的数使它们之和能被n整除。所以 n >= 3600 时输出 YES证明：n个数记为a[1],a[2],...a[n].设置一个数组sum，其存储信息为sum[i] = a[1] + a[2] + ...a[i];情况一：存在一个k(1 展开全文

ThinkofBlank

发表于 2020-04-15 08:24:49

转化题意：给你n个数，问你是否能选出若干个数使得数字的和为3600的倍数（至少选一个）一开始，我打的01背包，dp[i]表示和模3600为i的方案数一开始，dp[0]为1，不难发现，若dp完后，dp[0]>1的话，就表示存在和为3600，不过，我们计算下复杂度：很明显，对于此题是过不展开全文

小小小小大白

发表于 2020-05-30 21:57:43

链接：https://ac.nowcoder.com/acm/contest/5203/B来源：牛客网题目描述Listening to the music is relax, but for obsessive(强迫症), it may be unbearable.HH is an obsessiv 展开全文

pphkaa

发表于 2020-04-14 22:28:25

这道题感觉是枚举加一些优化在里面。还是以例子为例吧。dp[i]=1表示某种组合加起来除以3600的余数为i，一开始的时候dp[]数组全为0；当某个组合是3600的倍数的时候，dp[0]=1,这便是说明可以组合形成3600的倍数，便可以输出YES，否则输出NO。假如：2000 1000 3000一开始展开全文

zylb

发表于 2020-04-17 00:18:59

完全背包相信大家都会做，但是Tn*3600的复杂度貌似不可过，所以我们用bitset优化背包即可。注意bitset范围要开2*3600，因为有"<<a[i]"。 #include <bits/stdc++.h> using namespace std; int T,n; i 展开全文

_LRJ_

发表于 2020-04-15 13:57:35

题意有t个样例，每个样例是给你n个数，问你能不能凑出来3600的倍数。那么这道题属于是背包问题，就是看每个数能不能取到。这里提供用bitset的一种做法（比较厉害），bitset上面每个数代表这个数能不能被取到，当然我们首先会对所有的a[i]取模3600，这样的话，每个a[i]都在0-3599范围里展开全文