首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 全国信息学奥林匹克联赛(NOIP2019)复赛 提高组 day1

全国信息学奥林匹克联赛(NOIP2019)复赛 提高组 day1 VIP

信息学奥赛-提高级 共 3 题 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

格雷码

【题目描述】

通常,人们习惯将所有n位二进制串按照字典序排列,例如所有2位二进制串按 字典序从小到大排列为:00, 01, 10, 11

格雷码(Gray Code)是一种特殊的n位二进制串排列法,它要求相邻的两个二进 制串间恰好有一位不同.特别地,第一个串与最后一个串也算作相邻。

所有2位二进制串按格雷码排列的一个例子为:00, 01, 11, 10。

n位格雷码不止一种,下面给出其中一种格雷码的生成算法:

1.1位格雷码由两个1位二进制串组成,顺序为:0, 1。

2.n + 1位格雷码的前2^n个二进制串,可以由依此算法生成的n位格雷码(总共 2^n个n位二进制串)按顺序排列,再在每个串前加一个前缀0构成。

3.n + 1位格雷码的后2^n个二进制串,可以由依此算法生成的n位格雷码(总共 2^n个n位二进制串)按逆序排列,再在每个串前加一个前缀1构成。

综上,n + 1位格雷码,由n位格雷码的2^n个二进制串按顺序排列再加前缀0,和 按逆序排列再加前缀1构成,共2^n+1个二进制串。另外,对于n位格雷码中的2^n个 二进制串,我们按上述算法得到的排列顺序将它们从0~2^n - 1编号。

按该算法,2位格雷码可以这样推出:

1.己知1位格雷码为0, 1

2.前两个格雷码为00, 01.后两个格雷码为11, 10。合并得到00, 01, 11, 10, 编号依次为0〜3。

同理,3位格雷码可以这样推出:

1.己知2位格雷码为:00, 01, 11 10。

2.前四个格雷码为:000, 001, 011.010。后四个格雷码为:110, 111, 101, 100。合并得到:000, 001. 011, 010, 110, 111. 101, 100,编号依次为 0 ~7。

现在给出n,k请你求出按上述算法生成的n位格雷码中的k号二进制串。

【输入格式】

从文件code.in中读入数据。

仅一行两个整数n,k意义见题目描述。

【输出格式】

输出到文件code.out中。

仅一行一个n位二进制串表示答案。

【样例1输入】

23

【样例1输出】

10

【样例1解释】

2位格雷码为:00, 01, 11. 10,编号从0〜3,因此3号串是10。

【样例2输入】

35

【样例2输出】

111

【样例2解释】

3 位格雷码为:000, 001. 011, 010, 110, 111. 101, 100,编号从 0 〜7,因此 5 号串是111。

【数据范围】

对于50%的数据:n≤ 10

对于80%的数据:k≤5x10^6

对于95%的数据:k≤  2^63 - 1

对于 100% 的数据:1 ≤ n ≤ 64,0 ≤ k≤2^n

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;">    int n;</p><p style="text-align: left;">    unsigned long long k;</p><p style="text-align: left;">    cin&gt;&gt;n&gt;&gt;k;</p><p style="text-align: left;">    unsigned long long s;</p><p style="text-align: left;">    for(int i=n;i&gt;=1;i--)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        s=pow(2,i);</p><p style="text-align: left;">        if(k&gt;=(s/2))</p><p style="text-align: left;">        {</p><p style="text-align: left;">            k=s-k-1;</p><p style="text-align: left;">            printf("1");</p><p style="text-align: left;">        }</p><p style="text-align: left;">        else</p><p style="text-align: left;">            printf("0");</p><p>        </p><p style="text-align: left;">    }</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
2. 简答题

括号树

【题目背景】

本题中合法括号串的定义如下:

1.0是合法括号串。

2.如果A是合法括号串,则(A)是合法括号串。

3.如果A, B是合法括号串,则AB是合法括号串。

本题中子串与不同的子串的定义如下:

