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 ;

 }

Click To

——by BlackStorm, from here: http://www.cnblogs.com/BlackStorm/p/4988586.html .

SUCC

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