原文链接：

http://www.wutianqi.com/?p=1181

大家在学习C++编程时，一般在输入方面都是使用的cin.
而cin是使用空白（空格，制表符和换行符）来定字符串的界的。
这就导致了对于带有空格的字符串，比如”I Love www.CppLeyuan.com”
只能读入”I”，后面的都无法读入。
这时怎么办？

 一.对于字符数组：
方法一：getline()
读入整行数据，它使用回车键输入的换行符来确定输入结尾。
调用方法: cin.getline(str, len);
第一个参数str是用来存储输入行的数组名称，第二个参数len是要读取的字符数。

方法二：get()

调用方法：cin.get(str, len);

那么两者有何区别？
两者都读取一行输入，直至换行符。
然后，getline将丢弃换行符，而get()将换行符保留在输入序列里。
所以，再使用cin.get()输入多行数据时，中间可以使用get()消除换行符。

因为get(str, len)和get()都是cin的类成员，所以可以合并起来写：

(欢迎大家去我论坛学习:C++奋斗乐园：http://www.cppleyuan.com/)

二.对于string类
方法一:getline(cin, str)

这说明这里的getline不是类方法。

PS:以后如果对输入方面还有更多了解，会继续补充，希望大家支持，多多交流。

原创链接：http://www.wutianqi.com/?p=1162

上次论坛里一个会员问的。
感觉这个程序作为DFS入门是很理想的，大家应该都能看懂。
贴出来和大家分享：

 

 1#include<iostream>
 2using namespace std;
 3int a[100] = {0};
 4int n;
 5int count=0; 
 6void dfs(int k)
 7{
 8   if(k >= n)
 9   {
10      for(int i = 0;i < n;i++)
11      {
12         cout<<a[i]<<" ";
13      }
14      count++;
15      cout<<endl;
16   }     
17   else
18   {
19      for(int i = 1;i <= n;i++)
20      {
21         a[k] = i; 
22         dfs(k + 1);        
23      }       
24   }    
25}
26int main()
27{
28   while(cin>>n)
29   {
30      count=0;
31      int k = 0;
32      dfs(k);  
33      cout<<count<<endl;             
34   }    
35}

 

---

http://www.wutianqi.com/?p=1157

---

集合A的幂集是由集合A的所有子集所组成的的集合。

 

如：A={1，2，3}，则A的幂集P（A）={{1，2，3}，{1，2}，{1，3}，{1}，{2，3}，{2}，{3}，{ }}。

求一个集合的幂集就是求一个集合的所有的子集，方法有穷举法，分治法，回溯等，这里主要介绍一下回溯法。

回溯法是设计递归过程的一种重要的方法，它的求解过实质上是一个先序遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历过程中的。

幂集中的每个元素是一个集合，它或是空集，或含集合A中一个元素，或含集合A中两个元素…… 或等于集合A。反之，从集合A 的每个元素来看，它只有两种状态：它或属幂集的无素集，或不属幂集的元素集。则求幂集p(A)的元素的过程可看成是依次对集合A中元素进行“取”或“舍”的过程，并且可以用一棵二叉树来表示过程中幂集元素的状态变化过程，树中的根结点表示幂集元素的初始状态（空集）；叶子结点表示它的终结状态，而第i层的分支结点，则表示已对集合A中前i-1个元素进行了取舍处理的当前状态（左分支表示取，右分支表示舍 ）。因此求幂集元素的过程即为先序遍历这棵状态树的过程。

具体算法如下：

C/C++描述：

 1#include <iostream>
 2#include <cstring>
 3#include <ctype.h>
 4#include <stdlib.h>
 5#include <string>
 6using namespace std;
 7 
 8char a[100];
 9char b[100];
10 
11void GetPowerSet(int i, char a[])
12{
13    char x;
14    int k;
15    int len = strlen(a);
16    if(i >= len)
17    {
18        if(b[0])
19            cout << b <<  endl;
20        else
21            cout << "XX" << endl;  // 表示空集
22    }
23    else
24    {
25        x = a[i];
26        k = strlen(b);
27        b[k] = x;
28        GetPowerSet(i+1, a);
29        b[k] = 0;
30        GetPowerSet(i+1, a);
31    }
32}
33 
34 
35int main()
36{
37    while(scanf("%s", a) != EOF)
38    {
39        printf("%s的幂集是:\n", a);
40        printf("------------\n");
41        GetPowerSet(0, a);
42        printf("------------\n");
43    }
44}

原文链接：
http://www.wutianqi.com/?p=1028

          回忆起以前我看这本书，联系自己学编程这一年多，感触颇多。记得这本书刚出来时，我就在中关村图书大厦买了一本。至今已经快一年了。故事情节依稀记得一点。

          里面讲到了BOSS 绝的奋斗史，读大学时和寝室一伙人到处折腾，给别人装机子，去小公司找工作，以及后来的作为招聘人员去自己学校招员工，私下接外挂破解，和女友的坎坷经历直到最后的分手。

          绝影的人生并不好走，虽然大学还未毕业就找到工作了，但是可以看出他的艰辛，经常熬夜赶项目；节假日不能陪家人，结果女友也要求分手了。

          我不知道该说什么好，别人都说嫁人要嫁程序员，程序员只关心电脑，不会在外面过那种花花绿绿的生活，这是褒义，还是贬义？也许只有说这话的人心里才清楚。

          我大学是读自动化的，连我都不知道我为何要报自动化，我只知道，高考没考到自己预想的分数，考了一个半吊子的分数：568分，而一本分数线是548.就这么高不高，低不低的。连我老爸当年读的中南财经政法大学都读不了，于是我也懒得管了，直接让我父母报，结果第一志愿是北京化工大学的机械工程及其自动化，第二志愿是北京化工大学的自动化。最后第一志愿没录取，于是我到了北化的自动化系。虽然读了两年大学，我还不知道我这个专业到底是干啥的，只知道这个专业是一个万金油，啥都行~~~

           大一刚进校，因为高考完在家天天玩网游，开学了还没回过神来，别人都忙于互相认识，一起游览北京的一些旅游景点，而我却忙于在网吧与寝室两地颠簸。那时刚开学，班级和学校有许多的活动，我一个都没参加，记得开学就有学校和院的各个部门招人手，我那时没认识到德育分的重要性，也没有刻意去培养自己的结交能力(不过我的朋友还是非常多的~~在学校，许多人都和我很熟悉，因为我个人性格是比较活泼开朗的，且喜欢开玩笑，所以都比较随和。)，但学校又要求每人都得报2项，所以其中一项我没去，另外一项别人打电话过来了，我也说没时间~~~（是不是很拽？）其实也不是不给他们面子，只是在我眼中，我不喜欢这些权势及口头上的较量，靠嘴皮子进去，一点用都没，而且在我看来，这些东西都是无聊至极的，一群把自己当成官一样来看待的，让我感觉很不舒服。我喜欢那种靠自己真实实力较量的生活。并且在我看来，等工作了这些权势竞争的生活多的是，在大学去浪费时间花在这上面太不值得了。就这么浑浑噩噩的一个学期快过完了，临近寒假，发现别人虽然分一部分心思去弄学校各个部门的活，但是也确实培养了他们的个人能力，而我呢？除了会去网吧，还是去网吧。虽然那时成绩不差，在班级30人中还能排在第10名。但是自己缺乏了其他独特的能力。因为我接触计算机很早，是从小学5年级开始的，所以我想到了从计算机这方面发展，刚开始对编程一窍不通，买了基本PS,FLASH,DW的书看，结果自己就是在美术细胞上太过于匮乏，始终弄不好，就这样折腾了3个多月，最终放弃了，那时也知道了C语言，且知道下学期要学C语言，所以就提前自学了。我的编程生涯也就是从这个时候开始的（起步很晚~~）。

           刚开始学C语言，我就被吸引了，作为男生，我相信好多人都很YM那些开发软件的人，我也不例外，而接触了C语言，我才知道，这就是可以开发出软件的东东，于是，我埋头苦学…汗，其实也算不上苦学，就是把自己的课程都丢了，天天只看C语言的书，因为我不是计算机专业的，没人教我，也没人给我经验，我就只能靠自己，计算机编程这方面的书都很贵的，还好有父母的经济支持，这样算一算，我10个月在买书上就花了2000元。我到现在都不知道怎么花的，反正牛人的书我都买了，还订了好多杂志。记得看了谭老的《C语言程序》，《C Primer Plus》, 《The C Programming Language》 《C陷阱与缺陷》 《C专家编程》等等~~~太多了，我经常没去上课，一个人抱着书和电脑去图书馆学。结果自己专业没顾着，大二下学期还弄了个年级300人，倒数10几名~~

           大二上学期我报了等级考试的三级数据库，也顺利的一次通过。呵呵，现在想来，也没啥高兴的，毕竟那些都是虚的，只需要靠2本书死记就过的，没有一点技术含量，不值得高兴。到了现在，数据库的一些知识也快忘光了。

           大二上学期的暑假，我开始学习C++了。那时学了一段时间，寂寞了，于是建了几个QQ群，在网上召集了一批C++爱好者一起交流，也就是那个时候，有了创办一个论坛让大家一起交流学习的想法。也就是在大二下学期开学后，随着群的人越来越多，许多人也提议弄一个专门学习交流的地方，于是我买了空间和域名，办了一个论坛。因为我觉得人生就要奋斗，我们学习编程，何尝不是在为以后而奋斗，所以我给群，以及论坛取名叫C++奋斗乐园。域名我也选择了cppleyuan。

           最开始接触ACM不知道是在什么时候，应该实在大一下学期或大二上学期吧。那时就觉得这挺有趣的，但是也没买书学习算法，就这么直接找上了POJ，经常把题目看懂就花了1个小时，然后做不出来，再分析别人代码又是几个小时~~~汗…后来觉得这东西不是我这种人弄的，就放弃了。不过还好，只是暂时放弃，在大二下学期开学后1个月，也就是2010年4月份左右吧。我又开始搞ACM了，因为学习C和C++也有一段时间了，对于编程也有了一定的认识，不再是那个初入编程大门，懵懵懂懂乱学的人了，我买了刘如佳老师的《算法学习经典入门》，《算法艺术与信息学竞赛》，吴文虎老师的《世界大学生程序设计竞赛》以及算法的圣经—-《算法导论》。就这么开始一个人在算法的海洋里探索了。也就是这个时候，因为自己对这方面有了解，并且觉得论坛不能只搞C++方面，所以我把论坛一部分分给了算法。毕竟算法是程序的灵魂。但是POJ对于我这个刚起步的小菜来说还是难了些。所以我开始转向HDOJ了，7月10号注册的。今天是8月17号，已经刷了210道水题了。我感觉，每AC一道题目，就感觉自己快乐了一分。也许这就是算法的魅力把，也可能这就是男人喜欢对事物的绝对掌控，感觉自己学懂了这个算法，就感觉自己多了一项能力。

           假期我给论坛弄了C/C++小项目和ACM刷题活动。当时我还到处找资料，花了一下午为C/C++小项目的第一个写了一个详细的流程图，结果到最后无人问津，只有个别人做了，wujing的就做的很好，赞一个。不过还好，ACM刷题活动倒是很受欢迎，每天都有一批人和我一起刷，包括MiYu,大帅，萝莉，timest,ac-quest等等。当然，amb教主我就不多说了，我只能YM。小白就是专门和我竞争的家伙。。。最近被他赶超了10题。郁闷。不过假期确实还是很开心的。毕竟结交了一群志同道合的朋友。

          现在假期也快结束了，8月20号返校，还得搬校区。

         看的书很多，想的也很多。喜欢思考编程，思考人生哲理。平时除了编程的书，我就最喜欢看自然科学和人生哲理了，《当下的力量》，《遇见心想事成的自己》，《秘密》这些书都很好，教会了我很多道理。感觉这些书就和算法一样，讲的都是内涵。人生就像编程，编的是人生，让人生合理，规划好人生，人生才能成功。

           最后，我想感谢C++奋斗乐园的各位斑竹，感谢假期陪我刷题的哥们，感谢支持我的论坛会员们。Orz

         以上算是发泄自己的情感，也算是倾述自己的经历，或算是总结自己的经验。不求能给大家什么帮助，只求大家能一起多交流点自己的经验，互相借鉴，互相学习。
                                                                                                                                                                                                
                                                                                                                                                                          TankyWoo    
                                                                                                                                                                    2010年8月7号
我的博客：http://www.wutianqi.com/ 希望大家多多交流。

（原创链接：http://www.wutianqi.com/?p=264）
思想：对于不超过n的每个非负整数P，删除2*P, 3*P…，当处理

完所有数之后，还没有被删除的就是素数。

若用vis[i]==1表示已被删除，则代码如下：
—————————————————–
代码一：

1memset(vis, 0, sizeof(vis));
2for(int i = 2; i <= 100; i++)
3    for(int j = i*2; j <= 100; j += i)
4        vis[j] = 1;

上面的代码效率已经很高了。
但还可以继续优化。
看一个改进的代码：
——————————————————
代码二：

 1int m = sqrt(double(n+0.5));
 2 
 3for(int i = 2; i <= m; i++)
 4    if(!vis[i])
 5    {
 6        prime[c++] = i;
 7        for(int j = i*i; j <= n; j += i)
 8        {
 9            vis[j] = 1;
10        }
11    }

——————————————————
先分析代码一：
这个代码就是简单的将Eratosthenes筛选法描述出来。不用多说。
分析代码二：
考虑几点：
1.为何从i=2~m?
因为下面的j是从i*i开始的。
2.为何j从i*i开始？
因为首先在i=2时，偶数都已经被删除了。
其次，“对于不超过n的每个非负整数P”， P可以限定为素数，
为什么？
因为，在 i 执行到P时，P之前所有的数的倍数都已经被删除，若P

没有被删除，则P一定是素数。
而P的倍数中，只需看：
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
（因为P为素数，所以为奇数，而偶数已被删除，不需要考虑p*(p

-1)等）（Tanky Woo的程序人生）
又因为(p-4)*p 已在 (p-4)的p倍中被删去，故只考虑：
p*p, p*(p+2)….即可
这也是i只需要从2到m的原因。
当然，上面 p*p, p*(p+2)…的前提是偶数都已经被删去，而代码

二若改成 j += 2*i ,则没有除去所有偶数，所以要想直接 加2*i

。只需在代码二中memset()后面加：
for(int i = 4; i <= n; i++)
if(i % 2 == 0)
vis[i] = 1;
这样，i只需从3开始，而j每次可以直接加 2*i.
------------------------------------------------------
这里用代码二给大家一个完整的代码：

 1//版本二
 2//Author: Tanky Woo
 3//Blog: www.wutianqi.com
 4 
 5#include <stdio.h>
 6#include <string.h>
 7#include <math.h>
 8int vis[100];
 9int prime[100];
10int c = 0;
11int n;
12int main()
13{
14    scanf("%d", &n);
15    int cnt = 1;
16 
17    memset(vis, 0, sizeof(vis));
18    int m = sqrt(double(n+0.5));
19 
20    for(int i = 2; i <= m; i++)
21        if(!vis[i])
22        {
23            prime[c++] = i;
24            for(int j = i*i; j <= n; j += i)
25            {
26                vis[j] = 1;
27                //printf("%d\n", j);
28            }
29        }
30 
31    for(int i = 2; i < n; i++)
32    {
33        if(vis[i] == 0)
34        {
35            printf("%d ", i);
36            cnt++;
37            if(cnt % 10 == 0)
38                printf("\n");
39        }
40    }
41    printf("\ncnt = %d\n", cnt);
42    return 0;
43}

完毕。

---

欢迎大家和我交流。(我的博客:http://www.wutianqi.com/)

背包之01背包、完全背包、多重背包详解

PS：大家觉得写得还过得去，就帮我顶博客，谢谢。

首先说下动态规划，动态规划这东西就和递归一样，只能找局部关系，若想全部列出来，是很难的，比如汉诺塔。你可以说先把除最后一层的其他所有层都移动到2，再把最后一层移动到3，最后再把其余的从2移动到3，这是一个直观的关系，但是想列举出来是很难的，也许当层数n=3时还可以模拟下，再大一些就不可能了，所以，诸如递归，动态规划之类的，不能细想，只能找局部关系。

1.汉诺塔图片

（引至杭电课件:DP最关键的就是状态，在DP时用到的数组时，也就是存储的每个状态的最优值，也就是记忆化搜索）

要了解背包，首先得清楚动态规划：

动态规划算法可分解成从先到后的4个步骤：

1. 描述一个最优解的结构；

2. 递归地定义最优解的值；

3. 以“自底向上”的方式计算最优解的值；

4. 从已计算的信息中构建出最优解的路径。

其中步骤1~3是动态规划求解问题的基础。如果题目只要求最优解的值，则步骤4可以省略。

背包的基本模型就是给你一个容量为V的背包

在一定的限制条件下放进最多(最少?)价值的东西

当前状态→ 以前状态

看了dd大牛的《背包九讲》(点击下载)，迷糊中带着一丝清醒，这里我也总结下01背包，完全背包，多重背包这三者的使用和区别，部分会引用dd大牛的《背包九讲》，如果有错，欢迎指出。

(www.wutianqi.com留言即可)

首先我们把三种情况放在一起来看：

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

比较三个题目，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。

——————————————————————————————————————————————————————————–：

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

把这个过程理解下：在前i件物品放进容量v的背包时，

它有两种情况：

第一种是第i件不放进去，这时所得价值为:f[i-1][v]

第二种是第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]

（第二种是什么意思？就是如果第i件放进去，那么在容量v-c[i]里就要放进前i-1件物品）

最后比较第一种与第二种所得价值的大小，哪种相对大，f[i][v]的值就是哪种。

（这是基础，要理解！）

这里是用二位数组存储的，可以把空间优化，用一位数组存储。

用f[0..v]表示，f[v]表示把前i件物品放入容量为v的背包里得到的价值。把i从1~n(n件)循环后，最后f[v]表示所求最大值。

*这里f[v]就相当于二位数组的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重点！思考）
首先要知道，我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即：for i=1..N
现在思考如何能在是f[v]表示当前状态是容量为v的背包所得价值，而又使f[v]和f[v-c[i]]+w[i]标签前一状态的价值？

逆序！

这就是关键！

1for i=1..N
2   for v=V..0
3        f[v]=max{f[v],f[v-c[i]]+w[i]};
4

分析上面的代码：当内循环是逆序时，就可以保证后一个f[v]和f[v-c[i]]+w[i]是前一状态的！
这里给大家一组测试数据：

测试数据：
10,3
3,4
4,5
5,6

这个图表画得很好，借此来分析：

C[v]从物品i=1开始，循环到物品3，期间，每次逆序得到容量v在前i件物品时可以得到的最大值。（请在草稿纸上自己画一画）

这里以一道题目来具体看看：

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2602

代码在这里：http://www.wutianqi.com/?p=533

分析：

具体根据上面的解释以及我给出的代码分析。这题很基础，看懂上面的知识应该就会做了。

——————————————————————————————————————————————————————————–

完全背包：

完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

完全背包按其思路仍然可以用一个二维数组来写出：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

同样可以转换成一维数组来表示：

伪代码如下：



for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-c[i]]+w[i]}

