且听疯吟

【kickstart】 kick start 2021 roundB

2022-11-20

google kick start 2021 roundB

google kickstart的题目质量很高，虽然比不上竞赛的难度，但是都是非常有思考的题目。
还是把题解仔细的写一遍，非常喜欢这类型的题目。

Increasing Substring

题目

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a882

题意

暴力统计

思路

  1. 判断当前字符为结尾的最长递增连续字符串的长度。

代码

#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){
    string s;
    int n;
    cin>>n;
    cin>>s;
    vector<int> ans(n,1);
    for(int i = 1; i < s.size(); ++i){
        if(s[i] > s[i-1]){
            ans[i] = ans[i-1] + 1;
        }else{
            ans[i] = 1;
        }
    }    
    cout<<"Case #"<<t<<": ";
    for(int i = 0; i < n; ++i){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}

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

Longest Progression

题目

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a3a5

题意

滑动窗口

思路

  1. 在最多只能改变一个元素的情况下，求连续最长的等差序列的长度。典型的滑动窗口，跟力扣的某个题目非常像。我们设left[i]为以第i个元素为结尾的最长连续等差序列的长度，right[i]为以第i个元素为开始的最长连续等差序列的长度，所以我们每次尝试改变第i个元素，然后进行前后可能的元素进行相连即可尝试得到最长的长度。
  2. 时间复杂度为$O(n)$,空间复杂度为$O(n)$.

代码

#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 n;
    int ans = 2;
    cin>>n;
    vector<int> arr = vector<int>(n);
    vector<int> left = vector<int>(n);
    vector<int> right = vector<int>(n);
    for(int i = 0; i < n; ++i) cin>>arr[i];
    
    /*left*/
    left[0] = 1;
    left[1] = 2;
    for(int i = 2; i < n; ++i){
        if(arr[i] - arr[i-1] == arr[i-1] - arr[i-2]){
            left[i] = left[i-1] + 1;
        }else{
            left[i] = 2;
        }
    }
    right[n-1] = 1;
    right[n-2] = 2;
    for(int i = n-3; i >= 0; --i){
        if(arr[i] - arr[i+1] == arr[i+1] - arr[i+2]){
            right[i] = right[i+1] + 1;
        }else{
            right[i] = 2;
        }
    }
    ans = max(ans, 1 + right[1]);
    ans = max(ans,1 + left[n-2]);
    if(n <= 3){
        ans = n;
    }else{
        for(int i = 1; i < n-1; ++i){
            if(i == 1){
                if(arr[i+1] - arr[i-1] == 2*(arr[i+2] - arr[i+1])){
                    ans = max(ans,right[i+1] + 2);
                }else{
                    ans = max(ans,right[i+1] + 1);
                }
            }else if(i == n-2){
                if(arr[i+1] - arr[i-1] == 2*(arr[i-1] - arr[i-2])){
                    ans = max(ans,left[i-1] + 2);
                }else{
                    ans = max(ans,left[i-1] + 1);
                }
            }else{
                if(arr[i+1] - arr[i-1] == 2*(arr[i+2] - arr[i+1]) && \
                   arr[i+1] - arr[i-1] == 2*(arr[i-1] - arr[i-2])){
                    ans = max(ans,left[i-1] + right[i+1] + 1);
                }else if(arr[i+1] - arr[i-1] == 2*(arr[i+2] - arr[i+1])){
                    ans = max(ans,right[i+1] + 2);
                }else if(arr[i+1] - arr[i-1] == 2*(arr[i-1] - arr[i-2])){
                    ans = max(ans,left[i-1] + 2);
                }else{
                    ans = max(ans,right[i+1] + 1);
                    ans = max(ans,left[i-1] + 1);
                }
            }
        }
    }

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

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

Consecutive Primes

给定数字num,求小等于num且刚好能够被分解为两个连续的质数的乘积的最大元素。

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a8e6

题意

数学问题

思路

  1. 首先因为题目中限定了元素的大小，我们仔细推算一下，肯定只能由这三个连续的质数的组合，$p_{1} < p_{2} < \sqrt{num} < p_{3}$,最终的结果要么为$p_{1}*p_{2}$,要么为$p_{2}*p_{3}$.
  2. 如果数据量非常小的话，我们直接用素数筛查法，即可求出所有的素数，但是因为本题中的数据量非常大，所以我们需要另辟蹊径。仔细查看一下数学知识，素数最大间隔，根据题目中的判断，我们可以猜测两个素数之间的最大间隔也就在几百，所以我们此时就可以用暴力求解，然后同时可以利用素因子快速检测一个数是否为素数因为我们只需要检测$lg(lg(num))$范围的素因子即可。
  3. 时间复杂度计算还是太麻烦了，大概在$O(k*lg(lg(num)))$.

代码

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

using namespace std;

