寒假训练（二）"/>
2016级ACM寒假训练（二）
第一题
单词排序
Problem:A
Time Limit:1000ms
Memory Limit:65535K
Description
给定一组单词，对单词进行自小到大的排序。
Input
输入数据有多组，每组的第1行为n，表示该组有n个单词(n最多为200，且每个单词的长度不超过20)，接下来是具体的n个单词;
Output
输出数据有多行，每组n行，输出该组单词中自小到大排好序的单词。
Sample Input
5 banana apple orange pear peach 4 green black white red
Sample Output
apple banana orange peach pear black green red white
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<=n<=20);然后为n行的字符串（包含空格，字符串的个数小于100）
Output
把这些串按照从小到大的顺序输出（输出可以使用puts());
Sample Input
3 good kood bug i am dog dx
Sample Output
dog dx good kood bug i 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<=len<=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; //提前结束本次存储数组的循环，因为开头就是5int 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; //提前结束本次存储数组的循环，因为开头就是5int 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;
}
更多推荐
2016级ACM寒假训练（二）
发布评论