【2012百度之星资格赛试题与AC代码合集】
2012百度之星资格赛试题与AC代码
A:百度计算器的加法
时间限制: 1000ms 内存限制: 10000kB
描述
百度框计算中提供了计算器这个功能，模拟计算器中的复杂功能，我们最先需要解决的就是实现加法模块。今天就给你个机会，和百度计算器一样，计算一下十以内的加法吧。
输入
仅有一组数据，包含两个正整数，分别为a, b(0 <= a, b <= 10)
输出
一个正整数，暨输入a, b后对应的a+b的计算结果
样例输入
5 2
样例输出
7
#include
#include
/*
author tilltheendwjx
blog http://www.wendangku.net/doc/39d92648852458fb770b5616.html/wjh200821或者http://www.wendangku.net/doc/39d92648852458fb770b5616.html/tilltheendwjx/
*/
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d",a+b);
//system("pause");
return 0;
}
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设备的数量。每个输出占一行。
样例输入
3
2 2 2
3 3 2 4
6 2 2 2 3 4 5
样例输出
3
7
13
#include
using namespace std;
/*
author tilltheendwjx
blog http://www.wendangku.net/doc/39d92648852458fb770b5616.html/wjh200821或者http://www.wendangku.net/doc/39d92648852458fb770b5616.html/tilltheendwjx/
*/
int main()
{
int n;
cin>>n;
int k;
int *a;
int *b=new int[n];
for(int i=0;i { cin>>k; a=new int[k]; int sum=0; for(int j=0;j { cin>>a[j]; sum+=a[j]; } b[i]=sum+1-k; } for(int i=0;i { cout< } delete a; //system("pause"); return 0; } C:易手机的套餐 时间限制: 1000ms 内存限制: 10000kB 描述 装载百度易平台的易手机已经上市，为了更好的为大家提供服务。百度与合作的运营商正在讨论为易手机用户推出一款特别的套餐，帮助大家更好的利用易手机。作为这个项目负责人的晓萌调研了大量用户使用这个套餐后会出现的资费预估，让我们来看看这个特别的套餐到底会带来怎样资费情况吧。 输入 输入数据包括十二行，每行包括一个数字（不含金钱符号$），表示晓萌调研的某一用户使用特别套餐后，一月到十二月消费的资费情况。每行包括的这个数字精确到小数点后两位。 输出 输出仅一行，表示用户使用该套餐后，针对给出的12个月的资费的均值情况。在分位采用四舍五入进位。输出以金钱符号$开头，输出中不含空格等其它特别字符。 样例输入 112.00 249.12 214.12 34.10 223.05 109.20 53.27 102.25 239.18 95.99 95.01 25.75 样例输出 $129.42 #include #include #include /* author tilltheendwjx blog http://www.wendangku.net/doc/39d92648852458fb770b5616.html/wjh200821或者http://www.wendangku.net/doc/39d92648852458fb770b5616.html/tilltheendwjx/ */ int main() { float a[12]; float avg=0; int i=0; for(i=0;i<2;i++) { a[i]=0.00; } for(i=0;i<12;i++) { scanf("%f",&a[i]); avg=avg+a[i]; } printf("$%.2f",(float)(avg/12)); //system("pause"); return 0; } 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。 样例输入 4 12:00 01:01 3:00 00:00 样例输出 24 15 12 #include #include /* author tilltheendwjx blog http://www.wendangku.net/doc/39d92648852458fb770b5616.html/wjh200821或者http://www.wendangku.net/doc/39d92648852458fb770b5616.html/tilltheendwjx/ */ int main() { int n; int *a; int *b; int *c; int i=0; scanf("%d",&n); a=(int *)malloc(sizeof(int)*n); b=(int *)malloc(sizeof(int)*n); c=(int *)malloc(sizeof(int)*n); for(i=0;i { scanf("%d:%d",&a[i],&b[i]); if(b[i]!=0) { c[i]=0;} else { if((a[i]+12)==24) c[i]=24; else c[i]=(a[i]+12)%24; } } for(i=0;i { printf("%d\n",c[i]); } free(a); free(b); free(c); //system("pause"); return 0; } 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! #include #include #include #include #include /* author tilltheendwjx blog http://www.wendangku.net/doc/39d92648852458fb770b5616.html/wjh200821或者http://www.wendangku.net/doc/39d92648852458fb770b5616.html/tilltheendwjx/ */ int main() { char a[100]; char b[100]; int i=0; int j=0; int flag=0; int javature=0; int cture=0; scanf("%s",a); for(i=0;i<100;i++) { if(a[i]=="\0") break; if(a[i]=="_") { if((islower(a[i+1])==0)||i==0||a[i+1]=="\0") flag=1; else cture=1; i++; b[j]=(char)toupper(a[i]); j++; } else if((isupper(a[i])!=0)) { if((a[i-1]=="_")||i==0) flag=1; else javature=1; b[j]="_"; j++; b[j]=(char)tolower(a[i]); j++; } else { b[j]=a[i]; j++; } } b[j]="\0"; if(flag==0) { if(javature==1&&cture==1) printf("Error!"); else printf("%s",b); } else printf("Error!"); //system("pause"); return 0; } 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小时稳定在岗的蝌蚪团最少成员的数量。 样例输入 5 1 720 18:00 12:00 1 1080 00:00 23:00 1 1080 00:00 20:00 1 1050 06:00 00:00 1 360 18:00 00:00 3 1 540 00:00 00:00 3 480 08:00 10:00 09:00 12:00 13:00 19:00 1 420 17:00 00:00 3 1 1440 00:00 00:00 1 720 00:00 12:15 1 720 12:05 00:15 样例输出 2 1 1 #include #include #include #define maxn 102 int d[maxn],g[maxn][maxn],f[maxn][maxn],pre[maxn],map[maxn][maxn],sum[maxn],current[maxn]; int n,m,num,mm; struct node { int x,y; }seg[1000],time[1000]; #define oo 0xfffffff int cmp(const void *a,const void *b) { struct node *va=(struct node*)a; struct node *vb=(struct node*)b; return va->x-vb->x; } void rev_bfs(int t) { int queue[maxn],flag[maxn]; int head,tail,i; memset(sum,0,sizeof(sum)); for (i=0;i<=n+49;i++) { d[i]=n+49; sum[n+49]++; } sum[n+49]--; sum[0]++; d[t]=0; queue[1]=t; flag[t]=1; head=1;tail=1; memset(flag,0,sizeof(flag)); while (head<=tail) { for (i=0;i<=n+49;i++) if (flag[i]==0&&g[i][queue[head]]>0) { queue[++tail]=i; d[i]=d[queue[head]]+1; sum[n+49]--; sum[d[i]]++; flag[i]=1; } head++; } } void augment(int s,int t) { int i,min; min=oo; for (i=t;i!=s;i=pre[i]) if (g[pre[i]][i] min=g[pre[i]][i]; for (i=t;i!=s;i=pre[i]) { g[pre[i]][i]-=min;; g[i][pre[i]]+=min; f[pre[i]][i]+=min; f[i][pre[i]]-=min; } } int retreat(int *u,int s) { int v,min; min=n+49; for (v=0;v<=n+49;v++) if (g[*u][v]>0&&d[v] min=d[v]; sum[d[*u]]--; if ((sum[d[*u]])==0&&d[*u]<=n+49) return 0; d[*u]=min+1; sum[d[*u]]++; current[*u]=0; if (*u!=s) *u=pre[*u]; return 1; } void ISAP(int s,int t) { int u,v; rev_bfs(t); u=s; while (d[s] { for (v=current[u];v<=n+49;v++) if (g[u][v]>0&&d[u]==d[v]+1) break; if (v<=n+49) { current[u]=v; pre[v]=u; u=v; if (u==t) { augment(s,t); u=s; } } else if (retreat(&u,s)==0) return; } } void init() { int i,j,a,b,c,d,min,t,k,ans,max,st,en,temp; while (scanf("%d",&n)!=EOF&&n) { memset(map,0,sizeof(map));; for (i=1;i<=n;i++) { scanf("%d%d",&m,&t); map[48][i+48]=t/30; num=0; mm=0; for (j=1;j<=m;j++) { scanf("%d:%d %d:%d",&a,&b,&c,&d); if (a==c&&b==d) { for (k=0;k<48;k++) map[i+48][k]=1; continue; } if (c==0&&d==0) { num++; seg[num].x=a*60+b; seg[num].y=1440; } else if (a*60+b>c*60+d) { num++; seg[num].x=a*60+b; seg[num].y=1440; num++; seg[num].x=0; seg[num].y=c*60+d; } else { num++; seg[num].x=a*60+b; seg[num].y=c*60+d; } } if (num==0) continue; qsort(seg+1,num,sizeof(seg[1]),cmp); st=seg[1].x;en=seg[1].y; seg[num+1].x=1500;seg[num+1].y=1600; for (j=2;j<=num+1;j++) { a=seg[j].x; b=seg[j].y; if (st<=a&&a<=en&&en en=b; else if (a>en) { mm++; time[mm].x=st; time[mm].y=en; st=a; en=b; } } for (j=1;j<=mm;j++) { a=time[j].x/60; b=time[j].x-60*a; c=time[j].y/60; d=time[j].y-60*c; if (a==c) { if (b==0&&d>=30) map[i+48][a*2]=1; } else { if (b>0&&b<=30) b=30; if (b>30) { a++; b=0; } if (d<30) d=0; if (d>30) d=30; while (a!=c||b!=d) { map[i+48][a*2+b/30]=1; b+=30; if (b==60) { a++; b=0; } } } } } max=oo; for (j=0;j<48;j++) { temp=0; for (k=49;k if (map[k][j]>0) temp++; if (temp max=temp; } ans=0; for (j=1;j<=max;j++) { memset(g,0,sizeof(g)); memset(f,0,sizeof(f)); memset(current,0,sizeof(current)); for (i=0;i<=49+n;i++) for (k=0;k<=49+n;k++) g[i][k]=map[i][k]; for (i=0;i<48;i++) g[i][n+49]=j; ISAP(48,n+49); min=oo; for (i=0;i<48;i++) if (f[i][n+49] min=f[i][n+49]; if (min>ans) ans=min; } printf("%d\n",ans); } } int main() { init(); //system("pause"); return 0; } G:聊天就是Repeat 时间限制: 1000ms 内存限制: 65536kB 描述 百度Hi作为百度旗下的即时聊天工具，在百度公司内部很是流行。要实现这样 的一个聊天工具，最重要的问题就是要能保证我发出的内容能原封不动的在接收同学那里显示出来。今天，就给你一个机会，让你模拟一下百度Hi传递信息的过程，把我发给Robin的聊天内容原封不动的输出出来。 输入 输入的聊天内容数据有多组，每组数据占一行。 输出 与输入聊天内容完全相同的内容。请注意每组数据中的空格也要原封不动的被传过去噢~ 样例输入 Hello Robin 今天下午去五福颁奖，具体时间是2012年8月3日 15:40噢~ 样例输出 Hello Robin 今天下午去五福颁奖，具体时间是2012年8月3日 15:40噢~ #include #include /* author tilltheendwjx blog http://www.wendangku.net/doc/39d92648852458fb770b5616.html/wjh200821或者http://www.wendangku.net/doc/39d92648852458fb770b5616.html/tilltheendwjx/ */ using namespace std; int main() { while(1) { string str; getline(cin,str); if(str.length()<=0) break; cout< } //system("pause"); return 0; } H:用户请求中的品牌 时间限制: 1000ms 内存限制: 65536kB 描述 馅饼同学是一个在百度工作，做用户请求（query）分析的同学，他在用户请求中经常会遇到一些很奇葩的词汇。在比方说“johnsonjohnson”、“duckduck”， 这些词汇虽然看起来是一些词汇的单纯重复，但是往往都是一些特殊品牌的词汇，不能被拆分开。为了侦测出这种词的存在，你今天需要完成我给出的这个任务——“找出用户请求中循环节最多的子串”。 输入 输入数据包括多组，每组为一个全部由小写字母组成的不含空格的用户请求（字符串），占一行。用户请求的长度不大于100,000。 最后一行输入为#，作为结束的标志。 输出 对于每组输入，先输出这个组的编号（第n组就是输出“Case n:”）；然后输出这组用户请求中循环节最多的子串。如果一个用户请求中有两个循环节数相同的子串，请选择那个字典序最小的。 样例输入 ilovejohnsonjohnsonverymuch duckduckgo aaabbbcccisagoodcompany # 样例输出 Case 1: johnsonjohnson Case 2: duckduck Case 3: aaa #include #include #include #include #define MAXN 100002 int wa[MAXN], wb[MAXN], wv[MAXN], wd[MAXN], Height[MAXN], sa[MAXN], rank[MAXN]; int n; inline bool IsEqual(int *r, int a, int b, int l) { return (r[a] == r[b] && r[a + l] == r[b + l]); } void da(int *r, int m = 27) { int i, j, p, *x = wa, *y = wb, *t; memset(wd, 0, sizeof(wd)); for (i = 0; i < n; i++) wd[x[i] = r[i]]++; x[n] = y[n] = 0; for (i = 1; i < m; i++) wd[i] += wd[i - 1]; for (i = n - 1; i >= 0; i--) sa[--wd[x[i]]] = i; for (p = 1, j = 1; p <= n; m = p, j *= 2) { for(p = 0, i = n - j; i < n; i++) y[p++] = i; for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j; for(i = 0; i < n; i++) wv[i] = x[y[i]]; memset(wd, 0, sizeof(wd)); for(i = 0; i < n; i++) wd[wv[i]]++; for(i = 1; i < m; i++) wd[i] += wd[i - 1]; for(i = n - 1; i >= 0; i--) sa[--wd[wv[i]]] = y[i]; for(t = x, x = y, y = t, i = 1, p = 2,x[sa[0]] = 1; i < n; i++) x[sa[i]] = IsEqual(y, sa[i-1], sa[i], j) ? p - 1 : p++; } } void CalHeight(int *r) { int i, j, k; for (i = 0; i < n; i++)rank[sa[i]] = i; for (i = 0, Height[0] = k = 0; i < n; Height[rank[i++]] = k) for (k?k--:0, j=(rank[i]>0)?sa[rank[i]-1]:0; rank[i]>0&&r[i+k]==r[j+k]; k++); } int ffmin[MAXN][20]; void setf() { int i,j; memset(ffmin,0,sizeof(ffmin)); for(i=1;i<=n;i++){ ffmin[i][0]=Height[i]; } for(j=1;j<=(int)(log((double)(n+1))/log(2.0));j++) for(i=1;i+(1< ffmin[i][j]=ffmin[i][j-1] int findmin(int l,int r) { int k=(int)(log(1.0*(r-l+1))/log(2.0)); return ffmin[l][k] } char str[MAXN]; int r[MAXN]; int sp; int tsp; int maxl; int main() { int cases=0,i; while(scanf("%s",&str)!=EOF&&str[0]!="#") { cases++; printf("Case %d: ",cases); n=strlen(str); memset(r, 0, sizeof(r)); maxl=1; for (i = 0; i < n; i++) r[i] = str[i] - "a" + 1; da(r); CalHeight(r); setf(); int l,max=1; sp=0; for(l=1;l<=n/2;l++){ int cur=0; while(cur+l if(r[cur]==r[cur+l]){ int s,e; int k,lcp; s=rank[cur]; e=rank[cur+l]; if(s>e){ s^=e; e^=s; s^=e; } s++; lcp=findmin(s,e); tsp=cur; int ss=0; for (int p=cur - 1; p>= 0 && p > (cur-l) && r[p] == r[p + l];p--) if(++ss == (l-(lcp%l))) tsp= p; else if(rank[tsp] > rank[p]) tsp= p; k=(lcp+ss)/l+1; if(k>max){ max=k; maxl=l; sp=tsp; }