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

2022 省队二轮集训培训日记 Day1

时间:2023-07-13 21:11:34浏览次数:55  
标签:rt int rep mid Day1 se 2022 inline 省队

模拟赛

这里的题解在出题人的基础上进行补充。

T1

原题链接

首先忽略所有全开的子树(在这样的子树内我们不应该选择任何路径),选一个关的点作为根

设 $f_{u,0/1,0/1/2}$ 表示满足条件

  • $u$ 最后是关/开的,子树内其它点最后都是开的
  • 子树内有 0/1/2 个路径端点,其它端点为 $u$

的最小路径长度

设加入 $u$ 的前若干个儿子后的结果为 $tmp_{0/1,0/1/2}$,需要加入儿子 $v$,转移的规则为:

  • 关于端点个数这一维是个背包
  • 路径拼接时,可能会多走一次某个点。具体地,当 $v$ 子树内的端点数为 $0/1/2$ 时,分别会多走 $u$,$\emptyset$,$v$
  • 在考虑上一条多走的情况下,如果 $v$ 最后被关闭了,那么还需要在中间走一个 $u-v$ 补一下。

考场上,除了看出来是个 DP,其它都没有看出来。

  • 注意树上路径 dp 可以采用记录端点个数。但是要小心处理单个点的情况。
  • 注意如果方便的话优先处理掉没有用的部分,因为它们可能对答案造成干扰。
  • 注意 dp 初值取 $\min$ 或 $\max$ 的时候考虑 $\inf$ 和 $-\inf$
  • 转移要注意状态的严谨性,以及举几个例子来验证。
#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 500010
#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,f[N][2][3];
char s[N];
vi e[N];
bool vis[N];

inline void pre(int k,int fa){
    vis[k]=s[k]-'0';
    for(int to:e[k]) if(to!=fa){
        pre(to,k);vis[k]&=vis[to];
    }
}
inline void dfs(int u,int fa){
    int tmp[2][3];mset(tmp,0);
    int op=(s[u]=='1');rep(i,0,2) f[u][op^1][i]=tmp[op^1][i]=1;
    rep(i,0,2) f[u][op][i]=tmp[op][i]=INF;
    for(int to:e[u]) if(to!=fa&&!vis[to]){
        dfs(to,u);mset(f[u],INF);
        rep(i,0,1)rep(j,0,2)rep(k,0,1)rep(o,0,j){
            cmin(f[u][i][j],f[to][k][o]+tmp[i^k^(o&1)][j-o]+2*(k^1^(o==2))+((o&1)^1));
        }
        rep(i,0,1)rep(j,0,2)tmp[i][j]=f[u][i][j];
    }
    // rep(i,0,1)rep(j,0,2)printf("f[%d][%d][%d]=%d\n",u,i,j,f[u][i][j]);
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);scanf("%s",s+1);
    rep(i,1,n-1){
        int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
    }
    int rt=-1;rep(i,1,n) if(s[i]=='0') rt=i;pre(rt,0);dfs(rt,0);
    printf("%lld\n",min(f[rt][1][2],min(f[rt][1][0],f[rt][1][1])));
    return 0;
}

T2

一段区间的权值为 $len\times \min{a}\times \min{b}$,求最大的权值

分治,计算出所有三元组(到中点的距离,到中点的 $\min{a}$,到中点的 $\min{b}$),考虑合并。首先考虑两个 $\min$ 都在同一边取到的情况,此时另一边只需要让长度尽量大即可,容易单调扫描出另一边的合法区间。不在同一边的情况,同样可以单调扫描出另一边的合法区间,不妨设 $\min{a}$ 在左边取到,那么两个三元组会产生贡献 $(L+R)\cdot ma_l\cdot mb_r$,其中 $(L+R)\cdot mb_r$ 相当于一次函数最值,可以通过线段树维护凸包的方式快速计算。直接计算是三个 $\log$ ,但是注意 $L$ 是单调的,所以线段树上每个凸包的最优解都是单调移动的,这样就可以去掉一个 $\log$

如何用线段树维护凸包?只需要在每个线段树的节点开一个栈,保存这个线段树节点所代表的区间中的所有点的凸包即可。然后本来是要在上面二分的,但是因为具有单调性,可以用指针扫。

如何想到分治,只需要考虑答案是 $len\times ma\times mb$,而最值和区间都是分治的常见套路。

原题链接

