迎接新同學(xué)，不解釋。
試題
2011年9月開(kāi)學(xué)模擬賽（基礎(chǔ)代碼部分）
八進(jìn)制減法
分班
素?cái)?shù)路
冪次方
整數(shù)聯(lián)接
源程序名稱(chēng)
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
測(cè)試點(diǎn)數(shù)
10
10
10
10
10
試題分值
100
100
100
100
100
時(shí)間限制
1秒
1秒
1秒
1秒
1秒
空間限制
30M
30M
30M
30M
30M
1、八進(jìn)制減法（sub.pas/c/cpp）
【問(wèn)題描述】
編寫(xiě)程序，計(jì)算出兩個(gè)200位以?xún)?nèi)的八進(jìn)制相減的差；例如：
123-456=-333
567-123=444
【輸入格式】
共兩行。第一行為被減數(shù)A，第二行為減數(shù)B；
【輸出格式】
共一行：輸出A-B的差。注意，數(shù)字左邊不可有多余的前導(dǎo)0。
【樣例】
樣例1
樣例2
樣例3
sub.in
456
455
12
12
455
456
sub.out
1
0
-1
2、分班（selection.pas/c/cpp）
【問(wèn)題描述】
眾所周知，二中每年高一新生都要分班，設(shè)共有N位學(xué)生參加分班，學(xué)校共有M個(gè)班，那么分班的一種方法是：
（1） 將所有同學(xué)按中考成績(jī)S由高到低排序，成績(jī)相同的學(xué)生，按學(xué)號(hào)SN從小到大排序；
（2） 從1班到M班，按照成績(jī)由高到低“S”型劃分；例如：有3個(gè)班，9名學(xué)生，則分班結(jié)果為：
班級(jí)
成績(jī)排序
1班
第1名 第6名 第7名
2班
第2名 第5名 第8名
3班
第3名 第4名 第9名
現(xiàn)在請(qǐng)你輸出最后的分班結(jié)果。
【輸入格式】
第一行：2個(gè)整數(shù)N、M，分別表示學(xué)生數(shù)和班級(jí)數(shù)；
第二行：N個(gè)整數(shù)，表示學(xué)號(hào)為1~N的學(xué)生中考成績(jī)S；
【輸出格式】
共M行，每i行有若干個(gè)整數(shù)，表示第i班學(xué)生的學(xué)號(hào)，按名次由小到大輸出；
【樣例】
selection.in
9 3
725 724 730 731 728 729 740 736 747
selection.out
9 6 5
7 3 1
8 4 2
【數(shù)據(jù)范圍】
1<=M<=N<=10^5
1<=S<=10^4
3、素?cái)?shù)路（prime.pas/c/cpp）
【問(wèn)題描述】
給定兩個(gè)四位素?cái)?shù)S和T，定義一條從S到T的素?cái)?shù)路為：從S出發(fā)，每次修改其中的一位數(shù)字得到新素?cái)?shù)Pi（不能出現(xiàn)前導(dǎo)零），如果能得到從S到T的素?cái)?shù)序列：S,P1,P2,…,Pk,T，則稱(chēng)這個(gè)序列為一條從S到T的素?cái)?shù)路，上述素?cái)?shù)路的長(zhǎng)度為K+1。
現(xiàn)在給定S和T，如果存在素?cái)?shù)路，請(qǐng)給出最短素?cái)?shù)路的長(zhǎng)度，否則，直接給出信息“Impossible”。
【輸入格式】
共一行。兩個(gè)四位素?cái)?shù)S和T，中間用空格隔開(kāi)。
【輸出格式】
共一行。如果存在從S到T的素?cái)?shù)路，請(qǐng)輸出最短素?cái)?shù)路的長(zhǎng)度；否則輸出“Impossible”（不輸出左右引號(hào)）。
【樣例】
prime.in
1033 8179
prime.out
6
【樣例說(shuō)明】
一條最短的素?cái)?shù)路為：1033 → 1733 → 3733 → 3739 → 3779 → 8779 → 8179
4．冪次方（power.pas/c/cpp）
【問(wèn)題描述】
任何一個(gè)正整數(shù)都可以用2的冪次方表示。例如： 137=27+23+20
同時(shí)約定方次用括號(hào)來(lái)表示，即ab 可表示為a（b）。
由此可知，137可表示為： 2（7）+2（3）+2（0）
進(jìn)一步：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）
【輸入格式】
共一行：正整數(shù)N（n≤20000）
【輸出格式】
共一行：符合約定的n的0，2表示（在表示中不能有空格）
【樣例】
power.in
137
power.out
2(2(2)+2+2(0))+2(2+2(0))+2(0)
附加題：整數(shù)聯(lián)接（link.pas/c/cpp）
【問(wèn)題描述】
設(shè)有n個(gè)正整數(shù)（n≤1000），將它們聯(lián)接成一排，組成一個(gè)最大的多位整數(shù)。
例如：n=3時(shí)，3個(gè)整數(shù)13，312，343聯(lián)接成的最大整數(shù)為：34331213
又如：n=4時(shí)，4個(gè)整數(shù)7，13，4，246聯(lián)接成的最大整數(shù)為：7424613
【輸入格式】
第一行：一個(gè)正整數(shù)n，表示有n個(gè)數(shù)；
第二行：共n個(gè)正整數(shù)（不大于32767）
【輸出格式】
一行：聯(lián)接成的多位數(shù)中最大整數(shù)。
【樣例】
link.in
3
13 312 343
link.out
34331213第一題，高精度加減，我多考慮了輸入為負(fù)的情況，寫(xiě)了一個(gè)小時(shí)。。。（吳天書(shū)也考慮了，結(jié)果寫(xiě)殘了。。。還有悅姐，幾乎花了所有的時(shí)間考慮這個(gè)。。）
第三題，寬搜無(wú)壓力。
第四題，遞歸無(wú)言。
第二題，桶排+鏈表。第二個(gè)鏈表開(kāi)小了。。。wa了兩個(gè)點(diǎn)。
第5題，顯然是排序+貪心，怎么排？
我寫(xiě)的是從高位到低位比較，但對(duì)相等的處理的很模糊，
吳天書(shū) 舉出 76 和7例子，果然會(huì)錯(cuò)，
于是我加了補(bǔ)丁, 用多出來(lái)的第一位與原串的第一位比較，相等再比較第二位 ----> 50分。
吳天書(shū)把段字符串循環(huán)補(bǔ)成等長(zhǎng)，然后比較，70分。
標(biāo)解就是，用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