【kick start】 2021 google kickstart round H

google kickstart round H

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

Problem A - Retype

题目

选择游戏重启的位置

思路

1. 真心是送分问题，一共只有两种选择，要么从头开始，要么倒回到第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

  思路

1. 典型的可以用数位dp来解决该问题，我们可以转换思路，设count(x)表示从1到x之间的boring number的个数，则结果可以转化为: $$ans = count(R) - count(L-1)$$
2. 难点在于求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)$.

题意

中位数。

思路

1. 我们仔细观察一下，实际上目标值的(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)$$
2. 在已知条件下，我们很容易求出y的值，因为知道要满足距离之和最小的值为中位数。我们对所有坐标的纵坐标按照大小进行排序,Y即为排序后的中位数。 $$Y = \frac{y_{\frac{n-1}{2}} + y_{\frac{n}{2}}}{2}$$
3. 我们再来求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之间的最短路劲。

题意

图的遍历

解题思路

1. 题目挺有新意的，如果直接用bfs来遍历图的话，按照图中给定的数据集肯定会超时，所以必须要转换思路。
2. 我们可以转换成求字符a,b的最短距离。我们可以求所所有字符的最短转移路劲，本题也就转化为求所有可能的字符的最短转换路径。
3. 我们假设源字符串为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.
4. 我们可以很容易求出，两个字符串之间的字符跳转的最短转换距离，最终的答案为$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

  思路

1. 典型的可以用数位dp来解决该问题，我们可以转换思路，设count(x)表示从1到x之间的boring number的个数，则结果可以转化为: $$ans = count(R) - count(L-1)$$
2. 难点在于求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)$.

题意

中位数。

思路

1. 我们仔细观察一下，实际上目标值的(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)$$
2. 在已知条件下，我们很容易求出y的值，因为知道要满足距离之和最小的值为中位数。我们对所有坐标的纵坐标按照大小进行排序,Y即为排序后的中位数。 $$Y = \frac{y_{\frac{n-1}{2}} + y_{\frac{n}{2}}}{2}$$
3. 我们再来求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之间的最短路劲。

题意

图的遍历

解题思路

1. 题目挺有新意的，如果直接用bfs来遍历图的话，按照图中给定的数据集肯定会超时，所以必须要转换思路。
2. 我们可以转换成求字符a,b的最短距离。我们可以求所所有字符的最短转移路劲，本题也就转化为求所有可能的字符的最短转换路径。
3. 我们假设源字符串为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.
4. 我们可以很容易求出，两个字符串之间的字符跳转的最短转换距离，最终的答案为$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
• 关注我的微信公众号: 公务程序猿