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

来补解题报告。

Problem A: 【C语言训练】求具有abcd=(ab+cd)^2性质的四位数
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 37 Solved: 37
[Submit][Status][Web Board]
Description
3025这个数具有一种独特的性质：将它平分为二段，即30和25，使之相加后求平方，即(30+25)2，恰好等于3025本身。请求出具有这样性质的全部四位数

Input
Output
满足题意的数全部四位数(从小到大输出,且数之间用两个空格分开)
Sample Input
Sample Output
2025 3025 9801
HINT
根据题意可以采用穷举法，对所有四位数进行判断，从而筛选出符合这种性质的四位数。具体算法实现，可任取一个四位数，将其截为两部分，前两位为a，后两位为b，然后套用公式计算并判断。

[Submit][Status][Web Board]

不写了，答案就是样例上面的了。

Problem B: VIJOS-P1237
Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 101 Solved: 12
[Submit][Status][Web Board]
Description
天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例，就越完美。现在天使给了小杉N只翅膀，小杉想挑出一对最完美的。
Input
每组测试数据的第一行有一个数N(2< =N< =30000) 第二行有N个不超过1e5的正整数，表示N只翅膀的长度。 20%的数据N< =100
Output
对每组测试数据输出两个整数，表示小杉挑选出来的一对翅膀。注意，比较短的在前，如果有多对翅膀的完美程度一样，请输出最小的一对。
Sample Input
4
2 3 4 6
Sample Output
2
3
HINT
你可以认为黄金分割比就是0.6180339887498949

题目大意：不用多说，给你n个数，要求挑出两个数使得两者之比最接近黄金分割。

分析：首先当然要按大小先排个序，然后维护一个最接近黄金比例的结果就可以了，采用类似于二分的思想。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 #define st 0.6180339887498949
 7 #define maxlen 30010
 8 using namespace std;
 9 int num[maxlen];
10 double myabs(double x)
11 {
12     return x<0?-x:x;
13 }
14 int main()
15 {
16     int n;
17     while(scanf("%d",&n)!=EOF)
18     {
19         int s=1,e=2;
20         double minc=1000;
21         int mina,minb;
22         for (int i=1; i<=n; i++)
23             scanf("%d",&num[i]);
24         sort(num,num+n);
25         while(e<=n)
26         {
27             if (myabs(num[s]*1.0/num[e]-st)<minc)
28             {
29                 mina=num[s];
30                 minb=num[e];
31                 minc=myabs(num[s]*1.0/num[e]-st);
32             }
33             if (myabs(num[s]*1.0/num[e])<st)
34                 s++;
35             else
36                 e++;
37         }
38         printf("%d\n%d\n",mina,minb);
39     }
40     return 0;
41 }

View Code

Problem C: 多项式构造问题
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 58 Solved: 14
[Submit][Status][Web Board]
Description
给你 9个整数，分别是 x的 8次方至次方至 0次方的系数，请按照多项式一般形合理地构造。规则如下：
1. 多项式的必须按其指数从高到低排列
2. 指数必须跟在符号“ ^”后显示
3. 有常数的只显示常数项
4. 只显示系数不为 0的项；系数全 0，需显示常数项
5. 项与间的加号或减两边需上空格
6. 首项是正系数，其前不加符号否则负与间空格
7. 负系数的项
要显示成减一个正8. 系数是 1，指数为 0时，系数的 1才显示。

Input
有若干个行，每一上9个系数，间有空格隔开的绝对值为小于 1000的整数。

Output
对输入中的每一行系数，出应多项式个。

Sample Input
0 0 0 1 22 –333 0 1 –1
0 0 0 0 0 0 –55 5 0
Sample Output
x^5 + 22x^4 – 333x^3 + x – 1
-55x^2 + 5x

