首页 > 其他分享 >2022 省队二轮集训培训日记-Day7

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

时间：2023-07-13 21:12:16浏览次数：43  
标签：typedef int Day7 long li 2022 inline 省队 define

模拟赛

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

标签：typedef,int,Day7,long,li,2022,inline,省队,define
From： https://www.cnblogs.com/HeNuclearReactor/p/17552180.html

相关文章

  • 2022 省队二轮集训培训日记-Day5
    模拟赛T1非常简单的构造，但是我忘了判断$m=2$和对只有一个点特判的输出错误，导致挂成$20$。具体思路，考虑欧拉路径只能有两个奇点，但是每条边上中间的都是奇点，所以我们需要删掉边缘的一些边，直到剩下两个奇点，然后对于$n,m$都是偶数，或者一个偶数一个奇数，或者两个都是奇数来分别......
  • 2022 省队二轮集训培训日记-Day4
    模拟赛T1首先是曼哈顿距离到切比雪夫距离的转化，到原点曼哈顿距离为定值$a$的点组成的图形为一个斜正方形，且原点到顶点的距离为$a$，正方形边长为$\sqrt{2}a$，而到原点切比雪夫距离为$a$的点组成的图形为正正方形，且边长为$2a$，那么我们可以通过把平面坐标系旋转$45$度，并把......
  • 2022 省队二轮集训培训日记 Day1
    模拟赛这里的题解在出题人的基础上进行补充。T1原题链接首先忽略所有全开的子树（在这样的子树内我们不应该选择任何路径），选一个关的点作为根设$f_{u,0/1,0/1/2}$表示满足条件$u$最后是关/开的，子树内其它点最后都是开的子树内有0/1/2个路径端点，其它端点为$u$的最小......
  • 神策数据荣获亚马逊云科技“2022 年度独立软件开发（ISV）合作伙伴”称号
    近日，以“共见·价值成就”为主题的亚马逊云科技中国合作伙伴峰会成功举办。神策数据荣获亚马逊云科技“2022年度独立软件开发（ISV）合作伙伴”称号！“2022年度独立软件开发（ISV）合作伙伴”是亚马逊云科技与神策数据合作共赢的标志，它见证了双方依托亚马逊云科技ISV全成长路径，从能力构......
  • 2022ICPC杭州站 A （裴蜀 + 扩欧）
    题目链接：A题意：给定一个序列\(a\)，让序列加上一个等差序列，求出总和%$m$的最小值以及等差序列的\(s\)和公差\(d\)。思路：定义\(a\)序列总和为sum。则求解的答案为\((sum+n∗s+n∗(n+1)2∗d)\)%m的最小值。根据裴蜀定理得到原式等于\(sum+x∗gcd(n,n∗(n+1)/2)+y......
  • 【专题】2022年中国跨境电商行业研究报告PDF合集分享（附原数据表）
    报告链接：http://tecdat.cn/?p=32044近年来，我国的跨境电子商务发展迅速，在过去五年中，其贸易额增长率达到了16.2%，已经成为稳定对外贸易的一支重要力量（查看文末了解报告PDF版本免费获取方式）。一方面，随着跨境电子商务的发展，跨境电子商务的监管政策得到了进一步的改善，跨境电子商务的规......
  • P8339 [AHOI2022] 钥匙 思考--zhengjun
    很容易考虑到计算贡献。该问题的关键在于——如何使得钥匙和宝箱的对应关系不算重Warning：有这样的二元对应关系，可以考虑一下转化为括号序列！转化为括号序列之后，发现路径上括号串的对应关系能够预处理出来。套个虚树和扫描线，就做完了。代码#include<bits/stdc++.h>using......
  • 助教工作总结（2022下路由交换技术上）
    一、助教工作的具体职责和任务1.线上线下给同学解答问题2.给老师布置的作业做一份尽可能标准且好理解的答案文档给同学们参考由于我大一提前学完了这门课程，所以作为刚学完且同班的同学，我更能体会到入门路由交换技术的疑难点。由于这门课的实验作业比较多，为了让......
  • 你省（福建）省队集训 Day5 T3 乱搞分析
    简要题意有\(1\leT\le10^6\)次询问，每次询问正整数\(x,p\)，\(p\)为素数，令\(n=xp^2\)，问是否存在三个正整数\(a,b,c\)，满足\(ab+bc+ca=n\)。有的话给出构造，否则输出\(-1\)。solution打表注意到只有\(n=4,18\)是无解的。打表namespaceDB{ constintN=1e5; struc......
  • 2022-2023 XCPC生涯总结
    参加比赛总结ICPC2022网络预选第一场2022.9.17队名沿用了去年yezi他们队的队名，这场因为有六级所以只有我们队和james_zhou队打.Caed开场过了CDH，开始写A，我一直在想L，240分钟左右我们分别把A和L过了，一起想G，Caed神中神最后把G想出来了。赛后知道是校排75，大概稳前100了，考虑到应......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99