迎接新同学，不解释。
试题
2011年9月开学模拟赛（基础代码部分）
八进制减法
分班
素数路
幂次方
整数联接
源程序名称
sub
selection
prime
power
link
输入文件
sub.in
selection.in
prime.in
power.in
link.in
输出文件
sub.out
selection.out
prime.out
power.out
link.out
测试点数
10
10
10
10
10
试题分值
100
100
100
100
100
时间限制
1秒
1秒
1秒
1秒
1秒
空间限制
30M
30M
30M
30M
30M
1、八进制减法（sub.pas/c/cpp）
【问题描述】
编写程序，计算出两个200位以内的八进制相减的差；例如：
123-456=-333
567-123=444
【输入格式】
共两行。第一行为被减数A，第二行为减数B；
【输出格式】
共一行：输出A-B的差。注意，数字左边不可有多余的前导0。
【样例】
样例1
样例2
样例3
sub.in
456
455
12
12
455
456
sub.out
1
0
-1
2、分班（selection.pas/c/cpp）
【问题描述】
众所周知，二中每年高一新生都要分班，设共有N位学生参加分班，学校共有M个班，那么分班的一种方法是：
（1） 将所有同学按中考成绩S由高到低排序，成绩相同的学生，按学号SN从小到大排序；
（2） 从1班到M班，按照成绩由高到低“S”型划分；例如：有3个班，9名学生，则分班结果为：
班级
成绩排序
1班
第1名 第6名 第7名
2班
第2名 第5名 第8名
3班
第3名 第4名 第9名
现在请你输出最后的分班结果。
【输入格式】
第一行：2个整数N、M，分别表示学生数和班级数；
第二行：N个整数，表示学号为1~N的学生中考成绩S；
【输出格式】
共M行，每i行有若干个整数，表示第i班学生的学号，按名次由小到大输出；
【样例】
selection.in
9 3
725 724 730 731 728 729 740 736 747
selection.out
9 6 5
7 3 1
8 4 2
【数据范围】
1<=M<=N<=10^5
1<=S<=10^4
3、素数路（prime.pas/c/cpp）
【问题描述】
给定两个四位素数S和T，定义一条从S到T的素数路为：从S出发，每次修改其中的一位数字得到新素数Pi（不能出现前导零），如果能得到从S到T的素数序列：S,P1,P2,…,Pk,T，则称这个序列为一条从S到T的素数路，上述素数路的长度为K+1。
现在给定S和T，如果存在素数路，请给出最短素数路的长度，否则，直接给出信息“Impossible”。
【输入格式】
共一行。两个四位素数S和T，中间用空格隔开。
【输出格式】
共一行。如果存在从S到T的素数路，请输出最短素数路的长度；否则输出“Impossible”（不输出左右引号）。
【样例】
prime.in
1033 8179
prime.out
6
【样例说明】
一条最短的素数路为：1033 → 1733 → 3733 → 3739 → 3779 → 8779 → 8179
4．幂次方（power.pas/c/cpp）
【问题描述】
任何一个正整数都可以用2的幂次方表示。例如： 137=27+23+20
同时约定方次用括号来表示，即ab 可表示为a（b）。
由此可知，137可表示为： 2（7）+2（3）+2（0）
进一步：7= 22+2+20 （21用2表示）
3=2+20
所以最后137可表示为：
2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：
1315=210 +28 +25 +2+1
所以1315最后可表示为：
2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
【输入格式】
共一行：正整数N（n≤20000）
【输出格式】
共一行：符合约定的n的0，2表示（在表示中不能有空格）
【样例】
power.in
137
power.out
2(2(2)+2+2(0))+2(2+2(0))+2(0)
附加题：整数联接（link.pas/c/cpp）
【问题描述】
设有n个正整数（n≤1000），将它们联接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213
又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613
【输入格式】
第一行：一个正整数n，表示有n个数；
第二行：共n个正整数（不大于32767）
【输出格式】
一行：联接成的多位数中最大整数。
【样例】
link.in
3
13 312 343
link.out
34331213第一题，高精度加减，我多考虑了输入为负的情况，写了一个小时。。。（吴天书也考虑了，结果写残了。。。还有悦姐，几乎花了所有的时间考虑这个。。）
第三题，宽搜无压力。
第四题，递归无言。
第二题，桶排+链表。第二个链表开小了。。。wa了两个点。
第5题，显然是排序+贪心，怎么排？
我写的是从高位到低位比较，但对相等的处理的很模糊，
吴天书 举出 76 和7例子，果然会错，
于是我加了补丁, 用多出来的第一位与原串的第一位比较，相等再比较第二位 ----> 50分。
吴天书把段字符串循环补成等长，然后比较，70分。
标解就是，用a接b和b接a比较，再排序。。。
比较难想。
AC代码：
sub
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 inline void change(char &a,char &b)
5 {a^=b;b^=a;a^=b;}
6 int main()
7 {
8 bool ax=0,bx=1,anx=0;//0:+ 1:-
9 int al,bl,ansl;
10 char ac[256],bc[256];
11 char ans[256];
12 memset(ans,0,sizeof(ans));
13 freopen("sub.in","r",stdin);
14 freopen("sub.out","w",stdout);
15 scanf("%s\n",ac);
16 scanf("%s\n",bc);
17 al=strlen(ac);
18 bl=strlen(bc);
19 //
20 if(ac[0]=='-')
21 {
22 ax^=1;
23 for(int i=1;i<=al-1;i++)
24 ac[i-1]=ac[i];
25 al--;
26 }
27 if(bc[0]=='-')
28 {
29 bx^=1;
30 for(int i=1;i<=bl-1;i++)
31 bc[i-1]=bc[i];
32 bl--;
33 }
34 //
35 for(int i=0;i<=al-1;i++)
36 ac[i]-='0';
37 for(int i=0;i<=bl-1;i++)
38 bc[i]-='0';
39 //
40 for(int i=0;i<=al/2-1;i++)
41 change(ac[i],ac[al-i-1]);
42 for(int i=0;i<=bl/2-1;i++)
43 change(bc[i],bc[bl-i-1]);
44 //
45 if(ax==bx)// same
46 {
47 ansl=al>bl?al:bl;
48 for(int i=0;i<=al-1;i++)
49 {
50 ans[i]+=ac[i];
51 ans[i+1]+=ans[i]/8;
52 ans[i]%=8;
53 }
54 for(int i=0;i<=bl-1;i++)
55 {
56 ans[i]+=bc[i];
57 ans[i+1]+=ans[i]/8;
58 ans[i]%=8;
59 }
60 for(int i=bl;i<=ansl-1;i++)
61 {
62 ans[i+1]+=ans[i]/8;
63 ans[i]%=8;
64 }
65 if(ans[ansl]>0)
66 ansl++;
67 if(ax)
68 printf("-");
69 for(int j=ansl-1;j>=0;j--)
70 printf("%d",ans[j]);
71 }
72 else
73 {
74 if(ax)//-/+
75 {
76 if(al>bl)
77 anx=1;
78 else if(bl>al)
79 anx=0;
80 else for(int i=al-1;i>=0;i--)
81 if(ac[i]>bc[i])
82 {anx=1;break;}
83 else if(ac[i]<bc[i])
84 {anx=0;break;}
85 if(anx)//anx=1 a>b -
86 {
87 ansl=al;
88 for(int i=0;i<=ansl-1;i++)
89 {
90 ans[i]+=ac[i];
91 ans[i+1]+=ans[i]/8;
92 ans[i]%=8;
93 }
94 for(int i=0;i<=bl-1;i++)
95 {
96 ans[i]-=bc[i];
97 if(ans[i]<0)
98 {
99 ans[i+1]--;
100 ans[i]+=8;
101 }
102 }
103 while(ans[ansl-1]==0&&ansl>=1)
104 ansl--;
105 if(ansl==0)
106 printf("%d",0);
107 else{
108 printf("-");
109 for(int j=ansl-1;j>=0;j--)
110 printf("%d",ans[j]);
111 }
112 }
113 else
114 {
115 ansl=bl;
116 for(int i=0;i<=ansl-1;i++)
117 {
118 ans[i]+=bc[i];
119 ans[i+1]+=ans[i]/8;
120 ans[i]%=8;
121 }
122 for(int i=0;i<=al-1;i++)
123 {
124 ans[i]-=ac[i];
125 if(ans[i]<0)
126 {
127 ans[i+1]--;
128 ans[i]+=8;
129 }
130 }
131 while(ans[ansl-1]==0&&ansl>=1)
132 ansl--;
133 if(ansl==0)
134 printf("%d",0);
135 else{
136 for(int j=ansl-1;j>=0;j--)
137 printf("%d",ans[j]);
138 }
139 }
140 }
141 else//a+ b-
142 {
143 if(al>bl)
144 anx=1;
145 else if(bl>al)
146 anx=0;
147 else for(int i=al-1;i>=0;i--)
148 if(ac[i]>bc[i])
149 {anx=1;break;}
150 else if(ac[i]<bc[i])
151 {anx=0;break;}
152 if(anx)//anx=1
153 {
154 ansl=al;
155 for(int i=0;i<=ansl-1;i++)
156 {
157 ans[i]+=ac[i];
158 ans[i+1]+=ans[i]/8;
159 ans[i]%=8;
160 }
161 for(int i=0;i<=bl-1;i++)
162 {
163 ans[i]-=bc[i];
164 if(ans[i]<0)
165 {
166 ans[i+1]--;
167 ans[i]+=8;
168 }
169 }
170 while(ans[ansl-1]==0&&ansl>=1)
171 ansl--;
172 if(ansl==0)
173 printf("%d",0);
174 else{
175 for(int j=ansl-1;j>=0;j--)
176 printf("%d",ans[j]);
177 }
178 }
179 else
180 {
181 ansl=bl;
182 for(int i=0;i<=ansl-1;i++)
183 {
184 ans[i]+=bc[i];
185 ans[i+1]+=ans[i]/8;
186 ans[i]%=8;
187 }
188 for(int i=0;i<=al-1;i++)
189 {
190 ans[i]-=ac[i];
191 if(ans[i]<0)
192 {
193 ans[i+1]--;
194 ans[i]+=8;
195 }
196 }
197 while(ans[ansl-1]==0&&ansl>=1)
198 ansl--;
199 if(ansl==0)
200 printf("%d",0);
201 else{
202 printf("-");
203 for(int j=ansl-1;j>=0;j--)
204 printf("%d",ans[j]);
205 }
206 }
207 }
208 }
209 return 0;
210 }
211 selection
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 const int maxn=10001,maxm=100001;
5 int n,m,t,now,x;
6 int head[maxn];
7 int tail[maxn];
8 int to[maxm];
9 int To[maxm];
10 int Class[maxm];
11 int end[maxm];
12 int main()
13 {
14 freopen("selection.in","r",stdin);
15 freopen("selection.out","w",stdout);
16 memset(head,0,sizeof(head));
17 memset(tail,0,sizeof(tail));
18 memset(to,0,sizeof(to));
19 memset(To,0,sizeof(To));
20 memset(Class,0,sizeof(Class));
21 scanf("%d %d",&n,&m);
22 for(int i=1;i<=n;i++)
23 {
24 scanf("%d",&t);
25 if(head[t]==0)
26 head[t]=i;
27 to[tail[t]]=i;
28 tail[t]=i;
29 }
30 t=1;x=1;//1+ 0-
31 for(int i=maxn-1;i>=1;i--)
32 if(head[i])
33 for(int j=head[i];j!=0;j=to[j])
34 {
35 if(Class[t]==0)
36 Class[t]=j;
37 To[end[t]]=j;
38 end[t]=j;
39 if(t==1&&x==0){x=1;}
40 else if(t==m&&x==1){x=0;}
41 else if(x)t++;
42 else t--;
43 }
44 for(int i=1;i<=m;i++)
45 {
46 for(int j=Class[i];j!=0;j=To[j])
47 printf("%d ",j);
48 printf("\n");
49 }
50 return 0;
51 }
52 prime
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 bool p[10001];
5 int Queue[10001],Tail=1,Head=1;
6 int num[10001];
7 int t,goal;
8 int main()
9 {
10 freopen("prime.in","r",stdin);
11 freopen("prime.out","w",stdout);
12 memset(p,true,sizeof(p));
13 scanf("%d %d",&Queue[Head],&goal);
14 p[0]=p[1]=false;
15 for(int i=2;i<=10000;i++)
16 if(p[i])
17 for(int j=i*2;j<=10000;j+=i)
18 p[j]=false;
19 num[Head]=0;
20 p[Queue[Head]]=false;
21 while(Tail>=Head)
22 {
23 if(Queue[Head]==goal)
24 break;
25 // printf("%d ",Queue[Head]);
26 //first can't be 0!!!
27 for(int i=1;i<=9;i++)
28 {
29 t=i*1000+Queue[Head]%1000;
30 if(p[t])
31 {
32 Tail++;
33 Queue[Tail]=t;
34 num[Tail]=num[Head]+1;
35 p[t]=false;
36 }
37 }
38 //
39 for(int i=0;i<=9;i++)
40 {
41 t=i*100+Queue[Head]%100+(Queue[Head]/1000)*1000;
42 if(p[t])
43 {
44 Tail++;
45 Queue[Tail]=t;
46 num[Tail]=num[Head]+1;
47 p[t]=false;
48 }
49 }
50 //
51 for(int i=0;i<=9;i++)
52 {
53 t=i*10+Queue[Head]%10+(Queue[Head]/100)*100;
54 if(p[t])
55 {
56 Tail++;
57 Queue[Tail]=t;
58 num[Tail]=num[Head]+1;
59 p[t]=false;
60 }
61 }
62 //
63 for(int i=0;i<=9;i++)
64 {
65 t=i+(Queue[Head]/10)*10;
66 if(p[t])
67 {
68 Tail++;
69 Queue[Tail]=t;
70 num[Tail]=num[Head]+1;
71 p[t]=false;
72 }
73 }
74 Head++;
75 }
76 if(Queue[Head]==goal)
77 printf("%d",num[Head]);
78 else
79 printf("Impossible");
80 return 0;
81 }
82 power
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 void work(int t);
5 int main()
6 {
7 freopen("power.in","r",stdin);
8 freopen("power.out","w",stdout);
9 int n;
10 scanf("%d",&n);
11 work(n);
12 return 0;
13 }
14 void work(int t)
15 {
16 // printf("(%d)",t); system("pause");
17 int q=0;
18 if(t==0)
19 {
20 printf("2(0)");
21 return;
22 }
23 if(t==1)
24 {
25 printf("2");
26 return;
27 }
28 for(int i=15;i>=0;i--)
29 if(t&(1<<i))
30 {
31 if(q)printf("+");
32 if(i!=1&&i!=0)
33 printf("2(");
34 work(i);
35 if(i!=1&&i!=0)
36 printf(")");
37 q=1;
38 }
39 return;
40 }
41 link
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 int n,maxl;
5 char a[1001][20],t[20];
6 bool cmp(char a[],char b[]);
7 int main()
8 {
9 freopen("link.in","r",stdin);
10 freopen("link.out","w",stdout);
11 scanf("%d",&n);
12 for(int i=1;i<=n;i++)
13 scanf("%s",a[i]);
14 for(int i=1;i<=n;i++)
15 for(int j=i+1;j<=n;j++)
16 if(cmp(a[j],a[i])){
17 strcpy(t,a[i]);
18 strcpy(a[i],a[j]);
19 strcpy(a[j],t);
20 }
21 for(int i=1;i<=n;i++)
22 printf("%s",a[i]);
23 return 0;
24 }
25 bool cmp(char a[],char b[])
26 {
27 int al=strlen(a),bl=strlen(b);
28 char c1[20],c2[20];
29 for(int i=0;i<=al-1;i++)
30 c1[i]=c2[i+bl]=a[i];
31 for(int i=0;i<=bl-1;i++)
32 c2[i]=c1[i+al]=b[i];
33 for(int i=0;i<=al+bl-1;i++)
34 if(c1[i]>c2[i])
35 return true;
36 else if(c1[i]<c2[i])
37 return false;
38 return false;
39 }
40