正文 

当前位置： 首页 > 代码 > java教程

[国家集训队]旅游(代码片段)

zh-comld zh-comld     2022-12-30     537

关键词：

Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N ? 1 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

Solution

调了一下午+一晚上，唉，代码能力实在不行。

一眼链剖维护。

线段树记一个最大值，最小值，区间和。

犯的错：while写成if，单点修改时要把所有数据清空，标记下传时tag^=1，每次修改都要pushup。

Code

#include<iostream>
#include<cstdio>
#define N 200002
#define inf 0x7f7f7f7f
using namespace std;
int size[N],head[N],son[N],tot,topo,top[N],fa[N],num[N],dfn[N],deep[N],n,ji[N],m,jj[N];
char s[10];
int tr[N<<2],ma[N<<2],mi[N<<2];
bool la[N<<2]; 
struct ff
    int n,to,l,tag;
e[N<<1];
inline void add(int u,int v,int l,int tag)
    e[++tot].n=head[u];
    e[tot].to=v;
    head[u]=tot;e[tot].l=l;e[tot].tag=tag;

void dfs(int u,int f)
    size[u]=1;
    for(int i=head[u];i;i=e[i].n)if(e[i].to!=f)
        int v=e[i].to;
        deep[v]=deep[u]+1;fa[v]=u;
        dfs(v,u);
        size[u]+=size[v];
        jj[e[i].tag]=v;
        num[v]=e[i].l;
        if(size[v]>size[son[u]])son[u]=v;
    

void dfs2(int u)
    dfn[u]=++topo; 
    ji[topo]=u;
    if(!top[u])top[u]=u;
    if(son[u])top[son[u]]=top[u],dfs2(son[u]);
    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa[u]&&e[i].to!=son[u])dfs2(e[i].to);

inline void pushdown(int cnt)
    tr[cnt<<1]*=-1;tr[cnt<<1|1]*=-1;
    ma[cnt<<1]*=-1;ma[cnt<<1|1]*=-1;
    mi[cnt<<1]*=-1;mi[cnt<<1|1]*=-1; 
    swap(ma[cnt<<1],mi[cnt<<1]);swap(ma[cnt<<1|1],mi[cnt<<1|1]);
    la[cnt]^=1;la[cnt<<1]^=1;la[cnt<<1|1]^=1;  
 
void update2(int cnt,int l,int r,int L,int R)
    if(l>=L&&r<=R)
        tr[cnt]*=-1;mi[cnt]*=-1;ma[cnt]*=-1;la[cnt]^=1;
        swap(mi[cnt],ma[cnt]);
        return;
    
    int mid=(l+r)>>1;
    if(la[cnt])pushdown(cnt);
    if(mid>=L)update2(cnt<<1,l,mid,L,R);
    if(mid<R) update2(cnt<<1|1,mid+1,r,L,R);
    tr[cnt]=tr[cnt<<1]+tr[cnt<<1|1];
    ma[cnt]=max(ma[cnt<<1],ma[cnt<<1|1]);
    mi[cnt]=min(mi[cnt<<1],mi[cnt<<1|1]); 

int query(int cnt,int l,int r,int L,int R,int tag)//0求和1最大值2最小值 
    if(l>=L&&r<=R)
      if(!tag)return tr[cnt];
      if(tag==1)return ma[cnt];
      return mi[cnt];
   
    int mid=(l+r)>>1;
    if(la[cnt])pushdown(cnt);
    int ans=0,ans1=-inf,ans2=inf;
    if(mid>=L)
        int bi=query(cnt<<1,l,mid,L,R,tag);
        if(tag==0)ans+=bi;
        else if(tag==1)ans1=max(ans1,bi);
        else ans2=min(ans2,bi);
    
    if(mid<R)
        int bi=query(cnt<<1|1,mid+1,r,L,R,tag);
        if(!tag)ans+=bi;
        else if(tag==1)ans1=max(ans1,bi);
        else ans2=min(ans2,bi);
    
