ACdream 1726 A Math game
Game Math
2023-09-11 14:15:28 时间
A Math game
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)
Problem Description
Recently, Losanto find an interesting Math game. The rule is simple: Tell you a number H, and you can choose some numbers from a set {a[1],a[2],......,a[n]}.If the sum of the number you choose is H, then you win. Losanto just want to know whether he can win the game.
Input
There are several cases.
In each case, there are two numbers in the first line n (the size of the set) and H. The second line has n numbers {a[1],a[2],......,a[n]}.0<n<=40, 0<=H<10^9, 0<=a[i]<10^9,All the numbers are integers.
In each case, there are two numbers in the first line n (the size of the set) and H. The second line has n numbers {a[1],a[2],......,a[n]}.0<n<=40, 0<=H<10^9, 0<=a[i]<10^9,All the numbers are integers.
Output
If Losanto could win the game, output "Yes" in a line. Else output "No" in a line.
Sample Input
10 87 2 3 4 5 7 9 10 11 12 13 10 38 2 3 4 5 7 9 10 11 12 13
Sample Output
No Yes
Source
第九届北京化工大学程序设计竞赛
Manager
解题:用vector 差点T成傻逼
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 50; 4 typedef long long LL; 5 LL sum,A[2000100],B[2000010]; 6 int x,y; 7 int main() { 8 int n; 9 while(~scanf("%d%lld",&n,&sum)) { 10 int a = (n>>1),b = n-a; 11 x = y = 0; 12 LL tmp; 13 bool flag = sum?false:true; 14 for(int i = 0; i < a; ++i) { 15 scanf("%lld",&tmp); 16 for(int j = x - 1; j >= 0 && !flag; --j) { 17 A[x++] = A[j] + tmp; 18 if(A[j] + tmp == sum) flag = true; 19 } 20 A[x++] = tmp; 21 if(tmp == sum) flag = true; 22 } 23 for(int i = 0; i < b; ++i) { 24 scanf("%lld",&tmp); 25 for(int j = y-1; j >= 0 && !flag; --j) { 26 B[y++] = (B[j] + tmp); 27 if(B[j] + tmp == sum) flag = true; 28 } 29 B[y++] = tmp; 30 if(tmp == sum) flag = true; 31 } 32 sort(B,B + y); 33 sort(A,A + x); 34 if(!flag && x && y && A[x-1] + B[y-1] >= sum && A[0] + B[0] <= sum){ 35 for(int i = 0; i < x && !flag; ++i){ 36 if(A[i] + B[y-1] < sum) continue; 37 flag = binary_search(B,B + y,sum - A[i]); 38 if(A[i] + B[0] > sum) break; 39 } 40 } 41 puts(flag?"Yes":"No"); 42 } 43 return 0; 44 }
相关文章
- zoj 3593 One Person Game
- Unity for Windows: III–Publishing your unity game to Windows Phone Store
- 2014 网选 5011 Game(Nim游戏,数学题)
- [Javascript] Broadcaster + Operator + Listener pattern -- 27. combine multi broadcaster and compose operator to implement game logic
- 【Codeforces 492D】Vanya and Computer Game
- 【codeforces 777B】Game of Credit Cards
- 【hdu 1517】A Multiplication Game
- 【CS Round #48 (Div. 2 only)】Game of Chance
- 【 Codeforces Round #430 (Div. 2) A 】 Kirill And The Game
- [LeetCode] 45. Jump game II ☆☆☆☆☆(跳跃游戏 2)
- ZOJ 3529 A Game Between Alice and Bob(博弈论-sg函数)
- LeetCode——Jump Game