526互联

2022 省队二轮集训培训日记-Day7

发布时间 2023-07-13 21:09:22作者: NuclearReactor

模拟赛

T1

这个题一看就非常 DP，考虑设 $f_i$ 表示跳到 $i$ 的最优解，但是发现无法转移。

为什么？考虑从 $j$ 跳到 $i$ 时，我们除了考虑 $j$ 与 $i$ 之间的 $x$ 需要满足 $x+a_x<i$ 之外，对于 $x<j$，我们仍然有同样的限制。所以这个限制我们干脆再开一维记一下，设 $f_{i,x}$ 表示对于 $j<i$ 都有 $j+a_j\le x$，跳到 $i$ 的最优解。那么我们有转移：

$$
f_{j,i-1}+w(j,i)\rightarrow f_{i,j+a_j+c},(c>0)
$$

注意 $j,i$ 之间所有不合法的都已经删掉了。

看似这个方程是 $n^3$ 的，但是我们可以先不管这个 $c$，而转移之前，我们先对 $f_j$ 做一下前缀取 $\min$ 即可。

我考场没想出来，DP 还是太差了。

代码：

#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 3010
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int f[N][N<<1],a[N],g[N][N],n;

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);rep(i,1,n) read(a[i]);
    rep(i,3,n)dec(j,1,i-2) g[j][i]=g[j+1][i]+(j+1+a[j+1]>=i);
    // rep(i,3,n)rep(j,1,i-2) printf("g[%d][%d]=%d\n",j,i,g[j][i]);
    mset(f,INF);rep(k,1,n<<1) f[1][k]=0; 
    rep(j,1,n){
        rep(i,0,n<<1) cmin(f[j][i],f[j][i-1]);
        rep(i,j,n-1) if(j+a[j]>=i+1){
            // printf("Before f[%d][%d]=%d\n",i+1,j+a[j],f[i+1][j+a[j]]);
            cmin(f[i+1][j+a[j]],f[j][i]+g[j][i+1]);
            // printf("Update f[%d][%d]=%d\n",i+1,j+a[j],f[i+1][j+a[j]]);
        }
    }
    // rep(i,1,n)rep(j,1,(n<<1)) printf("f[%d][%d]=%d\n",i,j,f[i][j]);
    int ans=INF;
    rep(i,n,n<<1) cmin(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}

T2

感觉不像是 DP 能解决的事情，于是就往图论那边凑，因为网络流的题面，所以优先选择网络流。

首先考虑流量守恒的限制，源点和汇点比较特殊，可以通过源汇点之间连边来解决，然后像上下界网络流一样连边，我们考虑因为流量增加或减少带来的代价可能是 $0,1,2$，所以我们采用一个费用流的模型。

安歇保证流量守恒的边费用都是 $0$，它们只用来保障流量守恒的限制。至于代价，我们考虑在原图上的连边进行更改。

我们让流量作为增加，所以减少就需要回退流量，建边跑费用流即可。

#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 210
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,m,c,f;

struct edge{
    int to,next,f,v;
    inline void Init(int to_,int ne_,int f_,int v_){
        to=to_;next=ne_;f=f_;v=v_;
    }
}li[N*10];
int head[N],tail=1,va[N],ans;

inline void Add(int from,int to,int f,int v){
    // printf("from=%d to=%d w=%d c=%d\n",from,to,f,v);
    li[++tail].Init(to,head[from],f,v);head[from]=tail;swap(from,to);
    li[++tail].Init(to,head[from],0,-v);head[from]=tail;
}

queue<int> q;
int d[N],now[N],s,t,Ans;
bool vis[N];

inline bool spfa(int s){
    while(q.size()) q.pop();
    bool op=0;
    mset(d,INF);mset(vis,0);d[s]=0;q.push(s);vis[s]=1;now[s]=head[s];
    while(q.size()){
        int top=q.front();q.pop();vis[top]=0;
        Next(top){
            int to=li[x].to,f=li[x].f,v=li[x].v;if(!f||d[to]<=d[top]+v)continue;
            d[to]=d[top]+v;if(!vis[to]) vis[to]=1,q.push(to);now[to]=head[to];
        }
    }
    if(d[t]>=INF) return 0;else return 1;
}
inline int dinic(int k,int flow){
    if(k==t) return flow;int rest=flow,x;vis[k]=1;
    for(x=now[k];x&&rest;x=li[x].next){
        int to=li[x].to,f=li[x].f,v=li[x].v;
        if(!f||d[to]!=d[k]+v||(vis[to]&&to!=t)) continue;int val=dinic(to,min(rest,f));
        if(!val) d[to]=INF;li[x].f-=val;li[x^1].f+=val;rest-=val;Ans+=val*v;
    }
    now[k]=x;
    return flow-rest;
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);
    rep(i,1,m){
        int u,v,c,f;read(u);read(v);read(c);read(f);
        if(c<=f){
            Ans+=f-c;
            Add(u,v,INF,2);Add(v,u,f-c,0);Add(v,u,c,1);
        }
        else{
            Add(u,v,c-f,1);Add(v,u,f,1);Add(u,v,INF,2);
        }
        va[u]-=f;va[v]+=f;
    }
    Add(n,1,INF,0);
    Add(1,n,INF,0); 
    // puts("here");
    s=++n;t=++n;
    rep(i,1,n-2){
        // printf("i=%d\n",i);
        if(va[i]<=0) Add(i,t,-va[i],0);
        else Add(s,i,va[i],0);
    }
    // printf("Ans=%d\n",Ans);
    while(spfa(s)) ans+=dinic(s,INF);
    // printf("ans=%d\n",ans);
    printf("%d\n",Ans);
    return 0;
}