分析：纯模拟题，就是细节比较多，需要注意一下。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int a[10];
 6 void Print()
 7 {
 8     int j=0;
 9     while (a[j]==0 && j<8)
10         ++j;
11     bool flag=false;
12     if (j==8)
13         flag=true;
14     if (j!=8)
15     {
16         if (a[j]<0)
17         {
18             printf("-");
19             a[j]*=-1;
20         }
21         if (a[j]>1)
22         {
23             if (j<7) printf("%dx^%d",a[j],8-j);
24             if (j==7) printf("%dx",a[j]);
25         }
26         else
27         {
28             if (j<7) printf("x^%d",8-j);
29             if (j==7) printf("x");
30         }
31     }
32     if (j!=8) ++j;
33     while (j<8)
34     {
35         while (a[j]==0)
36             ++j;
37         if (j>=8) break;
38         printf(" ");
39         if (a[j]>0)
40             printf("+ ");
41         else
42         {
43             printf("- ");
44             a[j]*=-1;
45         }
46         if (a[j]>1)
47         {
48             if (j<7)
49                 printf("%dx^%d",a[j],8-j);
50             if (j==7)
51                 printf("%dx",a[j]);
52         }
53         else
54         {
55             if (j<7)
56                 printf("x^%d",8-j);
57             if (j==7)
58                 printf("x");
59         }
60         ++j;
61     }
62     if (a[j]!=0)
63     {
64         if (!flag)
65             printf(" ");
66         if (!flag && a[j]>0)
67             printf("+");
68         if (a[j]<0)
69         {
70             printf("-");
71             a[j]*=-1;
72         }
73         if (!flag) printf(" ");
74         printf("%d",a[j]);
75     }
76     else if (flag)
77         printf("0");
78     printf("\n");
79 }
80  
81 int main()
82 {
83     while (scanf("%d",&a[0])!=EOF)
84     {
85         for(int i=1;i<9;++i)
86         scanf("%d",&a[i]);
87         Print();
88     }
89 }

View Code

Problem D: 三角迷宫
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 22 Solved: 12
[Submit][Status][Web Board]
Description
这里有45个数字组成的一个三角阵，数字分别是1、2、3、...、9不等。要求你每次从顶点A处开始，一步步地通过它相邻的数字走到对边为止：但是一定要全部通过1，2，3,....,9这些数字，缺一不可，顺序不限，也不得重复，更不许走回头路。
A 1
3 6
9 7 8
2 6 3 9
3 1 5 8 5
5 9 4 6 3 2
8 3 2 9 4 9 1
6 5 7 4 1 2 8 7
7 1 4 8 7 4 5 6 2
对上述三角迷宫，我们可以找到一条路线，A 处：139654278。你能找出这一条路线来吗？

Input
输入有若干组测试数据，其第一行是整数n，表示三角迷宫的个数。接着有n 组测试数据，每一组是一个三角迷宫的描述，共9 行，第i 行上有i 个1 到9 之间的数字符号，i=1，2，„，9，每行上的数字符号之间有一个空格。两个三角迷宫之间有一个空行。

Output
对输入中描述的每组三角迷宫，确定从顶点A 出发，可否一步步地通过它相邻的数字走到对边为止，使路径上包含1，2，3„9 这全部9 个数字，顺序不限，不要重复，不许走回头路。先输出“Case#:”，其中“#”是三角迷宫的组号。如果从该顶点出发，可以确定这样的路线，则在下一行上输出“Possible”，否则输出“Impossible”。

Sample Input
2
1
3 6
9 7 8
2 6 3 9
3 1 5 8 5
5 9 4 6 3 2
8 3 2 9 4 9 1
6 5 7 4 1 2 8 7
7 1 4 8 7 4 5 6 2

4
3 6
9 7 8
2 6 3 9
3 1 5 8 5
5 9 4 6 3 2
8 3 2 9 4 9 1
6 5 7 4 1 2 8 7
7 1 4 8 7 4 5 6 2
Sample Output
Case 1:
Possible
Case 2:
Impossible
HINT

题目大意：从最顶端开始向下走，每次只能走当前位置相邻的位置么不能往回走，问能不能走过所有的9个数字（1-9）

分析：训练的时候没有写这个题目，应该就是深搜下去，递归到最后一层的时候判断一下9个数字是不是都走过来。状态数量不多。

