解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 A - Attack and Split

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有一隻史萊姆可以進行分裂和合併，大小為 x 的史萊姆可以分裂成兩個小史萊姆 y 和 z，滿足 x = y + z。當兩個史萊姆大小 p, q 合併時，新的史萊姆為 r = p xor q。請問是否存在數次的分裂和合併，所有史萊姆都消失！

Sample Input

1
2
3
4
3
1 1
2 9 17
3 12 15 19

Sample Output

1
2
3
No
Yes
Yes

Solution

亂來的奇偶和判定！以下是不負責任的說法！對於一種合法解 {a1, a2}，則 {a1-1, 1, a2-1, 1} 也一定會合法，不斷地拆分下去，所有史萊姆的大小都是 1，也發現到總和一定是偶數。因此只要判斷總和的奇偶數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int n;
        long long x, sum = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            sum += x;
        }
        puts(sum%2 ? "No" : "Yes");
    }
    return 0;
}
/*
 3
 1 1
 2 9 17
 3 12 15 19
*/