1.字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置l与终止位置r来表示,记为S(l,r)(1≤l≤r≤|S|,|S|表示S的长度)。

2.S的两个子串视作不同当且仅当它们在S中的位置不同,即l不同或r不同。

【题目描述】

一个大小为n的树包含n个结点和n-1条边,每条边连接两个结点,且任意两个 结点间有且仅有一条简单路径互相可达。

小Q是一个充满好奇心的小朋友,有一天他在上学的路上碰见了一个大小为n的 树,树上结点从1~n编号,1号结点为树的根。除1号结点外,每个结点有一个父亲 结点,u (2≤ u≤n)号结点的父亲为fu (1 ≤ fu < u)号结点。

小Q发现这个树的每个结点上恰有一个括号,可能是'('或')'。小Q定义si为:将 根结点到i号结点的简单路径上的括号,按结点经过顺序依次排列组成的字符串。

显然si是个括号串,但不一定是合法括号串,因此现在小Q想对所有的i(1≤i≤n) 求岀,si中有多少个互不相同的子串是合法括号串。

这个问题难倒了小Q,他只好向你求助。设si共有ki个不同子串是合法括号串, 你只需要告诉小Q所有ixki的异或和,即:

(1 x k1) xor (2 x k2) xor (3 x k3)xor .…xor (n x kn)其中xor是位异或运算。

【输入格式】

从文件brackets.in中读入数据。

第一行一个整数n,表示树的大小。

第二行一个长为n的由'('与')'组成的括号串,第i个括号表示i号结点上的括号。 

第三行包含n-1个整数,第i(1≤i<n)个整数表示i+1号结点的父亲编号fi+1。

【输出格式】

输出到文件brackets.out中。

 仅一行一个整数表示答案。

【样例1输入】

5

