SHU 2013 暑期集训（7-15）解题报告

Problem A: 【C语言训练】字符串正反连接

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 78 Solved: 41
[Submit][Status][Web Board]

Description

所给字符串正序和反序连接，形成新串并输出

Input

任意字符串（长度<=50）

Output

字符串正序和反序连接所成的新字符串

Sample Input

123abc

Sample Output

123abccba321

HINT

分析：水题，直接正向输出后反向输出。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define maxlen 1100
 5 using namespace std;
 6 char str[maxlen];
 7 int main ()
 8 {
 9     while(gets(str))
10     {
11         int len=strlen(str);
12         for(int i=0;i<len;++i)
13                 printf("%c",str[i]);
14         for(int i=len-1;i>=0;--i)
15              printf("%c",str[i]);
16         printf("
");
17     }
18 }

View Code

Problem B: 【C语言训练】大、小写问题

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 101 Solved: 39
[Submit][Status][Web Board]

Description

输入一串字符,将其中的大写变成小写，若不为大写则原样输出

Input

任意字符串(长度在100以内)以回车表示输入结束

Output

将其中的大写输出相应的小写，若不为大写则原样输出

Sample Input

A123b

Sample Output

a123b

HINT

分析：水题，将大写字母换成小写后输出即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define maxlen 1100
 5 using namespace std;
 6 char str[maxlen];
 7 int main ()
 8 {
 9     while(gets(str))
10     {
11         int len=strlen(str);
12         for(int i=0;i<len;++i)
13         {
14             if(str[i]>='A'&&str[i]<='Z')
15                 printf("%c",str[i]-'A'+'a');
16             else
17                 printf("%c",str[i]);
18         }
19         cout<<endl;
20     }
21 }

View Code

Problem C: 农场的边长

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 95 Solved: 19
[Submit][Status][Web Board]

Description

飞哥最近得到了一大块 n*m 的土地，他想在这块土地上建一个正方形的农场，但是这块土地有些地方被大石头占着，无法使用，于是飞哥想来问你在这块土地上能建成的农场的最大边长为多少？

Input

第一个数T表示数组组数
每组数据一开始有两个整数 n和 m，表示土地的长和宽。
接下来是个 n*m 的矩阵，元素只有 0 和 1 ，0表示这块地方被石头占着。1表示可以使用。

m,n<=1000

Output

对每组数据输出一行，表示农场最大的边长。

Sample Input

1 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1

Sample Output

题目大意：给你一个01矩阵(n*m)问这个矩阵中全部由1填满的正方形最大的边长是多少。

分析：动态规划。dp[i][j]表示以第i行第j列这个位置为右下角满足条件的正方形最大边长，那么方程为

if(maps[i][j]==1) dp[i][j]=min{dp[i-1][j-1],dp[i-1][j],dp[i][j-1]}+1

最后遍历一下dp数组找到最大的就是答案。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define maxlen 1100
 5 using namespace std;
 6 int maps[maxlen][maxlen],dp[maxlen][maxlen];
 7 int Max(int a,int b)
 8 {
 9     return a>b?a:b;
10 }
11 int Min(int a,int b)
12 {
13     return a>b?b:a;
14 }
15 int n,m;
16 bool judge(int x,int y)
17 {
18     if(x>=1&&x<=n&&y>=1&&y<=m)
19         return maps[x][y];
20     return false;
21 }
22 int main ()
23 {
24     int t;
25     scanf("%d",&t);
26     while(t--)
27     {
28         scanf("%d%d",&n,&m);
29         memset(dp,0,sizeof(dp));
30         for(int i=1;i<=n;++i)
31             for(int j=1;j<=m;++j)
32             {
33                 scanf("%d",&maps[i][j]);
34                 if(maps[i][j]==1)
35                     dp[i][j]=1;
36             }
37         int ans=0;
38         for(int i=1;i<=n;++i)
39         {
40             for(int j=1;j<=m;++j)
41             {
42                 if(maps[i][j])
43                 {
44                     dp[i][j]=Min(dp[i-1][j-1],Min(dp[i-1][j],dp[i][j-1]))+1;
45                 }
46                 ans=Max(ans,dp[i][j]);
47             }
48         }
49         printf("%d
",ans);
50     }
51 }

View Code

Problem D: 滑雪(小数据)

Problem E: 滑雪（大数据）

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 22 Solved: 21
[Submit][Status][Web Board]

Description

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

Sample Output

HINT

题目大意：poj1088 http://poj.org/problem?id=1088 给你一个矩阵，你可以从任一点出发向四周走，但要求下一步的值比这一步大，问你最长能走多远。

分析:对于小数据我们可以暴力搜索求解，对于大数据，我们可以记忆化搜索。枚举每个点为起点，深度优先搜索返回最长的长度，最后遍历

求的最大值。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define maxlen 110
 5 using namespace std;
 6 int maps[maxlen][maxlen],dp[maxlen][maxlen];
 7 int xx[]={0,0,1,-1};
 8 int yy[]={1,-1,0,0};
 9 int max(int a,int b)
10 {
11     return a>b?a:b;
12 }
13 int n,m;
14 int dfs(int x,int y)
15 {
16     if(dp[x][y])
17         return dp[x][y];
18     for(int i=0;i<4;++i)
19     {
20 
21         int nextx=x+xx[i];
22         int nexty=y+yy[i];
23         if(nextx>=0&&nextx<n&&nexty>=0&&nexty<m&&maps[nextx][nexty]<maps[x][y])
24         if(dfs(nextx,nexty)+1>dp[x][y])
25             dp[x][y]=dfs(nextx,nexty)+1;
26     }
27     return dp[x][y];
28 }
29 int main ()
30 {
31     while(scanf("%d%d",&n,&m)!=EOF)
32     {
33         for(int i=0;i<n;++i)
34             for(int j=0;j<m;++j)
35                 scanf("%d",&maps[i][j]);
36         int ans=0;
37         memset(dp,0,sizeof(dp));
38         for(int i=0;i<n;++i)
39         {
40             for(int j=0;j<m;++j)
41             {
42                 ans=max(ans,dfs(i,j));
43             }
44         }
45         cout<<ans+1<<endl;
46     }
47 }

View Code

Problem F: 搜索基础练习题1

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 88 Solved: 26
[Submit][Status][Web Board]

Description

一个m*n的矩形区域中有些地方是不能走过的（用1表示，0表示可以走过），走的方向可以沿4个方向走（上、下、左、右），问题很简单，就是给你一个矩形，能否从左上角走到右下角？

Input

有多组数据，每组数据的第一行为一对整数m和n表示矩形的长和宽，接下来是一个m*n的数字矩形，用空格隔开。m,n<=100

Output

每组数据输出一行，如果可以到达，输出Y，否则输出N。

Sample Input

3 3 0 1 1 0 0 1 1 0 0

Sample Output

HINT

题目大意：见上

分析：简单搜索，从（0,0）搜索，标记能到达的点，最后看一下（m，n）是否被标记，对应输出Y/N。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define maxlen 1100
 5 using namespace std;
 6 int maps[maxlen][maxlen],visited[maxlen][maxlen];
 7 int xx[]= {0,0,1,-1};
 8 int yy[]= {1,-1,0,0};
 9 int Max(int a,int b)
10 {
11     return a>b?a:b;
12 }
13 int Min(int a,int b)
14 {
15     return a>b?b:a;
16 }
17 int n,m;
18 bool judge(int x,int y)
19 {
20     if(x<=0||x>m||y<=0||y>n)
21         return false;
22     if(maps[x][y]==1)
23         return false;
24     else
25         return true;
26 }
27 void dfs(int x,int y)
28 {
29 
30     if(!judge(x,y)||visited[x][y])
31         return ;
32     visited[x][y]=1;
33     for(int i=0; i<4; ++i)
34     {
35         int tx=x+xx[i];
36         int ty=y+yy[i];
37         if(!visited[tx][ty])
38         {
39             dfs(tx,ty);
40         }
41     }
42 }
43 int main ()
44 {
45     while(scanf("%d%d",&m,&n)!=EOF)
46     {
47         for(int i=1; i<=m; ++i)
48         {
49             for(int j=1; j<=n; ++j)
50             {
51                 scanf("%d",&maps[i][j]);
52             }
53         }
54         memset(visited,0,sizeof(visited));
55 
56         if(!judge(m,n)||!judge(1,1))
57             printf("N
");
58         else
59         {
60             dfs(1,1);
61             if(visited[m][n])
62                 printf("Y
");
63             else
64                 printf("N
");
65         }
66     }
67 }

View Code

Problem G: VIJOS-P1311

Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 17 Solved: 13
[Submit][Status][Web Board]

Description

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

Input

输入的第一行为一个单独的整数n (n< =20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

Output

只需输出以此字母开头的最长的“龙”的长度

Sample Input

5 at touch cheat choose tact a

Sample Output

HINT

连成的“龙”为atoucheatactactouchoose

题目大意：给你n个字符串，每个字符串最多使用两次，在给你一个首字母，问可以连起来的最长单词长度为多少。

分析:搜索。首先我们先预处理一下，开一个二维数组maps[i][j]表示第i个字符串与第j个字符串匹配的长度(i 的尾部与j的头部)，然后枚举每一个字符串作为开头，深度优先搜索能够达到的最长的长度，取一个最长的就是答案。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <algorithm>
 6 #define maxlen 1100
 7 using namespace std ;
 8 int maps[25][maxlen];
 9 int n;
10 char c;
11 char str[25][maxlen];
12 int visited[25];
13 int dfs(int s)
14 {
15     int ans=0,flag=0;
16     for(int i=0; i<n; i++)
17     {
18         int temp=0;
19         if(maps[s][i]&&visited[i])
20         {
21             flag=1;
22             visited[i]--;
23             temp=dfs(i);
24             visited[i]++;
25             temp+=strlen(str[s])-maps[s][i];
26         }
27         ans=max(ans,temp);
28     }
29     if(!flag)
30         return strlen(str[s]);
31     return ans;
32 }
33 int main()
34 {
35     while(scanf("%d",&n)!=EOF)
36     {
37         for(int i=0; i<n; i++)
38             scanf("%s",str[i]);
39         cin>>c;
40         memset(maps,0,sizeof(maps));
41         for(int i=0; i<n; i++)
42         {
43             for(int j=0; j<n; j++)
44             {
45                 int len1=strlen(str[i]);
46                 int len2=strlen(str[j]);
47                 for(int k=0; k<len1&&k<len2; k++)
48                 {
49                     if(strncmp(str[i]+len1-k-1,str[j],k+1)==0)
50                     {
51                         maps[i][j]=k+1;
52                         break;
53                     }
54                 }
55             }
56         }
57         for(int i=0; i<n; i++)
58             visited[i]=2;
59         int cnt=0;
60         for(int i=0; i<n; i++)
61         {
62             if(str[i][0]==c)
63             {
64                 visited[i]--;
65                 cnt=max(cnt,dfs(i));
66             }
67         }
68         printf("%d
",cnt);
69     }
70 }

View Code