//    tr[cnt]=tr[cnt<<1]+tr[cnt<<1|1];
//    ma[cnt]=max(ma[cnt<<1],ma[cnt<<1|1]);
//    mi[cnt]=min(mi[cnt<<1],mi[cnt<<1|1]);
    if(!tag)return ans;
    else if(tag==1)return ans1;
    else return ans2;

int que(int x,int y,int tag)
    int ans=0,ans1=-inf,ans2=inf;
    while(top[x]!=top[y])
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        if(!tag)ans+=query(1,2,topo,dfn[top[x]],dfn[x],tag);
        else if(tag==1)ans1=max(ans1,query(1,2,topo,dfn[top[x]],dfn[x],tag));
        else ans2=min(ans2,query(1,2,topo,dfn[top[x]],dfn[x],tag));
        x=fa[top[x]];
    
    if(dfn[x]>dfn[y])swap(x,y);
    if(x!=y)
    if(!tag)ans+=query(1,2,topo,dfn[x]+1,dfn[y],tag);
        else if(tag==1)ans1=max(ans1,query(1,2,topo,dfn[x]+1,dfn[y],tag));
        else ans2=min(ans2,query(1,2,topo,dfn[x]+1,dfn[y],tag));
      
    if(!tag)return ans;
    else if(tag==1)return ans1;
    else return ans2;

void update(int cnt,int l,int r,int x,int y)
    if(l==r)
        tr[cnt]=mi[cnt]=ma[cnt]=y;la[cnt]=0;
        return;
    
    int mid=(l+r)>>1;
    if(la[cnt])pushdown(cnt);
    if(mid>=x)update(cnt<<1,l,mid,x,y);
    else update(cnt<<1|1,mid+1,r,x,y);
    tr[cnt]=tr[cnt<<1]+tr[cnt<<1|1];
    ma[cnt]=max(ma[cnt<<1],ma[cnt<<1|1]);
    mi[cnt]=min(mi[cnt<<1],mi[cnt<<1|1]); 

void work(int u,int v)
    while(top[u]!=top[v])
        if(deep[top[u]]<deep[top[v]])swap(u,v);
        update2(1,2,topo,dfn[top[u]],dfn[u]);
        u=fa[top[u]]; 
    
    if(dfn[u]>dfn[v])swap(u,v);
    if(u!=v)update2(1,2,topo,dfn[u]+1,dfn[v]);

void build(int cnt,int l,int r)
    if(l==r)
        tr[cnt]=ma[cnt]=mi[cnt]=num[ji[l]];
        return;
    
    int mid=(l+r)>>1;
    build(cnt<<1,l,mid);build(cnt<<1|1,mid+1,r);
    tr[cnt]=tr[cnt<<1]+tr[cnt<<1|1];
    ma[cnt]=max(ma[cnt<<1],ma[cnt<<1|1]);
    mi[cnt]=min(mi[cnt<<1],mi[cnt<<1|1]);

