Google_Kick_Start 2020 Round H

总结

代码地址 题目地址 关键算法 难度
Q1-Retype.cpp Retype 直接计算 简单
Q2-BoringNumber.cpp Boring Numbers 排列组合 简单
Q3-Rugby.cpp Rugby 最优解 较难
Q4-Friends.cpp Friends 最短路径+trik 较难

Q1-Retype

/***********************************************
♡        Filename : 2020H-Q1-Retype.cpp
♡  
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-11-27 00:24:16
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

typedef long long ll;
// 根据题意,直接模拟两种方法,输出min值即可。
const int maxnn = 1e9+20;
void solve()
{
    ll N, K, S;
    cin>>N>>K>>S;

    ll ans1,ans2;
    ans1 = K-1+1+N;
    ans2 = (K-1)+(K-S)+(N-S+1);
    cout<<min(ans1,ans2)<<endl;

}

int main()
{
    int t;
    cin >> t;
    for(int i=1; i<=t; ++i) {
        cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

Q2-BoringNumber

/***********************************************
♡        Filename : 2020H-Q2-BoringNumber.cpp
♡
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-11-26 22:22:28
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <strstream>
using namespace std;

// 如果直接遍历,然后对每个数的每一位求奇偶性,则test1可以通过
// 但是test2数据太大,直接遍历则超时。
// 可以用组合数学的思想来做。
// 比如我们有一个数9734,我们计算1000到9734间一共有多少个符合题目的数字。
// 对于第1位(奇位),而小于9的奇数有4个,则如果以这4个奇数为第1位,则有4*5*5*5个数。
// 因为第1位为9,是奇数,因此可以考虑对第2位进行计算,
// 对于第2位(偶位),而小于7的偶数有4个,则如果以9为第一位,这4个偶数为第2位,则有1*4*5*5个数。
// 因为第2位为7,是奇数,因此结束计算(后面的数一定不符合)
//
// 那么0-9734中有多少个满足条件的数呢?
// 对于4位的数,可以按照上面的方法做;对于3位数,应该有5^3个;对于2位数,应该有5^2个;对于1位数,应该有5^1个。
//
// 那么比如计算123-9734中有多少个满足的数呢?
// 我们可以转化为求(0-9724)的个数减去(0-123)的个数。
//
// 其中,因为对于2位数和1位数,两者是重复的,减去之后为0,因此可以免去计算。


// L 和 R 范围是1-1e18,longlong比较保险
typedef long long ll;

// 1,2,3……之前(包括)一共有多少个偶数
int under_even[10]={1,1,2,2,3,3,4,4,5,5};
// 一共有少个奇数
int under_odd[10]={0,1,1,2,2,3,3,4,4,5};

// longlong转string
string lltoString(long long t)
{
    std::string result;
    std::strstream ss;
    ss <<  t;
    ss >> result;
    return result;
}

// 对每一位,计算 剩余的奇/偶数,然后乘以len-1个5
ll cnt_part(int res, int len)
{
    ll ans = 0;
    int i;
    ans = res;
    for(i=1; i<len; i++)
    {
        ans *= 5;
    }
    return ans;
}

// 计算个数,例如1000-1234之间符合条件的个数
ll cnt_ans(string num)
{
    int len = num.length();
    int i;
    // 奇偶位标记
    bool flag = false;
    ll ans = 0;
    ll res = 0;
    // 对每一位进行遍历
    for(i=0; i<len; i++)
    {
        flag = !flag;
        // 当前是奇数位
        if(flag)
        {
            // 计算可选择的奇数个数
            if((num[i]-'0')%2) res = under_odd[num[i]-'0']-1;
            else res = under_odd[num[i]-'0'];
            // 可选择数*5*5*5……
            if(res>0) ans += cnt_part(res, len-i);

            // 如果当前的数也是奇数,则可以对下一位进行计算
            if((num[i]-'0')%2)
                continue;
            // 如果当前数不是奇数,则后面的数都不是了,则停止遍历
            else
                break;

        }
        // 当前是偶数位
        else
        {
            if(!((num[i]-'0')%2)) res = under_even[num[i]-'0']-1;
            else res = under_even[num[i]-'0'];
            if(res>0) ans += cnt_part(res, len-i);

            if(!((num[i]-'0')%2))
                continue;
            else 
                break;
        }
    }
    // 因为之前判断可选择的奇偶个数的时候,没有包括这个数本身
    // 因此遍历到最后一位的时候,需要再特殊判断一下最后一位是否满足,若满足加1
    // i==len 遍历到最后一位
    // len%2 判断最后一位是奇数还是偶数
    if(i==len && len%2 && (num[len-1]-'0')%2)
        ans++;

    if(i==len && !(len%2) && !((num[len]-'0')%2))
        ans ++;

    return ans;
}
void solve()
{
    ll L,R;
    string num_L, num_R;
    long long ans1, ans2, ans3;
    int i,j;
    ans1 = ans2 = ans3 = 0;
    scanf("%lld %lld", &L, &R);
    num_L = lltoString(L-1);
    num_R = lltoString(R);
    ans1 = cnt_ans(num_L);
    ans2 = cnt_ans(num_R);

    // 若两个数的位数不一样
    // 比如,56-1575
    // 函数计算的是0-55之间的个数和1000-1575之间的个数
    // 因此对于后者,需要加上位数为3和位数为2时,符合条件的个数
    // 分别是5^3,5^2
    for(i=num_L.length(); i<num_R.length(); i++)
        ans3 += pow(5,i);

    printf("%lld\n", ans2+ans3-ans1);
}
int main()
{
    int t,T;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        printf("Case #%d: ", t);
        solve();
    }
}

Q3-Rugby

/***********************************************
♡        Filename : 2020H-Q3-Rugby.cpp
♡  
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-12-01 13:28:20
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;


// 感觉像是考数学思维的一道题,反正看完题没有想到怎么做
// 官方的题解是:
// https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043b027#analysis
//
// x和y轴分开计算,计算每个人最终的理想x和理想y。
//
// 首先看y,最终所有的人要移动到同一行上,因此所有人都是垂直移动。
// 通过证明可以得到,如果理想的y是所有y的中位数,则垂直移动的总步数是最优的。
//
// 接下来看x,移动后保持原来的X轴从小到大顺序,可以保证总移动次数最少
// 那每个人的理想x应该是多少呢?
// 对于每个人,他前面有i个人,如果第一个人firstx的位置是x-i,则他将不需要移动
// 每个人都有一个理想的firstx, 分别是x0-0, x1-1, x2-2, x3-3...
// 则最优的firstx应该是所有的firstx的中位数
// 知道了最优的第一个人的位置,则后面所有人的位置也就知道了
const int maxn = 1e5+20;

int x[maxn];
int y[maxn];
long long solve()
{
    int N;
    memset(x, 0, sizeof(0));
    memset(y, 0, sizeof(0));
    int i, mid;
    int firstx, midy;
    long long ansx = 0;
    long long ansy = 0;

    scanf("%d", &N);
    for(i=0; i<N; i++)
        scanf("%d %d", &x[i], &y[i]);

    sort(x, x+N);

    // 每个人的理想firstx
    for(i=0; i<N; i++)
        x[i] -= i;


    sort(x, x+N);
    sort(y, y+N); 

    mid = N/2;

    // 第一个人的理想x位置
    // 每个人的理想y位置
    firstx = x[mid]; 
    midy = y[mid];
    for(i=0; i<N; i++)
    {
        ansx += abs(x[i]-firstx);
        ansy += abs(y[i]-midy);
    }
    return ansx+ansy;
}
int main()
{
    int t, T;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        printf("Case #%d: %lld\n", t, solve());
    }
}

Q4-Friends

/***********************************************
♡        Filename : 2020H-Q4-Friends.cpp
♡  
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-12-09 10:31:14
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;


// 用传统的最短路径算法,只能test1通过,test2会超时
// 最终还是采用了官方给的解决方法
// 
// 总体思想是 求一个点到另一个点的最短距离 转换为 求一个集合到另一个集合的最短距离
//
// 即,将名字拆分成每一个字母。然后两个字母有边当且仅当两个字母存在于同一个名字当中。
// 之后按照floyd算法计算两个字母之间的最短距离。计算得到邻接矩阵。
//
// 下面是第一个测试集的邻接矩阵
/*
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
A 0 1 - 1 2 - - 1 1 - 2 1 - 1 1 - - 2 - 1 2 2 - - 2 2 
B 1 0 - 1 2 - - 1 2 - 2 2 - 1 1 - - 2 - 2 2 2 - - 2 3 
C - - 0 - - - - - - - - - - - - - - - - - - - - - - - 
D 1 1 - 0 2 - - 1 2 - 2 2 - 1 1 - - 2 - 2 2 2 - - 2 3 
E 2 2 - 2 0 - - 2 1 - 1 1 - 1 2 - - 3 - 2 3 1 - - 3 1 
F - - - - - 0 - - - - - - - - - - - - - - - - - - - - 
G - - - - - - 0 - - - - - - - - - - - - - - - - - - - 
H 1 1 - 1 2 - - 0 2 - 2 2 - 1 1 - - 2 - 2 2 2 - - 2 3 
I1 2 - 2 1 - - 2 0 - 1 1 - 1 2 - - 3 - 1 3 1 - - 3 1 
J - - - - - - - - - 0 - - - - - - - - - - - - - - - - 
K 2 2 - 2 1 - - 2 1 - 0 2 - 1 2 - - 3 - 2 3 1 - - 3 2 
L 1 2 - 2 1 - - 2 1 - 2 0 - 2 2 - - 3 - 1 3 2 - - 3 1 
M - - - - - - - - - - - - 0 - - - - - - - - - - - - - 
N 1 1 - 1 1 - - 1 1 - 1 2 - 0 1 - - 2 - 2 2 1 - - 2 2 
O 1 1 - 1 2 - - 1 2 - 2 2 - 1 0 - - 1 - 2 1 2 - - 1 3 
P - - - - - - - - - - - - - - - 0 - - - - - - - - - - 
Q - - - - - - - - - - - - - - - - 0 - - - - - - - - - 
R 2 2 - 2 3 - - 2 3 - 3 3 - 2 1 - - 0 - 3 1 3 - - 1 4 
S - - - - - - - - - - - - - - - - - - 0 - - - - - - - 
T 1 2 - 2 2 - - 2 1 - 2 1 - 2 2 - - 3 - 0 3 2 - - 3 2 
U 2 2 - 2 3 - - 2 3 - 3 3 - 2 1 - - 1 - 3 0 3 - - 1 4 
V 2 2 - 2 1 - - 2 1 - 1 2 - 1 2 - - 3 - 2 3 0 - - 3 2 
W - - - - - - - - - - - - - - - - - - - - - - 0 - - - 
X - - - - - - - - - - - - - - - - - - - - - - - 0 - - 
Y 2 2 - 2 3 - - 2 3 - 3 3 - 2 1 - - 1 - 3 1 3 - - 0 4 
Z 2 3 - 3 1 - - 3 1 - 2 1 - 2 3 - - 4 - 2 4 2 - - 4 0 
*/
// 之后计算LIZZIE 到 BOHDAN 的最短距离,只需要依次遍历这两个名字中的字符,
// 然后查询两个字母之间的最短距离。最后从最短距离中取最小值即可。
//
// 思维很巧妙,但是真的没有想到这种方法,可能是经验不足吧。
//
// 进一步思考,能这样做的原因有两个:
// 1.单个名字,如果有重复字符,不会影响最终结果。
// 2.所有字母之间的权值都是1,不会出现两个字母之间有多个权值。
//


