Google_Kick_Start 2020 Round B

总结

代码地址 题目地址 关键算法 难度
Q1-BikeTour.cpp Bike Tour 直接遍历 简单
Q2-BusRoutes.cpp Bus Routes 直接遍历 简单
Q3-RobotPathDecoding.cpp Robot Path Decoding 系数栈 较难
Q4-WanderingRobot.cpp Wandering Robot 二项式

Q1-BikeTour

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

#define maxN 100

// 直接遍历
//
int main()
{
    int t,T;
    int N,n;
    int height[maxN];
    int cnt = 0;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        cnt = 0;
        memset(height, 0, sizeof(height));
        scanf("%d", &N);
        for(n=0; n<N; n++)
        {
            scanf("%d", &height[n]);
        }
        for(n=1; n<N-1; n++)
        {
            if(height[n]>height[n-1] && height[n]>height[n+1])
            {
                cnt++;
            }

        }
        printf("Case #%d: %d\n", t, cnt);
    }

    /* std::cout << "Hello world" << std::endl; */
    return 0;
}

Q2-BusRoutes

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

// So easy...
// 从最后一天到前一天遍历, D = D-D%x[i]; 最后的D就是结果

using namespace std;
typedef long long ll;
#define maxN 1000+50
int main()
{
    int t,T;
    ll N,D,n;
    ll x[maxN];
    scanf("%d", &T);
    ll ans;
    for(t=1; t<=T; t++)
    {
        memset(x, 0, sizeof(x));
        scanf("%lld %lld", &N, &D);
        for(n=0; n<N; n++)
        {
            scanf("%lld", &x[n]);
        }
        ans = D;
        for(n=N-1; n>=0; n--)
        {
            ans -= ans%x[n]; 
        }

        printf("Case #%d: %lld\n", t, ans);
    }
    /* std::cout << "Hello world" << std::endl; */
    return 0;
}

Q3-RobotPathDecoding

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <string.h>
#include <stack>
using namespace std;


// 可以想象成数学中计算向量的方式,垂直方向用y,水平方向用x
// 遇到数字index的时候,后面跟着一个左括号,需要对向量的系数乘以index,遇到右括号的时候恢复之前的系数
// 考虑用栈来保存系数,遇到左括号的时候压入系数,遇到右括号的时候弹出系数,则此时栈顶就是下一个的向量的系数

// 向量 first 为垂直方向, second为水平方向
pair<long long, long long> plc;
int maxx = 1e9;
// 计算位置
pair<long long, long long> solve(const std::string str)
{
    long long len = str.length();
    long long i,mul;
    // 系数栈
    stack<long long> index;
    index.push(1);
    // 直接遍历
    for(i=0; i<len; i++)
    {
        if(str[i] >='2' && str[i]<='9')
        {
            // 由于没有对系数进行取余,系数可能超出了longlong, 结果Test2未通过,取余后通过
            index.push((str[i]-'0')*index.top()%maxx);
        }
        else if(str[i] == '(')
        {
            continue;
        }
        else if(str[i] == ')')
        {
            index.pop();
        }
        else
        {
            printf("mul is %lld\n", index.top());
            if(str[i]=='N')  plc.first = (plc.first - index.top() + maxx)%maxx;
            if(str[i]=='S')  plc.first = (plc.first + index.top() + maxx)%maxx;
            if(str[i]=='W')  plc.second = (plc.second - index.top() + maxx)%maxx;
            if(str[i]=='E')  plc.second = (plc.second + index.top() + maxx)%maxx;
        }
    }
    return plc;
}

int main()
{
    string s;
    int t,T;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        cin>>s;
        plc.first = 0;
        plc.second = 0;
        plc = solve(s);
        printf("Case #%d: %lld %lld\n", t, plc.second+1, plc.first+1);
    }
    return 0;
}

Q4-WanderingRobot