顺序！

想必大家看出了和01背包的区别，这里的内循环是顺序的，而01背包是逆序的。
现在关键的是考虑：为何完全背包可以这么写？
在次我们先来回忆下，01背包逆序的原因？是为了是max中的两项是前一状态值，这就对了。
那么这里，我们顺序写，这里的max中的两项当然就是当前状态的值了，为何？
因为每种背包都是无限的。当我们把i从1到N循环时，f[v]表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。
这里同样给大家一道题目：

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1114

代码：http://www.wutianqi.com/?p=535

（分析代码也是学习算法的一种途径，有时并不一定要看算法分析，结合题目反而更容易理解。）

——————————————————————————————————————————————————————————–

多重背包

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

这里同样转换为01背包：

普通的转换对于数量较多时，则可能会超时，可以转换成二进制（暂时不了解，所以先不讲）

对于普通的。就是多了一个中间的循环，把j=0~bag[i]，表示把第i中背包从取0件枚举到取bag[i]件。

给出一个例题：

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2191

代码：http://www.wutianqi.com/?p=537

因为限于个人的能力，我只能讲出个大概，请大家具体还是好好看看dd大牛的《背包九讲》。

暂时讲完后，随着以后更深入的了解，我会把资料继续完善，供大家一起学习探讨。(我的博客：www.wutianqi.com如果大家有问题或者资料里的内容有错误，可以留言给出，谢谢您的支持。)