Problem E: 分型Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 29 Solved: 9
[Submit][Status][Web Board]
Description
分形在一定的技术意义上说，是在所有标度显示自相似性的一个对象或数量。对象不必在所有标度上展示完全相同的结构，但在所有标度上显示同样的结构“类型”。
分型块的定义如下：
次数是1的分型块只是：
X
次数2的分型块是：
X X
X
X X
如果利用B(n-1)表示次数是n-1的分型块，那么次数是n的分型块递归定义如下：
B(n-1) B(n-1)
B(n-1)
B(n-1) B(n-1)
你的任务是画一个次数是n的分型块。
Input
输入有多组测试数据。每行有一个不大于7的正整数n 。最后一行的一个负整数-1表示输入结束。
Output
对每组测试数据，输出用大写字母‘X’标记的分型块。每组测试数据后输出一个破折号。尾部无多余空格。
Sample Input
1
2
-1
Sample Output
X
-
X X
X
X X
-
HINT

题目大意:没什么好说的，打印图形。

分析：题目已经给提示需要进行分治，把图形分为5各部分，每个部分都是一样的，递归到下一层，一直到规模只有1时直接打印即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define  maxlen 3000
 5 using namespace std;
 6 char maps[maxlen][maxlen];
 7 int mypow(int x,int n)
 8 {
 9     int ans=1;
10     for(int i=0; i<n; ++i)
11     {
12         ans*=x;
13     }
14     return ans;
15 }
16 void Print(int x,int y ,int s)
17 {
18     if(s==1)
19     {
20         maps[x][y]='X';
21         return ;
22     }
23     int k=mypow(3,s-2);
24     Print(x,y,s-1);
25     Print(x,y+k*2,s-1);
26     Print(x+k,y+k,s-1);
27     Print(x+2*k,y,s-1);
28     Print(x+2*k,y+2*k,s-1);
29 }
30 int main ()
31 {
32     int n;
33     while(scanf("%d",&n)!=EOF)
34     {
35         if(n==-1)
36             break;
37         memset(maps,' ',sizeof(maps));
38         int k=mypow(3,n-1);
39         Print(0,0,n);
40         for(int i=0; i<k; ++i)
41         {
42             int pos;
43             for(pos=k-1;pos>=0;--pos)
44             {
45                 if(maps[i][pos]=='X')
46                     break;
47             }
48             for(int j=0;j<=pos;++j)
49                 cout<<maps[i][j];
50             cout<<endl;
51 
52         }
53         printf("-\n");
54     }
55 }

View Code

Problem F: 无向图的连通分支
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 24 Solved: 15
[Submit][Status][Web Board]
Description
输入一个无向图G，计算G的连通分支数。

Input
有多个无向图数据。每个无向描述的第1行是两个整数n和e，分别表示顶点数和边数。接着有e行，每行有2个整数a、b，分别是一条边的两个端点（起点和终点）。两个图之间空一行。

Output
对每个无向图，输出图中连通分支个数。

Sample Input
2 1
1 2

5 8
1 2
1 3
1 4
1 5
2 3
2 4
3 4
4 5
Sample Output
1
1
HINT

题目大意：求无向图连通分支数。

分析：枚举每个没有搜索过的顶点（没枚举一个计数器+1），dfs搜索整个图，标记搜索过的结点，最后输出答案就可以了。

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

View Code

Problem G: 奇异的结构
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 14 Solved: 9
[Submit][Status][Web Board]
Description
设k³0。有0、1序列组成的2k×2k阵列表示的图像，其中用0表示白，用1表示黑。

图12 0-1阵列图像

现在通过如下方式对黑白图像进行分割，构造一棵四叉树：

黑白图象划分

（1）如子图像不是全白或全黑，将它分割为四等分。

（2）从左上、右上、左下、右下依次对各子图像依次进行编号。

四叉树构造

（1）树中叶结点由白色或黑色标记。

（2）非叶子结点的四个子结点的顺序依次为左上、右上、左下、右下。

（3）四叉树由表示从黑叶结点到根结点路径的数字序列表示。

（4）每条路径是一个5进制数。

图12- 四叉树及结点编号

首先看图12- （A）的0-1图像。由于图像不全白也不全黑，因此进行分割，分成左上、右上、左下、右下四个部分。由于左上部分已是全白的，不必再分割。对右上部分需再分割成四小部分。此时这四小部分均已无法分割。再对其它部分进行处理。现在看结点情况，右上部分经第二次分割后的左下角的结点，其编号应为32，在四叉树中对应的结点为4号。

4号结点对应的五进制数为(32)5=(17)10；12号结点对应的五进制数为(43)5=(23)10；

