P5198: 教主的难题-训练套题T14T4
传统题
2.000s
时间限制
512MB
内存限制
4 提交
4 解决
【题目描述】
教主的难题(problem.pas/c/cpp)
【问题描述】
一个数x可以按以下规则生成数字：
1、将任意两位交换，若交换的数字为a和b，生成的代价为
((a and b)+(a xor b))*2
例如134可以生成431，因为431可以从134的个位（4）与百位（1）交换后得到，代价为((1
and 4)+(1 xor 4))*2=10。
2、将其中一位数删除，但是删除的数要满足大等于它左边的数，且小等于它右边的数，并且定义最高位左边的数为个位，个位右边的数为最高位。若删除的数字为a，它左边的数为b，它右边的数为c，则生成的代价为a+(b and c)+(b xor c)。
例如212，可以删除个位的数得到21，但是因为2>1，所以1是不能被删除的。特别地，若x为两位数，它能删除当且仅当x的两位数相同，若x为一位数，它是不能被删除的。
3、在两位数字之间，也可以是数字的前面或后面加入一位数，同样地，加入的数要满足大等于它左边的数，且小等于它右边的数，并且定义最高位左边的数为个位，个位右边的数为最高位。若加入的数字为a，它左边的数为b，它右边的数为c，则生成的代价为a+(b and c)+(b xor c)。
例如241，它可以在2与4之间加入一个3，生成2341，也可以在数的末尾加入一个1或者2，当然还有其它可以生成的数，但是不能在4和1之间加入数字。
你的任务是，S一开始为n个不同的给定数组成的集合，每次可以从S中取出一个数生成一个满足生成规则的数加入S中，并且取出的数仍然存在于S中。生成的数的位数不能大于S初始集合最大的数的位数。问在S元素最多的情况下，总代价最小是多少。
【输入格式】
输入的第1行为一个正整数n，为集合S初始元素个数。
第2行包含n个正整数a1,a2, ...,
an，数之间空格隔开，为S中初始元素。
【输出格式】
输出包括一个正整数，为最小代价。
【样例输入】
2
111 22
【样例输出】
12
【样例说明】
111删除1得到11，代价为2，11删除1得到1，代价为2，同样22删除和加入一个2得到2，222，代价均为4，总代价2+2+4+4=12。111无法生成1111因为111为一个3位数，而1111为一个4位数。
利用交换/添加规则无法让集合元素更多，所以最小代价为12。
【数据规模】
对于20%的数据，有ai＜100；
对于40%的数据，有ai＜1000；
对于50%的数据，有n=1；
对于60%的数据，有ai＜10000；
对于100%的数据，有ai＜100000，n≤5，保证的任何一位不包含0。
【提示】
教主的难题(problem) BFS，MST
对于一开始只有一个数字的情况，如果A能生成B那么A向B连一条边，由于所有生成规则都是可逆的，且代价相同，所以连出的是无向边。BFS出所有能生成的数字，并构图，最后即变成了最小生成树的模型，一开始的数为最小生成树的根，生成树上的边为生成数字的过程。由于图比较稀疏，所以用Kruskal就可以。
对于多个数字的情况，只要一开始在这些数字之间连条权为0的边即可。范围较小，并且图比较一般，不一定要加什么优化。