原文下载地址：（Word版）
http://download.csdn.net/sour

个人原创，转载请注明本文链接：http://www.wutianqi.com/?p=539

学校太让人失望了，居然连POJ都上不去了，还好今天ambition在我用百练AC掉这题后送来了另外一个POJ的网址，双喜临门，害我兴奋了半天，没有POJ的日子痛苦啊。毕竟题目来源还得靠它。

这是曾经没有AC掉的题目，不过在《程序设计导引及在线实践》上看过，看书写代码还是没亲自做的效果好。今天给假期题目来源找题，看中了这题，再次做，强化了一些基本功。

分析几点：

一。A~Z对应一个Hash数组

二。在每输入一个数据时就对数据进行处理，转换字母，去掉’-’

三。qsort的运行，具体看MSDN，这里就讲一点。

    一个是二位数组的qsort用法：

1
            2
            3
            4
            5
            6
            

 int compare( const void *arg1, const void *arg2 )
            {
            return strcmp((char*)arg1, (char*)arg2 );
            }
            int arr[n][11];
            qsort(arr, n, sizeof(arr[0]), compare);

  二是qsort的几个参数，这里一直不是记得很清楚。

1
            2
            3
            4
            5
            6
            

 void qsort(
            void *base,
            size_t num,
            size_t width,
            int (__cdecl *compare )(const void *, const void *)
            );

  注意：width: Element size in bytes

               cmp函数：如果是升序，则e1 > e2应返回1，e1 = e2 应返回0， e1 < e2 应返回-1.降序则相反。

