• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            題目大意:給出一個字符串,輸出字符串中的字符的全排列,要求按照字典序升序輸出,不允許重復。
            此題我認為沒有什么意義,因為C++的<algorithm>中有next_permutation()函數,直接可以通過不斷地求“下一個排列”得出結果,而且是可以判斷重復的!但是高中信息學競賽不允許用<algorithm>!如果不用這個函數真的好麻煩!我想到的是qsort+dfs+判重,還需要那么大的空間消耗來保存已出解!
            以下是我的代碼:
            #include<stdio.h>
            #include
            <string.h>
            #include
            <algorithm>
            using namespace std;
            int main()
            {
                
            /*
                freopen("data.in","r",stdin);
                freopen("data.out","w",stdout);
                //
            */
                
            char s[11],*s_end;
                
            long n;
                scanf(
            "%ld",&n);
                
            while (n--)
                {
                   scanf(
            "%s",s);
                   s_end
            =s+strlen(s);
                   sort(s,s_end);
                   
            do
                     printf (
            "%s\n", s);
                   
            while(next_permutation(s,s_end));
                   printf(
            "\n");
                }
            }
            補充:今天下午體育課的時候,突然想到一種不需要C++標準庫中的函數,也不需要判重的方法,同樣十分方便實現,而且復雜度很低。因為字符串一開始是已經排好序的,因此如果出現了重復,那么:要么當前生成的串與上一次生成的串字典序相同,要么比上次生成的串字典序小。因此,只要設置一個last字符串和now字符串,分別表示上次生成的串和當前正在生成的串,問題就解決了。
            以下是我的代碼(沒有提交,有興趣可以直接拿去嘗試):
            #include<stdio.h>
            #include
            <string.h>
            const long maxlen=18;
            long n,slen;
            char s[maxlen],now[maxlen],last[maxlen];
            bool used[maxlen];
            void swap(char &a,char &b)
            {
                
            char t=a;a=b;b=t;
            }
            void Qsort(char *a,long begin,long end)
            {
                
            long i=begin,j=end;
                
            char mid=a[(begin+end)/2];
                
            do{
                     
            while(a[i]<mid) i++;
                     
            while(a[j]>mid) j--;
                     
            if(i<=j)
                     {
                        swap(a[i],a[j]);
                        i
            ++;j--;
                     }
                }
            while(i<=j);
                
            if(i<end)   Qsort(a,i,end);
                
            if(j>begin) Qsort(a,begin,j);
            }
            void dfs(long dep)
            {
                
            if(dep>=slen)
                {
                   
            if(strcmp(now,last)>0)
                   {
                      printf(
            "%s\n",now);
                      strcpy(last,now);
                   }
                   
            return;
                }
                
            for(long i=0;i<slen;i++)
                  
            if(!used[i])
                  {
                     used[i]
            =true;
                     now[dep]
            =s[i];
                     dfs(dep
            +1);
                     used[i]
            =false;
                  }
            }
            int main()
            {
                
            /*
                freopen("data.in","r",stdin);
                freopen("data.out","w",stdout);
                //
            */
                scanf(
            "%ld",&n);
                
            for(long k=1;k<=n;k++)
                {
                   memset(s,
            0,sizeof(s));
                   memset(now,
            0,sizeof(now));
                   memset(last,
            0,sizeof(last));
                   memset(used,
            0,sizeof(used));
                   
            //  Clear
                   scanf("%s",s);
                   
            //  Read In
                   slen=strlen(s);
                   Qsort(s,
            0,slen-1);
                   
            //  Qsort
                   dfs(0);printf("\n");
                   
            //  Dfs
                }
            return 0;
            }


            posted on 2010-01-08 13:35 lee1r 閱讀(699) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:搜索
            综合久久精品色| 狠狠精品干练久久久无码中文字幕 | 9191精品国产免费久久| 久久er国产精品免费观看2| 嫩草影院久久99| 欧美精品九九99久久在观看| 亚洲狠狠婷婷综合久久蜜芽 | 久久99久久成人免费播放| 午夜精品久久久久久影视riav| 无码人妻少妇久久中文字幕蜜桃| 久久精品国产精品亚洲精品| 久久噜噜久久久精品66| 久久99热只有频精品8| 久久亚洲色一区二区三区| 久久综合狠狠综合久久| 色天使久久综合网天天| 91精品国产综合久久精品| 久久99九九国产免费看小说| 99久久免费只有精品国产| 久久棈精品久久久久久噜噜| 久久天天日天天操综合伊人av| 精品久久8x国产免费观看| 久久精品国产久精国产果冻传媒| 欧美色综合久久久久久| 久久精品国产91久久麻豆自制| 色综合久久无码中文字幕| 亚洲精品99久久久久中文字幕| 久久精品中文字幕第23页| 欧美久久精品一级c片片| 99久久无码一区人妻a黑| 国产亚洲精品久久久久秋霞| 国产欧美久久久精品影院| 中文字幕精品无码久久久久久3D日动漫 | 色婷婷综合久久久久中文字幕| 成人午夜精品久久久久久久小说| 国产精品国色综合久久| 国产精品99久久99久久久| 久久国产成人精品麻豆| 国产亚洲欧美成人久久片| 色综合久久久久网| 久久露脸国产精品|