形式化题目

给定 6 个非负整数 $a_1, \dots, a_6$，表示价值分别为 $1 \dots 6$ 的大理石各有 $a_v$ 块（总块数 $\leqslant 20000$）。问能否把这些大理石分成两部分，使两部分价值总和相等。

形式化地，记总价值 $total = \sum_{v=1}^{6} (v+1)\, a_v$，等分可行当且仅当存在整数 $x_v \in [0, a_v]$，使得

这是标准的多重背包可行性问题：物品价值为 $v+1$、数量上限为 $a_v$，问能否恰好装满容量 $total/2$。

以样例 4 7 4 5 9 1 为例：$total = 4\cdot1 + 7\cdot2 + 4\cdot3 + 5\cdot4 + 9\cdot5 + 1\cdot6 = 101$ 是奇数，直接输出 Can't；而 9 8 1 7 2 4 的 $total = 9 + 16 + 3 + 28 + 10 + 24 = 90$，可以取一半 $45$（例如 $4$ 块价值 $6$、$2$ 块价值 $5$、$2$ 块价值 $4$、$3$ 块价值 $1$，$24+10+8+3=45$），输出 Can。

正解

思路

一句话本质：把「能凑出哪些价值」的布尔集合看成一个二进制位集，每种大理石逐块做一次 reach |= reach << w 的位集转移，最后查询第 $total/2$ 位。

朴素做法与瓶颈。 最直接的想法是枚举每块大理石分给哪一边，方案数是 $2^{\sum a_v}$（$\sum a_v$ 可达 20000），完全不可行。退一步用 DP：设 $dp[s]$ 表示「能否恰好凑出价值 $s$」，对每种大理石逐块拆成 0-1 背包——每加入一块价值 $w$ 的大理石，就有 $dp[s] \mathrel{|}= dp[s-w]$（$s$ 从大到小扫）。转移总量是 $\sum a_v \leqslant 20000$ 次，每次要扫整个 $[0, total/2]$，共约 $20000 \times 60000 = 1.2 \times 10^9$ 次布尔操作，朴素循环太慢，C++ 里需要 bitset。

第一步剪枝：奇偶性。 只有 $total$ 为偶数才可能等分。特别地，当 6 个 $a_v$ 全为奇数时，$total$ 是 6 个奇数之和，必为奇数，可以直接输出 Can't——这就是《算法竞赛进阶指南》里著名的奇偶剪枝，它只是奇偶判断的一条快捷路径，不改变算法主体。

第二步：把 dp 数组换成位集。 注意 $dp$ 本质上是一个 0/1 集合 $S = \{ s : dp[s] = 1 \}$。加入一块价值 $w$ 的大理石后，每个旧可达和 $s$ 变成「$s$ 与 $s+w$ 都可达」，即新集合

用整数位集表示恰好是 reach |= reach << w（第 $s$ 位为 1 表示价值 $s$ 可达）。转移从「扫一遍数组」塌缩成一条位运算语句，一次字长 64 位的与/或/移位顶掉 64 次布尔操作。由于等分只需要 $\leqslant total/2$ 的可达信息、且可达集合单调增大（大理石只会越加越多），每步用 (1 << (half+1)) - 1 截掉高位即可。

Python 的大整数天然就是任意长位集，reach 始终不超过 $total/2+1 \leqslant 100001$ 位，位集语义零成本落地：