T3

OJ 上的第 $16$ 个点似乎有点问题，问了问出题人，好像确实锅了。调了一下午终于在 cf 上过了。

我们考虑最小化两点间只有一条路径的点对数。设 $f_x$ 表示一个端点在 $x$ 子树外，一个端点在 $x$ 子树内，子树内的代价。简单树形 DP 就可以。考虑两个点对是祖先子孙关系，这种直接用 $f$ 数组来简单统计就可以。如果两个点在 $lca$ 处相遇，那么假设 $lca$ 一个儿子为 $a$，另一个为 $b$，且都在这条路径上，那么答案应该为：$f_a+f_b+G(n-siz_a-siz_b)$，其中 $G(x)=\frac{x(x-1)}{2}$，拆开这个式子发现可以斜率优化，维护凸包即可。

复杂度 $O(n\log n)$。

注：一定要检查斜率优化的横纵坐标是否写对，横坐标不一定是下标。

#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 700010
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=1e18;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

struct Point{
    int x,y;
    inline Point(){}
    inline Point(int x,int y) : x(x),y(y) {}
    inline Point operator - (const Point &b)const{return Point(x-b.x,y-b.y);}
    inline int operator ^ (const Point &b)const{return x*b.y-b.x*y;}
};

int n,f[N],siz[N],Ans=INF;
vi e[N],v;

inline int G(int n){return n*(n-1)/2;}
inline void dfs(int k,int fa){
    siz[k]=1;bool op=1;
    for(int to:e[k]) if(to!=fa){
        dfs(to,k);siz[k]+=siz[to];op=0;
    }
    if(op) return;
    f[k]=G(siz[k]);
    for(int to:e[k]) if(to!=fa){
        cmin(f[k],f[to]+G(siz[k]-siz[to]));
    }
}
inline void dfs2(int k,int fa){
    // printf("f[%lld]=%lld\n",k,f[k]);
    cmin(Ans,f[k]+G(n-siz[k]));
    for(int to:e[k]) if(to!=fa) dfs2(to,k);
}
inline bool cmp(int a,int b){return siz[a]>siz[b];}
inline int F(int x){return x*(x+1)/2-n*x;}
inline int B(int x){return f[x]+F(siz[x]);}
inline Point Po(int x){return Point(siz[x],B(x));}
int q[N],l,r;
inline void Dfs(int k,int fa){
    v.clear();
    for(int to:e[k]) if(to!=fa) v.pb(to);sort(v.begin(),v.end(),cmp);

    l=r=0;
    rep(i,0,(int)v.size()-1){
        // if(k==1) printf("l=%lld r=%lld\n",l,r);
        // if(k==1){rep(i,l+1,r) printf("%lld %lld,",Po(q[i]).x,Po(q[i]).y);puts("");}
        while(l<r-1&&((Po(q[l+2])-Po(q[l+1]))^Point(1,-siz[v[i]]))>=0){
            l++;
        }
        if(l<r){
            int a=v[i],b=q[l+1];
            // int a=7,b=4;
            // if(k==1) printf("a=%lld b=%lld B(a)=%lld B(b)=%lld\n",a,b,B(a),B(b));
            cmin(Ans,B(b)+siz[a]*siz[b]+B(a)+G(n));
        }
        while(l<r-1&&((Po(v[i])-Po(q[r]))^(Po(q[r-1])-Po(q[r])))<=0) r--;
        q[++r]=v[i];
    } 
    l=r=0;
    dec(i,0,(int)v.size()-1){
        while(l<r-1&&((Po(q[l+2])-Po(q[l+1]))^Point(1,-siz[v[i]]))<=0) l++;
        if(l<r){
            int a=v[i],b=q[l+1];
            cmin(Ans,B(b)+siz[a]*siz[b]+B(a)+G(n));
        }
        while(l<r-1&&((Po(v[i])-Po(q[r]))^(Po(q[r-1])-Po(q[r])))>=0) r--;
        q[++r]=v[i];
    }
    for(int to:e[k]) if(to!=fa) Dfs(to,k);
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);rep(i,1,n-1){
        int u,v;read(u);read(v);
        e[u].pb(v);e[v].pb(u);
    }
    int rt=-1;
    rt=1;
    dfs(rt,0);dfs2(rt,0);
    Dfs(rt,0);
    printf("%lld",n*(n-1)-Ans);
    return 0;
}