迎接新同學，不解釋。
試題
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