15号结点对应的五进制数为(134)5=(44)10

四叉树中黑结点共11个，这些黑结点对应的十进制表示为：9、14、17、22、23、44、63、69、88、94、113。这也称为图像的十进制表示。

现在你的任务是根据一个0-1图像，求图像的十进制表示；反过来，根据图像的十进制表示，求对应的0-1图像。

Input
有多组测试数据。每组的第1行是一个整数n，n可正可负，其绝对值m是2的幂。如n为正，那么接下来有n行，每行有n个0或1构成的字符串，这些表示一个0-1图像。如果n为负数，那么下面有若干以-1结尾的整数，前面的整数均为非负整数，表示图像的十进制表示。当n=0时表示输入结束。

Output
对每组测试数据，先输出测试数据编号（从1开始）。在接下来的行上，如果是一个0-1图像，那么以升序方式输出对应图像的十进制表示；如果输入是图像的十进制表示，那么输出图像的0-1表示。

Sample Input
8
00000000
00000000
00001111
00001111
00011111
00111111
00111100
00111000
-8
9 14 17 22 23 44 63 69 88 94 113 -1
2
00
00
-4
0 -1
0
Sample Output
Case 1
9 14 17 22 23 44 63 69 88 94 113
Case 2
00000000
00000000
00001111
00001111
00011111
00111111
00111100
00111000
Case 3

Case 4
1111
1111
1111
1111
HINT

题目大意：事实上就是一种编码的方式，给你图像要求你进行编码，给你编码，让你还原出图像。

分析：根据题目的说明，编码过程就是将图像分割的过程，全白为0，全黑为1，否则继续分治，最后构造一个叉树进行编码。

移码的过程就是将10进制的数转化为5进制然后倒过来生成图像。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define  maxlen 3000
  6 using namespace std;
  7 char maps[maxlen][maxlen];
  8 int num[maxlen];
  9 int n,m;
 10 int mypow(int x,int n)
 11 {
 12     int ans=1;
 13     for(int i=0; i<n; ++i)
 14     {
 15         ans*=x;
 16     }
 17     return ans;
 18 }
 19 void Display()
 20 {
 21     for(int i=0; i<n; ++i)
 22     {
 23         for(int j=0; j<n; ++j)
 24         {
 25             cout<<maps[i][j];
 26         }
 27         cout<<endl;
 28     }
 29 }
 30 void Dis()
 31 {
 32     for(int i=0; i<m; ++i)
 33     {
 34         if(i==m-1)
 35             cout<<num[i];
 36         else
 37             cout<<num[i]<<" ";
 38     }
 39     cout<<endl;
 40 }
 41 bool judgew(int x,int y,int s)
 42 {
 43     for(int i=x; i<x+s; ++i)
 44     {
 45         for(int j=y; j<y+s; ++j)
 46         {
 47             if(maps[i][j]!='0')
 48                 return false;
 49         }
 50     }
 51     return true;
 52 }
 53 bool judgeb(int x,int y,int s)
 54 {
 55     for(int i=x; i<x+s; ++i)
 56     {
 57         for(int j=y; j<y+s; ++j)
 58         {
 59             if(maps[i][j]!='1')
 60                 return false;
 61         }
 62     }
 63     return true;
 64 }
 65 void d2g(int x,int y,int d,int s)
 66 {
 67     if(d==0)
 68     {
 69         for(int i=x; i<x+s; ++i)
 70         {
 71             for(int j=y; j<y+s; ++j)
 72                 maps[i][j]='1';
 73         }
 74     }
 75     int k=d%5;
 76     d/=5;
 77     s/=2;
 78     if(k==1)
 79         d2g(x,y,d,s);
 80     else if(k==2)
 81         d2g(x,y+s,d,s);
 82     else if(k==3)
 83         d2g(x+s,y,d,s);
 84     else if(k==4)
 85         d2g(x+s,y+s,d,s);
 86 }
 87 void g2d(int k,int x,int y,int d,int s)
 88 {
 89     int sum=1;
 90     if(judgew(x,y,s))
 91         return ;
 92     if(judgeb(x,y,s))
 93         num[m++]=d;
 94     else
 95     {
 96         sum=mypow(5,k);
 97         s=s/2;
 98         g2d(k+1,x,y,d+sum*1,s);
 99         g2d(k+1,x,y+s,d+sum*2,s);
100         g2d(k+1,x+s,y,d+sum*3,s);
101         g2d(k+1,x+s,y+s,d+sum*4,s);
102     }
103 }
104 int main ()
105 {
106     int Case=1;
107     while(scanf("%d",&n)!=EOF)
108     {
109         if(n==0)
110             break;
111         memset(num,0,sizeof(num));
112         memset(maps,0,sizeof(maps));
113         if(n>0)
114         {
115             for(int i=0; i<n; ++i)
116                 for(int j=0; j<n; ++j)
117                     cin>>maps[i][j];
118             m=0;
119             g2d(0,0,0,0,n);
120             sort(num,num+m);
121             printf("Case %d\n",Case++);
122             Dis();
123         }
124         else if(n<0)
125         {
126             n=-n;
127             m=0;
128             int a;
129             for(int i=0; i<n; ++i)
130             {
131                 for(int j=0; j<n; ++j)
132                     maps[i][j]='0';
133             }
134             while(cin>>a)
135             {
136                 if(a==-1)
137                     break;
138                 num[m++]=a;
139                 d2g(0,0,a,n);
140             }
141             printf("Case %d\n",Case++);
142             Display();
143         }
144     }
145 }

