NOIP2019(提高组)正式赛.docx
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是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为“的树，树上结点从编号，1号结点为树的根。除1号结点外，每个结点有一个父亲结点，u(2u/1)号结点的父亲为4(lL<u)号结点°小Q发现这个树的每个结点上修有一个括号，可能是或小Q定义Si为：将根结点到i号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。显然Si是个括号串，但不一定是合法括号串，因此现在小Q想对所有的/(ln)求出，舟中有多少个互不相同的子串是合法括号串。这个问题难倒了小Q,他只好向你求助。设Sj共有自个不同子串是合法括号串，你只需要告诉小Q所有iX将的异或和，即：(IXA)xor(2×6)xor(3×23)xorxor(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-205×IO5参考答案#include<cstdio>#include<cstring>#include<algorithm>#defineIint#defineIllonglong#defineF(i,a,b)for(Ii=a;i<=b;i+)#defineFd(ifarb)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<,0,ch>,9')ch=getchar();while(ch>=,0'8tch<=,9,)x=x*10+ch-,0ch=getchar();)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(he<=ta)Ix=dhe+fz=x;Fd(if19f0)if(szi>ax)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.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;)Code2#include<cstdio>#include<cstring>#include<algorithm>#defineIint#defineIllonglong#defineF(i,a,b)for(Ii=a;i<=b;i+)#defineFd(irarb)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<,0'ch>,9')ch=getchar();while(ch>=,0'84ch<=,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();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是该树的重心当且仅当在树中删去C及与它关联的边后，分裂出的所有子树的大小均不超过玲（其中W是下取整函数）。对于包含至少一个结点的树，它的重心只可能有1或2个。课后老师给出了一个大小为的树S,树中结点从1编号。小简单的课后作业是求出S单独删去每条边后，分裂出的两个子树的重心编号和之和。即：Input从文件centroid.in中读入数据。本题输入包含多组测试数据。第一行一个整数T表示数据组数。接下来依次给出每组输入数据，对于每组数据：第一行一个整数表示树S的大小。接下来行，每行两个以空格分隔的整数%,片,表示树中的一条边（出,咽。Output输出到文件centroid.out中。共T行，每行一个整数，第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号点所在子树重心编号为5o因此答案为l÷2+3÷2+3÷5+2+3÷4+2÷5=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<cstdio>#include<algorithm>#include<climits>#include<cstring>#include<iostream>/#include<ctime>/#include<cmath>/#include<map>/#include<vector>/#include<set>/#include<string>#defineopenjn(x)freopen(*x".in,f,r,rstdin)#defineopen_out(x)freopen(#x,.out,f,w"fstdout)#defineopen_(x)freopen(x,.in,w,f
