• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

P6157有趣的游戏

分析

还是一样,看一看题目要求。

每一次系统会给出一条链,小A可以从这条链上找出两个点权不同的点x,y,他的得分是\(w_x mod w_y\)。然后小B会从整棵树中选取两个小 A 没有选过的点,计分方式同小答。

非常容易推理出,对于A而言,其选出的最大答案是选出一条链的最大值与次大值,则对A而言最优解就是次大值

则对于B而言,B需要从被A扣出两个点的树中,选出最大值与次大值,对B来说最优的就是这个次大值

这个题最难的对我而言其实是,怎么从把A选的两个点抠出来了

答案非常简单,用多重集就可以解决了。

直接从多重集中将A选中的删掉,再从多重集中找到最大值和次大值即可。

细节在代码中有注释。直接看。

Ac_code

#includebits/stdc .h

使用命名空间标准

const int N=1e5 10,M=N * 2;

结构节点

{

int l,r,fi,se;

} tr[N2];

int h[N],e[M],ne[M],w[N],idx

int sz[N],fa[N],son[N],dep[N];

int top[N],id[N],nw[N],ts;

多色调s;

int n,q;

void add(int a,int b)

{

e[idx]=b,ne[idx]=h[a],h[a]=idx;

}

void dfs1(int u,int pa,int depth)

{

sz=1,dep=深度;

for(int I=h;~我;我=ne)

{

int j=e

如果(j==pa)继续;

fa[j]=u;

dfs1(j,u,深度1);

SZ=SZ[j];

if(SZ[j]SZ[son])son=j;

}

}

void dfs2(int u,int tp)

{

top=tp,id=ts,NW[ts]=w

如果(!子)回归;

dfs2(son,TP);

for(int I=h;~我;我=ne)

{

int j=e

if(j==fa||j==son)继续;

dfs2(j,j);

}

}

无效推送(节点u,节点l、节点r)

{

u.fi=max(l.fi,r . fi);

u.se=max(l.fi==u.fi?l.se:l.fi,r.fi==u.fi?r . se : r . fi);

}

无效上推(整数)

{

push(tr,tr[u1],tr[u1 | 1]);

}

void build(int u,int l,int r)

{

如果(l==r)

{

tr={l,l,nw[l],-1 };//因为维护的是严格次小值,因此,当区间长为一时,记得初始化次小值为-1,华盛顿死我了

返回;

}

tr={l,r };

int mid=l r 1;

build(u1,l,mid),build(u1|1,mid 1,r);

俯卧撑(u);

}

void modify(int u,int x,int k)

{

if(tr).l==tr.r)

{

trfi=k;////因为维护的是严格次小值,因此,当区间长为一时,记得初始化次小值为-1,华盛顿死我了

//因为这个原因,所有单点修的时候,就不要改次小值了,还是-1

返回;

}

int mid=tr.l tr.R1;

if(x=中间值)修改(u1,x,k);

else modify(u1|1,x,k);

俯卧撑(u);

}

节点查询(int u,int l,int r)

{

if(l=tr).ltr.r=r)return tr

int mid=tr.l tr.R1;

节点res={0,0,-1,-1 };

if(lmid)返回查询(u1|1,l,r);

else if(r=mid)返回查询(u1,l,r);

其他

{

auto left=query(u1,l,r),right=query(u1|1,l,r);

推(res,左,右);

返回表示留数

}

}

int main()

{

scanf('%d ',n);

memset(h,-1,sizeof h);

for(int I=0;in-1;我)

{

int u,v;

scanf('%d%d ',u,v);

add(u,v),add(v,u);

}

for(int I=1;I=n;我)

{

int x;scanf('%d ',x);

w=x;插入(x);

}

scanf('%d ',q);

dfs1(1,-1,1);

dfs2(1,1);

build(1,1,n);

while(q -)

{

int op,x,y;scanf('%d%d%d ',op,x,y);

如果(!op)

{

s。erase(s . lower _ bound(w[x]);//嗷,还有,单点修改后,记得将s中的对应删掉

//同时,给向我一样语法不好的同学,提一句,多重集里不要之间删数值,会把所有对应值删掉

//因此,可以先下限找到,再删找到的对应迭代器的位置。

w[x]=y;

s。insert(w[x]);//也不要忘记再加上

modify(1,id[x],y);

}

其他

{

节点res={0,0,-1,-1 };

while(top[x]!=top[y])

{

if(dep[top[x]]dep[top[y]])swap(x,y);

push(res,res,query(1,id[top[x]],id[x]));

x=fa[top[x]];

}

if(dep[x]dep[y]) swap(x,y);

push(res,res,query(1,id[y],id[x]));

if(RES . se==-1)puts('-1 ');

其他

{

s.erase(s.lower_bound(res.fi))、s . erase(s . lower _ bound(RES . se));

printf('%d %d\n ',res.se,*(-s . lower _ bound(*-s . end())));//这里也是,找到最大值后,其前边的值不一定是次大值,直接二分查找

s.insert(res.fi),s . insert(RES . se);

}

}

}

返回0;

}

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now