现在的位置: 首页 > 综合 > 正文

2012百度之星资格赛试题与AC代码

2014年08月07日 ⁄ 综合 ⁄ 共 22374字 ⁄ 字号 小 中 大 ⁄ 评论关闭

百度文库下载地址：http://wenku.baidu.com/view/39d92648852458fb770b5616.html

2012百度之星资格赛试题与AC代码

A:百度计算器的加法

时间限制: 1000ms 内存限制: 10000kB

描述
百度框计算中提供了计算器这个功能，模拟计算器中的复杂功能，我们最先需要解决的就是实现加法模块。今天就给你个机会，和百度计算器一样，计算一下十以内的加法吧。

输入
仅有一组数据，包含两个正整数，分别为a, b(0 <= a, b <= 10)

输出
一个正整数，暨输入a, b后对应的a+b的计算结果

样例输入
5 2

样例输出
7

 

[cpp] view
plaincopy

  1.  1 #include <stdio.h>  
  2.  2   
  3.  3 #include <stdlib.h>  
  4.  4   
  5.  5 /* 
  6.  6  
  7.  7 author tilltheendwjx 
  8.  8  
  9.  9 blog   http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/ 
  10. 10  
  11. 11 */  
  12. 12   
  13. 13 int main()  
  14. 14   
  15. 15 {  
  16. 16   
  17. 17     int a,b;  
  18. 18   
  19. 19     scanf("%d%d",&a,&b);  
  20. 20   
  21. 21     printf("%d",a+b);  
  22. 22   
  23. 23    //system("pause");  
  24. 24   
  25. 25     return 0;    
  26. 26   
  27. 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设备的数量。每个输出占一行。

样例输入
3
2 2 2
3 3 2 4
6 2 2 2 3 4 5

样例输出
3
7
13

[cpp] view
plaincopy

  1. #include <iostream>  
  2. using namespace std;  
  3. /* 
  4. author tilltheendwjx 
  5. blog   http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/  
  6. */  
  7. int main()  
  8. {  
  9.     int n;  
  10.     cin>>n;  
  11.     int k;  
  12.     int *a;  
  13.     int *b=new int[n];  
  14.     for(int i=0;i<n;i++)  
  15.     {  
  16.        cin>>k;  
  17.        a=new int[k];  
  18.        int sum=0;  
  19.        for(int j=0;j<k;j++)  
  20.        {  
  21.                cin>>a[j];  
  22.                sum+=a[j];  
  23.        }  
  24.        b[i]=sum+1-k;  
  25.     }  
  26.     for(int i=0;i<n;i++)  
  27.     {  
  28.          
  29.        cout<<b[i]<<endl;  
  30.     }  
  31.     delete a;  
  32.    //system("pause");  
  33.    return 0;      
  34. }  


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

[cpp] view
plaincopy

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <math.h>  
  4. /* 
  5. author tilltheendwjx 
  6. blog   http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/  
  7. */  
  8. int main()  
  9. {  
  10.    float a[12];  
  11.    float avg=0;  
  12.    int i=0;  
  13.    for(i=0;i<2;i++)  
  14.    {  
  15.       a[i]=0.00;  
  16.    }  
  17.    for(i=0;i<12;i++)  
  18.    {  
  19.       scanf("%f",&a[i]);  
  20.       avg=avg+a[i];  
  21.    }  
  22.    printf("$%.2f",(float)(avg/12));  
  23.    //system("pause");  
  24.    return 0;     
  25. }   

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
0
15
12

[cpp] view
plaincopy

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. /* 
  4. author tilltheendwjx 
  5. blog   http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/  
  6. */  
  7. int main()  
  8. {  
  9.    int n;  
  10.    int *a;  
  11.    int *b;  
  12.    int *c;  
  13.    int i=0;  
  14.    scanf("%d",&n);  
  15.    a=(int *)malloc(sizeof(int)*n);  
  16.    b=(int *)malloc(sizeof(int)*n);  
  17.    c=(int *)malloc(sizeof(int)*n);  
  18.    for(i=0;i<n;i++)  
  19.    {  
  20.        scanf("%d:%d",&a[i],&b[i]);  
  21.        if(b[i]!=0)  
  22.        { c[i]=0;}  
  23.        else  
  24.        {  
  25.            if((a[i]+12)==24)  
  26.               c[i]=24;  
  27.            else  
  28.               c[i]=(a[i]+12)%24;  
  29.        }  
  30.           
  31.    }  
  32.    for(i=0;i<n;i++)  
  33.    {  
  34.        printf("%d\n",c[i]);  
  35.           
  36.    }  
  37.    free(a);  
  38.    free(b);  
  39.    free(c);  
  40.    //system("pause");  
  41.    return 0;     
  42. }   


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!

[cpp] view
plaincopy

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <math.h>  
  4. #include <string.h>  
  5. #include <ctype.h>  
  6. /* 
  7. author tilltheendwjx 
  8. blog   http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/  
  9. */  
  10. int main()  
  11. {  
  12.    char a[100];  
  13.    char b[100];  
  14.    int i=0;  
  15.    int j=0;  
  16.    int flag=0;  
  17.    int javature=0;  
  18.    int cture=0;  
  19.    scanf("%s",a);  
  20.    for(i=0;i<100;i++)  
  21.    {  
  22.        if(a[i]=='\0')  
  23.          break;  
  24.        if(a[i]=='_')  
  25.        {  
  26.           if((islower(a[i+1])==0)||i==0||a[i+1]=='\0')  
  27.              flag=1;  
  28.           else  
  29.              cture=1;  
  30.           i++;  
  31.           b[j]=(char)toupper(a[i]);  
  32.           j++;  
  33.        }  
  34.        else if((isupper(a[i])!=0))  
  35.        {  
  36.           if((a[i-1]=='_')||i==0)  
  37.             flag=1;  
  38.           else   
  39.             javature=1;  
  40.           b[j]='_';  
  41.           j++;  
  42.           b[j]=(char)tolower(a[i]);  
  43.           j++;  
  44.        }  
  45.        else  
  46.        {  
  47.            b[j]=a[i];  
  48.            j++;  
  49.        }  
  50.            
  51.    }  
  52.    b[j]='\0';  
  53.    if(flag==0)  
  54.    {  
  55.       if(javature==1&&cture==1)  
  56.          printf("Error!");  
  57.       else  
  58.          printf("%s",b);  
  59.    }  
  60.    else  
  61.        printf("Error!");  
  62.    //system("pause");  
  63.    return 0;     
  64. }   



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
0

样例输出
2
1
1

[cpp] view
plaincopy

  1. #include<stdio.h>  
  2.  #include<memory.h>  
  3.  #include<stdlib.h>  
  4.  #define maxn 102  
  5.   int d[maxn],g[maxn][maxn],f[maxn][maxn],pre[maxn],map[maxn][maxn],sum[maxn],current[maxn];  
  6.   int n,m,num,mm;  
  7.   struct node  
  8.  {  
  9.      int x,y;  
  10.  }seg[1000],time[1000];  
  11.   #define oo 0xfffffff  
  12.   int cmp(const void *a,const void *b)  
  13.  {  
  14.      struct node *va=(struct node*)a;  
  15.      struct node *vb=(struct node*)b;  
  16.      return va->x-vb->x;  
  17.  }  
  18.   void rev_bfs(int t)  
  19.  {  
  20.      int queue[maxn],flag[maxn];  
  21.      int head,tail,i;  
  22.      memset(sum,0,sizeof(sum));  
  23.      for (i=0;i<=n+49;i++)  
  24.      {  
  25.          d[i]=n+49;  
  26.          sum[n+49]++;  
  27.      }  
  28.      sum[n+49]--;  
  29.      sum[0]++;  
  30.      d[t]=0;  
  31.      queue[1]=t;  
  32.      flag[t]=1;  
  33.      head=1;tail=1;  
  34.      memset(flag,0,sizeof(flag));  
  35.      while (head<=tail)  
  36.      {  
  37.          for (i=0;i<=n+49;i++)  
  38.              if (flag[i]==0&&g[i][queue[head]]>0)  
  39.              {  
  40.                  queue[++tail]=i;  
  41.                  d[i]=d[queue[head]]+1;  
  42.                  sum[n+49]--;  
  43.                  sum[d[i]]++;  
  44.                  flag[i]=1;  
  45.              }  
  46.          head++;  
  47.      }  
  48.  }  
  49.   void augment(int s,int t)  
  50.  {  
  51.      int i,min;  
  52.      min=oo;  
  53.      for (i=t;i!=s;i=pre[i])  
  54.           if (g[pre[i]][i]<min)  
  55.              min=g[pre[i]][i];  
  56.      for (i=t;i!=s;i=pre[i])  
  57.      {  
  58.          g[pre[i]][i]-=min;;  
  59.          g[i][pre[i]]+=min;  
  60.          f[pre[i]][i]+=min;  
  61.          f[i][pre[i]]-=min;  
  62.      }  
  63.  }  
  64.   int retreat(int *u,int s)  
  65.  {  
  66.      int v,min;  
  67.      min=n+49;  
  68.      for (v=0;v<=n+49;v++)  
  69.          if (g[*u][v]>0&&d[v]<min)  
  70.              min=d[v];  
  71.      sum[d[*u]]--;  
  72.      if ((sum[d[*u]])==0&&d[*u]<=n+49) return 0;  
  73.      d[*u]=min+1;  
  74.      sum[d[*u]]++;  
  75.      current[*u]=0;  
  76.      if (*u!=s) *u=pre[*u];  
  77.      return 1;  
  78.  }  
  79.   void ISAP(int s,int t)  
  80.  {  
  81.      int u,v;  
  82.      rev_bfs(t);  
  83.      u=s;  
  84.      while (d[s]<n+50)  
  85.      {   
  86.          for (v=current[u];v<=n+49;v++)                                                                              
  87.              if (g[u][v]>0&&d[u]==d[v]+1)  
  88.                  break;  
  89.          if (v<=n+49)  
  90.          {  
  91.              current[u]=v;  
  92.              pre[v]=u;  
  93.              u=v;  
  94.              if (u==t)  
  95.              {  
  96.                  augment(s,t);  
  97.                  u=s;  
  98.              }  
  99.          }  
  100.          else if (retreat(&u,s)==0) return;  
  101.      }  
  102.  }  
  103.  void init()  
  104.  {  
  105.      int i,j,a,b,c,d,min,t,k,ans,max,st,en,temp;  
  106.      while (scanf("%d",&n)!=EOF&&n)  
  107.      {  
  108.          memset(map,0,sizeof(map));;  
  109.          for (i=1;i<=n;i++)  
  110.          {  
  111.              scanf("%d%d",&m,&t);  
  112.              map[48][i+48]=t/30;  
  113.              num=0;  
  114.              mm=0;  
  115.              for (j=1;j<=m;j++)  
  116.              {  
  117.                  scanf("%d:%d %d:%d",&a,&b,&c,&d);  
  118.                  if (a==c&&b==d)  
  119.                  {  
  120.                      for (k=0;k<48;k++)  
  121.                          map[i+48][k]=1;  
  122.                      continue;  
  123.                  }  
  124.                  if (c==0&&d==0)  
  125.                  {  
  126.                      num++;  
  127.                      seg[num].x=a*60+b;  
  128.                      seg[num].y=1440;  
  129.                  }  
  130.                  else if (a*60+b>c*60+d)  
  131.                  {  
  132.                      num++;  
  133.                      seg[num].x=a*60+b;  
  134.                      seg[num].y=1440;  
  135.                      num++;  
  136.                      seg[num].x=0;  
  137.                      seg[num].y=c*60+d;  
  138.                  }  
  139.                  else  
  140.                  {  
  141.                      num++;  
  142.                      seg[num].x=a*60+b;  
  143.                      seg[num].y=c*60+d;  
  144.                  }  
  145.              }  
  146.              if (num==0) continue;  
  147.              qsort(seg+1,num,sizeof(seg[1]),cmp);  
  148.              st=seg[1].x;en=seg[1].y;  
  149.              seg[num+1].x=1500;seg[num+1].y=1600;  
  150.              for (j=2;j<=num+1;j++)  
  151.              {  
  152.                  a=seg[j].x;  
  153.                  b=seg[j].y;  
  154.                  if (st<=a&&a<=en&&en<b)  
  155.                      en=b;  
  156.                  else if (a>en)  
  157.                  {  
  158.                      mm++;  
  159.                      time[mm].x=st;  
  160.                      time[mm].y=en;  
  161.                      st=a;  
  162.                      en=b;  
  163.                  }  
  164.              }  
  165.              for (j=1;j<=mm;j++)  
  166.              {  
  167.                  a=time[j].x/60;  
  168.                  b=time[j].x-60*a;  
  169.                  c=time[j].y/60;  
  170.                  d=time[j].y-60*c;  
  171.                  if (a==c)  
  172.                  {  
  173.                      if (b==0&&d>=30)  
  174.                          map[i+48][a*2]=1;  
  175.                  }  
  176.                  else  
  177.                  {  
  178.                      if (b>0&&b<=30) b=30;  
  179.                      if (b>30)   
  180.                      {  
  181.                          a++;  
  182.                          b=0;  
  183.                      }  
  184.                      if (d<30) d=0;  
  185.                      if (d>30) d=30;  
  186.                      while (a!=c||b!=d)  
  187.                      {  
  188.                          map[i+48][a*2+b/30]=1;  
  189.                          b+=30;  
  190.                          if (b==60)  
  191.                          {  
  192.                              a++;  
  193.                              b=0;  
  194.                          }  
  195.                      }  
  196.                  }  
  197.              }  
  198.          }  
  199.          max=oo;  
  200.          for (j=0;j<48;j++)  
  201.          {  
  202.              temp=0;  
  203.              for (k=49;k<n+49;k++)  
  204.                  if (map[k][j]>0) temp++;  
  205.              if (temp<max)  
  206.                  max=temp;  
  207.          }  
  208.          ans=0;  
  209.          for (j=1;j<=max;j++)  
  210.          {  
  211.              memset(g,0,sizeof(g));  
  212.              memset(f,0,sizeof(f));  
  213.              memset(current,0,sizeof(current));  
  214.              for (i=0;i<=49+n;i++)  
  215.                  for (k=0;k<=49+n;k++)  
  216.                      g[i][k]=map[i][k];  
  217.              for (i=0;i<48;i++)  
  218.                  g[i][n+49]=j;  
  219.              ISAP(48,n+49);  
  220.              min=oo;  
  221.              for (i=0;i<48;i++)  
  222.                  if (f[i][n+49]<min)  
  223.                      min=f[i][n+49];  
  224.              if (min>ans) ans=min;  
  225.          }  
  226.          printf("%d\n",ans);  
  227.      }  
  228.  }  
  229.  int main()  
  230.  {  
  231.      init();  
  232.      //system("pause");  
  233.      return 0;  
  234.  }  



G:聊天就是Repeat

时间限制: 1000ms 内存限制: 65536kB

描述
百度Hi作为百度旗下的即时聊天工具，在百度公司内部很是流行。要实现这样的一个聊天工具，最重要的问题就是要能保证我发出的内容能原封不动的在接收同学那里显示出来。今天，就给你一个机会，让你模拟一下百度Hi传递信息的过程，把我发给Robin的聊天内容原封不动的输出出来。

输入
输入的聊天内容数据有多组，每组数据占一行。

输出
与输入聊天内容完全相同的内容。请注意每组数据中的空格也要原封不动的被传过去噢~

样例输入
Hello Robin
今天下午去五福颁奖，具体时间是2012年8月3日 15:40噢~

样例输出
Hello Robin
今天下午去五福颁奖，具体时间是2012年8月3日 15:40噢~

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <string>  
  3. /* 
  4. author tilltheendwjx 
  5. blog   http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/  
  6. */  
  7. using namespace std;  
  8. int main()  
  9. {  
  10.       
  11.     while(1)  
  12.     {  
  13.           string str;  
  14.           getline(cin,str);  
  15.           if(str.length()<=0)  
  16.             break;   
  17.           cout<<str<<endl;  
  18.     }  
  19.    //system("pause");  
  20.    return 0;      
  21. }  



H:用户请求中的品牌

时间限制: 1000ms 内存限制: 65536kB

描述
馅饼同学是一个在百度工作，做用户请求（query）分析的同学，他在用户请求中经常会遇到一些很奇葩的词汇。在比方说“johnsonjohnson”、“duckduck”，这些词汇虽然看起来是一些词汇的单纯重复，但是往往都是一些特殊品牌的词汇，不能被拆分开。为了侦测出这种词的存在，你今天需要完成我给出的这个任务——“找出用户请求中循环节最多的子串”。

输入
输入数据包括多组，每组为一个全部由小写字母组成的不含空格的用户请求（字符串），占一行。用户请求的长度不大于100,000。
最后一行输入为#，作为结束的标志。

输出
对于每组输入，先输出这个组的编号（第n组就是输出“Case n:”）；然后输出这组用户请求中循环节最多的子串。如果一个用户请求中有两个循环节数相同的子串，请选择那个字典序最小的。

样例输入
ilovejohnsonjohnsonverymuch
duckduckgo
aaabbbcccisagoodcompany
#

样例输出
Case 1: johnsonjohnson
Case 2: duckduck
Case 3: aaa

 

[cpp] view
plaincopy

  1. #include <stdio.h>  
  2. #include<cstring>  
  3. #include<math.h>  
  4. #include<string.h>  
  5. #define MAXN  100002  
  6. int wa[MAXN], wb[MAXN], wv[MAXN], wd[MAXN], Height[MAXN], sa[MAXN], rank[MAXN];  
  7. int n;  
  8. inline bool IsEqual(int *r, int a, int b, int l)  
  9. {  
  10.     return (r[a] == r[b] && r[a + l] == r[b + l]);  
  11. }  
  12. void da(int *r, int m = 27)  
  13. {  
  14.     int i, j, p, *x = wa, *y = wb, *t;  
  15.     memset(wd, 0, sizeof(wd));  
  16.     for (i = 0; i < n; i++) wd[x[i] = r[i]]++; x[n] = y[n] = 0;  
  17.     for (i = 1; i < m; i++) wd[i] += wd[i - 1];  
  18.     for (i = n - 1; i >= 0; i--) sa[--wd[x[i]]] = i;  
  19.     for (p = 1, j = 1; p <= n; m = p, j *= 2)  
  20.     {  
  21.         for(p = 0, i = n - j; i < n; i++) y[p++] = i;  
  22.         for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j;  
  23.         for(i = 0; i < n; i++) wv[i] = x[y[i]];  
  24.         memset(wd, 0, sizeof(wd));  
  25.         for(i = 0; i < n; i++) wd[wv[i]]++;  
  26.         for(i = 1; i < m; i++) wd[i] += wd[i - 1];  
  27.         for(i = n - 1; i >= 0; i--) sa[--wd[wv[i]]] = y[i];  
  28.         for(t = x, x = y, y = t, i = 1, p = 2,x[sa[0]] = 1; i < n; i++)  
  29.             x[sa[i]] = IsEqual(y, sa[i-1], sa[i], j) ? p - 1 : p++;  
  30.     }  
  31. }  
  32. void CalHeight(int *r)  
  33. {  
  34.     int i, j, k;  
  35.     for (i = 0; i < n; i++)rank[sa[i]] = i;  
  36.     for (i = 0, Height[0] = k = 0; i < n; Height[rank[i++]] = k)  
  37.         for (k?k--:0, j=(rank[i]>0)?sa[rank[i]-1]:0; rank[i]>0&&r[i+k]==r[j+k]; k++);  
  38. }  
  39. int ffmin[MAXN][20];  
  40. void setf()  
  41. {  
  42.  int i,j;  
  43.  memset(ffmin,0,sizeof(ffmin));  
  44.  for(i=1;i<=n;i++){  
  45.   ffmin[i][0]=Height[i];  
  46.  }  
  47.  for(j=1;j<=(int)(log((double)(n+1))/log(2.0));j++)  
  48.   for(i=1;i+(1<<j)-1<=n;i++)  
  49.    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];  
  50. }  
  51. int findmin(int l,int r)  
  52. {  
  53.  int k=(int)(log(1.0*(r-l+1))/log(2.0));  
  54.  return ffmin[l][k]<ffmin[r-(1<<k)+1][k]?ffmin[l][k]:ffmin[r-(1<<k)+1][k];  
  55. }  
  56. char str[MAXN];  
  57. int r[MAXN];  
  58. int sp;  
  59. int tsp;  
  60. int maxl;  
  61. int main()  
  62. {  
  63.     int cases=0,i;  
  64.     while(scanf("%s",&str)!=EOF&&str[0]!='#')  
  65.     {  
  66.       cases++;  
  67.       printf("Case %d: ",cases);  
  68.       n=strlen(str);  
  69.       memset(r, 0, sizeof(r));  
  70.       maxl=1;  
  71.       for (i = 0; i < n; i++)  
  72.        r[i] = str[i] - 'a' + 1;  
  73.        da(r);  
  74.        CalHeight(r);  
  75.        setf();  
  76.        int l,max=1;  
  77.        sp=0;  
  78.        for(l=1;l<=n/2;l++){  
  79.        int cur=0;  
  80.        while(cur+l<n){  
  81.        if(r[cur]==r[cur+l]){  
  82.        int s,e;  
  83.        int k,lcp;  
  84.        s=rank[cur];  
  85.        e=rank[cur+l];  
  86.        if(s>e){  
  87.         s^=e;  
  88.         e^=s;  
  89.         s^=e;  
  90.        }  
  91.           s++;  
  92.           lcp=findmin(s,e);  
  93.        tsp=cur;  
  94.        int ss=0;  
  95.                     for (int p=cur - 1; p>= 0 && p > (cur-l) && r[p] == r[p + l];p--)  
  96.            if(++ss == (l-(lcp%l)))  
  97.             tsp= p;  
  98.            else if(rank[tsp] > rank[p])  
  99.             tsp= p;  
  100.        k=(lcp+ss)/l+1;  
  101.        if(k>max){   
  102.        max=k;  
  103.        maxl=l;  
  104.        sp=tsp;  
  105.        }  
  106.        else if(k==max&&rank[tsp]<rank[sp]){  
  107.         sp=tsp;  
  108.         maxl=l;  
  109.        }  
  110.        }  
  111.        cur+=l;  
  112.       }  
  113.       }  
  114.       if(max>1){  
  115.         for(i=sp;i<sp+max*maxl;i++)  
  116.          printf("%c",str[i]);  
  117.         printf("\n");  
  118.       }  
  119.       else{  
  120.        char c='z';  
  121.       for(i=0;i<n;i++)  
  122.        if(str[i]<c)  
  123.        c=str[i];  
  124.       printf("%c\n",c);  
  125.       }  
  126.      }  
  127.      return 0;  
  128. }  


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应该由空格分隔，并被舍入到小数点后第六位。

