2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest(部分题解)

C.Cover the Paths

  • 题意:在树上找一个点集,使得每条路径都与这个点集有交集。
  • 思路:将树链的LCA按深度排序,贪心的从深到浅的放,同时用树状数组维护区间被添加点的数量,如果这条树链中已经被添加了点那就不用加了,直接跳过。
#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
int n,m,u,v,i,cnt,dfs_clock,choose[N],sum[N],dfn[N],dep[N],fa[N],bel[N],sz[N],son[N];
struct Chain{
    int u,v,anc;
    bool operator<(const Chain&rhs)const{
        return dep[anc]>dep[rhs.anc];
    }
};
vector<int>G[N];
vector<Chain>res;
void dfs(int u,int f){
    sz[u]=1,son[u]=-1,fa[u]=f,dep[u]=dep[f]+1;
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int f){
    bel[u]=f,dfn[u]=++dfs_clock;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v){
    for (;bel[u]!=bel[v];dep[bel[u]]>dep[bel[v]]?u=fa[bel[u]]:v=fa[bel[v]]);
    return dep[u]>dep[v]?v:u;
}
inline int lowbit(int x){return x&(-x);}
void add(int x){for(;x<=n;x+=lowbit(x))sum[x]++;}
int get(int x){
    int ans=0;
    for (;x>0;x-=lowbit(x)) ans+=sum[x];
    return ans;
}
int query(int u,int v){
    int ans=0;
    while (bel[u]!=bel[v]){
        if (dep[bel[u]]<dep[bel[v]]) swap(u,v);
        ans+=get(dfn[u])-get(dfn[bel[u]]-1);
        u=fa[bel[u]];
    }
    if (dep[u]>dep[v]) swap(u,v);
    ans+=get(dfn[v])-get(dfn[u]-1);
    return ans;
}
void work(int u,int v,int anc){
    if (query(u,v)) return;
    choose[++cnt]=anc;
    add(dfn[anc]);
}
int main(){
    read(n);
    for (i=1;i<n;++i){
        read(u),read(v);
        G[u].PB(v);
        G[v].PB(u);
    }
    dfs(1,0),dfs2(1,1);
    for (read(m),i=1;i<=m;++i){
        read(u),read(v);
        res.PB((Chain){u,v,lca(u,v)});
    }
    sort(res.begin(),res.end());
    for (i=0;i<(int)res.size();++i) work(res[i].u,res[i].v,res[i].anc);
    printf("%d\n",cnt);
    for (i=1;i<=cnt;++i) printf("%d%c",choose[i],i==cnt?'\n':' ');
    return 0;
}

D.Elevator

  • 题意:坐电梯。给出每个人的到达时间和要去的楼层(都是从第 0层出发)。电梯会到电梯中人要去的最高层,再回到0层。你可以选择电梯在0层停多久。求送完所有人所需要的最短时间。需要注意的是,只要电梯在第0层,来的人就会直接进电梯等。
  • 思路:定义dp[i]为送前i个人上楼层的最短时间,要先注意到如果t_i< t_j以及a_i< a_j,显然i是没有用的,直接第j个人带它上去即可,所以最后的序列一定是a_i单调递减的。列出状态转移方程dp[i]=min(max(dp[j],t[i])+2*a[j+1])(j< i),由上面的条件得知dp[j]< t[i+1],不然是不合法的,第i+1个人一定会和第i个人一起上去,然后我们对max分类讨论,拿两个平衡树维护最值,支持插入即可。
#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int N=2e5+10;
const ll INF=2000000000000000000LL;
struct Node{
    int l,r,dat;
    ll val,mn,f;
};
struct Treap{
    Node a[N];
    int tot,root;