int main()
//    freopen("pus.in","r",stdin); 
//    freopen("233.out","w",stdout);
    scanf("%d",&n);int u,v,w;
    for(int i=1;i<n;++i)
      scanf("%d%d%d",&u,&v,&w);
      u++;v++;add(u,v,w,i),add(v,u,w,i);
   
    dfs(1,0);dfs2(1);
    build(1,2,topo);
    scanf("%d",&m); 
    while(m--)
        cin>>s;scanf("%d%d",&u,&v);++u,++v;
        if(s[0]==‘C‘)--u;--v;update(1,2,topo,dfn[jj[u]],v);
        else if(s[0]==‘N‘)work(u,v);
        else if(s[0]==‘S‘)printf("%d
",que(u,v,0));
        else if(s[0]==‘M‘&&s[1]==‘A‘)printf("%d
",que(u,v,1));
        else printf("%d
",que(u,v,2));
    
    return 0;

 

p1505[国家集训队]旅游(树剖板题)(代码片段)

P1505[国家集训队]旅游(树剖板题)1.边权转点权。dfs时边下放到点就行了，因为每个点的父边唯一。2.然后就是裸的线段树了，区间翻转，区间最值，单点修改，没了。3.码农题好想吐槽啊。//Problem:P1505[国家集训... 查看详情

p1505[国家集训队]旅游(代码片段)

DescriptionRay乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，T城中只有N?... 查看详情

[国家集训队]旅游(代码片段)

嘟嘟嘟 这其实就是一道树剖板子题，只不过就是写的长了一点。还是叨叨几点吧：1.区间取相反数：开一个标记数组，每一次亦或1，然后对应的sum取相反数，Max,Min交换，并且取相反数。2.题目中给的是边权，但要转化成点权... 查看详情

luogup1505[国家集训队]旅游(树链剖分+线段树)(代码片段)

传送门 解题思路快被调死的码农题，，，其实就是一个边权下放到点权的线段树+树剖。 #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>usingnamespacestd;constintMAXN=1 查看详情

p1505[国家集训队]旅游树链剖分(代码片段)

题目描述Ray乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，T城中只有N... 查看详情

bzoj2157「国家集训队」旅游（树链剖分，线段树，边权转点权）bzoj计划(代码片段)

整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划题目链接https://hydro.ac/d/bzoj/p/2157是hydro的BZOJ修复工程！Problem给定一棵nnn个节点的树，边带权，编号0∼n... 查看详情

bzoj2157「国家集训队」旅游（树链剖分，线段树，边权转点权）bzoj计划(代码片段)

整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划题目链接https://hydro.ac/d/bzoj/p/2157是hydro的BZOJ修复工程！Problem给定一棵nnn个节点的树，边带权，编号0∼n... 查看详情

p1505[国家集训队]旅游(代码片段)

(color#0066ff题目描述)Ray乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，... 查看详情

[国家集训队2011]旅游(宋方睿)

1867.[国家集训队2011]旅游(宋方睿)★★★★  输入文件：nt2011_travel.in  输出文件：nt2011_travel.out   简单对比时间限制：1s  内存限制：512MB【试题来源】2011中国国家集训队命题答辩【问题描述】Ray乐... 查看详情

基于php的旅游网站的设计与实现论文(代码片段)

某某自助游网站的设计与实现摘要目前旅游业是国家的战略性支柱产业，是十分具有发展潜力的朝阳产业和绿色产业。呼和浩特是一个有不同民族“大杂居，小聚居”的地方，所以对于发展旅游业还是比较有优势的。... 查看详情

html马纳里旅游胜地(代码片段)

查看详情

html旅游新不伦瑞克省(代码片段)

查看详情

c_cpp旅游指南(代码片段)

查看详情

旅游网站页面(代码片段)

旅游网管理页面基于HTML<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>杨永峰的大型网站</title></head><body><!--采用table来完成布局--&g 查看详情

bzoj1393旅游航道(代码片段)

Description　　SGOI旅游局在SG-III星团开设了旅游业务，每天有数以万计的地球人来这里观光，包括联合国秘书长，各国总统和SGOI总局局长等。旅游线路四通八达，每天都有总躲得载客太空飞船在星团的星球之间来往穿梭，他们保... 查看详情

旅游规划(代码片段)

题意：给一棵树，输出树上所有最长路径包含的节点 树的直径的应用#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>#defineN200005#defineN2400 查看详情

p1137旅行计划(代码片段)

题目描述小明要去一个国家旅游。这个国家有N个城市，编号为1～N，并且有M条道路连接着，小明准备从其中一个城市出发，并只往东走到城市i停止。所以他就需要选择最先到达的城市，并制定一条路线以城市i为终点，使得线路... 查看详情

luogup1137旅行计划(代码片段)

题目描述小明要去一个国家旅游。这个国家有N个城市，编号为1至N，并且有M条道路连接着，小明准备从其中一个城市出发，并只往东走到城市i停止。所以他就需要选择最先到达的城市，并制定一条路线以城市i为终点，使得线路... 查看详情