且听疯吟

【kick start】 2021 google kick start roundA

2022-11-20

2021 google kick start roundA

kick start的题目果真质量非常高，非常值得学习和练习的题目，非常喜欢这类的题目，前三题都可以做出来，不过题目D确实很难，我感觉自己肯定想不到解答的答案的。前三题就是leetcode的难度，最后一题确实很难。

K-Goodness String (5pts, 7pts)

题目


给定字符串，求出给定分值得最小变换次数

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cca3

题意

简单题目

思路

  1. 我们只需要求出$s[i] != s[n-1-i]$得字符对个数，最小的变换次数等于不同的字符对的个数与k的绝对值之差。
    #include<iostream>
    #include<vector>
    #include<set>
    #include<unordered_set>
    #include<map>
    #include<unordered_map>
    #include<string>
    #include<stack>
    #include<algorithm>
    #include<limits.h>

    using namespace std;

    void slove(int t){
        int good = 0;
        int bad = 0;
        int ans = 0;
        string str;
        int n,k;
        cin>>n>>k;
        cin>>str;
        for(int i = 0; i < (n>>1); ++i){
            if(str[i] == str[n-1-i]) good++;
            else bad++;
        }
        cout<<"Case #"<<t<<": "<<abs(k-bad)<<endl;
    }

    int main(){
        int t;
        cin>>t;
        for(int i = 0; i < t; ++i){
            slove(i+1);
        }
        return 0;
    }

L Shaped Plots (8pts, 12pts)

题目


求出给定的矩阵中L的个数，L形要求：

  • L的两个线段必须分别在一行和一列，两个线段必须必须与行、列平行；
  • L的两个线段有且只有一个点相交，且一条线段的长度为另一条线段的长度的两倍；
  • L的两个线段的长度必须大于等于2;

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068c509

题意

滑动窗口 + 前缀和

思路

  1. 我们分别求出以点(x,y)为起点，分别往上下左右四个方向的最长的连续的1的长度。
  2. 分别求出以点(x,y)为起点相交顶点的L的个数，分别在上下左右四个方向求一边，我们设L的两个线段的长度分别为$m,n$,则以m,n为长度的两个线段可能组成的L的形状个数为：
    $$
    cnt = max(0,min(m/2,n)-1) + max(0,min(m,n/2)-1)
    $$
  3. 时间复杂度$O(mn)$,空间复杂度$O(mn)$.

代码

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

using namespace std;

void slove(int t){
    int row;
    int col;
    int ans = 0;
    cin>>row>>col;
    vector<vector<int>> matrix(row,vector<int>(col));
    vector<vector<int>> left(row,vector<int>(col));
    vector<vector<int>> right(row,vector<int>(col));
    vector<vector<int>> down(row,vector<int>(col));
    vector<vector<int>> up(row,vector<int>(col));
    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j){
            cin>>matrix[i][j];
        }
    }
    for(int i = 0; i < row; ++i){
        int curr = 0;
        for(int j = 0; j < col; ++j){
            if(matrix[i][j] == 1) curr++;
            else curr = 0;
            left[i][j] = curr;
        }
        curr = 0;
        for(int j = col-1; j >= 0; --j){
            if(matrix[i][j] == 1) curr++;
            else curr = 0;
            right[i][j] = curr;
        }
    }
    for(int j = 0; j < col; ++j){
         int curr = 0;
        for(int i = 0; i < row; ++i){
            if(matrix[i][j] == 1) curr++;
            else curr = 0;
            up[i][j] = curr;
        }
        curr = 0;
        for(int i = row-1; i >= 0; --i){
            if(matrix[i][j] == 1) curr++;
            else curr = 0;
            down[i][j] = curr;
        }
    }
    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j){
            ans += max(min(left[i][j],up[i][j]/2) - 1,0);
            ans += max(min(left[i][j]/2,up[i][j]) - 1,0);
            ans += max(min(right[i][j],up[i][j]/2) - 1,0);
            ans += max(min(right[i][j]/2,up[i][j]) - 1,0);
            ans += max(min(left[i][j],down[i][j]/2) - 1,0);
            ans += max(min(left[i][j]/2,down[i][j]) - 1,0);
            ans += max(min(right[i][j],down[i][j]/2) - 1,0);
            ans += max(min(right[i][j]/2,down[i][j]) - 1,0);
        }
    }
    cout<<"Case #"<<t<<": "<<ans<<endl;
}

int main(){
    int t;
    cin>>t;
    for(int i = 0; i < t; ++i){
        slove(i+1);
    }
    return 0;
}

Rabbit House (9pts, 15pts)


这个题目跟leetcode上的那个容器的题目很像，所以是中规中矩的题目，不算很难，靠自己还能思考出来。

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14

题意

优先级队列

思路

  1. 我们将矩阵中所有单元的高度按照从高到底依次排列，每次从队列中取除当前高度最高的单元$(x,y)$,高度为$h$,则此时必须满足$(x,y)$周围的四个格子$(x-1,y),(x+1,y),(x,y+1),(x,y-1)$必须要大于等于$h-1$,如果当前格子的高度发生改变则将其从新放入队列中。
  2. 非常简单的优先级对即可解决，时间复杂度为$O(mnlg(mn))$,空间复杂度为$O(m*n)$.

代码

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

using namespace std;

struct Node{
    int x;
    int y;
    int val;
    Node(int x,int y,int val){
        this->x = x;
        this->y = y;
        this->val = val;
    }
};

struct cmp{
    bool operator()(Node & a,Node & b){
        return a.val < b.val;
    }
};

