CCPC-Wannafly Winter Camp Day8

感悟

  • 大概就是自己思路不够开阔吧。。。题目真的很考验自己分析题目条件的能力,还是要多写多想啊,不能只写简单题,一定要学会分析性质还有解法多想想。
  • 题目地址:https://www.zhixincode.com/contest/29

A-Aqours

  • 题意:给你一棵树,对每个叶子节点,求到小于它编号的叶子节点距离的最小值,保证对于2\le ip_i\le p_j
  • 思路:题目给定的条件告诉你每个节点的深度都是在递增的,我们给每个节点u维护一个f_u表示到u最近的叶子节点的距离,然后我们从小到大扫描每一个叶子节点,每次都暴力往上跳去更新f_u,直到跳到一个已被其他叶子节点跳到过的节点为止。那么对于当前的叶子节点,离它最近的编号小于它的叶子节点到它的距离就是跳到这个终止节点的f值+跳的步数。同时我们还要回溯原路返回去更新所有节点,因为这个时候可能会存在当前叶子比较深但之前有比较浅的叶子节点。然后因为题目给定的性质,我们可以知道一个节点的f值最多只会被最先跳到它的叶子节点赋值一次,总时间复杂度就是O(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=3e6+10;
int n,i,ans,deg[N],p[N],f[N];
int jump(int u,int cnt){
    if (~f[u]){
        ans=f[u]+cnt;
        return f[u]+1;
    }
    f[u]=cnt;
    if (u>1) f[u]=min(f[u],jump(p[u],cnt+1));
    return f[u]+1;
}
int main(){
    memset(f,-1,sizeof(f));
    read(n);
    for (i=2;i<=n;++i){
        read(p[i]);
        deg[p[i]]++;
    }
    for (i=1;i<=n;++i)if(!deg[i]){
        ans=-1;
        jump(i,0);
        printf("%d %d\n",i,ans);
    }
    return 0;
}

B-玖凛两开花

  • 题意:略。
  • 思路:首先题面给的算法不说可不可行,就算可行也基本写不了,所以要直接扔掉(不要再被骗了..想想徐州惨案..),然后我们可以想想既然是mex,那么我们肯定是要保证前面有连续一段都有值,再考虑到这个答案肯定是具有单调性的,因为假设前面填了111110000,那么我们可以拆掉几个匹配达到11100000的目的,所以我们二分答案。我们把小于x的放在左边,大于等于x的放在右边,做一张二分图,但是毫无疑问它们内部是有边的,但我们完全可以无视掉,因为选出这些边不会对“答案能达到x”更有利,然后就暴力连边用Dinic跑网络流看是否满流,也就是左边的点是否都被匹配上即可,时间复杂度O(m\sqrt n logn)
#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 maxn=10000+10;
const int INF=2000000000;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct Dinic{
    int n,m,s,t;
    vector<Edge>edges;
    vector<int>G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

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

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

    bool BFS(){
        memset(vis,0,sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s]=0;
        vis[s]=1;
        while (!Q.empty()){
            int x=Q.front();Q.pop();
            for (int i=0;i<(int)G[x].size();i++){
                Edge& e=edges[G[x][i]];
                if (!vis[e.to] && e.cap>e.flow){
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a){
        if (x==t || a==0) return a;
        int flow=0,f;
        for (int& i=cur[x];i<(int)G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if (d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if (a==0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t){
        this->s=s;this->t=t;
        int flow=0;
        while (BFS()){
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,INF);
        }
        return flow;
    }
}A;
int n,m,i,l,r,ans,u[maxn*2],v[maxn*2];
bool check(int x){
    A.init(n+2);
    for (int i=0;i<n;++i){
        if (i<x) A.AddEdge(0,i+1,1);
        else A.AddEdge(i+1,n+1,1);
    }
    for (int i=1;i<=m;++i){
        if ((u[i]<x && v[i]<x)||(u[i]>=x && v[i]>=x)) continue;
        if (u[i]>v[i]) swap(u[i],v[i]);
        A.AddEdge(u[i]+1,v[i]+1,1);
    }
    return A.Maxflow(0,n+1)==x;
}
int main(){
    read(n),read(m);
    for (i=1;i<=m;++i) read(u[i]),read(v[i]); 
    int l=1,r=n;
    while (l<=r){
        int mid=l+((r-l)>>1);
        if (check(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

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