Google Kick Start 2021 Round B 题解

[utterances-bot]

Google Kick Start 2021 Round B 题解 | CP Wiki

< @/docs/tutorial/kick-start/2021B/src/b.cpp

https://cp-wiki.vercel.app/tutorial/kick-start/2021B/

[mearcstapa-gqz]

第三题欧拉筛是可以的吗 看题解的意思O(n) 10^9过不了啊

[lucifer1004]

第三题欧拉筛是可以的吗 看题解的意思O(n) 10^9过不了啊

Kick Start是捆绑测试，100个Testcase算总时间，而欧拉筛只需要计算一次，所以能过。

[tommyjiang]

第三题不错，第二题有点难，应该二三互换一下位置。

[lucifer1004]

第三题不错，第二题有点难，应该二三互换一下位置。

从最后结果来看是这样，但其实第三题还是更难的；主要是网赛，质数相关的各种资料很容易查到。

[mike-box]

最后一题用线段树是不是时间复杂度更低一些？

[lucifer1004]

最后一题用线段树是不是时间复杂度更低一些？

是的呀，不过线段树的做法需要欧拉序+离线查询，需要的前置知识还是挺多的。

[mike-box]

我照着参考解答写了一个线段树版本的，感觉还好不需要特别复杂的前置知识就是普通的线段树。每个节点代表从limit的范围为[l,r]时的charge的公约数，不过需要前置处理的时将所有的查询按照城市进行分类。

#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;
        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;
}

[Deep-Coder-zhui]

请问下，为啥我没有登录时，公式编排显示有重复和乱码？

[lucifer1004]

请问下，为啥我没有登录时，公式编排显示有重复和乱码？

之前没有遇到过这个情况，不太清楚具体的原因。

[zml24]

补一个按照官方题解写的简单版本的线段树，主程序solve的逻辑主要有两部分。
首先build一个空树，最大值为load-limit L_i的最大值，并预处理出每个城市C_j对应的所有W_j，使用map<int, vector<pair<int, int>>>存储，vector的第一维是W_j，第二维是query的id。
然后执行dfs。dfs时每经过一个点，首先计算出所有查询对应的值，就是query(1, W_j)，然后dfs每一个子节点，使用update(L_i, A_i)和update(L_i, 0)恢复现场。

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

const int INF = 0x3f3f3f3f;
// const double INF = 1e20;
// const LL INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

static auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(20);
    cout.tie(nullptr);
    return 0;
}();

const int N = 50010, M = 100010, MX = 200010;

int n, m, mx;
int h[N], e[N << 1], w1[N << 1], ne[N << 1], idx;
LL w2[N << 1];
map<int, vector<PII>> mp;
LL ans[M];

struct Node {
    int l, r;
    LL gcd;
}tr[MX << 2];

LL _gcd(LL a, LL b) {
    return b ? _gcd(b, a % b) : a;
}

void add(int a, int b, int c, LL d) {
    e[idx] = b, w1[idx] = c, w2[idx] = d, ne[idx] = h[a], h[a] = idx++;
}

void pushup(Node &u, Node &l, Node &r) {
    u.gcd = _gcd(l.gcd, r.gcd);
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    if (l == r) tr[u] = {l, r};
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, LL v) {
    if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v};
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    if (l > mid) return query(u << 1 | 1, l, r);
    auto lc = query(u << 1, l, r), rc = query(u << 1 | 1, l, r);
    Node res;
    pushup(res, lc, rc);
    return res;
}

void dfs(int u, int father) {
    for (auto it : mp[u]) {
        Node t = query(1, 1, it.x);
        ans[it.y] = t.gcd;
    }
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        modify(1, w1[i], w2[i]);
        dfs(j, u);
        modify(1, w1[i], 0);
    }
}

void solve() {
    memset(h, -1, sizeof h);
    idx = 0;
    cin >> n >> m;
    mx = 0;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        LL d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
        add(b, a, c, d);
        mx = max(mx, c);
    }
    build(1, 1, mx);
    mp.clear();
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        mp[a].push_back({b, i});
    }
    dfs(1, -1);
    for (int i = 0; i < m; i++) cout << ans[i] << " ";
    cout << endl;
}

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

[mike-box]

跪求roundC解答。

[linqw2016]

这个代码输入输出会读错了，有没有大佬帮忙看看，谢谢

import java.util.*;

public class Problem4 {
    static class Tag{
        int L;
        long A;
        Tag(int l,long a){
            this.L=l;
            this.A=a;
        }
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int T=scanner.nextInt();
        for (int t = 0; t < T; t++) {
            int N=scanner.nextInt();
            int Q=scanner.nextInt();
            List<Long> ans=new ArrayList<>();
            Tag[][] M=new Tag[N+1][N+1];
            int X=0,Y=0,Li=0;
            long Ai=0;
            int Cj=0,Wj=0;
            for (int i = 0; i < N - 1; i++) {
                X=scanner.nextInt();
                Y=scanner.nextInt();
                Li=scanner.nextInt();
                Ai=scanner.nextLong();
                M[X][Y]=new Tag(Li,Ai);
                M[Y][X]=new Tag(Li,Ai);
            }
            //init path[];
            int[] path=new int[N+1];
            Arrays.fill(path,-1);
            path[1]=0;
            boolean[] visited=new boolean[N+1];
            Arrays.fill(visited,false);
            Queue<Integer> q=new LinkedList<>();
            q.add(1);
            visited[1]=true;
            while (!q.isEmpty()){
                int tmp=q.poll();
                for (int i = 1; i < N + 1; i++) {
                    if(M[tmp][i]!=null&&!visited[i]){
                        path[i]=tmp;
                        visited[i]=true;
                        q.add(i);
                    }
                }
            }
            for (int i = 0; i < Q; i++) {
                Cj=scanner.nextInt();
                Wj=scanner.nextInt();
                int start=Cj;
                long gcdans=0;
                while(path[start]!=0){
                    if(gcdans==1)break;
                    int before=path[start];
                    int L=M[before][start].L;
                    if(L<=Wj){
                        gcdans=gcd(gcdans,M[before][start].A);
                    }
                    start=before;
                }
                ans.add(gcdans);
            }
            System.out.print("Case #"+(t+1)+":");
            for (long a : ans) {
                System.out.print(" "+a);
            }
            System.out.println();
        }
    }
    public static long gcd(long a,long b){
        //let a>=b;
        if(a<b){
            long tmp=a;
            a=b;
            b=tmp;
        }
        if(b==0)return a;
        if(a%b==0)return b;
        return gcd(b,a%b);
    }
}