主题：第80次编程比赛（08第二学期开学第一炮）
雨中飞燕 [专家分：18980] 发布于 2009-02-21 18:44:00
原79次冠军因长时间不再发帖子，故本次由本人开展
[color=0000FF]题目描述：[/color]
现在，有两个正整数A和B，例如A是345，B是478，现在，需要把B插入到A里，
而A有三位，所以有四个位置选择，所得结果分别是：
478345, 347845, 344785, 345478
我们通过对比可以知道，在这当中最小的一个是344785
这两个正整数长度不超过100000位，各个位均不包含数字0
现在的目标是，要找出插入后所能得到的最小的整数，输出这个整数
[color=0000FF]样例输入：[/color]
345 478
12345 678
12 21
12 23
[color=0000FF]样例输出：[/color]
344785
12345678
1212
1223
[color=0000FF]答题要求：[/color]
请完善以下代码(C/C++均可)：
[code=c]#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}[/code]
其它信息：
本次比赛以公开答题代码的形式，且附以及时的测试，允许直接在本帖子讨论算法
测试内容：正确性，时间效率，空间效率，代码可读性
本次比赛结束时间3月8日 23:00
[color=FF0000]在本帖子回复广告或比赛无关内容者立即封ID及IP[/color]
最后更新于：2009-02-22 11:57:00
回复列表 （共182个回复）
131 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-03 17:47:00
127楼的代码错在1555559 5556
楼上的代码错在12 22222222221
132 楼
Reversed [专家分：0] 发布于 2009-03-03 19:04:00
又错了啊...
133 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-03 19:12:00
122 221这组错
134 楼
Reversed [专家分：0] 发布于 2009-03-03 20:06:00
/*我都不好意思发了 麻烦燕大再看看*/
#include <stdio.h>
#include <string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
int find_first_bigger(char* str, char c) {
char* temp = str;
int len = 0;
while (*temp <= c && *temp != '\0') {++temp; ++len;}
return len;
}
int find(char* str, char c) {
char* temp = str;
int len = 0;
while (*temp < c && *temp != '\0') {++temp; ++len;}
return len;
}
bool compare(char* str1, char* str2, char end, int& equal_num) {
equal_num = 0;
char* temp1 = str1; char* temp2 = str2;
int flag1 = 0; int flag2 = 0;
while (*temp1 == *temp2 && *temp1 != end && *temp2 != '\0') {
if (*temp1 == *str2) ++equal_num;
++temp1; ++temp2;
}
if (*temp1 == '\0' || *temp1 == end) {--temp1; flag1 = 1;}
if (*temp2 == '\0') {--temp2; flag2 = 1;}
while (*temp1 == *temp2 && (flag1 & flag2) != 1) {
if (flag1 == 1) ++temp2;
if (flag2 == 1) ++temp1;
}
if (*temp1 > *temp2)
return true;
else
return false;
}
inline void move(char* a, char* b, char* c,int fLen,int aLen,int bLen) {
memcpy(c, a, fLen);
memcpy(c + fLen, b, bLen);
memcpy(c + fLen + bLen, a + fLen, aLen - fLen + 2);
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int count = 0;
bool flag = true;
int big = find_first_bigger(a, *b);
char end = *(a + big);
int aLen = strlen(a);
int bLen = strlen(b);
int fLen = find(a, *b);
while (fLen < big) {
flag = compare(a + fLen, b, end, count);
if (flag == true) {
move(a, b, c, fLen, aLen, bLen);
return;
}
else {
int temp = fLen + count;
fLen = temp + find(a + temp, *b);
}
}
flag = compare(a + fLen, b, end, count);
if (flag == true)
move(a, b, c, big - 1, aLen, bLen);
else
move(a, b, c, big, aLen, bLen);
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}
135 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-03 20:17:00
7891177 91
这组出错
136 楼
Reversed [专家分：0] 发布于 2009-03-03 20:52:00
/*今晚在这里刷屏了...*/
#include <stdio.h>
#include <string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
int find_first_bigger(char* str, char c) {
char* temp = str;
int len = 0;
while (*temp <= c && *temp != '\0') {++temp; ++len;}
return len;
}
int find(char* str, char c) {
char* temp = str;
int len = 0;
while (*temp < c && *temp != '\0') {++temp; ++len;}
return len;
}
bool compare(char* str1, char* str2, char end, int& equal_num) {
equal_num = 0;
char* temp1 = str1; char* temp2 = str2;
int flag1 = 0; int flag2 = 0;
while (*temp1 == *temp2 && *temp1 != end && *temp2 != '\0') {
if (*temp1 == *str2) ++equal_num;
++temp1; ++temp2;
}
if (*temp1 == '\0' || *temp1 == end) {--temp1; flag1 = 1;}
if (*temp2 == '\0') {--temp2; flag2 = 1;}
if (*temp1 == *temp2 && (flag1 & flag2) != 1) {
if (flag1 == 1) ++temp2;
if (flag2 == 1) ++temp1;
}
if (*temp1 > *temp2)
return true;
else
return false;
}
inline void move(char* a, char* b, char* c,int fLen,int aLen,int bLen) {
memcpy(c, a, fLen);
memcpy(c + fLen, b, bLen);
memcpy(c + fLen + bLen, a + fLen, aLen - fLen + 2);
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int count = 0;
bool flag = true;
int big = find_first_bigger(a, *b);
char end = *(a + big);
int aLen = strlen(a);
int bLen = strlen(b);
int fLen = find(a, *b);
while (fLen < big) {
flag = compare(a + fLen, b, end, count);
if (flag == true) {
move(a, b, c, fLen, aLen, bLen);
return;
}
else {
int temp = fLen + count;
fLen = temp + find(a + temp, *b);
}
}
flag = compare(a + fLen, b, end, count);
if (flag == true)
move(a, b, c, big - 1, aLen, bLen);
else
move(a, b, c, big, aLen, bLen);
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}
137 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-03 22:41:00
12 2222221
这组错了
PS.你要是在我论坛提交来实时测试的话，'\0'最好换成0
因为有一些浏览器或者啥软件的，在你复制的时候无意把\0给去掉，只剩下''，导致编译错误
或者你提交之前手工改一下
138 楼
dert [专家分：0] 发布于 2009-03-04 15:49:00
#include <stdio.h>
#include<string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i=0,n=0,m=0;
char k=b[0],p[MAXLEN+1];
c[0]='\0';
while(a[i]!='\0')
{
if(a[i]<=k)
{
c[n++]=a[i];
i++;
}
else
{
strcat(c,b);
break;
}
}
while(a[i]!='\0')
{
p[m++]=a[i++];
p[m]='\0';
}
strcat(c,p);
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}
139 楼
mo_0820 [专家分：50] 发布于 2009-03-04 17:37:00
//莫非是/0的问题，12，22222221，我运行结果是1222222212没错呀。现改为0
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,j,k=0,m,flag=1;
for(i=0,j=0;flag;j++,i++)
{ if(!b[i]) i=0;
for(;a[j]<=b[i]&&flag;j++)
{ if(!i&&a[j])
{ c[k]=a[j]; k++;
if(a[j]==b[0]) break;
}
if(!a[j])
{ if(b[i]>b[0])
{ for(m=0;;k++)
{ c[k]=b[m];
if(!b[m]) break;
m++;
}
}
else
{ for(m=i;;k++)
{ c[k]=b[m]; m++;
if(!b[m]) break;
}
for(m=0,k++;m<i;m++,k++) c[k]=b[m];
c[k]=0;
}
flag=0;
}
if(flag&&i)
{ if(a[j]<=b[0])
{ c[k]=a[j]; k++;
if(a[j]<b[i]) i=0;
}
else
{ for(m=0;;k++)
{ if(b[m])
{ c[k]=b[m];m++;
}
else
{ for(;;k++)
{ c[k]=a[j];
if(!a[j]) break;
j++;
}
break;
}
}
flag=0;
}
}
if(i) break;
}
140 楼
mo_0820 [专家分：50] 发布于 2009-03-04 17:39:00
if(flag)
{ if(a[j]>b[i])
{ if(b[i]<b[0])
{ for(m=i;;k++)
{ c[k]=b[m]; m++;
if(!b[m]) break;
}
for(m=0,k++;m<i;m++,k++) c[k]=b[m];
for(;;k++)
{ c[k]=a[j];
if(!a[j]) break;
j++;
}
flag=0;
}
else
{ for(m=0;;k++)
{ if(b[m])
{ c[k]=b[m]; m++;
}
else
{ for(;;k++)
{ c[k]=a[j];
if(!a[j]) break;
else j++;
}
break;
}
}
flag=0;
}
}
}
}
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}
我来回复
您所在位置：