    int New(ll val,ll num){
        a[++tot].val=val;
        a[tot].dat=rng();
        a[tot].f=a[tot].mn=num;
        a[tot].l=a[tot].r=0;
        return tot;
    }
    void update(int p){
        if (a[p].l) a[p].mn=min(a[p].f,a[a[p].l].mn);
        if (a[p].r) a[p].mn=min(a[p].f,a[a[p].r].mn);
    }
    void build(){
        tot=0;
        root=1;
    }
    void zig(int&p){
        int q=a[p].l;
        a[p].l=a[q].r,a[q].r=p,p=q;
        update(a[p].r),update(p);
    }
    void zag(int&p){
        int q=a[p].r;
        a[p].r=a[q].l,a[q].l=p,p=q;
        update(a[p].l),update(p);
    }
    void Insert(int&p,ll val,ll v){
        if (p==0){
            p=New(val,v);
            return;
        }
        if (val==a[p].val){
            a[p].f=min(a[p].f,v);
            return;
        }
        if (val<a[p].val){
            Insert(a[p].l,val,v);
            if (a[p].dat<a[a[p].l].dat) zig(p);
        }
        else{
            Insert(a[p].r,val,v);
            if (a[p].dat<a[a[p].r].dat) zag(p);
        }
        update(p);
    }
    ll query(int&p,ll l,ll r,ll L,ll R){
        if (!p) return INF;
        if (L<=l && r<=R) return a[p].mn;
        ll t=L<=a[p].val && a[p].val<=R?a[p].f:INF;
        if (L<a[p].val) t=min(t,query(a[p].l,l,a[p].val-1,L,R));
        if (a[p].val<R) t=min(t,query(a[p].r,a[p].val+1,r,L,R));
        return t;
    }
}A,B;
struct P{
    ll t,a;
}a[N],q[N];
int n,cnt,i;
ll dp[N];
inline void ins(int x){
    if (dp[x]>=INF) return;
    A.Insert(A.root,dp[x],q[x+1].a);
    B.Insert(B.root,dp[x],dp[x]+q[x+1].a);
}
inline bool cmp(const P&a,const P&b){return a.t<b.t;}
int main(){
    while (~scanf("%d",&n)){
        for (i=1;i<=n;++i) read(a[i].t),read(a[i].a),a[i].a<<=1LL;
        for (cnt=0,i=1;i<=n;++i){
            while (cnt && q[cnt].a<=a[i].a) cnt--;
            q[++cnt]=a[i];
        }
        q[cnt+1].t=INF;
        A.build(),B.build();
        A.root=A.New(0,q[1].a);
        B.root=B.New(0,q[1].a);
        for (i=1;i<=cnt;++i){
            dp[i]=min(A.query(A.root,0LL,INF,0,q[i].t)+q[i].t,B.query(B.root,0LL,INF,q[i].t,q[i+1].t-1));
            ins(i);
        }
        printf("%lld\n",dp[cnt]);
    }
    return 0;
}

G.Berland Post

  • 题意:给你一张有向图,还有每条边的边权,现在告诉你一部分点的点权,另一部分点权未知,要求你找出满足条件的最小的T,使得存在一组点权满足所有边o_u+dis_{u->v}<= o_v+T,点权范围[-1e9,1e9]
  • 思路:观察到时间是具有单调性的,即如果这个时间可以,后面的时间一定都可以,所以二分时间T去找有没有满足条件的点权即可,然后对于每条边都是一个不等式,就是典型的差分约束了,注意到对于每个点我们也有限制条件,所以要建立一个虚拟源点0代表o_0,点的限制就相当于o_x-o_0<= XXX这样子,然后注意数组要开大。。。大概是第n次犯这种智障错误了。。。
#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2000+10;
const int INF=2000000000;
struct Edge{
    int from,to;
    double dist;
};
struct BellmanFood{
    int n,m;
    vector<Edge>edges;
    vector<int>G[N];
    bool inq[N];
    double d[N];
    int cnt[N];

