2012百度之星资格赛试题与AC代码合集
百度文库下载地址： http://wenku.baidu.com/view/39d92648852458fb770b5616.html 2012百度之星资格赛试题与AC代码
A:百度计算器的加法
时间限制: 1000ms 内存限制: 10000kB
描述
百度框计算中提供了计算器这个功能，模拟计算器中的复杂功能，我们最先需要解决的就是实现加法模块。今天就给你个机会，和百度计算器一样，计算一下十以内的加法吧。
输入
仅有一组数据，包含两个正整数，分别为a, b(0 <= a, b <= 10)
输出
一个正整数，暨输入a, b后对应的a+b的计算结果
1 #include <stdio.h>
2
3 #include <stdlib.h>
4
5 /*
6
7 author tilltheendwjx
8
9 blog http://blog.csdn.net/wjh200821 或者http://www.cnblogs.com/tilltheendwjx/
10
11 */
12
13 int main()
14
15 {
16
17 int a,b;
18
19 scanf( " %d%d " ,&a,& b);
20
21 printf( " %d " ,a+ b);
22
23 // system("pause");
24
25 return 0 ;
26
27 }
B:小诺爱USB设备
时间限制: 1000ms 内存限制: 65536kB
描述
在百度工作的小诺是一个USB设备迷，在他桌上有一堆的USB设备——USB鼠标、USB小音箱、USB按摩器……但是，公司配给小诺的ThinkPad X系列的电脑只有一个能用的USB接口。不过还好，小诺有一堆的USB Hub，可以把一个可用的USB接口变成多个USB接口。但是，小诺很难确定这些USB Hub能否满足他他众多的USB设备的需求。
输入
输入首行包括一个整数N（1 ≤ N ≤ 20），表示测试数据组数。接下去的N行，每行包括一组测试数据。每组测试数据行以一个整数K开头（1 ≤ K ≤ 10），表示这组测试数据提供的USB Hub的数量；紧接着，在同一行，有K个整数（每两个整数之间由一个空格分隔开），{M1，M2…Mi…MK}（2 ≤ Mi ≤ 10），每个整数表示了这个USB Hub能将一个USB接口数变成的多个USB接口的数量。
输出
针对每组测试数据输出一个结果，表示小诺用这组提供的USB Hub后，能最多使用的USB设备的数量。每个输出占一行。
1 #include <iostream>
2
3 using namespace std;
4
5 /*
6
7 author tilltheendwjx
8
9 blog http://blog.csdn.net/wjh200821 或者http://www.cnblogs.com/tilltheendwjx/
10
11 */
12
13 int main()
14
15 {
16
17 int n;
18
19 cin>> n;
20
21 int k;
22
23 int * a;
24
25 int *b= new int [n];
26
27 for ( int i= 0 ;i<n;i++ )
28
29 {
30
31 cin>> k;
32
33 a= new int [k];
34
35 int sum= 0 ;
36
37 for ( int j= 0 ;j<k;j++ )
38
39 {
40
41 cin>> a[j];
42
43 sum+= a[j];
44
45 }
46
47 b[i]=sum+ 1 - k;
48
49 }
50
51 for ( int i= 0 ;i<n;i++ )
52
53 {
54
55
56
57 cout<<b[i]<< endl;
58
59 }
60
61 delete a;
62
63 // system("pause");
64
65 return 0 ;
66
67 }
C:易手机的套餐
时间限制: 1000ms 内存限制: 10000kB
描述
装载百度易平台的易手机已经上市，为了更好的为大家提供服务。百度与合作的运营商正在讨论为易手机用户推出一款特别的套餐，帮助大家更好的利用易手机。作为这个项目负责人的晓萌调研了大量用户使用这个套餐后会出现的资费预估，让我们来看看这个特别的套餐到底会带来怎样资费情况吧。
输入
输入数据包括十二行，每行包括一个数字（不含金钱符号$），表示晓萌调研的某一用户使用特别套餐后，一月到十二月消费的资费情况。每行包括的这个数字精确到小数点后两位。
输出
输出仅一行，表示用户使用该套餐后，针对给出的12个月的资费的均值情况。在分位采用四舍五入进位。输出以金钱符号$开头，输出中不含空格等其它特别字符。
1 #include <stdio.h>
2
3 #include <stdlib.h>
4
5 #include <math.h>
6
7 /*
8
9 author tilltheendwjx
10
11 blog http://blog.csdn.net/wjh200821 或者http://www.cnblogs.com/tilltheendwjx/
12
13 */
14
15 int main()
16
17 {
18
19 float a[ 12 ];
20
21 float avg= 0 ;
22
23 int i= 0 ;
24
25 for (i= 0 ;i< 2 ;i++ )
26
27 {
28
29 a[i]= 0.00 ;
30
31 }
32
33 for (i= 0 ;i< 12 ;i++ )
34
35 {
36
37 scanf( " %f " ,& a[i]);
38
39 avg=avg+ a[i];
40
41 }
42
43 printf( " $%.2f " ,( float )(avg/ 12 ));
44
45 // system("pause");
46
47 return 0 ;
48
49 }
D:共同狂欢
时间限制: 1000ms 内存限制: 131072kB
描述
百度2005年8月5日上市时，在北京和纳斯达克的同学们每一个小时整点时就会通一次电话，对一下表，确认一切相关活动都精确同步。但是要注意，在两边的同学位于不同的时区，在夏时制时，两地时差12小时，因此，每次对表都需要做一下时区转换。你来帮我们完成这个有点麻烦的工作吧。
输入
输入的第一行包括一个整数T（T ≤ 30），表示测试数据的组数；接下去的T行每行包括一个时间，表示两地中的一个地方同学报出的整点的时间，表示成“H:M”的形式，其中H是小时（0 ≤ H ＜ 24，且当H小于10的时候可以表示成1位或者2位的形式）、M是分钟（0 ≤ M ＜ 60，且当M小于10的时候可以表示成1位或者2位）。
输出
每个测试数据输出一行，当是整点对时时，输出时区转换后的小时结果；当不是整点对时时，输出0。
1 #include <stdio.h>
2
3 #include <stdlib.h>
4
5 /*
6
7 author tilltheendwjx
8
9 blog http://blog.csdn.net/wjh200821 或者http://www.cnblogs.com/tilltheendwjx/
10
11 */
12
13 int main()
14
15 {
16
17 int n;
18
19 int * a;
20
21 int * b;
22
23 int * c;
24
25 int i= 0 ;
26
27 scanf( " %d " ,& n);
28
29 a=( int *)malloc( sizeof ( int )* n);
30
31 b=( int *)malloc( sizeof ( int )* n);
32
33 c=( int *)malloc( sizeof ( int )* n);
34
35 for (i= 0 ;i<n;i++ )
36
37 {
38
39 scanf( " %d:%d " ,&a[i],& b[i]);
40
41 if (b[i]!= 0 )
42
43 { c[i]= 0 ;}
44
45 else
46
47 {
48
49 if ((a[i]+ 12 )== 24 )
50
51 c[i]= 24 ;
52
53 else
54
55 c[i]=(a[i]+ 12 )% 24 ;
56
57 }
58
59
60
61 }
62
63 for (i= 0 ;i<n;i++ )
64
65 {
66
67 printf( " %d\n " ,c[i]);
68
69
70
71 }
72
73 free(a);
74
75 free(b);
76
77 free(c);
78
79 // system("pause");
80
81 return 0 ;
82
83 }
E:C++ 与Java
时间限制: 2000ms 内存限制: 65536kB
描述
在百度之星的贴吧里面，Java的爱好者和C++的爱好者总是能为这两种语言哪个更好争论上几个小时。Java的爱好者会说他们的程序更加整洁且不易出错。C++的爱好者则会嘲笑Java程序很慢而且代码很长。
另一个Java和C++爱好者不能达成一致的争论点就是命名问题。在Java中一个多个单词构成的变量名应该按照如下格式命名：第一个单词的开头用小写字母，其余单词都以大写字母开头，单词与单词之间不加分隔符，除单词的首字母之外的字母一律使用小写。例如：javaIdentifier, longAndMnemonicIdentifier, name, bAIDU.
与Java不同C++的命名全都使用小写字母，在单词和单词之间使用“_”来作为分隔符。例如：c_identifier, long_and_mnemonic_identifier, name (当名字中只有一个单词的时候，Java与C++的命名是相同的), b_a_i_d_u.
你的任务就是写一个程序能让C++和Java程序相互转化。当然转换完成的程序中的变量名也要符合其语言的命名规则，否则的话是不会有人喜欢你的转换器的。
首先你要做的就是写一个变量名转换器。给出一个变量名，你要先检测是Java的还是C++的，然后把它转化为另一种命名格式。如果两种都不是，那么你的程序就要报错。转换过程必须保持原有的单词顺序，只能改变字母的大小写和增加或删除下划线。
输入
输入有且仅有一行，是一个变量名，其中包含字母和下划线，长度不超过100。
输出
如果输入的是Java变量名那么输出它对应的C++形式。如果是C++的则输出对应的Java的形式。如果两种都不是就输出“Error!”。
样例输入
输入样例1：
long_and_mnemonic_identifier
输入样例2：
anotherExample
输入样例3：
i
输入样例4：
bad_Style
样例输出
输出样例1：
longAndMnemonicIdentifier
输出样例2：
another_example
输出样例3：
i
输出样例4：
Error!
1 #include <stdio.h>
2
3 #include <stdlib.h>
4
5 #include <math.h>
6
7 #include < string .h>
8
9 #include <ctype.h>
10
11 /*
12
13 author tilltheendwjx
14
15 blog http://blog.csdn.net/wjh200821 或者http://www.cnblogs.com/tilltheendwjx/
16
17 */
18
19 int main()
20
21 {
22
23 char a[ 100 ];
24
25 char b[ 100 ];
26
27 int i= 0 ;
28
29 int j= 0 ;
30
31 int flag= 0 ;
32
33 int javature= 0 ;
34
35 int cture= 0 ;
36
37 scanf( " %s " ,a);
38
39 for (i= 0 ;i< 100 ;i++ )
40
41 {
42
43 if (a[i]== ' \0 ' )
44
45 break ;
46
47 if (a[i]== ' _ ' )
48
49 {
50
51 if ((islower(a[i+ 1 ])== 0 )||i== 0 ||a[i+ 1 ]== ' \0 ' )
52
53 flag= 1 ;
54
55 else
56
57 cture= 1 ;
58
59 i++ ;
60
61 b[j]=( char )toupper(a[i]);
62
63 j++ ;
64
65 }
66
67 else if ((isupper(a[i])!= 0 ))
68
69 {
70
71 if ((a[i- 1 ]== ' _ ' )||i== 0 )
72
73 flag= 1 ;
74
75 else
76
77 javature= 1 ;
78
79 b[j]= ' _ ' ;
80
81 j++ ;
82
83 b[j]=( char )tolower(a[i]);
84
85 j++ ;
86
87 }
88
89 else
90
91 {
92
93 b[j]= a[i];
94
95 j++ ;
96
97 }
98
99
100
101 }
102
103 b[j]= ' \0 ' ;
104
105 if (flag== 0 )
106
107 {
108
109 if (javature== 1 &&cture== 1 )
110
111 printf( " Error! " );
112
113 else
114
115 printf( " %s " ,b);
116
117 }
118
119 else
120
121 printf( " Error! " );
122
123 // system("pause");
124
125 return 0 ;
126
127 }
F:百科蝌蚪团
时间限制: 1000ms 内存限制: 65536kB
描述
百度百科有一支神奇的队伍，他们叫自己“百科蝌蚪团”。为了更好的让蝌蚪团的成员们安排工作，百度百科的运营团队定出了一个24小时制的时间表。例如：
1. 每个蝌蚪团成员工作时长相同；
2. 必须安排蝌蚪团成员在他们方便的时间段工作；
3. 蝌蚪团成员安排时间最小安排时间节点（开始工作或停止工作）为半小时，比如04：00或04：30，而不是04：15；
4. 蝌蚪团成员一天在百度百科工作的时间是有上限的，他们会根据自己的情况给出上限。
5. 在特定时间段内必须有一定数量的蝌蚪团成员工作，以保证百度百科不断的进步
请帮运营团队计算一下，能保持24小时稳定在岗的蝌蚪团最少成员的数量。如果有2个蝌蚪团成员工作结束，同时另2个蝌蚪团成员开始工作，这段时间都算有2各成员稳定在岗。
输入
输入有多组，每组测试数据以一个整数N开头（1 ≤ N ≤ 50），表示蝌蚪团的成员数。紧接着，我们会有N个数据块，每一个数据块对应了一名蝌蚪团成员的日程情况。
每个数据块以两个整数开始，分别为K（1 ≤ K ≤ 50）和M（1 ≤ M ≤ 1440），用空格隔开。K表示这个数据块对应蝌蚪团成员方便的时间段的数量，M表示这个成员愿意每天在百度百科工作的最长分钟数。接下去的K行中，每行包括两个时间，分别表示成“HH：MM”的格式，以空格分隔，分别对应了该蝌蚪团成员一个方便的时间段的开始时间、结束时间；例如09：00 10：00表明他在早上九点到十点的时间段是方便的，可以在百度百科工作。如果两个时间相同，则说明这个他全天都是方便的。
最后一组数据的N为0，表示输入结束。
输出
对于每组数据，输出为一个整数，占一行。表示能保持24小时稳定在岗的蝌蚪团最少成员的数量。
1 #include<stdio.h>
2
3 #include<memory.h>
4
5 #include<stdlib.h>
6
7 #define maxn 102
8
9 int d[maxn],g[maxn][maxn],f[maxn][maxn],pre[maxn],map[maxn][maxn],sum[maxn],current[maxn];
10
11 int n,m,num,mm;
12
13 struct node
14
15 {
16
17 int x,y;
18
19 }seg[ 1000 ],time[ 1000 ];
20
21 #define oo 0xfffffff
22
23 int cmp( const void *a, const void * b)
24
25 {
26
27 struct node *va=( struct node* )a;
28
29 struct node *vb=( struct node* )b;
30
31 return va->x-vb-> x;
32
33 }
34
35 void rev_bfs( int t)
36
37 {
38
39 int queue[maxn],flag[maxn];
40
41 int head,tail,i;
42
43 memset(sum, 0 , sizeof (sum));
44
45 for (i= 0 ;i<=n+ 49 ;i++ )
46
47 {
48
49 d[i]=n+ 49 ;
50
51 sum[n+ 49 ]++ ;
52
53 }
54
55 sum[n+ 49 ]-- ;
56
57 sum[ 0 ]++ ;
58
59 d[t]= 0 ;
60
61 queue[ 1 ]= t;
62
63 flag[t]= 1 ;
64
65 head= 1 ;tail= 1 ;
66
67 memset(flag, 0 , sizeof (flag));
68
69 while (head<= tail)
70
71 {
72
73 for (i= 0 ;i<=n+ 49 ;i++ )
74
75 if (flag[i]== 0 &&g[i][queue[head]]> 0 )
76
77 {
78
79 queue[++tail]= i;
80
81 d[i]=d[queue[head]]+ 1 ;
82
83 sum[n+ 49 ]-- ;
84
85 sum[d[i]]++ ;
86
87 flag[i]= 1 ;
88
89 }
90
91 head++ ;
92
93 }
94
95 }
96
97 void augment( int s, int t)
98
99 {
100
101 int i,min;
102
103 min= oo;
104
105 for (i=t;i!=s;i= pre[i])
106
107 if (g[pre[i]][i]< min)
108
109 min= g[pre[i]][i];
110
111 for (i=t;i!=s;i= pre[i])
112
113 {
114
115 g[pre[i]][i]-= min;;
116
117 g[i][pre[i]]+= min;
118
119 f[pre[i]][i]+= min;
120
121 f[i][pre[i]]-= min;
122
123 }
124
125 }
126
127 int retreat( int *u, int s)
128
129 {
130
131 int v,min;
132
133 min=n+ 49 ;
134
135 for (v= 0 ;v<=n+ 49 ;v++ )
136
137 if (g[*u][v]> 0 &&d[v]< min)
138
139 min= d[v];
140
141 sum[d[*u]]-- ;
142
143 if ((sum[d[*u]])== 0 &&d[*u]<=n+ 49 ) return 0 ;
144
145 d[*u]=min+ 1 ;
146
147 sum[d[*u]]++ ;
148
149 current[*u]= 0 ;
150
151 if (*u!=s) *u=pre[* u];
152
153 return 1 ;
154
155 }
156
157 void ISAP( int s, int t)
158
159 {
160
161 int u,v;
162
163 rev_bfs(t);
164
165 u= s;
166
167 while (d[s]<n+ 50 )
168
169 {
170
171 for (v=current[u];v<=n+ 49 ;v++ )
172
173 if (g[u][v]> 0 &&d[u]==d[v]+ 1 )
174
175 break ;
176
177 if (v<=n+ 49 )
178
179 {
180
181 current[u]= v;
182
183 pre[v]= u;
184
185 u= v;
186
187 if (u== t)
188
189 {
190
191 augment(s,t);
192
193 u= s;
194
195 }
196
197 }
198
199 else if (retreat(&u,s)== 0 ) return ;
200
201 }
202
203 }
204
205 void init()
206
207 {
208
209 int i,j,a,b,c,d,min,t,k,ans,max,st,en,temp;
210
211 while (scanf( " %d " ,&n)!=EOF&& n)
212
213 {
214
215 memset(map, 0 , sizeof (map));;
216
217 for (i= 1 ;i<=n;i++ )
218
219 {
220
221 scanf( " %d%d " ,&m,& t);
222
223 map[ 48 ][i+ 48 ]=t/ 30 ;
224
225 num= 0 ;
226
227 mm= 0 ;
228
229 for (j= 1 ;j<=m;j++ )
230
231 {
232
233 scanf( " %d:%d %d:%d " ,&a,&b,&c,& d);
234
235 if (a==c&&b== d)
236
237 {
238
239 for (k= 0 ;k< 48 ;k++ )
240
241 map[i+ 48 ][k]= 1 ;
242
243 continue ;
244
245 }
246
247 if (c== 0 &&d== 0 )
248
249 {
250
251 num++ ;
252
253 seg[num].x=a* 60 + b;
254
255 seg[num].y= 1440 ;
256
257 }
258
259 else if (a* 60 +b>c* 60 + d)
260
261 {
262
263 num++ ;
264
265 seg[num].x=a* 60 + b;
266
267 seg[num].y= 1440 ;
268
269 num++ ;
270
271 seg[num].x= 0 ;
272
273 seg[num].y=c* 60 + d;
274
275 }
276
277 else
278
279 {
280
281 num++ ;
282
283 seg[num].x=a* 60 + b;
284
285 seg[num].y=c* 60 + d;
286
287 }
288
289 }
290
291 if (num== 0 ) continue ;
292
293 qsort(seg+ 1 ,num, sizeof (seg[ 1 ]),cmp);
294
295 st=seg[ 1 ].x;en=seg[ 1 ].y;
296
297 seg[num+ 1 ].x= 1500 ;seg[num+ 1 ].y= 1600 ;
298
299 for (j= 2 ;j<=num+ 1 ;j++ )
300
301 {
302
303 a= seg[j].x;
304
305 b= seg[j].y;
306
307 if (st<=a&&a<=en&&en< b)
308
309 en= b;
310
311 else if (a> en)
312
313 {
314
315 mm++ ;
316
317 time[mm].x= st;
318
319 time[mm].y= en;
320
321 st= a;
322
323 en= b;
324
325 }
326
327 }
328
329 for (j= 1 ;j<=mm;j++ )
330
331 {
332
333 a=time[j].x/ 60 ;
334
335 b=time[j].x- 60 * a;
336
337 c=time[j].y/ 60 ;
338
339 d=time[j].y- 60 * c;
340
341 if (a== c)
342
343 {
344
345 if (b== 0 &&d>= 30 )
346
347 map[i+ 48 ][a* 2 ]= 1 ;
348
349 }
350
351 else
352
353 {
354
355 if (b> 0 &&b<= 30 ) b= 30 ;
356
357 if (b> 30 )
358
359 {
360
361 a++ ;
362
363 b= 0 ;
364
365 }
366
367 if (d< 30 ) d= 0 ;
368
369 if (d> 30 ) d= 30 ;
370
371 while (a!=c||b!= d)
372
373 {
374
375 map[i+ 48 ][a* 2 +b/ 30 ]= 1 ;
376
377 b+= 30 ;
378
379 if (b== 60 )
380
381 {
382
383 a++ ;
384
385 b= 0 ;
386
387 }
388
389 }
390
391 }
392
393 }
394
395 }
396
397 max= oo;
398
399 for (j= 0 ;j< 48 ;j++ )
400
401 {
402
403 temp= 0 ;
404
405 for (k= 49 ;k<n+ 49 ;k++ )
406
407 if (map[k][j]> 0 ) temp++ ;
408
409 if (temp< max)
410
411 max= temp;
412
413 }
414
415 ans= 0 ;
416
417 for (j= 1 ;j<=max;j++ )
418
419 {
420
421 memset(g, 0 , sizeof (g));
422
423 memset(f, 0 , sizeof (f));
424
425 memset(current, 0 , sizeof (current));
426
427 for (i= 0 ;i<= 49 +n;i++ )
428
429 for (k= 0 ;k<= 49 +n;k++ )
430
431 g[i][k]= map[i][k];
432
433 for (i= 0 ;i< 48 ;i++ )
434
435 g[i][n+ 49 ]= j;
436
437 ISAP( 48 ,n+ 49 );
438
439 min= oo;
440
441 for (i= 0 ;i< 48 ;i++ )
442
443 if (f[i][n+ 49 ]< min)
444
445 min=f[i][n+ 49 ];
446
447 if (min>ans) ans= min;
448
449 }
450
451 printf( " %d\n " ,ans);
452
453 }
454
455 }
456
457 int main()
458
459 {
460
461 init();
462
463 // system("pause");
464
465 return 0 ;
466
467 }
G:聊天就是Repeat
时间限制: 1000ms 内存限制: 65536kB
描述
百度Hi作为百度旗下的即时聊天工具，在百度公司内部很是流行。要实现这样的一个聊天工具，最重要的问题就是要能保证我发出的内容能原封不动的在接收同学那里显示出来。今天，就给你一个机会，让你模拟一下百度Hi传递信息的过程，把我发给Robin的聊天内容原封不动的输出出来。
输入
输入的聊天内容数据有多组，每组数据占一行。
输出
与输入聊天内容完全相同的内容。请注意每组数据中的空格也要原封不动的被传过去噢~
样例输入
Hello Robin
今天下午去五福颁奖，具体时间是2012年8月3日 15:40噢~
样例输出
Hello Robin
今天下午去五福颁奖，具体时间是2012年8月3日 15:40噢~
1 #include <iostream>
2
3 #include < string >
4
5 /*
6
7 author tilltheendwjx
8
9 blog http://blog.csdn.net/wjh200821 或者http://www.cnblogs.com/tilltheendwjx/
10
11 */
12
13 using namespace std;
14
15 int main()
16
17 {
18
19
20
21 while ( 1 )
22
23 {
24
25 string str;
26
27 getline(cin,str);
28
29 if (str.length()<= 0 )
30
31 break ;
32
33 cout<<str<< endl;
34
35 }
36
37 // system("pause");
38
39 return 0 ;
40
41 }
H:用户请求中的品牌
时间限制: 1000ms 内存限制: 65536kB
描述
馅饼同学是一个在百度工作，做用户请求（query）分析的同学，他在用户请求中经常会遇到一些很奇葩的词汇。在比方说“johnsonjohnson”、“duckduck”，这些词汇虽然看起来是一些词汇的单纯重复，但是往往都是一些特殊品牌的词汇，不能被拆分开。为了侦测出这种词的存在，你今天需要完成我给出的这个任务——“找出用户请求中循环节最多的子串”。
输入
输入数据包括多组，每组为一个全部由小写字母组成的不含空格的用户请求（字符串），占一行。用户请求的长度不大于100,000。
最后一行输入为#，作为结束的标志。
输出
对于每组输入，先输出这个组的编号（第n组就是输出“Case n:”）；然后输出这组用户请求中循环节最多的子串。如果一个用户请求中有两个循环节数相同的子串，请选择那个字典序最小的。
样例输入
ilovejohnsonjohnsonverymuch
duckduckgo
aaabbbcccisagoodcompany
#
样例输出
Case 1: johnsonjohnson
Case 2: duckduck
Case 3: aaa
1 #include <stdio.h>
2
3 #include<cstring>
4
5 #include<math.h>
6
7 #include< string .h>
8
9 #define MAXN 100002
10
11 int wa[MAXN], wb[MAXN], wv[MAXN], wd[MAXN], Height[MAXN], sa[MAXN], rank[MAXN];
12
13 int n;
14
15 inline bool IsEqual( int *r, int a, int b, int l)
16
17 {
18
19 return (r[a] == r[b] && r[a + l] == r[b + l]);
20
21 }
22
23 void da( int *r, int m = 27 )
24
25 {
26
27 int i, j, p, *x = wa, *y = wb, * t;
28
29 memset(wd, 0 , sizeof (wd));
30
31 for (i = 0 ; i < n; i++) wd[x[i] = r[i]]++; x[n] = y[n] = 0 ;
32
33 for (i = 1 ; i < m; i++) wd[i] += wd[i - 1 ];
34
35 for (i = n - 1 ; i >= 0 ; i--) sa[--wd[x[i]]] = i;
36
37 for (p = 1 , j = 1 ; p <= n; m = p, j *= 2 )
38
39 {
40
41 for (p = 0 , i = n - j; i < n; i++) y[p++] = i;
42
43 for (i = 0 ; i < n; i++) if (sa[i] >= j)y[p++] = sa[i] - j;
44
45 for (i = 0 ; i < n; i++) wv[i] = x[y[i]];
46
47 memset(wd, 0 , sizeof (wd));
48
49 for (i = 0 ; i < n; i++) wd[wv[i]]++ ;
50
51 for (i = 1 ; i < m; i++) wd[i] += wd[i - 1 ];
52
53 for (i = n - 1 ; i >= 0 ; i--) sa[--wd[wv[i]]] = y[i];
54
55 for (t = x, x = y, y = t, i = 1 , p = 2 ,x[sa[ 0 ]] = 1 ; i < n; i++ )
56
57 x[sa[i]] = IsEqual(y, sa[i- 1 ], sa[i], j) ? p - 1 : p++ ;
58
59 }
60
61 }
62
63 void CalHeight( int * r)
64
65 {
66
67 int i, j, k;
68
69 for (i = 0 ; i < n; i++)rank[sa[i]] = i;
70
71 for (i = 0 , Height[ 0 ] = k = 0 ; i < n; Height[rank[i++]] = k)
72
73 for (k?k--: 0 , j=(rank[i]> 0 )?sa[rank[i]- 1 ]: 0 ; rank[i]> 0 &&r[i+k]==r[j+k]; k++ );
74
75 }
76
77 int ffmin[MAXN][ 20 ];
78
79 void setf()
80
81 {
82
83 int i,j;
84
85 memset(ffmin, 0 , sizeof (ffmin));
86
87 for (i= 1 ;i<=n;i++ ){
88
89 ffmin[i][ 0 ]= Height[i];
90
91 }
92
93 for (j= 1 ;j<=( int )(log(( double )(n+ 1 ))/log( 2.0 ));j++ )
94
95 for (i= 1 ;i+( 1 <<j)- 1 <=n;i++ )
96
97 ffmin[i][j]=ffmin[i][j- 1 ]<ffmin[i+( 1 <<(j- 1 ))][j- 1 ]?ffmin[i][j- 1 ]:ffmin[i+( 1 <<(j- 1 ))][j- 1 ];
98
99 }
100
101 int findmin( int l, int r)
102
103 {
104
105 int k=( int )(log( 1.0 *(r-l+ 1 ))/log( 2.0 ));
106
107 return ffmin[l][k]<ffmin[r-( 1 <<k)+ 1 ][k]?ffmin[l][k]:ffmin[r-( 1 <<k)+ 1 ][k];
108
109 }
110
111 char str[MAXN];
112
113 int r[MAXN];
114
115 int sp;
116
117 int tsp;
118
119 int maxl;
120
121 int main()
122
123 {
124
125 int cases= 0 ,i;
126
127 while (scanf( " %s " ,&str)!=EOF&&str[ 0 ]!= ' # ' )
128
129 {
130
131 cases++ ;
132
133 printf( " Case %d: " ,cases);
134
135 n= strlen(str);
136
137 memset(r, 0 , sizeof (r));
138
139 maxl= 1 ;
140
141 for (i = 0 ; i < n; i++ )
142
143 r[i] = str[i] - ' a ' + 1 ;
144
145 da(r);
146
147 CalHeight(r);
148
149 setf();
150
151 int l,max= 1 ;
152
153 sp= 0 ;
154
155 for (l= 1 ;l<=n/ 2 ;l++ ){
156
157 int cur= 0 ;
158
159 while (cur+l< n){
160
161 if (r[cur]==r[cur+ l]){
162
163 int s,e;
164
165 int k,lcp;
166
167 s= rank[cur];
168
169 e=rank[cur+ l];
170
171 if (s> e){
172
173 s^= e;
174
175 e^= s;
176
177 s^= e;
178
179 }
180
181 s++ ;
182
183 lcp= findmin(s,e);
184
185 tsp= cur;
186
187 int ss= 0 ;
188
189 for ( int p=cur - 1 ; p>= 0 && p > (cur-l) && r[p] == r[p + l];p-- )
190
191 if (++ss == (l-(lcp% l)))
192
193 tsp= p;
194
195 else if (rank[tsp] > rank[p])
196
197 tsp= p;
198
199 k=(lcp+ss)/l+ 1 ;
200
201 if (k> max){
202
203 max= k;
204
205 maxl= l;
206
207 sp= tsp;
208
209 }
210
211 else if (k==max&&rank[tsp]< rank[sp]){
212
213 sp= tsp;
214
215 maxl= l;
216
217 }
218
219 }
220
221 cur+= l;
222
223 }
224
225 }
226
227 if (max> 1 ){
228
229 for (i=sp;i<sp+max*maxl;i++ )
230
231 printf( " %c " ,str[i]);
232
233 printf( " \n " );
234
235 }
236
237 else {
238
239 char c= ' z ' ;
240
241 for (i= 0 ;i<n;i++ )
242
243 if (str[i]< c)
244
245 c= str[i];
246
247 printf( " %c\n " ,c);
248
249 }
250
251 }
252
253 return 0 ;
254
255 }
I:地图的省钱计划
时间限制: 1000ms 内存限制: 65536kB
描述
百度地图有自己的一套坐标系（你可以把它看作一个笛卡尔坐标系），在这套坐标系里，一个标准单位为1km。而在这坐标系上针对地理信息进行标注的数据，大多数时候是通过购买的方式完成的。为了节约数据更新的成本，数据组里的鑫哥想出了一个好主意——自己测数据。
鑫哥按照他的预想开始实验；在每组试验中，鑫哥选取了三个已经被准确标注在百度地图的坐标系里的移动运营商的基站作为信号接收点（这里可以准确的得到信号的接收时间信息）。当信号接收点附近的用户手机签到时，三个信号接收点就会先后接收到这个信号，并可以准确的知晓接收到信号的时间（将第一个信号点接收到信号的时间记为0秒时刻）。由此，我们就可以确定用户手机签到的位置的在地图的准确坐标了。
现在已知以下数据：
1.三个信号接收点在百度地图坐标系中的具体坐标(x1,y1), (x2,y2), (x3,y3)；
2.三个信号点得到用户发出的信号的时间t1, t2, t3（t1, t2, t3 ≥ 0），单位s; t1, t2, t3至少有一个数为0；
3.信号的转播速度C，单位m/s；
请帮助鑫哥写个程序，计算下用户发出信号的位置在百度地图坐标系内的坐标（这个点是唯一的）。
输入
输入包含多组数据，每组数据格式如下：
C
x1 y1 x2 y2 x3 y3
t1 t2 t3
最后一组数据为0，表示输入结束。
输出
针对每组测试数据，请先输出这个组的编号（第n组就是输出“Case n:”）；然后换行输出信号发出点的坐标(x,y) 。x，y应该由空格分隔，并被舍入到小数点后第六位。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cassert>
6 #include< string >
7 #include<algorithm>
8 #include<fstream>
9 #include<sstream>
10 #include< set >
11 #include<map>
12 #include<vector>
13 #include<queue>
14 #include<deque>
15 #include<complex>
16 #include<numeric>
17 using namespace std;
18 double x[ 10 ], y[ 10 ], t[ 10 ];
19 bool solve( int i, int j, int k)
20 {
21 double x1, y1, x2, y2, t1, t2;
22 x1 = x[j] - x[i];
23 x2 = x[k] - x[i];
24 y1 = y[j] - y[i];
25 y2 = y[k] - y[i];
26 t1 = t[j] - t[i];
27 t2 = t[k] - t[i];
28
29 double A1 = x1*x1 + y1*y1 - t1* t1;
30 double A2 = x2*x2 + y2*y2 - t2* t2;
31 double A = A1*y2-A2*y1, B = A1*x2-A2*x1, C = A1 * t2 - A2 * t1;
32 double cita = atan2(B, A);
33 double sum = asin(- C/sqrt(A*A+B*B+1e- 15 ));
34
35 double alpha = sum - cita;
36 double r;
37 if (abs(A1)> abs(A2))
38 r = A1/(t1 + x1 *cos(alpha) + y1 * sin(alpha))/ 2 ;
39 else
40 r = A2/(t2 + x2 *cos(alpha) + y2 * sin(alpha))/ 2 ;
41
42 if (r< 0 )
43 {
44 sum = - sum + 3.141592653579 ;
45 alpha = sum - cita;
46 if (abs(A1)> abs(A2))
47 r = A1/(t1 + x1 *cos(alpha) + y1 * sin(alpha))/ 2 ;
48 else
49 r = A2/(t2 + x2 *cos(alpha) + y2 * sin(alpha))/ 2 ;
50 }
51
52
53 printf( " %.6f %.6f\n " , r * cos(alpha) + x[i], r * sin(alpha) + y[i]);
54 }
55 int main()
56 {
57 for ( int dd = 1 ; ; ++ dd)
58 {
59 double c;
60 scanf( " %lf " , & c);
61 c/= 1000 ;
62 if (abs(c) < 1e- 6 )
63 break ;
64 scanf( " %lf %lf %lf %lf %lf %lf " , x, y, x+ 1 , y+ 1 , x+ 2 , y+ 2 );
65 scanf( " %lf %lf %lf " , t, t+ 1 , t+ 2 );
66 printf( " Case %d:\n " , dd);
67 t[ 0 ] *= c;
68 t[ 1 ] *= c;
69 t[ 2 ] *= c;
70 if (solve( 0 , 1 , 2 ))
71 continue ;
72 }
73 return 0 ;
74 }
J:百度的新大厦
时间限制: 1000ms 内存限制: 65536kB
描述
继百度搜索框大厦之后，百度又于2012年初在深圳奠基了新的百度国际大厦，作为未来百度国际化的桥头堡。不同于百度在北京的搜索框大厦，新的百度国际大厦是一栋高楼，有非常多的楼层，让每个楼中的电梯都能到达所有楼层将是一个极为不明智的设计。因此，设计师给出了一个特别的设计——一共大厦有m个电梯，每个电梯只有两个按钮，（针对第i个电梯）两个按钮分别可以使电梯向上或ui层向下一定di层；百度国际大厦很高，你永远到不了顶层，也就是说电梯没有上限，但是，电梯不可以钻入地下，也就是说是有下限的。我们将每层楼用整数标记，为了体现IT公司的特质，我们以0作为地面这一层的标记。
如果你某天在百度国际大厦的0层，仅可以选择m个电梯中的一个乘坐（不可以中途换电梯），请你计算，你按电梯中的按钮n次后（每次两个按钮选一个按），可以到达的最低楼层数。
输入
输入的第一行包括两个整数，分别为n和m（1 ≤ n ≤ 1,000,000，1 ≤ m ≤ 2,000），表示按电梯按钮的次数和大厦中的电梯数量。接下去的m行，每行包括2个由空格分割的数字，分别表示了提供的m个电梯中的某一个的上行按钮上升一次的层数ui和下行按钮下降一次的层数di（1 ≤ ui,di ≤ 1000）
输出
输出一个正整数，表示选用m个电梯中的一个后，在电梯里按电梯中的按钮n次后（每次两个按钮选一个按），可以到达的最低楼层数。
提示
按钮上的移动楼层数无法改变，比方说从8层向下9层是不可行的
1 #include <stdio.h>
2
3 #include <stdlib.h>
4
5 #include <math.h>
6
7 /*
8
9 author tilltheendwjx
10
11 blog http://blog.csdn.net/wjh200821 或者http://www.cnblogs.com/tilltheendwjx/
12
13 */
14
15 int main()
16
17 {
18
19 int n,m;
20
21 int * a;
22
23 int * b;
24
25 int i= 0 ;
26
27 int reault= 0 ;
28
29 int j= 0 ;
30
31 int tmp;
32
33 int low= 1 ;
34
35 int high= 0 ;
36
37 scanf( " %d%d " ,&n,& m);
38
39 high= n;
40
41 int mid;
42
43 a=( int *)malloc( sizeof ( int )* m);
44
45 b=( int *)malloc( sizeof ( int )* m);
46
47 for (i= 0 ;i<m;i++ )
48
49 {
50
51 scanf( " %d%d " ,&a[i],& b[i]);
52
53 }
54
55 for (i= 0 ;i<m;i++ )
56
57 {
58
59 low= 1 ;
60
61 high= n;
62
63 while ((high-low)> 2 )
64
65 {
66
67 mid=(low+high)/ 2 ;
68
69 tmp=a[i]*mid-b[i]*(n- mid);
70
71 if (tmp> 0 )
72
73 {
74
75 high= mid;
76
77 }
78
79 else
80
81 {
82
83 low=mid+ 1 ;
84
85 }
86
87
88
89 }
90
91 for (j=low;j<=high;j++ )
92
93 {
94
95 tmp=a[i]*j-b[i]*(n- j);
96
97 if (tmp> 0 )
98
99 { break ;}
100
101 }
102
103 if (reault== 0 )
104
105 reault= tmp;
106
107 else if (reault> tmp)
108
109 reault= tmp;
110
111 else
112
113 reault= reault;
114
115
116
117 }
118
119 printf( " %d " ,reault);
120
121 // system("pause");
122
123 return 0 ;
124
125 }
/* n次按键，m个电梯。每次选择上up，或者下down；
每次有一个能到达最小的层数；共有m个电梯选一个。输出最优解。
*/
#include "stdio.h"
int main()
{
int m,n,i;
int dist=9999;
scanf ( "%d%d" ,&n,&m);
for (i=1;i<=m;i++)
{
int u,d;
scanf ( "%d%d" ,&u,&d);
int jTemp = ( int )(d*n)/(u+d);
int udTemp1=u*jTemp-d*(n-jTemp);
int udTemp2=u*(jTemp+1)-d*(n-jTemp-1);
if (udTemp1<=0 && udTemp2>0){
if (udTemp2<dist)
dist = udTemp2;
}
else if (udTemp1>0)
{
if (udTemp1<dist)
dist = udTemp1;
}
}
printf ( "%d\n" ,dist);
return 0;
}
标签: 百度之星 资格赛 AC代码
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息查看更多关于2012百度之星资格赛试题与AC代码合集的详细内容...