google kickstart round H

google kick start的题目果真经典并且又不失思考的乐趣，质量非常高的题目，我觉得思考的深度非常有代表性。

Problem A - Retype

题目

选择游戏重启的位置

思路

真心是送分问题，一共只有两种选择，要么从头开始，要么倒回到第s关开始。
$$
minT = k + min(n,k+n-2*s)
$$

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>

using namespace std;
typedef pair<int,int> pii;

void slove(int t){
    int n,k,s;
    int ans = 0;
    cin>>n>>k>>s;
    ans = k + min(n,k+n-2*s);
    cout<<ans<<endl;
}

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

Boring Numbers

题目

boring number定义：从高位开始，起始索引为1，奇数位的数字为奇数，偶数位的数字为偶数。
求给定范围$[L,R]$中boring number的个数

题意

数位dp

思路

典型的可以用数位dp来解决该问题，我们可以转换思路，设count(x)表示从1到x之间的boring number的个数，则结果可以转化为:
$$
ans = count(R) - count(L-1)
$$
难点在于求count(x)，我们可以将小于x的数字分为两种情况，一种为数字的位数与x相等用$X_{lower}$表示;另一种为数字的位数与x相等，用$X_{equal}$表示。
$$
n = bits(x) \
count[x] = X_{lower} + X_{equal} \
X_{lower} = \sum_{i=1}^{n-1}5^{i}
$$

求$X_{equal}$稍微复杂点，我们设dp[i][0]表示字符的长度为i,且前i的数字与x相等且为boring number的个数，这个其实很简单，要么为0,要么为1；设dp[i][1]表示字符的长度为i,且前i的数字与x不相等且为boring number的个数，则此时:
$$
dp[i][1] = dp[i-1][1]5 + dp[i-1][0](X[i]/2) \
X_{equal} = dp[n][0] + dp[n][1] \
count[x] = \sum_{i=1}^{n-1}5^{i} + dp[n][0] + dp[n][1] \
$$

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<string.h>

using namespace std;
typedef pair<int,int> pii;
long long cnt[20];
long long dp[20][2];

long long count(long long n){
    long long ans = 0;
    if(n <= 0) return 0;
    vector<int> arr;

    for(int x = n; x != 0; x = x/10){
        arr.push_back(x%10);
    }
    reverse(arr.begin(),arr.end());
    for(int i = 1; i < arr.size(); ++i){
        ans += cnt[i];
    }
    int m = arr.size();
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    dp[0][1] = 0;
    
    for(int i = 1; i <= m; ++i){
        /*upper*/
        if((arr[i-1]%2) == (i%2)) dp[i][0] = dp[i-1][0];
        else dp[i][0] = 0;
        /*lower*/
        if(i  > 1) dp[i][1] += dp[i-1][1]*5;
        if(i == 1){
            dp[i][1] += arr[i-1]/2;
        }else{
             for(int j = 0; j < arr[i-1]; ++j){
                if((j%2) == (i%2)) dp[i][1] += dp[i-1][0];
            }
        }
    }
    ans += dp[m][0];
    ans += dp[m][1];
    return ans;
}

void slove(int t){
    long long l,r;
    long long ans = 0;
    cin>>l>>r;
    ans = count(r) - count(l-1);
    //cout<<count(r)<<":"<<count(l-1)<<endl;
    cout<<ans<<endl;
}

int main(){
    int t;
    cnt[0] = 1;
    for(int i = 1; i <= 18; ++i){
        cnt[i] = cnt[i-1]*5;
    }
    cin>>t;
    for(int i = 0; i < t; ++i){
        cout<<"Case #"<<i+1<<": ";
        slove(i+1);
    }
    return 0;
}

Rugby

给定一堆坐标$(x_{i},y_{i})$,求将这些坐标变为一行的最小曼哈顿距离之和:
$(X,Y),(X+1,Y),(X+2,Y),(X+3,Y),(X+4,Y)…(X+N,Y)$.

题意

中位数。

思路

