| 题目名称 | 769. [USACO Open12] 平衡奶牛子集 |
|---|---|
| 输入输出 | subsets.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 21 |
| 题目来源 |
 Makazeu
于2012-04-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：18， 提交：43， 通过率：41.86% | ||||
 cstdio |
100 | 0.233 s | 1.77 MiB | C++ |
 Hellc |
100 | 0.460 s | 32.31 MiB | C++ |
 liuyiche |
100 | 0.533 s | 3.87 MiB | C++ |
 神利·代目 |
100 | 0.626 s | 77.64 MiB | C++ |
 ppfish |
100 | 0.646 s | 2.62 MiB | C++ |
|
Hellc |
100 | 0.972 s | 32.30 MiB | C++ |
|
Hellc |
100 | 1.109 s | 32.30 MiB | C++ |
|
Lfc_HeSn |
100 | 1.200 s | 17.26 MiB | C++ |
 cwystc |
100 | 1.258 s | 5.50 MiB | C++ |
 zzj |
100 | 1.424 s | 4.09 MiB | C++ |
| 本题关联比赛 | |||
| SYOI 专题 6：折半搜索 | |||
| 关于 平衡奶牛子集 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
meet in the middle 练习题。。。。。。
| ||||
|
和NOI2001 方程的解数 有点像
| ||||
【题目描述】
Farmer John有N头奶牛（2<=N<=20），其中第i头牛每天能生产M(i)个单位的牛奶（1<=M(i)<=100000000）。FJ希望简化每天挤奶的过程，因此他在谷仓里装了一台崭新的挤奶机。不幸的是，他发现这台机器非常敏感：只有当谷仓左右两侧的奶牛产奶数量完全相等时，它才能正常工作！
我们称所有奶牛的一个子集是“平衡的”，如果它能被分成产奶数量完全相等的两组。因为只有一个平衡的奶牛子集才能让挤奶机工作，FJ希望知道在他的N头奶牛中有多少个子集是平衡的。请你帮助他计算出这个数目。
【输入格式】
第1行：一个整数N。
第2到N+1行：第i+1行包含M(i)。
【输出格式】
第1行：平衡子集的数量。
【输入样例】
4
1
2
3
4
【输出样例】
3
【提示】
有4头奶牛，产奶数量为1,2,3,4.
有三个平衡子集：{1,2,3}，可以被分成{1,2}和{3}；{1,3,4}可以被分成{1,3}和{4}；{1,2,3,4}可以被分成{1,4}和{2,3}。
【来源】
USACO 2012 US Open, Gold Division, Balanced Cow Subsets