(()()

1 1 2 2

【样例1输出】

6

【样例1解释】

树的形态如下图:

将根到1号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(,子串 是合法括号串的个数为0。

将根到2号结点的简单路径上的括号,按经过顺序排列所组成的字符串为((,子 串是合法括号串的个数为0。

将根到3号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(),子 串是合法括号串的个数为1。

将根到4号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(((,子 串是合法括号串的个数为0。

将根到5号结点的简单路径上的括号,按经过顺序排列所组成的字符串为((),子 串是合法括号串的个数为1。

【数据范围】

查看答案与解析
答案:<p style="text-align: left;">#include &lt;iostream&gt;</p><p style="text-align: left;">#include &lt;cstdio&gt;</p><p style="text-align: left;">#include &lt;vector&gt;</p><p style="text-align: left;">#include &lt;stack&gt;</p><p> </p><p style="text-align: left;">typedef long long ll;</p><p style="text-align: left;">const int maxn = 500005;</p><p> </p><p style="text-align: left;">std :: vector &lt;int&gt; G[maxn];</p><p style="text-align: left;">std :: stack &lt;int&gt; bra;</p><p> </p><p style="text-align: left;">char str[maxn];</p><p style="text-align: left;">int fa[maxn];</p><p style="text-align: left;">ll con[maxn], k[maxn];</p><p> </p><p style="text-align: left;">void dfs(int u) {</p><p style="text-align: left;">    int num = 0;</p><p style="text-align: left;">    if (str[u] == '(')</p><p style="text-align: left;">        bra.push(u);</p><p style="text-align: left;">    else if (!bra.empty()){</p><p style="text-align: left;">        num = bra.top();</p><p style="text-align: left;">        bra.pop();</p><p style="text-align: left;">        con[u] = con[fa[num]] + 1;</p><p style="text-align: left;">    }</p><p> </p><p style="text-align: left;">    k[u] = k[fa[u]] + con[u];</p><p style="text-align: left;">    for (int i = 0; i &lt; G[u].size(); ++i)</p><p style="text-align: left;">        dfs(G[u][i]);</p><p>    </p><p style="text-align: left;">    if (num != 0)</p><p style="text-align: left;">        bra.push(num);</p><p style="text-align: left;">    else if (!bra.empty())</p><p style="text-align: left;">        bra.pop();</p><p style="text-align: left;">    return ;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int main() {</p><p style="text-align: left;">    int n;</p><p style="text-align: left;">    std :: scanf("%d", &amp;n);</p><p style="text-align: left;">    std :: scanf("%s", str + 1);</p><p style="text-align: left;">    for (int i = 2; i &lt;= n; ++i) {</p><p style="text-align: left;">        std :: scanf("%d", &amp;fa[i]);</p><p style="text-align: left;">        G[fa[i]].push_back(i);</p><p style="text-align: left;">    }</p><p style="text-align: left;">    ll ans = 0;</p><p style="text-align: left;">    dfs(1);</p><p style="text-align: left;">    for (int i = 1; i &lt;= n; ++i)</p><p style="text-align: left;">        ans ^= k[i] * (ll)i;</p><p style="text-align: left;">    std :: printf("%lld\n", ans);</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
3. 简答题

树上的数

【题目描述】

给定一个大小为n的树,它共有n个结点与n-1条边,结点从1~n编号。初始 时每个结点上都有一个1~n的数字,且每个1~n的数字都只在恰好一个结点上出现。

接下来你需要进行恰好n-1次删边操作,每次操作你需要选一条未被删去的边, 此时这条边所连接的两个结点上的数字将会交换.然后这条边将被删去。

n-1次操作过后,所有的边都将被删去。此时,按数字从小到大的顺序,将数字 1~n所在的结点编号依次排列,就得到一个结点编号的排列Pi。现在请你求出,在最 优操作方案下能得到的字典序最小的Pi。

如上图,蓝圈中的数字1〜5 一开始分别在结点②、①、③、⑤、④。按照⑴⑷(3)⑵ 的顺序删去所有边,树变为下图。按数字顺序得到的结点编号排列为 ①③④②⑤,该 排列是所有可能的结果中字典序最小的。

【输入格式】

从文件tree.in中读入数据。

本题输入包含多组测试数据。

第一行一个正整数T,表示数据组数。

对于每组测试数据:

第一行一个整数n,表示树的大小。

第二行n个整数,第i (1≤i≤ n)个整数表示数字i初始时所在的结点编号。 接下来n-1行每行两个整数x,y,表示一条连接x号结点与y号结点的边。

【输出格式】

输出到文件tree.out中。

对于每组测试数据,输出一行共n个用空格隔开的整数,表示最优操作方案下所 能得到的字典序最小的Pi。

【样例1输入】

4  

5

2 1 3 5 4

1 3

1 4

2 4

4 5

5

3 4 2 1 5

1 2

2 3

3 4

4 5

5

1 2 5 3 4

1 2

1 3

1 4

1 5

10

1 2 3 4 5 7 8 9 10 6

1 2

1 3

1 4

1 5

5 6

6 7

7 8

8 9

9 10

【样例1输出】

1 3 4 2 5

1  3 5 2 4

2  3 1 4 5 

2 3 4 5 6 1 7 8 9 10

【数据范围】

对于所有测试点:1 ≤ T ≤ 10,保证给出的是一个树。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;cstdio&gt;</p><p style="text-align: left;">#include&lt;vector&gt;</p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i&lt;=i##_end_;++i)</p><p style="text-align: left;">#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i&gt;=i##_end_;--i)</p><p style="text-align: left;">#define writc(a,b) fwrit(a),putchar(b)</p><p style="text-align: left;">#define mp(a,b) make_pair(a,b)</p><p style="text-align: left;">#define ft first</p><p style="text-align: left;">#define sd second</p><p style="text-align: left;">#define LL long long</p><p style="text-align: left;">#define ull unsigned long long</p><p style="text-align: left;">#define pii pair&lt;int,int&gt;</p><p style="text-align: left;">// #define FILEOI</p><p> </p><p style="text-align: left;">#define cg (c=getchar())</p><p style="text-align: left;">template&lt;class T&gt;inline void qread(T&amp; x){</p><p style="text-align: left;"><span style="white-space:pre"> </span>char c;bool f=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(cg&lt;'0'||'9'&lt;c)if(c=='-')f=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(x=(c^48);'0'&lt;=cg&amp;&amp;c&lt;='9';x=(x&lt;&lt;1)+(x&lt;&lt;3)+(c^48));</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(f)x=-x;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int qread(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=0;char c;bool f=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(cg&lt;'0'||'9'&lt;c)if(c=='-')f=-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(x=(c^48);'0'&lt;=cg&amp;&amp;c&lt;='9';x=(x&lt;&lt;1)+(x&lt;&lt;3)+(c^48));</p><p style="text-align: left;"><span style="white-space:pre"> </span>return f?-x:x;</p><p style="text-align: left;">}</p><p style="text-align: left;">#undef cg</p><p style="text-align: left;">template&lt;class T,class... Args&gt;inline void qread(T&amp; x,Args&amp;... args){qread(x),qread(args...);}</p><p style="text-align: left;">template&lt;class T&gt;inline T Max(const T x,const T y){return x&gt;y?x:y;}</p><p style="text-align: left;">template&lt;class T&gt;inline T Min(const T x,const T y){return x&lt;y?x:y;}</p><p style="text-align: left;">template&lt;class T&gt;inline T fab(const T x){return x&gt;0?x:-x;}</p><p style="text-align: left;">inline void getInv(int inv[],const int lim,const int MOD){</p><p style="text-align: left;"><span style="white-space:pre"> </span>inv[0]=inv[1]=1;for(int i=2;i&lt;=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;</p><p style="text-align: left;">}</p><p style="text-align: left;">template&lt;class T&gt;void fwrit(const T x){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x&lt;0)return (void)(putchar('-'),fwrit(-x));</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x&gt;9)fwrit(x/10);putchar(x%10^48);</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">const int MAXN=2000;</p><p> </p><p style="text-align: left;">struct edge{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int to,nxt;</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge(){}</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge(const int T,const int N):to(T),nxt(N){}</p><p style="text-align: left;">}e[(MAXN&lt;&lt;1)+5];</p><p style="text-align: left;">int tail[MAXN+5],ecnt,siz[MAXN+5];</p><p style="text-align: left;">inline void add_edge(const int u,const int v){</p><p style="text-align: left;"><span style="white-space:pre"> </span>++siz[u],++siz[v];</p><p style="text-align: left;"><span style="white-space:pre"> </span>e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;</p><p style="text-align: left;"><span style="white-space:pre"> </span>e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int N,minp;</p><p style="text-align: left;">int pt[MAXN+5];</p><p style="text-align: left;">int pre[MAXN+5][MAXN+5],nxt[MAXN+5][MAXN+5];</p><p style="text-align: left;">//这条边的 前驱,后继</p><p style="text-align: left;">int rt[MAXN+5][MAXN+5][2];</p><p style="text-align: left;">//点 u 的某一条边的 前根节点、后根节点</p><p style="text-align: left;">int len[MAXN+5][MAXN+5];</p><p style="text-align: left;">//这条边 所在链 的链表长度</p><p> </p><p style="text-align: left;">inline void init(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>qread(N);</p><p style="text-align: left;"><span style="white-space:pre"> </span>ecnt=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,1,N)qread(pt[i]),tail[i]=siz[i]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,1,N+1)rep(j,1,N+1)len[i][j]=pre[i][j]=nxt[i][j]=rt[i][j][0]=rt[i][j][1]=0;</p><p> </p><p style="text-align: left;"><span style="white-space:pre"> </span>int u,v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,1,N-1){</p><p style="text-align: left;"><span style="white-space:pre"> </span>qread(u,v);</p><p style="text-align: left;"><span style="white-space:pre"> </span>add_edge(u,v);</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[u][v]=pre[v][u]=nxt[u][v]=nxt[v][u]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rt[u][v][0]=rt[u][v][1]=v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rt[v][u][0]=rt[v][u][1]=u;</p><p style="text-align: left;"><span style="white-space:pre"> </span>len[u][v]=len[v][u]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">void findPath(const int u,const int p){//当前节点、前一个节点</p><p style="text-align: left;"><span style="white-space:pre"> </span>int a=rt[u][p][0],b=rt[u][p][1],ta,tb;</p><p style="text-align: left;"><span style="white-space:pre"> </span>//a:来的边的前根 ; b:来的边的后根</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p==N+1){//这是起点</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=tail[u],v;i;i=e[i].nxt){//从哪条边起飞</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=e[i].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ta=rt[u][v][0],tb=rt[u][v][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(ta!=v || (pre[u][p]==tb &amp;&amp; len[u][ta]&lt;siz[u]))</p><p style="text-align: left;"><span style="white-space:pre"> </span>//条件一:如果这条边已经有一个起点且不是自己</p><p style="text-align: left;"><span style="white-space:pre"> </span>//条件二:如果后面的那条边已经连接尾端, 且这条链的长度无法满足将所有边连起来</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;//那么就不能把 边{u,p} 与 边{u,v} 连在一起</p><p style="text-align: left;"><span style="white-space:pre"> </span>findPath(v,u);//否则可行</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p==b){//如果 边{u,p} 的后面还暂时没有指定必须删哪一条边, 那么就可以考虑枚举一条边接在后面</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(pre[u][N+1]==0 &amp;&amp; (nxt[u][N+1]!=a || len[u][a]==siz[u]))//则可以考虑在点 u 进行降落, 满足以下条件:</p><p style="text-align: left;"><span style="white-space:pre"> </span>//如果这个点的末删边还没有被指定(必须满足)</p><p style="text-align: left;"><span style="white-space:pre"> </span>//并且:</p><p style="text-align: left;"><span style="white-space:pre"> </span>//1.如果这条链接上开头,那么如果必须满足所有的边都在这条链上</p><p style="text-align: left;"><span style="white-space:pre"> </span>//2.如果没有接上开头,那么长度随意</p><p style="text-align: left;"><span style="white-space:pre"> </span>minp=Min(minp,u);//如果满足, 则 u 可以作为一个降落点</p><p> </p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=tail[u],v;i;i=e[i].nxt){//假定 u 为一个中转点, 则再枚举一条边作为 边{u,p} 的出边,与其尾相连</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=e[i].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ta=rt[u][v][0],tb=rt[u][v][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(a==ta || ta!=v || nxt[u][N+1]==v)//第一种大情况</p><p style="text-align: left;"><span style="white-space:pre"> </span>//如果这两条边已经在同一条链上</p><p style="text-align: left;"><span style="white-space:pre"> </span>//或者这个边不是一个起始边, 即枚举边的前面还有东西</p><p style="text-align: left;"><span style="white-space:pre"> </span>//或者枚举边是一条起飞边, 即保证它是所有对于 u 的边必须最先删除的边</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;//那么 当前 边{u,p} 都不能接在这条枚举边之上</p><p><span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>if(nxt[u][N+1]==a &amp;&amp; pre[u][N+1]==tb &amp;&amp; len[u][a]+len[u][ta]&lt;siz[u])</p><p style="text-align: left;"><span style="white-space:pre"> </span>//如果这两条边分别属于这个点 最先删除、最后删除 的链表上的 尾、头</p><p style="text-align: left;"><span style="white-space:pre"> </span>//那么它们组合起来必须等于所有边的数量之和</p><p style="text-align: left;"><span style="white-space:pre"> </span>//否则, 这就是 提前自闭 的情况</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p> </p><p style="text-align: left;"><span style="white-space:pre"> </span>findPath(v,u);//如果以上都不满足, 那么这条边是合法的</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else findPath(nxt[u][p],u);//否则我们只能按照之前的规定访问这条边</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void merge(const int u,const int a,const int b){</p><p style="text-align: left;">//函数条件:以 a 所在的链表为前链表</p><p style="text-align: left;">//并且满足 a 是前链表尾, b 是后链表头</p><p style="text-align: left;"><span style="white-space:pre"> </span>int ta=rt[u][a][0],tb=rt[u][b][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>nxt[u][a]=b;</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[u][b]=a;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=ta;i &amp;&amp; i!=N+1;i=nxt[u][i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>//访问链表的基本操作</p><p style="text-align: left;"><span style="white-space:pre"> </span>//更新每个点的前根、后根</p><p style="text-align: left;"><span style="white-space:pre"> </span>rt[u][i][0]=ta;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rt[u][i][1]=tb;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>len[u][ta]+=len[u][b];</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">bool getMark(const int u,const int p){//还原路径, 并且给路径打上标记</p><p style="text-align: left;">//如果这条路径找到终点, 返回 1, 否则返回 0</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(u==minp){//如果找到了终点</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[u][N+1]=p;//把这条边设为最后删除的边</p><p style="text-align: left;"><span style="white-space:pre"> </span>nxt[u][p]=N+1;//并且把这条边的下一条边标记为 N+1, 表示这条边是最后删除的</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>int a=rt[u][p][0],b=rt[u][p][1],ta,tb;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p==N+1){//这是起飞点</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=tail[u],v;i;i=e[i].nxt){</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=e[i].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ta=rt[u][v][0],tb=rt[u][v][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(ta!=v || (pre[u][N+1]==tb &amp;&amp; len[u][ta]&lt;siz[u]))</p><p style="text-align: left;"><span style="white-space:pre"> </span>//如果枚举边前面有东西, 那么这肯定不能接在起始边的后面, 因为它前面已经有个什么 逼 了</p><p style="text-align: left;"><span style="white-space:pre"> </span>//或者是枚举边连接到末尾, 但是这条单链长度不够将所有的边包含到链里面</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;//那么这条边肯定不在路径上面, 可直接跳过</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(getMark(v,u)){//如果这就是正确的路径</p><p style="text-align: left;"><span style="white-space:pre"> </span>nxt[u][N+1]=v;//因为 u 点是起飞点, 所以把这条边记录为 u 的起飞边</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[u][v]=N+1;//同时标记这条边的前驱, 与前面的 if 相互呼应(这不是语文...)</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else{//如果点 u 是中转点, 那么考虑枚举中转边</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p==b){//如果这条边在链上后面没有其他边的时候</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=tail[u],v;i;i=e[i].nxt){</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=e[i].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ta=rt[u][v][0],tb=rt[u][v][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(a==ta || ta!=v || nxt[u][N+1]==v)//参考 findPath() 中相同位置的注释</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(nxt[u][N+1]==a &amp;&amp; pre[u][N+1]==tb &amp;&amp; len[u][a]+len[u][ta]&lt;siz[u])//同样参考 findPath() 中同样位置</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(getMark(v,u)){</p><p style="text-align: left;"><span style="white-space:pre"> </span>merge(u,p,v);//把链表合并为一个</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else getMark(nxt[u][p],u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">signed main(){</p><p style="text-align: left;">#ifdef FILEOI</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("rdata.out","r",stdin);</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("file.out","w",stdout);</p><p style="text-align: left;">#endif</p><p style="text-align: left;"><span style="white-space:pre"> </span>int T=qread();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(T--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>init();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(N==1){</p><p style="text-align: left;"><span style="white-space:pre"> </span>writc(1,'\n');</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,1,N){</p><p style="text-align: left;"><span style="white-space:pre"> </span>minp=N+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>findPath(pt[i],N+1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>// printf("%d\n",minp);</p><p style="text-align: left;"><span style="white-space:pre"> </span>getMark(pt[i],N+1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>writc(minp,' ');</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>putchar('\n');</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。