View Code

Problem H: Fibonacci数列
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 69 Solved: 20
[Submit][Status][Web Board]
Description
Fibonacci数列的前两项均为1。从第3项起，各项均为其前2项的和，如1, 1, 2, 3, 5, 8, 13, 21, 34, 55，…。给定一个十进制正整数n，计算Fibonacci数列的第n项。
Input
输入数据有若干行，每行上有一个正整数n，（0<n<5000）。
Output
对于输入中每一个正整数n，直接输出一行结果。
Sample Input
2
15
25
Sample Output
1
610
75025
HINT

分析：大数高精度，直接使用大数的模板，这个模板很渣。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define  maxlen 5010
 5 using namespace std;
 6 class  bignum
 7 {
 8     private :
 9         int len;
10         int s[1100];
11     public:
12     bignum()
13     {
14         memset(s,0,sizeof(s));
15         len=1;
16     }
17     bignum(int num)
18     {
19         *this=num;
20     }
21     bignum(const char *num)
22     {
23         *this=num;
24     }
25     bignum operator=(const char *num)
26     {
27         len=strlen(num);
28         for(int i=0;i<len;i++)
29             s[i]=num[len-i-1]-'0';
30         return *this;
31     }
32     bignum operator=(int num)
33     {
34         char s[maxlen];
35         sprintf (s,"%d",num);// int to char
36         *this=s;
37         return *this;
38     }
39     string str()const
40     {
41         string res="";
42         for(int i=0;i<len;i++)
43         res=(char)(s[i]+'0')+res;
44         if(res=="")
45         res="0";
46         return res;
47     }
48     bignum operator +(const bignum &b)const
49     {
50         bignum c;
51         c.len=0;
52         for(int i=0,g=0;g||i<max(len,b.len);i++)
53         {
54             int x=g;
55             if(i<len)
56                 x+=s[i];
57             if(i<b.len)
58                 x+=b.s[i];
59             c.s[c.len++]=x%10;
60             g=x/10;
61         }
62         return c;
63     }
64 };
65 istream & operator>>(istream &in,bignum & x)
66 {
67     string s;
68     in>>s;
69     x=s.c_str();
70     return in;
71 }
72 ostream& operator <<(ostream &out,const bignum &x)
73 {
74     out<<x.str();
75     return out;
76 }
77 bignum f[maxlen]={1,1,2};
78 int main ()
79 {
80     for(int i=3;i<=5000;++i)
81         f[i]=f[i-1]+f[i-2];
82     int n;
83     int Case=1;
84     while(scanf("%d",&n)!=EOF)
85     {
86         cout<<f[n-1]<<endl;
87     }
88 }

View Code

优质内容筛选与推荐>>
1、整数快速幂（取模）、矩阵快速幂及其应用
2、SSM框架、Druid连接池实现多数据源配置（已上线使用）
3、八种基本数据类型的大小，以及他们的封装类
4、(三)：mongodb库表基本操作语句
5、JVM调优2

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看