void slove(int t){
    int row;
    int col;
    long long ans = 0;
    int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    cin>>row>>col;
    vector<vector<int>> matrix(row,vector<int>(col));
    vector<vector<bool>> visit(row,vector<bool>(col,false));
    priority_queue<Node,vector<Node>,cmp> pq;

    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j){
            cin>>matrix[i][j];
            pq.push({i,j,matrix[i][j]});
        }
    }
    while(!pq.empty()){
        Node curr = pq.top();
        pq.pop();
        visit[curr.x][curr.y] = true;
        if(curr.val != matrix[curr.x][curr.y]) continue;

        for(int i = 0; i < 4; ++i){
            int x = curr.x + d[i][0];
            int y = curr.y + d[i][1];
            if(x < 0 || y < 0 || x >= row || y >= col) continue;
            if(visit[x][y]) continue;
            if(matrix[x][y] < curr.val - 1){
                ans += curr.val - 1 - matrix[x][y];
                matrix[x][y] = curr.val - 1;
                pq.push({x,y,matrix[x][y]});
            }
            visit[x][y] = true;
        }
    }

    cout<<"Case #"<<t<<": "<<ans<<endl;
}

int main(){
    int t;
    cin>>t;
    for(int i = 0; i < t; ++i){
        slove(i+1);
    }
    return 0;
}

Checksum (10pts, 17pts, 17pts)

题目


给定矩阵和每行每列的异或校验和，求恢复矩阵所需要的最小代价。

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068c2c3

题意

最小生成树

解题思路

  1. 这个题目还是非常难的，根本不容易想到，我们首先将已经恢复的单元视作代价为$0$的未恢复的单元。
  2. 首先我们需要想到一个问题，思考一下我们至少需要恢复多少个单元，才能将所有的单元全部恢复，这个就是一个非常值得思考得问题，我们仔细想一下，因为已知每一行所有元素得异或校验和，则我们如果已经知道每一行的$n-1$个值，则我们就能通过校验和计算最后一个未知的数，对于每一列同样也是如此，所以我们可以猜测一下，我们至少需要恢复$(n-1)^{2}$个数据，才能完成所有的$n^{2}$数据恢复。
  • 我们可以计算一下，如果恢复的元素超过$(n-1)^{2}$个，则我们可以计算出肯定存在某一行或者某一列恢复的数据为$n$个，这个对于我们来说是不必要的。
  • 如果恢复的数据少于$(n-1)^{2}$,则此时我们还至少需要恢复$2*N$个数据，而我们实际上根据异或的校验和，至多能够推导出$2N-1$个数据。
  1. 根据以上推论，我们可以知道可以知道选择出最大的未解的$2n-1$个数据，剩余的$(n-1)^{2}$的数据恢复则花费的代价可能最小。如何选择$2n-1$个数据呢？假设我们按照以下顺序通过校验和来恢复最后剩余的$(2n-1)$个数据，顺序为：
    0 0 0 9 0 8
    0 2 0 0 3 0
    0 0 5 0 4 0
    0 1 0 0 0 0 
    0 0 6 0 0 7
    11 0 0 10 0 0
    $1 \rightarrow 2 \rightarrow 3 \rightarrow 4\rightarrow 5\rightarrow 6\rightarrow 7\rightarrow 8\rightarrow 9\rightarrow 10 \rightarrow 11$
    我们实际可以知道将行与列分别看成生成树中的两个顶点，我们实际可以看出由行与列组成成的图不能有环，如果存在环的话，则一定存在某一行或者某一列中有两个未知数，则此时就不可能恢复该行或者该列的元素。
  2. 根据以上得出我们只需要选出边与行的顶点组成的最大生成树，可以用prim或者Kruskal算法即可。因为在此图中一个顶点连接的边很多，此时明显我们用prim算法的时间复杂度更好。
  3. 代码直接copy lucifer的。

代码

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class UnionFind {
  int n;
  vector<int> parent, size;

public:
  UnionFind(int n) {
    this->n = n;
    parent = vector<int>(n);
    size = vector<int>(n, 1);
    for (int i = 0; i < n; ++i)
      parent[i] = i;
  }

  int find(int idx) {
    if (parent[idx] == idx)
      return idx;
    return parent[idx] = find(parent[idx]);
  }

  void connect(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa != fb) {
      if (size[fa] > size[fb]) {
        parent[fb] = fa;
        size[fa] += size[fb];
      } else {
        parent[fa] = fb;
        size[fb] += size[fa];
      }
    }
  }
};

class Solution {
public:
  void solve(int case_num) {
    printf("Case #%d: ", case_num);
    int n;
    read(n);
    vector<vector<int>> a(n, vector<int>(n));
    vector<vector<int>> b(n, vector<int>(n));
    vector<int> r(n);
    vector<int> c(n);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        read(a[i][j]);

    vector<tuple<int, int, int>> edges;
    ll tot = 0;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        read(b[i][j]);
        tot += b[i][j];
        edges.emplace_back(b[i][j], i, n + j);
      }
    sort(edges.rbegin(), edges.rend());
    UnionFind uf(n * 2);

    for (int i = 0; i < n; ++i)
      read(r[i]);
    for (int i = 0; i < n; ++i)
      read(c[i]);

    ll remove = 0;
    for (auto [weight, u, v] : edges) {
      if (uf.find(u) == uf.find(v))
        continue;
      remove += weight;
      uf.connect(u, v);
    }

    printf("%lld\n", tot - remove);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

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

Tags: kickstart
← 【kick start】 2021 google kickstart round H 【数学】 数学题目 →

扫描二维码，分享此文章