2016级ACM寒假训练（二）

第一题

单词排序

PRoblem:A

Time Limit:1000ms

Memory Limit:65535K

Description

给定一组单词，对单词进行自小到大的排序。
Input
输入数据有多组，每组的第1行为n，表示该组有n个单词(n最多为200，且每个单词的长度不超过20)，接下来是具体的n个单词;
Output
 输出数据有多行，每组n行，输出该组单词中自小到大排好序的单词。
Sample Input
5bananaappleorangepearpeach4greenblackwhitered
Sample Output
applebananaorangepeachpearblackgreenredwhite
Hint
难度系数 2分；简单 本题目考核知识点：   考点1：二维数组的定义。   考点2: 字符串数组的使用。   考点3：排序算法的应用。
利用C语言上课学的冒泡排序可以写出以下代码
#include <stdio.h>#include <stdlib.h>#include <string.h>int main(){   int n,i,j;     char t[20];     int a[200][20];   while(scanf("%d",&n)!=-1){       getchar();       for(i=0;i<n;i++){           gets(a[i]);       }       for(i=0;i<n-1;i++){           for(j=0;j<n-1-i;j++){                if(strcmp(a[j],a[j+1])>0){                    strcpy(t,a[j]);                    strcpy(a[j],a[j+1]);                    strcpy(a[j+1],t);                }          }       }       for(i=0;i<n;i++){            puts(a[i]);       }    }}用这次的sort函数，代码量大大减少
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;string s[201];int n,i;int main(){	while(~scanf("%d",&n))	{		for(i=0;i<n;i++)		 cin>>s[i];		sort(s,s+n);		for(i=0;i<n;i++)		cout<<s[i]<<endl;	}	return 0;} 第二题
阿里巴巴致富的秘密
Problem:B 
Time Limit:1000ms
Memory Limit:65535K
Description
阿里巴巴每次来到强盗的藏宝藏的洞穴门口，都要破译动门口的密码；密码由一些行的字符串构成，只要知道这些行字符串的顺序，就可以顺利的进入洞穴了，得到宝藏了！阿里巴巴冥思苦想，最后发现密码就是对这些字符串的从小到大排序就行了。
Input
输入数据有多组，每组第1行为n（1&lt;=n&lt;=20);然后为n行的字符串（包含空格，字符串的个数小于100）
Output
把这些串按照从小到大的顺序输出（输出可以使用puts());
Sample Input
3good kood bugi amdog dx
Sample Output
dog dxgood kood bugi am
前一个题的升级版，用gets读入即可
#include <stdio.h>#include <stdlib.h>#include <string.h>int main(){    int n,i,j,k;    char a[100][20];    char tmp[20];    while(scanf("%d",&n)!=-1)    {        getchar();        for(i=0;i<n;i++)        gets(a[i]);         for(i=0;i<n;i++)        {            strcpy(tmp,a[i]);            for(j=i+1;j<n;j++)            {                if(strcmp(tmp,a[j])>0)                {                    k=j;                    strcpy(tmp,a[j]);                    strcpy(a[k],a[i]);                    strcpy(a[i],tmp);                }            }        }        for(i=0;i<n;i++)        {            puts(a[i]);            //printf("/n");        }    }    //printf("Hello world!/n");    return 0;}依旧是 sort要短很多
新出现的c++函数 可以自己查阅相关资料 锻炼一下自学能力~~
#include <iostream>#include <string>#include <algorithm>using namespace std;string a[105];int main(){    int n;    while(cin>>n)    {        cin.get();        for(int i=0;i<n;i++)        getline(cin,a[i]);        sort(a,a+n);        for(int i=0;i<n;i++)        cout<<a[i]<<endl;    }    return 0;}第三题
Yukun的字符串
Problem:C 
Time Limit:1000ms
Memory Limit:65536K
Description
话说在上一场训练中，zhouyukun学长已经给大家讲解了字符串的有关知识，下面我们来复习一下。给你一个字符串让你对字符串中所有的字符按照从ASXII码大到小的顺序排序并输出。简单吧，那就来吧！
Input
输入一个字符串s（只含有英文大小写）,长度（1&lt;=len&lt;=100000）
Output
输出排序好的字符串
Sample Input
ababac
Sample Output
cbbaaa
排序字符串 小case啊
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;char a[100005];int main(){    //freopen("data.in","r",stdin);    //freopen("data.out","w",stdout);    while(~scanf("%s",a))    {        int n=strlen(a);        sort(a,a+n);        for(int i=n-1;i>=0;i--)            printf("%c",a[i]);        printf("/n");    }    return 0;}第四题 
排序
Problem:D 
Time Limit:1000ms
Memory Limit:65536K
Description
输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。	你的任务是：对这些分割得到的数字，依从小到大的顺序排序输出
Input
输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。  	输入数据保证：分割得到的非负整数长度不大于100；输入数据不可能全由‘5’组成。
Output
对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。
Sample Input
0051231232050775
Sample Output
0 77 12312320
涉及到部分结构体的知识 就当作预习吧····我出这题的本意是让大家用二维数组储存的……你们试着改改吧
#include <iostream>  #include <cstdio>  #include <cstring>  #include <algorithm>  using namespace std;    struct node  {      char s[110];  }nt[1010];    bool cmp(node a,node b)  {      int alen=strlen(a.s),blen=strlen(b.s);      if(alen<blen)      {          return true;      }      else if(alen>blen)      {          return false;      }      else      {          if(strcmp(a.s,b.s)<0)          {              return true;          }          else          {              return false;          }      }  }  int main()  {      //freopen("g://data.in", "r", stdin);      //freopen("g://data.out", "w", stdout);      char s[1010],st[110];      memset(st,0,sizeof(st));      while(scanf("%s",s)!=EOF)      {          int len=strlen(s);          int k=0,tlen=0;          for(int i=0;i<=len;i++)          if(i==len||s[i]=='5')  //遇到5和读到整体的最后一个字符都需结束并输出        {              if(tlen==0) continue;  //提前结束本次存储数组的循环，因为开头就是5            int d=0;              for(d=0;d<tlen-1;d++)              if(st[d]!='0')  //st[]是小段的数组            {                  break;  //哪位开始不等于0，则从那位开始复制            }              strcpy(nt[k++].s,st+d); //把小段的数组st复制给结构体数组nt[k++]            memset(st,0,sizeof(st));  //数组st随时清零更新            tlen=0;          }          else          {              st[tlen++]=s[i];  //在没遇到5的情况下，逐个的字符复制给小段的数组的对应位数        }          sort(nt,nt+k,cmp);          printf("%s",nt[0].s);  //为了保证开头没有空格，其余中间分割有空格的写法        for(int i=1;i<k;i++)          {              printf(" %s",nt[i].s);          }          puts("");      }      return 0;  }
终于改好的代码……
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct node{    char s[110];}nt[1010];char str[1010][110];bool cmp( char a[],char b[]){    int alen=strlen(a),blen=strlen(b);    if(alen<blen) return true;    else if(alen>blen) return false;    else    {        if(strcmp(a,b)<0)return true;        return false;    }}int main(){//    freopen("data.in", "r", stdin);    //freopen("g://data.out", "w", stdout);    char s[1010],st[1100];    memset(st,0,sizeof(st));    while(cin>>s)    {        if(strlen(s)==0)break;        int len=strlen(s);        int k=0,tlen=0;        for(int i=0;i<=len;i++)        {                if(i==len||s[i]=='5')  //遇到5和读到整体的最后一个字符都需结束并输出                {                    if(tlen==0) continue;  //提前结束本次存储数组的循环，因为开头就是5                    int d=0;                    for(d=0;d<tlen-1;d++)                        if(st[d]!='0')  //st[]是小段的数组                            break;  //哪位开始不等于0，则从那位开始复制                    strcpy(str[k],st+d);                    k++;                    for(int j=0;j<1009;j++)st[j]='/0';                    tlen=0;                }                else                {                    st[tlen++]=s[i];  //在没遇到5的情况下，逐个的字符复制给小段的数组的对应位数                }        }        for(int i=0;i<k-1;i++)        {            for(int j=0;j<k-1-i;j++)                if(!cmp(str[j],str[j+1]))                {                    char tmp[1100];                    strcpy(tmp,str[j]);                    strcpy(str[j],str[j+1]);                    strcpy(str[j+1],tmp);                }       // sort(nt,nt+k,cmp);       // printf("%s",nt[0].s);  //为了保证开头没有空格，其余中间分割有空格的写法        }        cout<<str[0];        for(int i=1;i<k;i++)        {            //printf(" %s",nt[i].s);            cout<<" "<<str[i];        }        puts("");    }    return 0;}
附上一份比赛里提交的代码：
#include <stdio.h>#include <string.h>int bj(char a[],char b[]){    int i;    if(strlen(a)==strlen(b))        {            for(i=0;a[i]==b[i]&&a[i]!='/0';i++);            return a[i]>b[i];        }    return strlen(a)>strlen(b);}void px(char a[501][101],int n){    int i,j,k;    char t[101];    for(i=0; i<n-1; i++)        for(j=0; j<n-1-i; j++)            if(bj(a[j],a[j+1]))            {                for(k=0; a[j][k]!='/0'; k++)                    t[k]=a[j][k];                t[k]='/0';                for(k=0; a[j+1][k]!='/0'; k++)                    a[j][k]=a[j+1][k];                a[j][k]='/0';                for(k=0; t[k]!='/0'; k++)                    a[j+1][k]=t[k];                a[j+1][k]='/0';            }}int main(){    char a[1001];    char b[501][101];    int i,k,j;    while(gets(a)!=NULL)    {        j=0;        for(i=0; a[i]!='/0';)        {            while(a[i]=='5')                i++;            if(i>=strlen(a))                break;            while(a[i]=='0')                i++;            if(a[i]=='5'||a[i]=='/0')            {                b[j][0]='0';                b[j][1]='/0';                j++;            }            else            {                for(k=0; a[i]!='5'&&a[i]!='/0'; k++,i++)                    b[j][k]=a[i];                b[j][k]='/0';                j++;            }        }        px(b,j);        printf("%s",b[0]);        for(i=1;i<j;i++)            printf(" %s",b[i]);        printf("/n");    }    return 0;}