// 26个字母
const int alp = 26;
// 矩阵最大值
const int inf = 1e9;
const int maxn = 5e4+20;
void solve()
{
    int N, Q;
    string s[maxn];
    int i,j,k;
    int matrix[alp][alp];
    int ans=0;
    scanf("%d %d", &N, &Q);

    // 初始化
    for(i=0; i<alp; i++)
    {
        for(j=0; j<alp; j++)
        {
            matrix[i][j] = inf;

            if(i==j)
                matrix[i][j] = 0;
        }
    }


    for(k=1; k<=N; k++)
    {
        cin>>s[k];
        // 两个字母有边
        for(i=0; i<s[k].length(); i++)
        {
            for(j=i+1; j<s[k].length(); j++)
            {
                // 相同的字符,无需边
                if(s[k][i] == s[k][j])
                    continue;

                matrix[s[k][i]-'A'][s[k][j]-'A'] = 1;
                matrix[s[k][j]-'A'][s[k][i]-'A'] = 1;
            }
        }
    }
    // floyd 算法
    for(k=0; k<alp; k++)
    {
        for(i=0; i<alp; i++)
        {
            for(j=0; j<alp; j++)
            {
                if(i!=j && (matrix[i][k]+matrix[k][j] < matrix[i][j]))
                    matrix[i][j] = matrix[i][k] + matrix[k][j];
            }
        }
    }



    // 查询
    int left,right;
    for(i=0; i<Q; i++)
    {
        ans = inf;
        scanf("%d %d", &left, &right);
        j--;
        k--;
        for(j=0; j<s[left].length(); j++)
        {
            for(k=0; k<s[right].length(); k++)
            {
                ans = min(ans, matrix[s[left][j]-'A'][s[right][k]-'A']);
            }
        }
        if(ans == inf)
            printf("-1 ");
        else
            printf("%d ", ans+2);
    }
    printf("\n");
}

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

One thought on “Google_Kick_Start 2020 Round H

Leave a Reply

Your email address will not be published.