我们仔细观察一下，实际上目标值的(x,y)实际上是独立的，相互之间不影响，则我们可以分别来求出(X,Y)。
$$
Target = min(\sum_{i=0}^{n-1}abs(x_{i}-X-i) + \sum_{i=0}^{n-1}abs(x_{i}-Y)
$$
在已知条件下，我们很容易求出y的值，因为知道要满足距离之和最小的值为中位数。我们对所有坐标的纵坐标按照大小进行排序,Y即为排序后的中位数。
$$
Y = \frac{y_{\frac{n-1}{2}} + y_{\frac{n}{2}}}{2}
$$
我们再来求X,我们同样也对x进行排序，我们需要求出$\sum_{i=0}^{n-1}abs(x_{i}-X-i)$的最小值，实际上可以转为$\sum_{i=0}^{n-1}abs((x_{i}-i) -X)$的最小值，因此我们此时构造数组：
$$
(x_{0},x_{1}-1,x_{2}-2,x_{3}-3…,x_{n}-n)
$$
此时求最小距离之和可以转换为求中位数即可，满足题目要求，此时我们相当于求上述转化数组的中位数。

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<string.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
void slove(int t){
    int n = 0;
    long long midx = 0;
    long long midy = 0;
    long long ans = 0;
    
    cin>>n;
    vector<long long> arrx(n);
    vector<long long> arry(n);
    for(int i = 0; i < n; ++i){
        cin>>arrx[i]>>arry[i];
    }
    sort(arry.begin(),arry.end());
    sort(arrx.begin(),arrx.end());
    for(int i = 0; i < n; ++i){
        arrx[i] -= i;
    }
    sort(arrx.begin(),arrx.end());
    midx = (arrx[(n-1)/2] + arrx[n/2])/2;
    midy = (arry[(n-1)/2] + arry[n/2])/2;
    for(int i = 0; i < n; ++i){
        ans += abs(arrx[i]-midx);
        ans += abs(arry[i]-midy);
    }
    cout<<ans<<endl;
}

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

Friends

题目

给定图，图中的每个节点含有一个字符串，如果两个字符串s,t存在有相同字母，则认为两个节点存在相互连接的边，给定一组查询(x,y)，求节点x与y之间的最短路劲。

题意

图的遍历

解题思路

题目挺有新意的，如果直接用bfs来遍历图的话，按照图中给定的数据集肯定会超时，所以必须要转换思路。
我们可以转换成求字符a,b的最短距离。我们可以求所所有字符的最短转移路劲，本题也就转化为求所有可能的字符的最短转换路径。
我们假设源字符串为s，目标字符串为t，假如s和t之间存在相同的字符e，则很容易我们知道直接跳一步即可得到结果,chain的最短长度应该为2。
s-(e)->t
假如s和t之间是通过不同的字符进行跳转得到的结果，且目标的最短的chain为：
s-(c1)->s1-(c2)->s2-(c3)->s3->...->sn-(cn)->t
根据以上推论我们可以知道如果满足最短的chain，则必然可以得到以下结论:
$$
c_{1} \neq c_{2} \neq c_{3} \neq c_{4} \neq c_{5} …. \neq c_{n}
$$
我们假设存在$c_{i} = c_{j}$,则我们可以判定直接可以通过i跳转到j即可，而不必再通过$c_{i+1},c_{i+2},…,c_{j-1}$进行跳转,因此我们只需求出不同字符之间跳转的最短距离即可。我们可以设相同字符的跳转距离为0.
我们可以很容易求出，两个字符串之间的字符跳转的最短转换距离，最终的答案为$minJump + 2$.

代码

---
title: 【google kickstart】  roundH
tags: kickstart
categories: 算法
---

# google kickstart round H
`google kick start`的题目果真经典并且又不失思考的乐趣，质量非常高的题目，我觉得思考的深度非常有代表性。

## Problem A - Retype
### 题目
选择游戏重启的位置
### 思路
1. 真心是送分问题，一共只有两种选择，要么从头开始，要么倒回到第`s`关开始。
$$
minT = k + min(n,k+n-2*s)
$$
### 代码
```c++
#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>

using namespace std;
typedef pair<int,int> pii;

void slove(int t){
    int n,k,s;
    int ans = 0;
    cin>>n>>k>>s;
    ans = k + min(n,k+n-2*s);
    cout<<ans<<endl;
}

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

Boring Numbers

题目

boring number定义：从高位开始，起始索引为1，奇数位的数字为奇数，偶数位的数字为偶数。
求给定范围$[L,R]$中boring number的个数

题意

数位dp

思路

典型的可以用数位dp来解决该问题，我们可以转换思路，设count(x)表示从1到x之间的boring number的个数，则结果可以转化为:
$$
ans = count(R) - count(L-1)
$$
难点在于求count(x)，我们可以将小于x的数字分为两种情况，一种为数字的位数与x相等用$X_{lower}$表示;另一种为数字的位数与x相等，用$X_{equal}$表示。
$$
n = bits(x) \
count[x] = X_{lower} + X_{equal} \
X_{lower} = \sum_{i=1}^{n-1}5^{i}
$$

求$X_{equal}$稍微复杂点，我们设dp[i][0]表示字符的长度为i,且前i的数字与x相等且为boring number的个数，这个其实很简单，要么为0,要么为1；设dp[i][1]表示字符的长度为i,且前i的数字与x不相等且为boring number的个数，则此时:
$$
dp[i][1] = dp[i-1][1]5 + dp[i-1][0](X[i]/2) \
X_{equal} = dp[n][0] + dp[n][1] \
count[x] = \sum_{i=1}^{n-1}5^{i} + dp[n][0] + dp[n][1] \
$$

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<string.h>

using namespace std;
typedef pair<int,int> pii;
long long cnt[20];
long long dp[20][2];

long long count(long long n){
    long long ans = 0;
    if(n <= 0) return 0;
    vector<int> arr;

    for(int x = n; x != 0; x = x/10){
        arr.push_back(x%10);
    }
    reverse(arr.begin(),arr.end());
    for(int i = 1; i < arr.size(); ++i){
        ans += cnt[i];
    }
    int m = arr.size();
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    dp[0][1] = 0;
    
    for(int i = 1; i <= m; ++i){
        /*upper*/
        if((arr[i-1]%2) == (i%2)) dp[i][0] = dp[i-1][0];
        else dp[i][0] = 0;
        /*lower*/
        if(i  > 1) dp[i][1] += dp[i-1][1]*5;
        if(i == 1){
            dp[i][1] += arr[i-1]/2;
        }else{
             for(int j = 0; j < arr[i-1]; ++j){
                if((j%2) == (i%2)) dp[i][1] += dp[i-1][0];
            }
        }
    }
    ans += dp[m][0];
    ans += dp[m][1];
    return ans;
}

void slove(int t){
    long long l,r;
    long long ans = 0;
    cin>>l>>r;
    ans = count(r) - count(l-1);
    //cout<<count(r)<<":"<<count(l-1)<<endl;
    cout<<ans<<endl;
}

int main(){
    int t;
    cnt[0] = 1;
    for(int i = 1; i <= 18; ++i){
        cnt[i] = cnt[i-1]*5;
    }
    cin>>t;
    for(int i = 0; i < t; ++i){
        cout<<"Case #"<<i+1<<": ";
        slove(i+1);
    }
    return 0;
}

Rugby

给定一堆坐标$(x_{i},y_{i})$,求将这些坐标变为一行的最小曼哈顿距离之和:
$(X,Y),(X+1,Y),(X+2,Y),(X+3,Y),(X+4,Y)…(X+N,Y)$.

题意

中位数。

思路

我们仔细观察一下，实际上目标值的(x,y)实际上是独立的，相互之间不影响，则我们可以分别来求出(X,Y)。
$$
Target = min(\sum_{i=0}^{n-1}abs(x_{i}-X-i) + \sum_{i=0}^{n-1}abs(x_{i}-Y)
$$
在已知条件下，我们很容易求出y的值，因为知道要满足距离之和最小的值为中位数。我们对所有坐标的纵坐标按照大小进行排序,Y即为排序后的中位数。
$$
Y = \frac{y_{\frac{n-1}{2}} + y_{\frac{n}{2}}}{2}
$$
我们再来求X,我们同样也对x进行排序，我们需要求出$\sum_{i=0}^{n-1}abs(x_{i}-X-i)$的最小值，实际上可以转为$\sum_{i=0}^{n-1}abs((x_{i}-i) -X)$的最小值，因此我们此时构造数组：
$$
(x_{0},x_{1}-1,x_{2}-2,x_{3}-3…,x_{n}-n)
$$
此时求最小距离之和可以转换为求中位数即可，满足题目要求，此时我们相当于求上述转化数组的中位数。

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<string.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
void slove(int t){
    int n = 0;
    long long midx = 0;
    long long midy = 0;
    long long ans = 0;
    
    cin>>n;
    vector<long long> arrx(n);
    vector<long long> arry(n);
    for(int i = 0; i < n; ++i){
        cin>>arrx[i]>>arry[i];
    }
    sort(arry.begin(),arry.end());
    sort(arrx.begin(),arrx.end());
    for(int i = 0; i < n; ++i){
        arrx[i] -= i;
    }
    sort(arrx.begin(),arrx.end());
    midx = (arrx[(n-1)/2] + arrx[n/2])/2;
    midy = (arry[(n-1)/2] + arry[n/2])/2;
    for(int i = 0; i < n; ++i){
        ans += abs(arrx[i]-midx);
        ans += abs(arry[i]-midy);
    }
    cout<<ans<<endl;
}

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

Friends

题目

题意

图的遍历

解题思路

题目挺有新意的，如果直接用bfs来遍历图的话，按照图中给定的数据集肯定会超时，所以必须要转换思路。
我们可以转换成求字符a,b的最短距离。我们可以求所所有字符的最短转移路劲，本题也就转化为求所有可能的字符的最短转换路径。
我们假设源字符串为s，目标字符串为t，假如s和t之间存在相同的字符e，则很容易我们知道直接跳一步即可得到结果,chain的最短长度应该为2。
s-(e)->t
假如s和t之间是通过不同的字符进行跳转得到的结果，且目标的最短的chain为：
s-(c1)->s1-(c2)->s2-(c3)->s3->...->sn-(cn)->t
根据以上推论我们可以知道如果满足最短的chain，则必然可以得到以下结论:
$$
c_{1} \neq c_{2} \neq c_{3} \neq c_{4} \neq c_{5} …. \neq c_{n}
$$
我们假设存在$c_{i} = c_{j}$,则我们可以判定直接可以通过i跳转到j即可，而不必再通过$c_{i+1},c_{i+2},…,c_{j-1}$进行跳转,因此我们只需求出不同字符之间跳转的最短距离即可。我们可以设相同字符的跳转距离为0.
我们可以很容易求出，两个字符串之间的字符跳转的最短转换距离，最终的答案为$minJump + 2$.

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<string.h>
#include<queue>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f;

void slove(int t){
    int n,q;
    cin>>n>>q;
    vector<string> arr(n);
    vector<vector<int>> dp(26,vector<int>(26,INF));
    vector<pii> query(q);

    for(int i = 0; i < n; ++i) cin>>arr[i];
    for(int i = 0; i < q; ++i) cin>>query[i].first>>query[i].second;
    for(int i = 0; i < 26; ++i) dp[i][i] = 0;
    for(auto s : arr){
        vector<bool> count(26,false);
        for(auto c : s) count[c-'A'] = true;
        for(int j = 0; j < 26; ++j){
            for(int k = 0; k < 26; ++k){
                if(j == k) continue;
                if(count[j]&&count[k]){
                    dp[j][k] = 1;
                    dp[k][j] = 1;
                }
            }
        }
    }
    for(int i = 0; i < 26; ++i){
        for(int j = 0; j < 26; ++j){
            for(int k = 0; k < 26; ++k){
                dp[i][k] = min(dp[i][k],dp[i][j] + dp[j][k]);
            }
        }
    }
    for(auto v : query){
        int x = v.first - 1;
        int y = v.second - 1;
        int curr = INF;
        for(auto a : arr[x]){
            for(auto b : arr[y]){
                curr = min(curr,dp[a-'A'][b-'A']);
            }
        }
        cout<<(curr == INF ? (-1) : (curr + 2))<<" ";
    }
    cout<<endl;
}

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

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: kickstart

← 【google】 google 【kick start】 2021 google kick start roundA →

扫描二维码，分享此文章

【kick start】 2021 google kickstart round H

google kickstart round H

Problem A - Retype

题目

思路

代码

Boring Numbers

题目

题意

思路

代码

Rugby

题意

思路

代码

Friends

题目

题意

解题思路

代码

Boring Numbers

题目

题意

思路

代码

Rugby

题意

思路

代码

Friends

题目

题意

解题思路

代码