hdu - 1716 排列2 (使用set对全排列结果去重)-白红宇的个人博客

发布日期：2021-05-13 00:44:50 浏览次数：15 分类：博客文章

本文共 2960 字，大约阅读时间需要 9 分钟。

　　题意很简单，只是有几个细节要注意，首先就是一次只是输入四个数字、输出结果要从小到大（进行全排列之前要进行排序）、题目要求千位数相同的在一行，中间使用空格隔开（第二次在输出的时候判断上一次记录的千位数是不是和这一次的相等，相等就输出空格，不等就输出换行）、每组输出数据间加一个空行，最后一组后不可以有空行（第二次之后输入的不是0 0 0 0就输出一个空行就可以了，否则break）。

　　还要两个隐藏的条件：①输出的时候前导0的一组不要；②输入数据可以有相同的数字，输出的时候要进行去重；

　　对于本题来说，由于时间复杂度不是很大，可以使用一个容器（vector，arraylist）把结果存起来，在存的时候或者是输出的时候去遍历整个容器是不是有当前的这组数据，再进行相关处理。

　　我这里偷了一下懒（实际上是想熟悉一下set），不得说set确实挺好用的。全排列的知识点请参考：（默认从小到大的顺序储存）

　　具体输出格式以及代码控制见代码：

1 #include 
    
      2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 using namespace std; 8 9 char s[8];10 char res[8];11 bool used[10];12 char c;13 bool f;14 set
          
            se;15 16 void print () {17 18 for (set
           
            ::iterator p = se.begin(); p != se.end(); ++p) {19 if (f) {20 if (c == (*p)[0]) {21 cout << ' ';22 } else {23 cout << endl;24 }25 }26 while ((*p)[0] == '0') {27 p++;28 }29 cout << *p;30 c = (*p)[0];31 f = true;32 }33 }34 35 void perm (int pos, int n) {36 if (pos == n) {37 se.insert (res);38 return ;39 }40 for (int i = 0; i < n; ++i) {41 if (!used[i]) {42 res[pos] = s[i];43 used[i] = true;44 perm (pos+1, n);45 used[i] = false;46 }47 }48 }49 50 int main () {51 bool a = false;52 while (1) {53 f = false;54 for (int i = 0; i < 4; ++i) {55 cin >> s[i];56 }57 if (s[0] == '0' && s[1] == '0' && s[2] == '0' && s[3] == '0') {58 break;59 }60 if (a) {61 cout << endl;62 }63 a = true;64 sort (s, s+4);65 memset(used, false, sizeof (used));66 perm(0, 4);67 print();68 se.clear();69 cout << endl;70 }71 return 0;72 }

　　在这里添加一点使用set求交集、并集、差集的几个函数的笔记：

1 #include 
    
      2 #include 
     
       3 #include 
      
        4 #include 
       
         5 using namespace std; 6  7 int main () { 8     set
        
          a, b, c; 9     int n;10     cout << "A:" << endl;11     for (int i = 0; i < 3; ++i) {12         cin >> n;13         a.insert (n);14     }15     cout << "B:" << endl;16     for (int i = 0; i < 4; ++i) {17         cin >> n;18         b.insert (n);19     }20     21     c.clear();22     set_intersection (a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin()));23     for (set
         
          ::iterator p = c.begin(); p != c.end(); ++p) {24 cout << *p << ' ';25 }26 cout << endl;27 28 c.clear();29 set_union (a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin()));30 for (set
          
           ::iterator p = c.begin(); p != c.end(); ++p) {31 cout << *p << ' ';32 }33 cout << endl;34 35 c.clear();36 set_difference (a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin())); 37 for (set
           
            ::iterator p = c.begin(); p != c.end(); ++p) {38 cout << *p << ' ';39 }40 cout << endl;41 return 0;42 }43 44 /*45 A:46 1 2 447 B:48 3 2 1 349 1 250 1 2 3 451 452 */

　　C++对学习算法来说，确实很方便，一方面节省了很多时间，另一方面也会忘记最基础算法的实现，比如想到交换，都可以一行swap(a, b);实现，都不会想到去另外定义一个变量t，更不会想到定义一个函数，使用指针的方式从地址上实现数值的交换。

　　所以，先定个小目标：STL既要会用，更要学会看源代码。

上一篇：hdu 2072 1106学一波字符串分割，C语言与C++两种方法

下一篇：多种方法实现实现全排列 + sort调用标准函数库函数的简述

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章