SCNU 2015ACM新生赛初赛【1007. ZLM的扑克牌】解题报告

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接详见SCNU 2015新生网络赛 1007. ZLM的扑克牌。

其实我在想这题的时候，还想过要不要设置求最小的排列，并且对于回文数字的话，可以把扑克牌折起来（从而这个数字会变小）；甚至要不要设置扑克牌旋转、翻转之后，读出的数字要改变。但这样的话好像我也不会做辣！= =|||于是这道题目最后就变成了一个简单贪心题。题目大意大概就是这样的：给出一个包含$n$个数字的多重集，要求使用集合中的元素拼凑出一个最大的数字，问最大所能拼凑出的数字是多少？

贪心算法需要对贪心策略进行证明。比如大部分同学可能会想到的是，做一个简单的排序，把数字大的排在前面，数字小的排在后面，然后按顺序输出就好啦！但很可惜这是错的！因为对于$12345$，它比$67$要大，但$67$应该排在它的前面，因为$1234567$是小于$6712345$的。

我们考虑两个数字串$A$和$B$，组合得到一个新的数字串$AB$或$BA$，定义关系$\succ$，当且仅当$AB > BA$严格成立时，$A \succ B$成立。对于集合中另一个数字串$C$且$A \succ B$，如果$C \succ A$，则一定满足$C \succ B$；如果$B \succ C$，则一定满足$A \succ C$；否则应当再进行一次比较以确定$A$、$B$、$C$三者的序关系。对于全集$S_{N}$，至多进行有限次即$O(N^{2})$的比较可以使整个集合满足全序关系，于是基于这种比较的排序方法可行。

接下来考虑下代码，因为输入输出量比较大，而时限只有1s，所以C++的输入输出方法被卡得死死的，只要使用了就一定会TLE。另外STL的string类也会导致TLE，这个我原先倒是没想过要卡的，但至少给大家一个警醒，不要滥用STL，STL大概为了做到泛型编程和通用性，通常会损失一些性能，因此在某些时候远不及于自己写的代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h> namespace cmp {
char tx[], ty[];
int compare(const void*a, const void*b) {
strcat(strcpy(tx, (char*)a), (char*)b);
strcat(strcpy(ty, (char*)b), (char*)a);
return strcmp(ty, tx);
}
} char x[][];
int main() {
int cse, T, N, i;
scanf("%d", &T);
for(cse=; cse<=T; cse++) {
printf("Case #%d:\n", cse);
scanf("%d", &N);
for(i=; i<N; i++)
scanf("%s", x[i]);
qsort(x, N, , cmp::compare);
for(i=; i<N; i++)
printf(x[i]);
puts("");
}
return ;
}

上面的代码用了C++的命名空间，你也可以选择用函数内静态变量，或直接暴露成全局变量。其中利弊请自行体会= =||

另外注意一下我在qsort的compare中写的是strcmp(ba,ab)，其中原因请参看strcmp函数返回值说明以及qsort函数参数说明，并注意一下$a$和$b$之间的关系。

附：数据生成程序如下：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h> int main() {
freopen("in.txt", "w+", stdout);
int T = ;
printf("%d\n", T);
srand(time(NULL));
for(int a=; a<=; a++)
for(int b=; b<a*; b++) {
int N = rand()%((int)pow(, a)-)+;
printf("%d\n", N);
for(int i=; i<N; i++) {
int X = rand()%((int)pow(, -a)-)++(int)pow(rand()%, -a);
printf("%d ", X);
}
puts("");
}
return ;
}