    void init(int n){
        this->n=n;
        for (int i=0;i<=n;i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int u,int v,double w){
        edges.push_back((Edge){u,v,w});
        m=edges.size();
        G[u].push_back(m-1);
    }

    bool negativeCycle(){
        queue<int>Q;
        for (int i=0;i<=n;i++){
            d[i]=cnt[i]=0;
            inq[i]=true;
            Q.push(i);
        }

        while (!Q.empty()){
            int u=Q.front();Q.pop();
            inq[u]=false;
            for (int i=0;i<(int)G[u].size();i++){
                Edge &e=edges[G[u][i]];
                if (d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    if (!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=true;
                        if (++cnt[e.to]>n+1) return true;
                    }
                }
            }
        }
        return false;
    }

    void spfa(){
        queue<int>Q;
        for (int i=0;i<=n;i++){
            d[i]=2000000000000000000LL;
            inq[i]=cnt[i]=0;
        }
        d[0]=0,inq[0]=true;
        Q.push(0);

        while (!Q.empty()){
            int u=Q.front();Q.pop();
            inq[u]=false;
            for (int i=0;i<(int)G[u].size();i++){
                Edge &e=edges[G[u][i]];
                if (d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    if (!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=true;
                        if (++cnt[e.to]>n+1) return;
                    }
                }
            }
        }
    }
}solver;
int n,m,i,u[N],v[N],w[N],val[N];
char s[10];
bool check(double T){
    for (int i=1;i<=m;++i) solver.edges[n*2+i-1].dist=T-w[i];
    return !solver.negativeCycle();
}
void pre(){
    solver.init(n);
    for (int i=1;i<=n;++i){
        if(val[i]!=-INF){
            solver.AddEdge(0,i,val[i]);
            solver.AddEdge(i,0,-val[i]);
        }
        else{
            solver.AddEdge(0,i,1000000000);
            solver.AddEdge(i,0,1000000000);
        }
    }
    for (int i=1;i<=m;++i) solver.AddEdge(v[i],u[i],0);
}
int main(){
    while (~scanf("%d%d",&n,&m)){
        for (i=1;i<=n;++i){
            scanf("%s",s);
            if (s[0]=='?') val[i]=-INF;
            else sscanf(s,"%d",&val[i]);
        }
        for (i=1;i<=m;++i) read(u[i]),read(v[i]),read(w[i]);
        pre();
        double l=0,r=1000000000;
        for (i=1;i<=60;++i){
            double mid=(l+r)/2.0;
            if (check(mid)) r=mid;
            else l=mid;
        }
        printf("%.7f\n",(l+r)/2.0);
        for (solver.spfa(),i=1;i<=n;++i) printf("%.7f%c",solver.d[i],i==n?'\n':' ');
    }
    return 0;
}

J. Subsequence Sum Queries

  • 题意:给一个数列。每次询问一个区间。问区间内的数组成的多重集有多少个子集的和是m的倍数。
  • 思路:考虑询问离线,分治解决,预处理出[l,mid]倒序的背包方案数还有[mid+1,r]正序的背包方案数,那么询问区间跨过mid的答案就是\sum_{j+k=m}f[L[i]][j]*g[R[i]][k],剩下的递归处理,时间复杂度O((nm+q)logn+qm)
#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2e5+10;
const int P=1e9+7;
int n,m,q,i,L[N],R[N],ans[N],a[N],f[N][20],g[N][20];
inline void up(int&a,int b){a+=b;if(a>=P)a-=P;}
void solve(int l,int r,vector<int> v){
    if (l>r || v.size()==0) return;
    int i,j,mid=l+((r-l)>>1);
    for(i=l;i<=mid+1;++i)for(j=0;j<m;++j)f[i][j]=0;
    for (f[mid+1][0]=1,i=mid;i>=l;--i){
        for (j=0;j<m;++j){
            up(f[i][j],f[i+1][j]);
            up(f[i][(j+a[i])%m],f[i+1][j]);
        }
    }
    for(i=mid;i<=r;++i)for(j=0;j<m;++j)g[i][j]=0;
    for (g[mid][0]=1,i=mid+1;i<=r;++i){
        for (j=0;j<m;++j){
            up(g[i][j],g[i-1][j]);
            up(g[i][(j+a[i])%m],g[i-1][j]);
        }
    }
    vector<int>vl,vr;
    for (i=0;i<(int)v.size();++i){
        if (L[v[i]]>mid) vr.PB(v[i]);
        else if (R[v[i]]<mid) vl.PB(v[i]);
        else{
            for (j=0;j<m;++j) up(ans[v[i]],1LL*f[L[v[i]]][j]*g[R[v[i]]][(m-j)%m]%P);
        }
    }
    solve(l,mid-1,vl);
    solve(mid+1,r,vr);
}
int main(){
    read(n),read(m);
    for (i=1;i<=n;++i) read(a[i]),a[i]%=m;
    read(q);
    vector<int>v;
    for (i=1;i<=q;++i){
        read(L[i]),read(R[i]);
        v.PB(i);
    }
    solve(1,n,v);
    for (i=1;i<=q;++i) printf("%d\n",ans[i]);
    return 0;
}

K. Consistent Occurrences