/***********************************************
♡        Filename : 2020B-Q4-WanderingRobot.cpp
♡  
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-11-20 13:56:52
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
using namespace std;


// 代码是根据官方给出的方法写得。
// 官方解释:https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d8565#analysis
// 
// 对于从(0,0)到(x,y),概率P(x,y)为 pow(0.5,x+y)*方法数,而方法数=C(x,x+y)
// 
// 但是若(x,y)处于最后一行或者最后一列,则不能按照上面的方式计算概率
// 假设最后一行有3个方格,
// 则对于第1个方格,其概率为pow(0.5, H);
// 则对于第2个方格,其概率为 第一个方格的概率+上面一个方格的概率*0.5
// 即,pow(0,5,H)+P(i, j-1)
// 则对于第3个方格,其概率为 第二个方格的概率+上面一个方格的概率*0.5
//
// 对于最后一列,方法与最后一行相同。
//
// 为了防止溢出,做log处理
// 
// 计算log(num!),以2为底
//
//

const int max_num = 2*1e5+20;

// log(0), log(1), log(2), log(3), log(4)……
double log_arr[max_num];
/*
将log计算结果存储为数组,时间会快一些,否则会TLE
double mylog(int num)
{
  int i;
  double sum = 0.0;
  if(num == 0 || num == 1)
    return sum;
  for(i=1; i<=num; i++)
  {
    sum += log(i)/log(2);
  }
  return sum;
}
*/

// 计算log(P(x,y)) = log( pow(0.5, (x+y)) * C(x,x+y) ) = log((x+y)!) - log(x!) - log(y!) - (x+y)
/*double probility(int x, int y)
{
  return mylog(x+y)-mylog(x)-mylog(y)-(x+y);
}
*/

double probility(int x, int y)
{
    return log_arr[x+y]-log_arr[x]-log_arr[y]-(x+y);
}


// 计算通过的概率之和
double cal(int W, int H, int L, int U, int R, int D)
{
  double ans=0.0, sum=0.0;
  double temp=0.0;
  int i,j,k;

  memset(log_arr, 0, sizeof(log_arr));

  log_arr[0] = 0.0;
  for(i=1; i<=(W+H); i++)
      log_arr[i] = log_arr[i-1] + log(i)/log(2);

  // 处理右上角的方块
  if(R!=W)
  {
    j=min(U,D);
    for(i=R+1; i<=W; i++){
      j--;
      if(j<0)
        break;
      // 最后一列
      if(i==W)
      {
        if(j==0) ans += pow(2, -W);
        else{
          temp = pow(2, -W);
          for(k=1; k<=j; k++)
            temp = temp + 0.5*pow(2, probility(i-1, k));
          ans += temp;
        }
      }
      else
        ans += pow(2,probility(i,j));
    }
  }
  // 处理左下角的方块
  if(L!=0){
    j=max(U,D);
    for(i=L-1; i>=0; i--){
      j++;
      if(j>H)
        break;
      // 最下面一行
      if(j==H)
      {
        if(i==0) ans += pow(2, -H);
        else{
          temp = pow(2, -H);
          for(k=1; k<=i; k++)
            temp = temp + 0.5*pow(2, probility(k, j-1));
          ans += temp;
        }
      }
      else
        ans += pow(2,probility(i,j));
    }
  }
  return ans;
}

void solve()
{
  int W,H,L,R,U,D;
  scanf("%d %d %d %d %d %d", &W, &H, &L, &U, &R, &D);
  //cout<<W<<H<<L<<U<<R<<D<<endl;
  double ans = cal(W-1, H-1, L-1, U-1, R-1, D-1);
  if(ans == 0)
    cout<<"0.0"<<endl;
  else
    cout<<ans<<endl;
}

int main()
{
  int t,T;
  scanf("%d", &T); 
  for(t=1; t<=T; t++)
  {
    printf("Case #%d: ", t);
    solve();
  }
  return 0;
}
1+

One thought on “Google_Kick_Start 2020 Round B

Leave a Reply

Your email address will not be published.