沂水网站开发,第三方平台推广,单页产品销售网站如何做推广,谷歌做网站文章目录题目描述题意#xff1a;题解#xff1a;传送时间限制#xff1a;C/C 2秒#xff0c;其他语言4秒 空间限制#xff1a;C/C 131072K#xff0c;其他语言262144K 64bit IO Format: %lld 题目描述 Listening to the music is relax, but for obsessive(强迫症), it …
文章目录题目描述题意题解传送时间限制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:0100 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可以用mod3600的倍数mod后都是0直接求dp[0]是否等于1 每读取一个a就把a与之前所求的值进行相加存在cnt里然后再给dp[]cnt就是工具人
#includebits/stdc.h
#define mem(a) memset(a,0,sizeof(a))using namespace std;
const int maxn1e53;
bool dp[maxn],cnt[maxn];
const int mod3600;
int main()
{int t,n;scanf(%d,t);while(t--){mem(dp);mem(cnt);scanf(%d,n);for(int i1;in;i){int a;cina;a%3600;if(!dp[0]){for(int j0;j3600;j){if(dp[j]0||j0){cnt[(aj)%3600]1;}}for(int j0;j3600;j){if(cnt[j])dp[j]1;if(cnt[j]1)cnt[j]0;}// mem(cnt);}}if(!dp[0])coutNOendl;else coutYESendl;}return 0;
}有个很玄学的地方我把读入n放在两个mem之前数据就过了一半放后面就ac了不知道为什么 看来卡时间卡的太紧了笑哭