  • 题意:询问一个串中某个串不重叠的最多出现次数。
  • 思路:考虑到题目限制,询问串的长度和小于1e5,对所有询问离线建立AC自动机。考虑我们要保证最多的话肯定是从前往后匹配能放就放,贪心即可,所以拿主串在AC自动机上走,走到一个单词节点就沿着后缀链接回溯,同时记录一个上次走到这个单词节点的时候我们主串走过的长度,只有这个长度加单词长度小于现在的位置才可以更新答案,时间复杂度不会算,据队友说极限数据是卡到O(n\sqrt n)
#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
const int SIGMA_SIZE=26;
char s[N];
string tmp[N];
int n,m,i,ID,tot,ans[N],fail[N],last2[N],id[N*SIGMA_SIZE],last[N*SIGMA_SIZE],l[N*SIGMA_SIZE],ch[N][SIGMA_SIZE];
bool isWord[N*SIGMA_SIZE];
queue<int>Q;
void ins(const string&s,int len,int x){
    int p=0;
    for (int i=0;i<len;++i){
        int idx=s[i]-'a';
        if (!ch[p][idx]) ch[p][idx]=++tot;
        p=ch[p][idx];
    }
    isWord[p]=1;
    id[p]=x;
    l[p]=len;
}
void getFail(){
    for (int i=0;i<SIGMA_SIZE;++i){
        if (ch[0][i]) Q.push(ch[0][i]);
    }
    while (!Q.empty()){
        int u=Q.front();Q.pop();
        for (int i=0;i<SIGMA_SIZE;++i){
            if (ch[u][i]){
                fail[ch[u][i]]=ch[fail[u]][i];
                last[ch[u][i]]=isWord[fail[ch[u][i]]]?fail[ch[u][i]]:last[fail[ch[u][i]]];
                Q.push(ch[u][i]);
            }
            else ch[u][i]=ch[fail[u]][i];
        }
    }
}
void update(int j,int pp){
    if (isWord[j]){
        if (last2[id[j]]+l[j]<=pp){
            ans[id[j]]++;
            last2[id[j]]=pp;
        }
        update(last[j],pp);
    }
}
void work(){
    int p=0;
    for (int i=0;s[i];++i){
        int idx=s[i]-'a';
        p=ch[p][idx];
        if (isWord[p]) update(p,i+1);
        else if (last[p]) update(last[p],i+1);
    }
}
map<string,int>mp;
void add(const string&s){
    if (mp.find(s)!=mp.end()) return;
    mp[s]=++ID;
    ins(s,(int)s.length(),ID);
}
int main(){
    read(n),read(m);
    scanf("%s",s);
    for (i=1;i<=m;++i){
        cin>>tmp[i];
        add(tmp[i]);

    }
    getFail();
    work();
    for (i=1;i<=m;++i) printf("%d\n",ans[mp[tmp[i]]]);
    return 0;
}

L.Increasing Costs

