《NOIP2019(提高组)正式赛.docx》由会员分享，可在线阅读，更多相关《NOIP2019(提高组)正式赛.docx（18页珍藏版）》请在课桌文档上搜索。
1、NOIP2019提高组正式赛dayl【题目背景】本题中合法括号串的定义如下：1 .()是合法括号串。2 .如果A是合法括号串，则（八）是合法括号串。3 .如果A,B是合法括号串，则AB是合法括号串。本题中于串与不同的子串的定义如下：1 .字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置，与终止位置厂来表示，记为S(,r)(lrS,ISI表示S的长度)。2 .S的两个子串视作不同当且仅当它们在S中的位置不同，即,不同或r不同。Description【题目描述】一个大小为n的树包含个结点和/1-1条边，每条边连接两个结点，且任意两个结点间有且仅有条简单路径互相可达。小Q是一个
2、充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为“的树，树上结点从编号，1号结点为树的根。除1号结点外，每个结点有一个父亲结点，u(2u/1)号结点的父亲为4(lLu)号结点小Q发现这个树的每个结点上修有一个括号，可能是或小Q定义Si为：将根结点到i号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。显然Si是个括号串，但不一定是合法括号串，因此现在小Q想对所有的/(ln)求出，舟中有多少个互不相同的子串是合法括号串。这个问题难倒了小Q,他只好向你求助。设Sj共有自个不同子串是合法括号串，你只需要告诉小Q所有iX将的异或和，即：(IXA)xor(26)xor(323)xorx
3、or(nXkn)Input从文件brackets.in中读入数据。第一行一个整数，表示树的大小。第二行一个长为的由(与T组成的括号串，第i个括号表示i号结点上的括号。第三行包含n-l个整数，第i(1iV)个整数表示i+1号结点的父亲编号工+10Output输出到文件brackets.out中。仅一行一个整数表示答案。SampleInputSampleOutputDataConstraint测试点编号n特殊性质128fi=i-l34200572000810无1114IO5fi=i-l15-16无17-205IO5参考答案#include#include#include#defineIint#de
4、fineIllonglong#defineF(i,a,b)for(Ii=a;i=b;i)#definemem(afb)memset(afb,sizeof(a)#defineN1000010usingnamespacestd;InrxftN*2fnxN*2flNfaNftot;IsN20ffN20fdN*2fbzN;Ilans,gN;charch;voidadd(Ix,Iy)t+tot=y;nxtot=lxJx=tot;voidrd(I&x)x=0;ch=getchar();while(ch,9)ch=getchar();while(ch=,08tch=,9,)x=x*10+ch-,0ch=ge
5、tchar();)voiddfs(Ix,Iy)mem(bzf0);Ii=l,j=l;dl=l;bzl=l;while(i=j)x=di+;for(Ik=lx;k;k=nxk)if(!bztk)bztk=l;d+j=tk;ftkO=x;stkO=ax;atk+=ax;)voiddg(IxfIy)mem(bzf0);Ihe=l,ta=l;d1=l;bzl=1;while(heax)z=fzi;)if(afz0=ax)g+=gfz-gffz00+1；)for(Ik=lx;k;k=nxk)if(!bztk)bztk=l;d+ta=tk;gtk+=gx;)Imain()freopen(ubrackets
6、.in,f,r,fstdin);freopen(,brackets.out,f,w,istdout);rd(n);F(irlfn)ch=getchar();while(ch!=,),84ch!=,(,)ch=getchar();if(ch=1(,)ai=l;elseai=-l;)F(i,2,n)rd(x);add(xri);add(irx);)dfs(lfO);F(j,F,19)F(iflfn)fij=ffij-lj-l;sij=min(sij-lfsfij-lj-l);)dg(lfO);F(i,l,n)ansA=(i*gi);printf(,%lldn,fans);returnO;)Code
7、2#include#include#include#defineIint#defineIllonglong#defineF(i,a,b)for(Ii=a;i=b;i)#definemem(arb)memset(afb,sizeof(a)#defineN1000010usingnamespacestd;InfxN*2fnxN*2JNraNfsNftotffNfpJaN;Ilans,gN;charch;voidadd(Ix,Iy)t+tot=y;nxtot=lxJx=tot;voidrd(I&x)x=0;ch=getchar();while(ch,9)ch=getchar();while(ch=,
8、084ch=,9,)x=x*10+ch-,0,jch=getchar();)voiddg(IxfIy)sx=ax+sy;gx+=gy;if(ax=l)fx=x;elseP=fy;if(P)gx+=gfap-gfafap+1;fx=ffap;)ansA=(x*gx);for(Ik=lx;k;k=nxk)f(tk!=y)dg(tkfx);)Imain()freopen(,brackets.in,r,fstdin);freopen(,brackets.out,f,w,fstdout);rd(n);F(irlfn)ch=getchar();while(ch!=)8ich!=,(,)ch=getchar
9、();ai=ch=,(,71:-1;)F(if2fn)rd(x);fai=x;add(xri);add(i,x);dg(lfO);printf(,%lldn,fans);return0;2019提高组正式赛day2树的重心（centroid）Description小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：1 .一个大小为的树由个结点与-1条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树：而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。2 .对于一个大小为的树与任意一个树中结点c,称C是
10、该树的重心当且仅当在树中删去C及与它关联的边后，分裂出的所有子树的大小均不超过玲（其中W是下取整函数）。对于包含至少一个结点的树，它的重心只可能有1或2个。课后老师给出了一个大小为的树S,树中结点从1编号。小简单的课后作业是求出S单独删去每条边后，分裂出的两个子树的重心编号和之和。即：Input从文件centroid.in中读入数据。本题输入包含多组测试数据。第一行一个整数T表示数据组数。接下来依次给出每组输入数据，对于每组数据：第一行一个整数表示树S的大小。接下来行，每行两个以空格分隔的整数%,片,表示树中的一条边（出,咽。Output输出到文件centroid.out中。共T行，每行一个整
11、数，第i行的整数表示：第i组数据给出的树单独删去每条边后，分裂出的两个子树的重心编号和之和。SampleInput1225312423524635778129131014113512361367SampleOutput132256DataConstraint【样例i解释】对于第一组数据:删去边(1,2), 删去边(2,3), 删去边(2,4), 删去边(3,5),1号点所在子树重心编号为1,2号点所在子树重心编号为2,3o2号点所在子树重心编号为2,3号点所在子树重心编号为3,5)o2号点所在子树重心编号为2,3,4号点所在子树重心编号为4)o3号点所在子树重心编号为2),5号点所在子树重心编
12、号为5o因此答案为l2+32+35+2+34+25=32oSolution测试点编号n=特殊性质1-27无3-51996819999-1149991A12-15262143B1699995无17-1819999519-20299995表中特殊性质一栏，两个变量的含义为存在一个1的排列A(ln),使得:z树的形态是一条链。即Vlivzn存在一条边(R,pi+)8：树的形态是一个完美二叉树。即Vl/吟，存在两条边(php2i)与(A,P2,+)o对于所有测试点：1T5,1%,y,zu保证给出的图是一个树。参考答案#include#include#include#include#include/#i
13、nclude/#include/#include/#include/#include/#include#defineopenjn(x)freopen(*x.in,f,r,rstdin)#defineopen_out(x)freopen(#x,.out,f,wfstdout)#defineopen_(x)freopen(x,.in,w,fstdout)#defineopen(x)openjn(x);open_out(x)#definemes(xfy)memset(xfy,sizeof(x)#definemec(x,y)memcpy(xfyfsizeof(x)#definefo(xfy,z)for
14、(x)=(y);(x)=(z);(x)-)usingnamespacestd;typedeflonglongII;typedefdoubledb;typedefunsignedlonglongull;constintN=300010;constintS=19;/inlineintRandom(inta,intb)returnrand()%(b-a+1)+a;templateinlineTread(T&x)intf=1;charch=getchar();x=0;while(ch9,)if(ch=,)f=-1;ch=getchar();)while(ch=0,&chsizlinkx0)linkx0
15、=s;sizx+=sizs;)inlinevoidGetAns(intx)registerintSIZE=sizx/2fu=xfifjfflag=1;fd(j,S,O)if(sizx-sizlinkuj=SIZE)u=linkuj;ans+=u;if(u1=x&sizusizMax)Max=ei.x;linkxO=Max;UpdateLink(X);)if(sizxsizlinksO)links0=x;UpdateLink(三);)voidDFS(intxfintfrom)for(inti=lastxrs;i;i=ei.next)s=ei.x;if(s!=from)GetAns(s);Spin(s);GetAns(x);DFS(sfx);Spin(x);)intmain()open(centroid);read(T);registerintifjfx,y;while(T-)ans=k=0;fo(i,1,n)lasti=0;read(n);fo(i,2,n)read(x)fread(y);Add(xfy)fAdd(yfx);)DFSO(lf0);fo(jflfS)fo(iflfn)linkij=linklinkij-lj-1;DFS(lf0);printf(u%lldn,fans);)return0;
