2017-2018 ACM-ICPC Latin American Regional Programming Contest

总体情况

总共通过7题CEFGHIJ。其中我完成HIJ三题。纯属被大佬带飞系列。

解题报告

H - Hard choice

签到题

#include <bits/stdc++.h>

using namespace std;

int a1,b1,c1,a2,b2,c2;

int main() {

    cin>>a1>>b1>>c1>>a2>>b2>>c2;

    cout<<max(a2-a1,0)+max(b2-b1,0)+max(c2-c1,0)<<endl;

}

I - Imperial roads

比较裸，类似求次小生成树。这里写的是树链剖分+Kruskal，当然用树上倍增或者LCT维护都很棒。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1000005;

struct Edge {

    int u,v,w;

    bool operator < (const Edge &b) const {

        return w<b.w;

    }

};

struct Ed {

    int u,v,w;

    bool operator < (const Ed &b) const {

        if(u==b.u) return v<b.v;

        else return u<b.u;

    }

    bool operator > (const Ed &b) const {

        if(u==b.u) return v>b.v;

        else return u>b.u;

    }

    bool operator == (const Ed &b) const {

        return u==b.u && v==b.v;

    }

    bool operator >= (const Ed &b) const {

        return *this>b || *this==b;

    }

    bool operator <= (const Ed &b) const {

        return *this<b || *this==b;

    }

};

int n,m,q,t1,t2,t3,t4;

Edge e[N]; Ed E[N];

bool f[N];

vector <pair<int,int> > g[N];

namespace Kruskal {

    int fa[N],ans;

    int find(int x) {

        return fa[x]==x?x:fa[x]=find(fa[x]);

    }

    void merge(int p,int q) {

        p=find(p); q=find(q); fa[p]=q;

    }

    void solve() {

        sort(e+1,e+m+1);

        for(int i=1;i<=n;i++) fa[i]=i;

        for(int i=1;i<=m;i++) {

            if(find(e[i].u)!=find(e[i].v)) {

                merge(e[i].u,e[i].v);

                ans+=e[i].w;

                f[i]=true;

                g[e[i].u].push_back(make_pair(e[i].v,e[i].w));

                g[e[i].v].push_back(make_pair(e[i].u,e[i].w));

            }

        }

    }

}

namespace SegmentTree {

    int a[N<<2],b[N<<2];

    void build(int p,int l,int r,int *src) {

        if(l==r) a[p]=src[l];

        else {

            build(p*2,l,(l+r)/2,src);

            build(p*2+1,(l+r)/2+1,r,src);

            a[p]=max(a[p*2],a[p*2+1]);

            if(a[p*2]<a[p]) b[p]=a[p*2];

            else if(a[p*2+1]<a[p]) b[p]=a[p*2+1];

            else b[p]=max(b[p*2],b[p*2+1]);

        }

    }

    int query(int p,int l,int r,int ql,int qr) {

        if(l>qr||r<ql) return 0;

        if(l>=ql && r<=qr) return a[p];

        return max(query(p*2,l,(l+r)/2,ql,qr),query(p*2+1,(l+r)/2+1,r,ql,qr));

    }

    int querys(int p,int l,int r,int ql,int qr) {

        if(l>qr||r<ql) return 0;

        if(l>=ql && r<=qr) return b[p];

        return max(querys(p*2,l,(l+r)/2,ql,qr),querys(p*2+1,(l+r)/2+1,r,ql,qr));

    }

}

namespace Tree {

    int ind,fa[N],siz[N],dep[N],dis[N],vis[N],wson[N],top[N],dfn[N];

    void dfs1(int p) {

        vis[p]=1; siz[p]=1;

        for(int i=0;i<g[p].size();i++) {

            int q=g[p][i].first;

            if(vis[q]) continue;

            dep[q]=dep[p]+1;

            dis[q]=g[p][i].second;

            fa[q]=p;

            dfs1(q);

            siz[p]+=siz[q];

            if(siz[wson[p]]<siz[q]) wson[p]=q;

        }

    }

    void dfs2(int p) {

        vis[p]=1;

        dfn[p]=++ind;

        if(wson[p]) {

            top[wson[p]]=top[p];

            dfs2(wson[p]);

        }

        for(int i=0;i<g[p].size();i++) {

            int q=g[p][i].first;

            if(vis[q]) continue;

            top[q]=q;

            dfs2(q);

        }

    }