  • 题意:给一个无向图,问给每条边加税后,分别会有多少个点从起点出发涨价了。
  • 思路:求出最短路后,建立最短路图,只有必经边才会造成后面的点涨价,于是对最短路图建立Dominator Tree,把边拆看成一个额外的点,u->v即拆成u->i->v,每条边的答案就是这些边的代表的点为根的子树大小。
#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2e5+10;
const int M=4e5+10;
const ll INF=2000000000000000000LL;
struct Edge{
    int from,to,dist;
};
struct HeapNode{
    ll d;
    int u;
    bool operator <(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m;
    vector<Edge>edges;
    vector<int>G[N];
    bool done[N];
    ll d[N];

    void init(int n){
        this->n=n;
        for (int i=0;i<=n;i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from,int to,int dist){
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }

    void dijkstra(int s){
        priority_queue<HeapNode>Q;
        for (int i=0;i<=n;i++) d[i]=INF;
        d[s]=0;
        memset(done,false,sizeof(done));
        Q.push((HeapNode){0,s});
        while (!Q.empty()){
            HeapNode x=Q.top();Q.pop();
            int u=x.u;
            if (done[u]) continue;
            done[u]=true;
            for (int i=0;i<(int)G[u].size();i++){
                Edge &e=edges[G[u][i]];
                if (d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }
}solver;
int n,m,i,u,v,w,cnt,p,dfs_clock,sum[N],deg[M],id[M],sz[M],mn[M],dfn[M],f[M],rk[M],fa[M],sdom[M],idom[M];
vector<int>G[M],pre[M],G2[M],bucket[M];
inline void addEdge(int u,int v){
    G[u].PB(v);
    pre[v].PB(u);
    deg[v]++;
}
void dfs(int u){
    dfn[u]=++dfs_clock,rk[dfs_clock]=u,sdom[u]=dfs_clock;
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        if (dfn[v]) continue;
        dfs(v);
        fa[v]=u;
    }
}
int Find(int p){
    if (f[p]==p) return p;
    int root=Find(f[p]);
    if (sdom[mn[f[p]]]<sdom[mn[p]]) mn[p]=mn[f[p]];
    return f[p]=root;
}
inline int eval(int p){
    Find(p);
    return mn[p];
}
void LengauerTarjan(){
    dfs(cnt);
    for (i=dfs_clock;i>=2;--i){
        p=rk[i];
        for (int k:pre[p]){
            if (dfn[k]){
                sdom[p]=min(sdom[p],sdom[eval(k)]);
            }
        }
        bucket[rk[sdom[p]]].PB(p);
        int anc=fa[p];f[p]=fa[p];
        for (int v:bucket[anc]){
            int u=eval(v);
            idom[v]=sdom[u]==sdom[v]?anc:u;
        }
        bucket[anc].clear();
    }
    for (i=2;i<=dfs_clock;++i) p=rk[i],idom[p]=idom[p]==rk[sdom[p]]?idom[p]:idom[idom[p]];
    for (i=2;i<=dfs_clock;++i) p=rk[i],sdom[p]=rk[sdom[p]];
}
void dfs2(int u){
    for (int i=0;i<(int)G2[u].size();++i){
        dfs2(G2[u][i]);
        sz[u]+=sz[G2[u][i]];
    }
    sum[id[u]]=sz[u];
}
void solve(){
    for (i=1;i<cnt;++i) G2[idom[i]].PB(i);
    dfs2(cnt);
    for (i=1;i<=m;++i) printf("%d\n",sum[i]);
}
int main(){
    read(n),read(m);
    solver.init(n);
    for (i=1;i<=m;++i){
        read(u),read(v),read(w);
        solver.AddEdge(u,v,w);
        solver.AddEdge(v,u,w);
    }
    solver.dijkstra(1);
    for (i=1;i<=n;++i){
        sz[i]=solver.d[i]<INF;
    }
    for (cnt=n,i=0;i<m;++i){
        Edge& e=solver.edges[i<<1];
        int u=e.from,v=e.to,w=e.dist;
        if (solver.d[u]+w==solver.d[v]) id[++cnt]=i+1,addEdge(u,cnt),addEdge(cnt,v);
        if (solver.d[v]+w==solver.d[u]) id[++cnt]=i+1,addEdge(v,cnt),addEdge(cnt,u);
    }
    for (cnt++,i=1;i<cnt;++i) if(!deg[i]) addEdge(cnt,i);
    for (i=1;i<=cnt;++i) f[i]=mn[i]=i;
    LengauerTarjan();
    solve();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注