bool visit[100006];
vector<long long> prime;

bool isPrime(long long x){
    long long h = sqrt(x);
    for(int i = 0; i < prime.size() && prime[i] <= h; ++i){
        if(x%prime[i] == 0) return false;
    }

    return true;
}

void slove(int t){
    long long num;
    long long ans;
    long long idx;
    vector<long long> arr;
    
    cin>>num;
    long long x = sqrt(num);
    /*upper*/
    for(int i = x+1; i < num ;++i){
        if(isPrime(i)){
            arr.push_back(i);
            break;
        }
    }
    /*lower*/
    for(int i = x; i >= 2; --i){
        if(isPrime(i)){
            arr.push_back(i);
            if(arr.size() >= 3) break;
        }
    }

    ans = 0;
    if(arr[0]*arr[1] <= num){
        ans = max(ans,arr[0]*arr[1]);
    }
    if(arr[1]*arr[2] <= num){
        ans = max(ans,arr[1]*arr[2]);
    }

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

int main(){
    int t;
    cin>>t;

    /*find all prime*/
    memset(visit,0,sizeof(visit));
    for(int i = 2;i <= 100005; ++i){
        if(visit[i]) continue;
        prime.push_back(i);
        for(int j = i; j <= 100005; j = j + i){
            visit[j] = true;
        }
    }
    for(int i = 0; i < t; ++i){
        slove(i+1);
    }
    return 0;
}

Truck Delivery

题目

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a885#problem

题意

线段树

解题思路

  1. 对于test1的数据集感觉一般人都能拿到分，无非是每次遇到查询，进行暴力检测路劲即可，即可得到所有可能的$GCD$的值，这个13分感觉很好难，时间复杂度为$O(N*Q)$.
  2. 对于第二个测试集则需要进行深入思考的深度，仔细发现一下，如果我们采用dfs遍历每一条路径时，如果所经历的路径已经按照limit进行排序好了，则我们可以很容易的利用二分查找即可在$O(lg(MAX(L)))$的时间复杂度内完成一次查询，如果需要这样进行查询的话则我们需要构造一种数据结构在$O(lg(MAX(L)))$的时间复杂度内完成这个查询。仔细思索一下我们可以构造线段树，线段树的长度为$(1,MAX(L))$,线段树的key为$L_{i}$,值为$V_{i}$,初始时设置$V_{i} = 0$.每次遇到查询$(C_{i},W_{i})$时，我们只需要查询$(1,W_{i})$范围的$gcd$即可。我们在遍历到某个节点时，则我们需要对线段树进行更新，每次更新$(L_{i},gcd(V_{i},C_{i}))$，每当我们从第$i$个节点退出时，则我们需要更新线段树的节点，需要将其节点的值从$gcd(V_{i},C_{i})$恢复到$V_{i}$.
  3. 时间复杂度为$O((2*N+Q)*lg(MAX(L)))$,空间复杂度为$O(MAX(L))$.

代码

  • 暴力解法
    #include<iostream>
    #include<vector>
    #include<set>
    #include<unordered_set>
    #include<map>
    #include<unordered_map>
    #include<string>
    #include<stack>
    #include<algorithm>
    #include<limits.h>
    #include<string.h>
    #include<queue>

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

    void slove(int t){
        int n,q;
        cin>>n>>q;
        vector<vector<long long>> graph(n);
        vector<vector<pii>> edgs(n,vector<pii>(n));
        for(int i = 0; i < n-1; ++i){
            long long x,y,l,a;
            cin>>x>>y>>l>>a;
            x--;
            y--;
            graph[x].push_back(y);
            graph[y].push_back(x);
            edgs[x][y] = {l,a};
            edgs[y][x] = {l,a};
        }

        vector<long long> fa = vector<long long>(n);
        vector<bool> visit(n);
        queue<long long> qu;

        /*bfs*/
        qu.push(0);
        visit[0] = true;
        while(!qu.empty()){
            int curr = qu.front();
            qu.pop();

            /*neg*/
            for(auto v : graph[curr]){
                if(visit[v]) continue;
                visit[v] = true;
                fa[v] = curr;
                qu.push(v);
            }
        }

        std::cout<<"Case #"<<t<<": ";
        for(int i = 0; i < q; ++i){
            long long c,w;
            long long num = 0;
            cin>>c>>w;
            c--;
            
            while(c != 0){
                pii curr = edgs[c][fa[c]];
                if(w >= curr.first){
                    if(num == 0) num = curr.second;
                    else num = __gcd(num,curr.second);
                }
                c = fa[c];
            }
            std::cout<<num<<" ";
        }
        std::cout<<endl;
    }

    int main(){
        int t;
        cin>>t;
        for(int i = 0; i < t; ++i){
            slove(i+1);
        }
        return 0;
    }
  • 线段树解法
    #include<iostream>
    #include<vector>
    #include<set>
    #include<unordered_set>
    #include<map>
    #include<unordered_map>
    #include<string>
    #include<stack>
    #include<algorithm>
    #include<limits.h>
    #include<string.h>
    #include<queue>

    using namespace std;
    typedef pair<long long,long long> pll;
    typedef pair<int,int> pii;
    typedef long long int64;
    typedef long int32;

    struct SegTreeNode{
        int l;
        int r;
        vector<long long> gcd;
    };

    struct Edge{
        int city;
        int limit;
        long long charge;
        Edge(int city,int limit,long long charge){
            this->city = city;
            this->limit = limit;
            this->charge = charge;
        }
    };

    const long long MAXN = 200005;
    SegTreeNode tree[MAXN*4];

    #define CHL(x) (x*2)
    #define CHR(x) (x*2 + 1)

    bool pushUpTree(int idx){
        long long left = tree[CHL(idx)].gcd.back();
        long long right = tree[CHR(idx)].gcd.back();
        tree[idx].gcd[0] = __gcd(left,right);
        return true;
    }

    bool buildTree(int l,int r,int idx){
        if(l > r) return false;
        tree[idx].l = l;
        tree[idx].r = r;
        tree[idx].gcd.push_back(0);
        if(l == r){
            return true;
        }

        int mid = (l+r)>>1;
        buildTree(l,mid,CHL(idx));
        buildTree(mid+1,r,CHR(idx));
        pushUpTree(idx);
        return true;
    }

    bool updateTree(int idx,int x,long long charge,int add){
        if(x < tree[idx].l || x > tree[idx].r ) return false;
        if(tree[idx].l == tree[idx].r && tree[idx].l == x){
            if(add == 1){
                //向当前节点加入一个新值
                long long val = tree[idx].gcd.back();
                tree[idx].gcd.push_back(__gcd(val,charge));
            }else if(add == -1){
                //弹出最后一个值
                tree[idx].gcd.pop_back();
            }
            return true;
        }
        
        long long mid = (tree[idx].l + tree[idx].r)>>1;
        if(x <= mid){
            updateTree(CHL(idx),x,charge,add);
        }else{
            updateTree(CHR(idx),x,charge,add);
        }
        pushUpTree(idx);
        return true;
    }

    long long queryTree(int idx,int w){
        if(w < tree[idx].l) return 0;
        if(tree[idx].l == tree[idx].r && tree[idx].r <= w){
            return tree[idx].gcd.back();
        }
        if(w >= tree[idx].r){
            return tree[idx].gcd.back();
        }else{
            int mid = (tree[idx].l + tree[idx].r)>>1;
            if(w <= mid){
                return queryTree(CHL(idx),w);
            }else if(w > mid){
                long long left = queryTree(CHL(idx),w);
                long long right = queryTree(CHR(idx),w);
                return __gcd(left,right);
            }
        }
    }

    bool dfs(int curr, vector<bool> & visit,vector<long long> & res,vector<vector<Edge>> & graph,vector<vector<pii>> & query){
        for(int i = 0; i < graph[curr].size(); ++i){
            int nx = graph[curr][i].city;
            int limit = graph[curr][i].limit;
            long long charge = graph[curr][i].charge;
            if(visit[nx]) continue;
            visit[nx] = true;

            //更新当前的（L,C）
            updateTree(1,limit,charge,1);
            for(auto v : query[nx]){
                int weight = v.first;
                int idx = v.second;
                res[idx] = queryTree(1,weight);
            }
            dfs(nx,visit,res,graph,query);
            //删除当前的边
            updateTree(1,limit,charge,-1);
            visit[nx] = false;
        }

        return true;
    }

    void slove(int t){
        int n,q;    
        /*input the value*/
        cin>>n>>q;
        vector<vector<Edge>> graph(n);
        vector<vector<pii>> query(n);
        vector<bool> visit(n,false);
        vector<long long> ans(q);
        for(int i = 0; i < n-1; ++i){
            int64 x,y,l,a;
            cin>>x>>y>>l>>a;
            x--;
            y--;
            graph[x].push_back(Edge(y,l,a));
            graph[y].push_back(Edge(x,l,a));
        }
        
        for(int i = 0; i < q; ++i){
            long long c,w;
            long long num = 0;
            cin>>c>>w;
            c--;
            //按照城市将所有的查询进行分类
            query[c].push_back({w,i});     
        }
        visit[0] = true;

        /*dfs every node*/
        dfs(0,visit,ans,graph,query);
        std::cout<<"Case #"<<t<<": ";
        for(int i = 0; i < q; ++i){
            cout<<ans[i]<<" ";
        }
        std::cout<<endl;
    }

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

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

Tags: kickstart
← 【算法】 mono stack 【google】 google →

扫描二维码，分享此文章