题目描述
忘川沧月是一名 OIer，他的家族有 (n) 个人。每年，当这 (n) 个人过生日的时候，忘川沧月都要去给他们买蜡烛。
不过最近忘川沧月却很纠结……因为他爷爷要过 (68) 岁生日了，他认为买 (68) 根蜡烛简直就是一件**的事情。。。
这天，忘川沧月路过了一个蜡烛商店……
蜡烛商店中有 (10) 种蜡烛，形状分别是 (0)~(9) 这 (10) 个数字，不过对于每种蜡烛，商店的存货量仅有一根。另外，忘川沧月已经有了一个 (+) 形状的蜡烛。
忘川沧月想购买一些蜡烛，使得他的家族中所有人的年龄都可以用他购买的数字和 (+) 表示出来。
例如 (12) 就有 (11) 种表示方法：(12)、(0+12)、(2+10)、(3+9)、(4+8)、(5+7)、(7+5)、(8+4)、(9+3)、(10+2)、(12+0)。注意 (6+6)、(1+11)、(11+1) 是不行的，因为每种蜡烛仅有一根。
但是由于这种蜡烛很贵，忘川沧月想购买尽量少的蜡烛来达到他的目的，你能帮帮他吗？
输入格式
每个测试点包含多组测试数据。
本题共有 (5) 个测试点，每个测试点包含不多于 (10000) 组数据。
每组数据包含 (n+1) 个用空格隔开的整数，其中第一个整数 (n) 是家族成员的数量，接下来 (n) 个整数是他们的年龄。
(n=0) 表示输入的结束。
输出格式
设需要购买的蜡烛数字 从大到小 排列构成了一个整数 (T)，如果在购买最少数量的蜡烛的前提下，答案不唯一，请输出 (T) 最大的答案。
对于每组数据，按照样例输出的格式，先输出 Case X: （(X) 代表测试数据编号，从 (1) 开始，冒号后面还有一个空格），再输出 (T)。
数据范围
测试时间限制 (1000\, extrm{ms})，空间限制 (1\, extrm{GiB})。
- 对于 (40\%) 的数据，数据组数不超过 (100)；
- 对于另外 (20\%) 的数据，数据组数不超过 (1000)；
- 对于 (100\%) 的数据，测试数据组数不超过 (10000)，(1le nle 10)，每个人的年龄是不大于 (100) 的正整数。
分析
众所周知。
所以我们要敢于尝试暴力算法！
对于这一题，不要想太多。看到那个多组数据了没有？暴力处理，再快速处理询问就完了，奥利给！
好了装逼结束。
这一题，我们要善于挖掘深藏在计算机内的氮磷钾暴力潜能！
注意到多组数据，所以优先预处理。
事实上，对于每一种蜡烛的卖法，都可以预处理出来能买哪些蜡烛。再处理询问就简单多了，只要从大到小枚举所有能满足的集合，选择最优即可。
预处理复杂度为 (Theta(2^{10} imes max age)) 单次询问复杂度是 (Theta(2^{10} imes max age))。
虽然复杂度有一点悬，但是我们可以用 bitset 大法优化。然后就能跑过去了。
Code
真是一道好的暴力练手题啊。
（虽然代码挺难敲的 (color{red}{Qomega Q})）
#include <cstdio>
#include <bitset>
using namespace std;
typedef unsigned long long ull;
const int max_n = 10, max_set = (1 << max_n), max_age = 100;
struct resk
{
bitset<max_age+1> bt;
int bit_cnt;
} can_make[max_set];
int num[max_age+1], first_d[max_age+1], second_d[max_age+1];
bitset<max_age+1> cur;
int main()
{
int cas, tmp, len, plen, ans, min_size, cas_id;
for (int st = 1; st < max_set; st++)
{
can_make[st].bit_cnt = can_make[st>>1].bit_cnt + (st & 1);
len = 0;
for (int i = 0; i < max_n; i++)
if ((st >> i) & 1)
{
num[len] = i, first_d[len] = 0, second_d[len] = i;
can_make[st].bt[i] = true;
len++;
}
plen = len;
for (int i = 0; i < plen; i++)
for (int j = 0; j < plen; j++)
if (num[i] && i != j)
{
num[len] = num[i] * 10 + num[j], first_d[len] = num[i], second_d[len] = num[j];
can_make[st].bt[num[i]*10+num[j]] = true;
len++;
}
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++)
{
if (num[i] + num[j] <= 100 && (!first_d[i] || !first_d[j] || first_d[i] != first_d[j])
&& (!first_d[i] || first_d[i] != second_d[j]) && (!first_d[j] || first_d[j] != second_d[i])
&& second_d[i] != second_d[j])
can_make[st].bt[num[i]+num[j]] = true;
}
}
cas_id = 1;
while (scanf("%d", &cas) != EOF && cas)
{
cur.reset();
for (int i = 0; i < cas; i++)
{
scanf("%d", &tmp);
cur[tmp] = true;
}
min_size = 666;
for (int i = max_set - 1; i >= 0; i--)
if (can_make[i].bit_cnt < min_size && (can_make[i].bt & cur) == cur)
min_size = can_make[i].bit_cnt, ans = i;
printf("Case %d: ", cas_id);
for (int i = max_n - 1; i >= 0; i--)
if ((ans >> i) & 1)
putchar(i + '0');
putchar('
');
cas_id++;
}
return 0;
}
后记
这道题真的是一道极其暴力的题。
所以，暴力在关键时刻，不失为一种好的算法。