百度之星初赛（1）解题报告

                         超级赛亚ACMer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1536    Accepted Submission(s): 437

Problem Description

百小度是一个ACMer，也是一个超级赛亚人，每个ACMer都有一个战斗力，包括百小度。
所谓超级赛亚人的定义，是说如果在对抗中刚好接近极限状态，那就会激发斗志，实力提升.

具体来说，就是百小度现在要接受一些ACMer的挑战了，这些ACMer有n个人，第i个人的战斗力是a[i]。


百小度接下来可以自主安排与这n个ACMer的PK顺序，他要想在PK赛中赢过另外一个ACMer，就必须使得自己的战斗力不小于对方（平局情况他会按照百小度字典上的规则把自己排在第一).

如果百小度的战斗力大于对方，那么百小度就会轻易获胜，得不到锻炼并且骄傲起来，他以后的战斗力将保持在这个值，再也不会发生改变。
如果百小度的战斗力等于对方，那么百小度在获胜的同时也会感到很吃力，但是这会激发百小度的斗志，使得他刻苦刷题，在下场PK赛之前，战斗力最多提升k点（即可以提升0~k点任意值）.

k是百小度的潜力提升上限，会被给定一个初始值，这个潜力提升上限k在后面的比赛中会下降.

每战胜一个ACMer，这个潜力上限k将减少1（因为超级赛亚人百小度也会感到累），但k最低只会减少到0，即不会出现战斗力下降的情况
。也就是第一次比赛如果激发了百小度的斗志，他能把战斗力提升0~k的任一值，如果第二次比赛继续被激发斗志，他能在第一次提升后的基础上，把战斗力再提升0 max(0,k−1) ,依次类推…

m是百小度的初始战斗力上限，也就是百小度第一次进行PK赛的时候，可以选择0~m的任意一个值作为他的战斗力.

现在希望你编写程序，判断一下百小度是否战胜所有的ACMer.

 

Input

输入包含多组数据（数据不超过500组)

第一行一个整数T，表示T组数据

对于每组数据，第一行包括三个整数n,m,k(1≤n≤104,1≤m,k≤108)

第二行包括n个正整数，表示彪形大汉的战斗力（战斗力为不超过1012 的正整数）

 

Output

对于每组数据，先输出一行Case #i: (1≤i≤T)

如果百小度能打败所有的ACMer，再输出"why am I so diao?"

否则再输出"madan!"

 

Sample Input

2

5 11 3

15 13 10 9 8

5 11 3

8 9 10 13 16

 

Sample Output

Case #1:

why am I so diao?

Case #2:

madan!

Hint

第一组样例解释 5个ACMer，初始战斗力选择范围是[0,11],接下来每场战斗力提升上限是3,2,1,0,0,...,0 百小度首先使得自己的初始战斗力为10，打败战斗力为10的第一个ACMer， 然后选择战斗力提升3，变成13，打败战斗力为13的第二个ACMer， 然后选择战斗力提升2，变成15，打败战斗力为15的第三个ACMer， 之后再以任意顺序打败剩下的ACMer

 

Source

2015年百度之星程序设计大赛 - 初赛(1) 

 

题意：   就好比上台阶，每次自己跳跃的高度有限，怎么样跳到顶点是一个思路。

思路：    对于给定的那些战斗力的进行升序排序，然后采取贪心策略，每次尽可能的往上走。

 

代码：

   