struct Point{
    ll x,y;
    inline Point(){}
    inline Point(ll x,ll y) : x(x),y(y) {}
    inline ll operator ^ (const Point &b)const{return x*b.y-y*b.x;}
    inline Point operator - (const Point &b)const{return Point(x-b.x,y-b.y);}
    inline bool operator < (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}c[N];

struct Node{
    vc<Point> v,sta;
    int id,top;
    inline void GetSta(){
        top=0;
        for(Point x:v){
            while(top&&((x-sta[top])^(sta[top-1]-sta[top]))>=0) top--;
            sta[++top]=x;
        }
        id=top;
    }
    inline int Ask(int k){
        Point now(1,k);
        while(id&&((sta[id]-sta[id-1])^(now))>=0) id--;
        return sta[id].y-sta[id].x*k;
    }
}p[N<<2];

#define ls(k) k<<1
#define rs(k) k<<1|1
struct SegmentTree{
    inline void Build(int k,int l,int r){
        p[k].v.clear();
        p[k].v.resize(r-l+1);p[k].sta.resize(r-l+2);int mid=(l+r)>>1;
        if(l==r){p[k].v[0]=c[l];p[k].GetSta();return;}
        // exit(0);
        Build(ls(k),l,mid);Build(rs(k),mid+1,r);
        merge(p[ls(k)].v.begin(),p[ls(k)].v.end(),p[rs(k)].v.begin(),p[rs(k)].v.end(),p[k].v.begin());
        // exit(0);
        p[k].GetSta();
    }
    inline ll Ask(int k,int l,int r,int z,int y,int x){
        if(z<=l&&r<=y) return p[k].Ask(x);int mid=(l+r)>>1;
        ll ans=0;
        if(z<=mid) ans=max(ans,Ask(ls(k),l,mid,z,y,x));
        if(mid<y) ans=max(ans,Ask(rs(k),mid+1,r,z,y,x));return ans;
    }
}st;

int n,a[N],b[N],B[N];
ll Ans;

inline void Solve(int l,int r){
    int mid=(l+r)>>1;
    int ma=INF,mb=INF,R=mid-1;
    dec(i,l,mid){
        cmin(ma,a[i]);cmin(mb,b[i]);
        while(R+1<=r&&a[R+1]>=ma&&b[R+1]>=mb) R++;
        cmax(Ans,ma*mb*(R-i+1));
    }
    B[mid]=b[mid];rep(i,mid+1,r) B[i]=min(B[i-1],b[i]);
    rep(i,mid,r) c[i-mid+1].x=-B[i],c[i-mid+1].y=B[i]*(i-mid);
    // exit(0);
    st.Build(1,1,r-mid+1);
    // exit(0);
    R=mid-1;ma=INF;mb=INF;
    int L=mid;
    // exit(0);
    dec(i,l,mid){
        cmin(ma,a[i]);cmin(mb,b[i]);
        while(L<=r&&b[L]>mb) L++;if(L>r) break;
        while(R+1<=r&&a[R+1]>=ma) R++;
        if(L>R) continue;
        Ans=max(Ans,ma*st.Ask(1,1,r-mid+1,L-mid+1,R-mid+1,mid-i+1));
    }
}

inline void Divi(int l,int r){
    if(l>r) return;int mid=(l+r)>>1;
    Solve(l,r);reverse(a+l,a+r+1);reverse(b+l,b+r+1);
    Solve(l,r);reverse(a+l,a+r+1);reverse(b+l,b+r+1);
    Divi(l,mid-1);Divi(mid+1,r);
}

signed main(){
    // freopen("my.in","r",stdin);
    read(n);rep(i,1,n) read(a[i]),read(b[i]);
    Divi(1,n);
    printf("%lld\n",Ans);
    return 0;
}

T3

原题链接

考虑大部分点的 lca 都是在分叉点上,除非在一条链上,我们考虑只保留分叉点和其儿子之间的连边,其余都缩成一个点,首先点数是 $O(n)$ 的,而且我们只需要知道每个点缩点之后是哪个点,新树上两个点的 lca 是什么就可以了。

整个过程可以用可持久化线段树从下往上做。

int n,q,t,a[N],b[N],mod,c[N<<2];
struct Node{
    int siz,val,ls,rs;
    inline Node(){}
    inline Node(int siz,int val) : siz(siz),val(val) {}
}p[N*40];
int rt[N],fa[N<<2][21],dep[N<<2],ans;
vi e[N<<2];
#define ls(k) p[k].ls
#define rs(k) p[k].rs
struct SegmentTree{
    int tot;
    inline SegmentTree(){tot=0;}
    inline void PushUp(int k){p[k].siz=p[ls(k)].siz+p[rs(k)].siz;}
    inline void Change(int &k,int last,int l,int r,int w,int x1,int x2){
        k=++tot;p[k]=p[last];int mid=(l+r)>>1;
        if(l==r){p[k].siz=x1;p[k].val=x2;return;}
        if(w<=mid) Change(ls(k),ls(last),l,mid,w,x1,x2);
        else Change(rs(k),rs(last),mid+1,r,w,x1,x2);PushUp(k);
    }
    inline P Ask(int k,int l,int r,int siz){
        if(l==r) return mp(l,p[k].val);int mid=(l+r)>>1;
        if(siz<=p[ls(k)].siz) return Ask(ls(k),l,mid,siz);
        else return Ask(rs(k),mid+1,r,siz-p[ls(k)].siz);
    }
    inline void Build(int &k,int l,int r){
        k=++tot;int mid=(l+r)>>1;if(l==r){p[k].siz=1;p[k].val=l;return;}
        Build(ls(k),l,mid);Build(rs(k),mid+1,r);PushUp(k);
    }
}st;

inline void dfs(int k,int fat){
    fa[k][0]=fat;rep(i,1,20) fa[k][i]=fa[fa[k][i-1]][i-1];dep[k]=dep[fat]+1;
    for(int to:e[k]) if(to!=fat) dfs(to,k);
}
inline int Lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    dec(i,0,20) if(dep[fa[a][i]]>=dep[b]) a=fa[a][i];if(a==b) return a;
    dec(i,0,20) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i];return fa[a][0];
}
inline int getid(int x){
    return lower_bound(b+1,b+n+2,x)-b;
}
inline int ID(int x){
    int id=lower_bound(b+1,b+n+2,x)-b-1;
    return x-(1+id)*id/2;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(q);read(t);mod=(n+1)*(n+2)/2;
    rep(i,1,n) read(a[i]);int tot=n+1;st.Build(rt[n+1],1,n+1);
    rep(i,1,n+1) b[i]=(1+i)*i/2;
    dec(i,1,n){
        // printf("ID(a[i])=%d\n",ID(a[i]));
        P now=st.Ask(rt[i+1],1,n+1,ID(a[i]));
        P now2=st.Ask(rt[i+1],1,n+1,ID(a[i])+1);
        // printf("now.fi=%d now.se=%d now2.fi=%d now2.se=%d\n",now.fi,now.se,now2.fi,now2.se);
        st.Change(rt[i],rt[i+1],1,n+1,now2.fi,0,-1);
        ++tot;st.Change(rt[i],rt[i],1,n+1,now.fi,1,tot);
        e[tot].pb(now.se);e[tot].pb(now2.se);
        // printf("Add %lld %lld\n",tot,now.se);printf("Add %lld %lld\n",tot,now2.se);
    }
    dfs(tot,0);
    rep(i,1,n) c[st.Ask(rt[getid(a[i])],1,n+1,ID(a[i])).se]=a[i];
    rep(i,1,q){
        int x,y;read(x);read(y);
        x=(x-1+t*ans)%mod+1;y=(y-1+t*ans)%mod+1;
        // printf("getid(x)=%d ID(x)=%d x=%d\n",getid(x),ID(x),x);
        P now=st.Ask(rt[getid(x)],1,n+1,ID(x));
        // printf("getid(y)=%d ID(y)=%d y=%d\n",getid(y),ID(y),y);
        P now2=st.Ask(rt[getid(y)],1,n+1,ID(y));
        // printf("now.se=%d now2.se=%d\n",now.se,now2.se);
        int l=Lca(now.se,now2.se);
        if(now.se==now2.se){
            if(x<y) swap(x,y);printf("%lld\n",(ans=y));
        }
        else if(l==now.se||l==now2.se){
            if(l==now.se) printf("%lld\n",(ans=x));
            else printf("%lld\n",(ans=y));
        }
        else{
            // puts("here");printf("l=%d\n",l);
            printf("%lld\n",(ans=c[l]));
        }
    }
    return 0;
}

标签:rt,int,rep,mid,Day1,se,2022,inline,省队
From: https://www.cnblogs.com/HeNuclearReactor/p/17552176.html

相关文章

  • day118 - 基于xml管理bean的入门案例
    基于xml管理bean入门案例导入依赖<dependencies><!--基于Maven依赖传递性,导入spring-context依赖即可导入当前所需所有jar包--><dependency><groupId>org.springframework</groupId><artifactId>spring-context</artifactId>......
  • Day1
    Markdown学习标题二级标题三级标题#+空格+标题+空格(标题层级与#数相关)字体Hello,WorldHello,World!Hello,World!Hello,World!引用Day1分割线三个-或者*图片超链接点击跳转列表ACABC表格名字性别生日张三男1997.1.1代码Wo......
  • 神策数据荣获亚马逊云科技“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......
  • nestjs入门学习 | day1
    nestjs入门学习|day1day1:为什么要用nestjs,和egg区别对比nest项目初始化,了解目录结构nestcli命令了解nest基础知识点学习:控制器、服务、模块为什么要用nestjs,和egg区别对比官网介绍Nest提供了一种开箱即用的应用程序架构,允许开发人员和团队创建高度可测试、可扩展......
  • 助教工作总结(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了,考虑到应......