    void presolve() {

        dfs1(1);

        memset(vis,0,sizeof vis);

        top[1]=1;

        dfs2(1);

    }

    int query(int p,int q) {

        int ret=0;

        while(top[p]!=top[q]) {

            if(dep[top[p]]<dep[top[q]]) swap(p,q);

            ret = max(ret,SegmentTree::query(1,1,n,dfn[top[p]],dfn[p]));

            p=fa[top[p]];

        }

        if(dep[p]>dep[q]) swap(p,q);

        return max(ret,SegmentTree::query(1,1,n,dfn[p]+1,dfn[q]));

    }

    /*int querys(int p,int q) {

        int ret=0, lim=query(p,q);

        while(top[p]!=top[q]) {

            if(dep[top[p]]<dep[top[q]]) swap(p,q);

            if(SegmentTree::query(1,1,n,dfn[top[p]],dfn[p])<lim)

                ret=max(ret,SegmentTree::query(1,1,n,dfn[top[p]],dfn[p]));

            else

                ret=max(ret,SegmentTree::querys(1,1,n,dfn[top[p]],dfn[p]));

            p=fa[top[p]];

        }

        if(dep[p]>dep[q]) swap(p,q);

        if(SegmentTree::query(1,1,n,dfn[p]+1,dfn[q])<lim)

            return max(ret,SegmentTree::query(1,1,n,dfn[p]+1,dfn[q]));

        else

            return max(ret,SegmentTree::query(1,1,n,dfn[p]+1,dfn[q]));

    }*/

}

int val[N];

int main() {

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++) {

        scanf("%d%d%d",&t1,&t2,&t3);

        e[i].u=t1;

        e[i].v=t2;

        e[i].w=t3;

        E[i].u=t1;

        E[i].v=t2;

        E[i].w=t3;

    }

    sort(E+1,E+m+1);

    Kruskal::solve();

    Tree::presolve();

    for(int i=1;i<=n;i++) {

        val[Tree::dfn[i]]=Tree::dis[i];

    }

    SegmentTree::build(1,1,n,val);

    int ans = Kruskal::ans;

    scanf("%d",&q);

    for(int i=1;i<=q;i++) {

        scanf("%d%d",&t1,&t2);

        Ed qe;

        qe.u = t1; qe.v = t2;

        int eid = lower_bound(E+1,E+m+1,qe) - E;

        cout<<ans + E[eid].w - Tree::query(t1,t2)<<endl;

    }

}

J - Jumping frog

容易发现，步数\(k\)可行的充要条件是 \((n,k)\) 可行。于是可以按照 \((n,k)\) 对集合 \(K\) 划分等价类，只需要检验集合 \(D = \{d: d|n\}\) 中的所有元素即可。容易发现对任意 \(d \in D\)，只需要检查是否存在 \(x \in [0,d)\) 使得对任意 \(x+id\) 位置是 Rock。计算答案只要统计所有合法等价类的大小之和即可。

划分等价类时求解若干次GCD，时间复杂度 \(O(n \log{n})\)。检查只需要 \(O(n)\) 扫描，而等价类个数 \(|D|\) ，等于 \((n,k)\) 的所有可能取值。考虑到若\(g=(n,k)\)，则必有 \(g|n\)，因此 \(|D|+1\) 即为 \(n\) 的因数个数。根据因数个数定理容易证明， \(n\) 的因数个数有渐进上界\(O(\sqrt{n})\)，于是总体时间复杂度为 \(O(n \sqrt{n})\)。

#include <bits/stdc++.h>

using namespace std;

int n;

char s[100005];

vector <int> d;

int dsize[100005],buf[100005];

int gcd(int a,int b) {

    return !b?a:gcd(b,a%b);

}

bool check(int k) {

    memset(buf,0,sizeof buf);

    for(int i=0;i<n;i++) if(s[i]=='P') buf[i%k]++;

    for(int i=0;i<k;i++) if(buf[i]==0) return true;

    return false;

}

int main() {

    ios::sync_with_stdio(false);

    cin>>s;

    n=strlen(s);

    for(int i=1;i<n;i++) {

        if(n%i==0) d.push_back(i);

    }

    for(int i=1;i<n;i++) {

        dsize[gcd(i,n)]++;

    }

    int ans = 0;

    for(int i=0;i<d.size();i++) {

        if(check(d[i])) ans += dsize[d[i]];

    }

    cout<<ans<<endl;

}

巴特西

训练20191007 2017-2018 ACM-ICPC Latin American Regional Programming Contest