暑期集训热身赛(郑大)

前几道题太简单了，直接跳过

问题 F: 字符串反转

题目描述

小C很喜欢倒着写单词，现在给你一行小C写的文本，你能把每个单词都反转并输出它们吗？

输入

输入包含多组测试样例。第一行为一个整数T，代表测试样例的数量，后面跟着T个测试样例。
每个测试样例占一行，包含多个单词。一行最多有1000个字符。

输出

对于每一个测试样例，你应该输出转换后的文本。

样例输入

3
olleh !dlrow
I ekil .bulcmca
I evol .mca

样例输出

hello world!
I like acmclub.
I love acm.

第一次提交显示编译错误，什么忽略了函数的返回值 (黑人问号...............)

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4  
 5 using namespace std;
 6  
 7 void change(char str[])
 8 {
 9     int i,j;
10     j=0;
11     char string[50];
12     if(strlen(str)==1)
13     {
14         printf("%s",str);
15         return ;
16     }
17     for(i=strlen(str)-1;i>=0;i--)
18     {
19         string[j++]=str[i];
20     }
21     string[j++]=0;
22     printf("%s",string);
23     return ;
24 }
25  
26 int main()
27 {
28     int n;
29     scanf("%d",&n);
30     getchar();
31     while(n--)
32     {
33         char str[1000];
34         gets(str);
35         int len=strlen(str);
36         str[len]=' ';
37         len++;
38         str[len]=0;
39         char tem[50];
40         int j=0;
41         for(int i=0;i<len;i++)
42         {
43             if(str[i]!=' ')
44             {
45                 tem[j++]=str[i];
46             }
47             else if(str[i]==' '&&str[i-1]!=' ')
48             {
49                 tem[j++]=0; 
50                 change(tem);
51                 j=0;
52                 memset(tem,0,sizeof(tem));
53                 if(i!=len-1) printf(" ");
54             }
55             else
56                 printf(" ");
57         }
58         printf("
");
59     }
60     return 0;
61 }
62 /**************************************************************
63     Problem: 1095
64     User: 201820222
65     Language: C++
66     Result: 编译错误
67 ****************************************************************/

第二次把change中的一个return删了，就能编译了(再次黑人问号)，但是显示运行错误。

运行时错误，非法的内存访问，数组越界，指针漂移，调用禁用的系统函数等。

猜测数组开小了。。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4  
 5 using namespace std;
 6   
 7 void change(char str[])
 8 {
 9     int i,j;
10     j=0;
11     char string[50];
12     for(i=strlen(str)-1;i>=0;i--)
13     {
14         string[j++]=str[i];
15     }
16     string[j++]=0;
17     printf("%s",string);
18     return ;
19 }
20  
21 int main()
22 {
23     int n;
24     scanf("%d",&n);
25     getchar();
26     while(n--)
27     {
28         char str[1000];
29         gets(str);
30         int len=strlen(str);
31         str[len]=' ';
32         len++;
33         str[len]=0;
34         char tem[50];
35         int j=0;
36         for(int i=0;i<len;i++)
37         {
38             if(str[i]!=' ')
39             {
40                 tem[j++]=str[i];
41             }
42             else if(str[i]==' '&&str[i-1]!=' ')
43             {
44                 tem[j++]=0; 
45                 change(tem);
46                 j=0;
47                 memset(tem,0,sizeof(tem));
48                 if(i!=len-1) printf(" ");
49             }
50             else
51                 printf(" ");
52         }
53         printf("
");
54     }
55     return 0;
56 }
57 /**************************************************************
58     Problem: 1095
59     User: 201820222
60     Language: C++
61     Result: 运行错误
62 ****************************************************************/

第三次，完美。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4  
 5 using namespace std;
 6   
 7 void change(char str[])
 8 {
 9     int i,j;
10     j=0;
11     char string[1001];
12     for(i=strlen(str)-1;i>=0;i--)
13     {
14         string[j++]=str[i];
15     }
16     string[j++]=0;
17     printf("%s",string);
18     return ;
19 }
20  
21 int main()
22 {
23     int n;
24     scanf("%d",&n);
25     getchar();
26     while(n--)
27     {
28         char str[1001];
29         gets(str);
30         int len=strlen(str);
31         str[len]=' ';
32         len++;
33         str[len]=0;
34         char tem[1001];
35         int j=0;
36         for(int i=0;i<len;i++)
37         {
38             if(str[i]!=' ')
39             {
40                 tem[j++]=str[i];
41             }
42             else if(str[i]==' '&&str[i-1]!=' ')
43             {
44                 tem[j++]=0; 
45                 change(tem);
46                 j=0;
47                 memset(tem,0,sizeof(tem));
48                 if(i!=len-1) printf(" ");
49             }
50             else
51                 printf(" ");
52         }
53         printf("
");
54     }
55     return 0;
56 }
57 /**************************************************************
58     Problem: 1095
59     User: 201820222
60     Language: C++
61     Result: 正确
62     Time:1 ms
63     Memory:1120 kb
64 ****************************************************************/

虽然这题一波三折，但是很开心，内存耗时都最短。

问题 H: 回文子串（easy）

题目描述

输入一个字符串，输出该串的最长回文子串长度
子串：在原串中连续出现的字符串片段
(腾讯面试题）

输入

只有一行，包含一个字符串，长度不超过100

输出

输出一个整数，即最长回文子串的长度

样例输入

1abcba2

样例输出

直接分奇偶，暴力解决

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4  
 5 using namespace std;
 6  
 7 int main()
 8 {
 9     char str[100];
10     gets(str);
11     int max=0;
12     for(int i=1;i<strlen(str);i++)
13     {
14         int m=1;
15         for(int j=1;;j++)
16         {
17             if(i-j<0||i+j>strlen(str))
18                 break;
19             else if(str[i-j]==str[i+j])
20                 m+=2;
21             else
22                 break;
23         }
24         if(m>max)
25             max=m;
26     }
27     for(int i=1;i<strlen(str)-1;i++)
28     {
29         if(str[i]!=str[i+1])
30             continue;
31         int m=2;
32         for(int j=1;;j++)
33         {
34             if(i-j<0||i+1+j>strlen(str))
35                 break;
36             else if(str[i-j]==str[i+1+j])
37                 m+=2;
38             else
39                 break;
40         }
41         if(m>max)
42             max=m;
43     }
44     printf("%d
",max);
45     return 0;
46 }

还可以设i，j，从两头遍历，利用reverse，交换i和j中间的字串，存到一个临时的数组中，然后看临时数组和原字符串是否相等，相等此时的j-i+1就应为最大

问题 I: 最长公共子序列

题目描述

给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列，Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？

输入

输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。

输出

对于每组输入，输出两个字符串的最长公共子序列的长度。

样例输入

abcfbc abfcab
programming contest 
abcd mnp

样例输出

4
2
0

这题经典DP，以前看过，不过忘得差不多了，先留着吧，下周复习DP时在看

问题 J: 字符串统计的极限

题目描述

给出一个字符串，仅由大小写字母组成，将其中大写字母按照原始顺序挑出，组成新字符串，输出该串。

输入

一行，字符串。1=<长度<=10000000

输出

纯大写构成的串

样例输入

AAaaBBbb

样例输出

AABB

想法没错，但细节没弄好，不说了，往下看吧，哎

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4  
 5 using namespace std;
 6  
 7 int main()
 8 {
 9     char c;10     c=getchar();
11     while(c!='
')
12     {
13         if(c>='A'&&c<='Z')
14         printf("%c",c);
15         c=getchar();
16     }
17     printf("
");
18     return 0;
19 }
20 /**************************************************************
21     Problem: 4388
22     User: 201820222
23     Language: C++
24     Result: 时间超限
25 ****************************************************************/

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4  
 5 using namespace std;
 6  
 7 int main()
 8 {
 9     char c;
10     while(~scanf("%c",&c))
11     {
12         if(c>='A'&&c<='Z')
13         printf("%c",c);
14     }
15     printf("
");
16     return 0;
17 }
18 /**************************************************************
19     Problem: 4388
20     User: 201820222
21     Language: C++
22     Result: 时间超限
23 ****************************************************************/

最好玩的是下面的，相同的代码，不同的结果。。。。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4  
 5 using namespace std;
 6  
 7 int main()
 8 {
 9     char ch;
10     while((ch=getchar())!=EOF&&ch!='
')
11     {
12         if(ch>='A'&&ch<='Z')
13             printf("%c",ch);
14     }
15     printf("
");
16     return 0;
17 }
18 /**************************************************************
19     Problem: 4388
20     User: 201820222
21     Language: C++
22     Result: 编译错误
23 ****************************************************************/

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4   
 5 using namespace std;
 6   
 7 int main()
 8 {
 9     char ch;
10     while((ch=getchar())!=EOF&&ch!='
')
11     {
12         if(ch>='A'&&ch<='Z')
13             printf("%c",ch);
14     }
15     printf("
");
16     return 0;
17 }
18 /**************************************************************
19     Problem: 4388
20     User: 201820222
21     Language: C++
22     Result: 正确
23     Time:593 ms
24     Memory:1120 kb
25 ****************************************************************/