#include <stdio.h>
#include<algorithm>
#define maxn 10005
long long aa[maxn];
int main()
{
    int cnt=1,cas,i;
    long long nn,mm,kk,res;
    scanf("%d",&cas);
    while(cas--){
      scanf("%lld %lld %lld ",&nn,&mm,&kk);
      for(i=0 ; i<nn ; i++)
          scanf("%lld",aa+i);
      std::sort(aa,aa+nn);
      printf("Case #%d:
",cnt++);
      for(res=mm,i=0 ; i<nn ; i++ )
          if(aa[i]<=mm) res=aa[i];
        else break;

      while(i!=0&&i<nn){
       int j=i;
        while(j<nn&&res+kk>=aa[j]) j++;
        if(j==i)break;
         else res=aa[j-1];
        if(kk>0) kk--;
        i=j;
      }
      if(res>=aa[nn-1])
            puts("why am I so diao?");
        else
            puts("madan!");
    }
    return 0;
}

          找连续数

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 801    Accepted Submission(s): 294

Problem Description

小度熊拿到了一个无序的数组，对于这个数组，小度熊想知道是否能找到一个k 的区间，里面的 k 个数字排完序后是连续的。

现在小度熊增加题目难度，他不想知道是否有这样的 k 的区间，而是想知道有几个这样的 k 的区间。

 

Input

输入包含一组测试数据。

第一行包含两个整数n，m，n代表数组中有多少个数字，m 代表针对于此数组的询问次数，n不会超过10的4次方，m 不会超过1000。第二行包含n个正整数，第 I 个数字代表无序数组的第 I 位上的数字，数字大小不会超过2的31次方。接下来 m 行，每行一个正整数 k，含义详见题目描述，k 的大小不会超过1000。

 

Output

第一行输"Case #i:"。(由于只有一组样例，只输出”Case #1:”即可)

然后对于每个询问的 k，输出一行包含一个整数，代表数组中满足条件的 k 的大小的区间的数量。

 

Sample Input

6 2 3 2 1 4 3 5 3 4

 

Sample Output

Case #1: 2 2

 

Source

2015年百度之星程序设计大赛 - 初赛(1) 

 

思路：  对于一个集合{a1,a2,a3,a4, .... an }map，我们如何知道里面的数是连续，其实只需要满足这样的特征： 集合中最大值 和集合中最小值的差+1 = 集合中元素的个数 。  我们就可以去说，这个集合是连续的。

      

#include<iostream>
#include<map>
#include<stdio.h>
#include<string.h>

const int maxn= 10005;
int n,m,k;
int aa[maxn];
int res[1005];
int main()
{
   int T,cas=1;
   int max_a ,min_a ;
   std::map<int ,bool>tmp ;
  while(~scanf("%d%d",&n,&m)){

   for(int i=0;i<n;i++)
         scanf("%d",aa+i);
    //采用离线的方法
    memset(res, 0,sizeof(res));
    for(int i=0;i<n ;i++){
            max_a = aa[i];
            min_a = aa[i];
            tmp.clear();
       for(int j=i ; j<n&&j<1000+i;j++){
            if(max_a < aa[j] ) max_a = aa[j];
            if(min_a > aa[j] ) min_a = aa[j];
             tmp[aa[j]]=true;
          if(max_a -min_a==j-i&&max_a -min_a+1==tmp.size())
            res[max_a -min_a+1]++;
       }
    }
    printf("Case #%d:
",cas++);
   for(int i=0; i<m;i++)
   {
        scanf("%d",&k);
        printf("%d
",res[k]);
   }
   }
 return 0;
}

     很危险的滑了过去...920ms  

  

序列变换

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 581    Accepted Submission(s): 287

Problem Description

给定序列A={A1,A2,...,An} , 要求改变序列A中的某些元素，形成一个严格单调的序列B（严格单调的定义为：Bi<Bi+1,1≤i<N ）。

我们定义从序列A到序列B变换的代价为cost(A,B)=max(|Ai−Bi|)(1≤i≤N) 。

请求出满足条件的最小代价。

注意，每个元素在变换前后都是整数。

 

Input

第一行为测试的组数T(1≤T≤10) .

对于每一组：
第一行为序列A的长度N(1≤N≤105) ，第二行包含N个数，A1,A2,...,An .
序列A中的每个元素的值是正整数且不超过106 。

 

Output

对于每一个测试样例，输出两行：

第一行输出："Case #i:"。i代表第 i 组测试数据。

第二行输出一个正整数，代表满足条件的最小代价。

 

Sample Input

2 2 1 10 3 2 5 4

 

Sample Output

Case #1: 0 Case #2: 1

 

Source

2015年百度之星程序设计大赛 - 初赛(1) 

题意：  其实求的最小代价res，就是对于任意集合A{},使得里面的元素+—res，成为一个单调数列....

 

 刚开始搞不懂题目究竟是什么意思！ ╮(╯▽╰)╭

      简单的二分

代码：
  

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define maxn  100005
int aa[maxn];

bool solve(int var ,int n){
     //对于a[i]+|- var 变成单调数列
   int tmp = var +aa[n-1];
    for(int i=n-2; i>=0 ;i-- ){
         if (abs(tmp - 1 - aa[i]) <= var)
               tmp = tmp - 1;
        else if (tmp - 1 >= aa[i])
            tmp = aa[i] + var;
        else
            return 0;
    }
  return 1;
}
int main()
{
 int t,n;
 scanf("%d",&t);
 for(int cas=1;cas<=t;cas++){
     scanf("%d",&n);
    for(int i=0; i<n ;i++)
        scanf("%d",aa+i);

    printf("Case #%d:
",cas);
    int mid ,ri=1000005,le=0;
    while(le<ri){
         mid = le +((ri-le)>>1L);
        //判断是否为单调数列
        if(solve(mid,n))
            ri=mid ;
        else
            le = mid+1;
    }
    printf("%d
",le);
 }
 return 0;
}

                              KPI

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 639    Accepted Submission(s): 267

Problem Description

你工作以后, KPI 就是你的全部了. 我开发了一个服务，取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录，有时我想知道当前管道内请求的重要值得中间值。

 

Input

有大约100组数据。

每组数据第一行有一个n(1≤n≤10000) ，代表服务记录数。

接下来有n行，每一行有3种形式
  "in x": 代表重要值为x(0≤x≤109) 的请求被推进管道。
  "out": 代表服务拉取了管道头部的请求。
  "query: 代表我想知道当前管道内请求重要值的中间值. 那就是说，如果当前管道内有m条请求, 我想知道，升序排序后第floor(m/2)+1th 条请求的重要值.

为了让题目简单，所有的x都不同，并且如果管道内没有值，就不会有"out"和"query"操作。

 

Output

对于每组数据，先输出一行

Case #i:
然后每一次"query"，输出当前管道内重要值的中间值。

 

Sample Input

6 in 874 query out in 24622 in 12194 query

 

Sample Output

Case #1: 874 24622

 

Source

2015年百度之星程序设计大赛 - 初赛(1) 

 

这道题刚开始用堆来处理，发现总是出错！ 后来在看了下别人的解题报告，发现了一种新的思路，运用两个set集合，利用红黑树的特性。分段来进行排序

但是要总是保持这两颗树的元素个数之差保持在小于2的状态。而且要满足上层集合的个数始终大于或者等于下层集合个数。

  

#include<stdio.h>
#include<string.h>
#include<set>
#include<queue>
#include<stdlib.h>
#include<iostream>

int tt ,x,tmp,cnt=1;
char cmd[8];
int main( void )
{
   std::set<int> low,hig;

while(scanf("%d",&tt)!=EOF){
        std::queue<int>aa;
        printf("Case #%d:
",cnt++);
        low.clear();
        hig.clear();

  while(tt--){
    scanf("%s",cmd);
    if(cmd[0]=='i'){

        scanf("%d",&x);
        aa.push(x);
     if(hig.empty()|| x > *hig.begin())
               hig.insert(x);
      else
           low.insert(x);

    }
    else if(cmd[0]=='o'){

         tmp=aa.front();
         aa.pop();
       if(low.count(tmp))
           low.erase(tmp);
       else
           hig.erase(tmp);

    }else if(cmd[0]=='q')
        printf("%d
",*hig.begin());

     if(low.size()+1<hig.size()){
            low.insert(*hig.begin());
            hig.erase(*hig.begin());
        }
        else if(low.size()>hig.size()){
            hig.insert(*low.rbegin());
            low.erase(*low.rbegin());
        }
    }
  }
 return 0;
}

   方法二  利用线段树处理，类似于一个单点更新和离散化处理...

     

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<iostream>
#include<algorithm>


using namespace std;
const int maxn=10005;

int Hash[maxn],sum[maxn<<2];
int cnt;

typedef struct node{

     int var ;
     char cmd[6];

}Node;

void Push(int pos ){
    sum[pos]=sum[pos<<1]+sum[pos<<1|1];
}

 void Build(int st ,int en ,int pos){
    if(st==en){
        sum[st]=0;
        return ;
    }
    int mid=st+((en-st)>>1L);
    Build(st,mid,pos<<1);
    Build(mid+1,en,pos<<1|1);
    Push(pos);
 }

 void Update(int st ,int en ,int value ,int pos ,int find_p){

    if(st==en) {  //单点更新，说明增加或者减少一个点
      sum[pos]=value;
      return ;
    }
    int mid =st+((en-st)>>1L);
    if(find_p<=mid)
        Update(st , mid , value , pos<<1 , find_p);
    else
        Update(mid+1 , en , value , pos<<1|1 ,find_p);
    Push(pos);
 }

 int query(int st ,int en ,int pos ,int num){
    if(st==en)
       return st;
    int mid = st + ((en -st)>>1L);
    if(sum[pos<<1]>=num)
      return   query(st,mid,pos<<1 , num);
    else
      return   query(mid+1,en,pos<<1|1,num-sum[pos<<1]);  //相对起点为0
 }

//学习了某位大牛的STL用法
int HASH(int x ){

    return lower_bound(Hash ,Hash+cnt,x)-Hash;
}

Node tem[maxn];
int main()
{
    int nn,cas=1,pos;
    while(~scanf("%d",&nn)){
        queue<int>aa;
         cnt=0;
        memset(sum,0,sizeof(sum));
        printf("Case #%d:
",cas++);

        for(int i=0;i<nn;i++){
           scanf("%s",tem[i].cmd);
           if(tem[i].cmd[0]=='i'){
              scanf("%d",&tem[i].var);
              Hash[cnt++]=tem[i].var;
           }
        }
        sort(Hash,Hash+cnt);

       for(int i=0;i<nn;i++){
             if(tem[i].cmd[0]=='i')
        {
              pos = HASH(tem[i].var);
              Update(1,cnt+1,1,1,pos+1);
           aa.push(pos);

        }
        else if(tem[i].cmd[0]=='o')
        {
            pos =aa.front();
            aa.pop();
            Update(1,cnt+1,0,1,pos+1);

        }
        else{

             pos = sum[1]/2 +1;
             pos=query(1,cnt+1,1,pos);
             printf("%d
",Hash[pos-1]);

        }
       }
    }
  return 0;
}

速度499ms飘然而过！