样例输入
1000
0 1 1 1 2 1
0 0.6 1.6
1000
0 0 0 1 1 0
0.4142135 0 0
1000
0 0 1 0 2 1
0 0.414213562373 1
1000
0 0 0 -1 0 1
0 0 1
1000
0 0 0 1 0 -1
0 1 0
1000
0 0 1 0 -1 0
0 1 0
1000
0 0 -1 0 1 0
0 0 1
100
0 0 0 1 1 0
0 10 10
0

样例输出
Case 1:
0.200000 1.000000
Case 2:
1.000000 1.000000
Case 3:
0.000000 1.000000
Case 4:
0.000000 -0.500000
Case 5:
0.000000 -0.500000
Case 6:
-0.500000 0.000000
Case 7:
-0.500000 0.000000
Case 8:
0.000000 0.000000

[cpp] view
plaincopy

  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次后（每次两个按钮选一个按），可以到达的最低楼层数。

样例输入
10 3
15 4
15 12
7 12

样例输出
13

提示
按钮上的移动楼层数无法改变，比方说从8层向下9层是不可行的

[cpp] view
plaincopy

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <math.h>  
  4. /* 
  5. author tilltheendwjx 
  6. blog   http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/  
  7. */   
  8. int main()  
  9. {  
  10.     int n,m;  
  11.     int *a;  
  12.     int *b;  
  13.     int i=0;  
  14.     int reault=0;  
  15.     int j=0;  
  16.     int tmp;  
  17.     int low=1;  
  18.     int high=0;  
  19.     scanf("%d%d",&n,&m);  
  20.     high=n;  
  21.     int mid;  
  22.     a=(int *)malloc(sizeof(int)*m);  
  23.     b=(int *)malloc(sizeof(int)*m);  
  24.     for(i=0;i<m;i++)  
  25.     {  
  26.         scanf("%d%d",&a[i],&b[i]);   
  27.     }  
  28.     for(i=0;i<m;i++)  
  29.     {  
  30.         low=1;  
  31.         high=n;  
  32.         while((high-low)>2)  
  33.         {  
  34.            mid=(low+high)/2;  
  35.            tmp=a[i]*mid-b[i]*(n-mid);  
  36.            if(tmp>0)  
  37.             {  
  38.                  high=mid;        
  39.             }  
  40.             else  
  41.             {  
  42.                  low=mid+1;  
  43.             }              
  44.                          
  45.         }  
  46.         for(j=low;j<=high;j++)  
  47.         {  
  48.                  tmp=a[i]*j-b[i]*(n-j);  
  49.                  if(tmp>0)   
  50.                  {break;}         
  51.         }       
  52.         if(reault==0)  
  53.            reault=tmp;  
  54.         else if(reault>tmp)  
  55.            reault=tmp;  
  56.         else  
  57.            reault=reault;  
  58.              
  59.     }  
  60.     printf("%d",reault);  
  61.     //system("pause");  
  62.    return 0;     
  63. }  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