flowchart LR
    A[读入 a1..a6] --> B{6 个数量全为奇数?}
    B -- 是 --> X[输出 Can't]
    B -- 否 --> C{total 为奇数?}
    C -- 是 --> X
    C -- 否 --> D[reach = 1, 只有序 0 可达]
    D --> E[逐块: reach |= reach 左移 w<br/>再截断到 half+1 位]
    E --> F{第 half 位为 1?}
    F -- 是 --> G[输出 Can]
    F -- 否 --> X

小规模演算：以 0 2 1 0 0 0（2 块价值 2、1 块价值 3，$total = 7$ 为奇数，剪枝直接判负）换成 0 2 2 0 0 0（$total=8$，$half=4$）演示位集如何生长，行内十六进制是 reach 的二进制（高位在左、第 $s$ 位对应价值 $s$）：

最后查询第 $half = 4$ 位为 1，输出 Can（一半取两块价值 2）。观察重点：每一行都恰好是 $S \mathrel{|}= S + w$ 的集合效果——第 2 行里旧的 $\{0,2\}$ 平移成 $\{2,4\}$，并入后得到 $\{0,2,4\}$，这正是 0-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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 平分大理石：多重背包可行性，位图整体左移或
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

int cnt[6];                        // cnt[v]：价值 v+1 的宝石块数
vector<unsigned long long> reach;  // reach 的第 s 位 = 1 表示价值 s 可达

// 往可达集合里再加一块价值 bits 的宝石（整体左移 bits 位）
void add_piece(int bits, int limit) {
    int words = limit / 64 + 1;
    int ws = bits / 64, bs = bits % 64;
    for (int i = words - 1; i >= 0; i--) {
        unsigned long long x = reach[i];
        if (!x) {
            continue;
        }
        int lo = i + ws;
        if (lo < words) {
            reach[lo] |= x << bs;
        }
        if (bs && lo + 1 < words) {
            reach[lo + 1] |= x >> (64 - bs);
        }
    }
}

int main() {
    int printed = 0;
    while (true) {
        bool eof = false;
        for (int i = 0; i < 6; i++) {
            if (scanf("%d", &cnt[i]) != 1) {
                eof = true;
                break;
            }
        }
        if (eof) {
            break;
        }
        bool all_zero = true;
        for (int i = 0; i < 6; i++) {
            if (cnt[i]) {
                all_zero = false;
            }
        }
        if (all_zero) {
            break; // 全 0 行是结束标志
        }

        ll total = 0;
        for (int v = 0; v < 6; v++) {
            total += (ll)(v + 1) * cnt[v];
        }
        bool can = false;
        if (total % 2 == 0) { // 总价值为奇数，无法平分
            int half = (int)(total / 2);
            reach.assign(half / 64 + 1, 0);
            reach[0] = 1;
            for (int v = 0; v < 6; v++) {
                for (int t = 0; t < cnt[v]; t++) {
                    add_piece(v + 1, half);
                }
            }
            can = (reach[half >> 6] >> (half & 63)) & 1;
        }
        printf("%s\n", can ? "Can" : "Can't");
        printed++;
    }
    if (printed == 0) {
        printf("\n"); // 复刻 py 的 print('\n'.join([])) 行为
    }
    return 0;
}

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
28
29
30
31
32
33
34
35
36
37
38
39#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

ALL_ODD = (1 << 6) - 1  # 6 个价值全部为奇数时的位掩码：第 v 位 = 1 表示 a[v] 是奇数


def half_reachable(a: list[int]) -> bool:
    """价值总和的一半能否由各价值取 0..a[v] 个凑出（多重背包可行性）。"""
    half, total = divmod(sum((v + 1) * cnt for v, cnt in enumerate(a)), 2)
    if total:  # 总价值为奇数，无法平分
        return False

    reach = 1  # reach 的第 s 位 = 1：恰好凑出价值 s；初始只有 0 可达
    for v, cnt in enumerate(a):
        for _ in range(cnt):  # 朴素多重背包：逐个加入该价值的每一块
            reach |= reach << v + 1  # 每块贡献价值 v+1，更新可达和集合
            reach &= (1 << half + 1) - 1  # 超过 half 的部分对答案无用，截断
    return reach >> half & 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    while any(a := [next(data) for _ in range(6)]):  # 全 0 行是结束标志
        odd_mask = sum((cnt & 1) << v for v, cnt in enumerate(a))  # a[v] 为奇数 → 第 v 位
        can = half_reachable(a) if odd_mask != ALL_ODD else False  # 全奇数时总和为奇数
        out.append("Can" if can else "Can't")

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

实现要点：

• odd_mask = sum((cnt & 1) << v ...) 把 6 个数量的奇偶拼成 6 位掩码，odd_mask == ALL_ODD 一次比较就完成「全奇 → 总和为奇」的快捷剪枝；
• half_reachable 用 divmod 同时得到 half 和 total 的奇偶余数，奇数时连位集都不建；
• 内层 reach |= reach << v + 1（注意 Python 里 << 优先级低于 +，等价于 reach << (v+1)）与紧随的截断是一条转移语句的两半。

复杂度

设 $total \leqslant 6 \times 20000 = 120000$，$\sum a_v \leqslant 20000$：

• 时间：每组数据 $O\!\left(\sum a_v \cdot \dfrac{total}{64}\right)$ 次字操作（位集多重背包），约 $20000 \times 1875 \approx 3.75 \times 10^7$，与 C++ bitset 解法同阶；
• 空间：$O(total)$ 位，位集不超过 $100001$ 位（约 13 KB）。

多组数据规模都很小（每组 6 个数），读入用一次性 split 分词即可。

总结

• 等分问题 = 多重背包可行性：奇偶剪枝先排除 $total$ 为奇数（6 个数量全奇是它的快捷特判）。
• 可行性 DP 的状态是 0/1 集合，天然对应位集：逐块 reach |= reach << w 一条语句完成一次转移，把朴素 $O(\sum a_v \cdot total)$ 的布尔操作除以字长 64。
• Python 大整数即任意长位集，让 bitset 优化不写任何建表代码；思想可直接平移回 C++ 的 bitset<60001>。

图示解析

下图把「读入 → 剪枝 → 位集 DP → 查询」的完整决策路线放在一起，Can't 的三条出口（全奇、总价值奇数、半价值不可达）一目了然：

flowchart TD
    start([读入一组 a1..a6]) --> zero{"a 全为 0?"}
    zero -- 是 --> stop([结束])
    zero -- 否 --> alloodd{"6 个数量全为奇数?"}
    alloodd -- 是 --> cant1["Can't<br/>（6 个奇数之和必为奇）"]
    alloodd -- 否 --> oddeven{"total 是奇数?"}
    oddeven -- 是 --> cant2["Can't"]
    oddeven -- 否 --> dp["reach 从 000...001 出发<br/>逐块 reach |= reach << w 并截断"]
    dp --> check{"第 half 位为 1?"}
    check -- 是 --> can["Can"]
    check -- 否 --> cant3["Can't"]

对照正文的三条规则：前两条出口是纯奇偶判断、不碰 DP；只有走到 DP 那一格才发生 $O(\sum a_v \cdot total / 64)$ 的位集转移。这也解释了为什么剪枝虽然只是快捷路径，却在「全奇数」这类数据上把整组数据的开销降到近零。