直接发代码了：

时间有点大，是600多MS。

看见网上还有其他方法，大家可以去看看。

题目地址：

http://124.205.79.250/JudgeOnline/problem?id=1002

1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            39
            40
            41
            42
            43
            44
            45
            46
            47
            48
            49
            50
            51
            52
            53
            54
            55
            56
            57
            58
            59
            60
            61
            62
            63
            64
            65
            66
            67
            68
            69
            70
            71
            72
            73
            74
            

 // POJ 487-3279
            // Author: Tanky Woo
            #include <iostream>
            using namespace std;
             
            char hash[] = "22233344455566670778889990";
             
            char telphone[100001][20];
            char temp[20];
             
            int compare( const void *arg1, const void *arg2 )
            {
            return strcmp((char*)arg1, (char*)arg2 );
            }
             
            // www.wutianqi.com
            int main()
            {
            //freopen("input.txt", "r", stdin);
            int flag = 0;
            int nCases;
            scanf("%d", &nCases);
            for(int i = 0; i < nCases; ++i)
            {
            getchar();
            scanf("%s", telphone[i]);
            int len = strlen(telphone[i]);
            int t = 0;
            for(int j = 0; j < len; ++j)
            {
            if(telphone[i][j] >= 'A' && telphone[i][j] <= 'Z')
            temp[t++] = hash[telphone[i][j]-'A'];
            else if(telphone[i][j] >= '0' && telphone[i][j] <= '9')
            temp[t++] = telphone[i][j];
            else if(telphone[i][j] == '-')
            ;
            }
            strcpy(telphone[i], temp);
            }
             
            qsort(telphone, nCases, sizeof(telphone[0]), compare);
             
             
            for(int i = 0; i < nCases; ++i)
            {
             
            int cnt = 1;
            strcpy(temp, telphone[i]);
            int j;
            for(j = i+1; j < nCases; ++j)
            {
            if(strcmp(temp, telphone[j]) == 0)
            cnt++;
            else
            break;
            }
            if(cnt > 1)   //这个地方没处理好，麻烦。。。
            {
            flag = 1;
            for(int k = 0; k < 3; ++k)
            printf("%c", temp[k]);
            printf("-");
            for(int k = 3; k < 7; ++k)
            printf("%c", temp[k]);
            printf(" %d\n", cnt);
            }
            i = j-1;
            }
            if(flag == 0)
            printf("No duplicates.\n");
             
             
            return 0;
            }