首页 > Music Problem

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范围里展开全文