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

全国信息学(计算机)奥林匹克联赛(NOIP2007)复赛 提高组 VIP

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

一、简答题

1. 简答题

统计数字

【问题描述】

某次科研调查时得到了 n 个自然数,每个数均不超过 1500000000(1.5*109)。已知不相同的数

不超过 10000 个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统

计结果。

【输入】

 输入文件 count.in 包含 n+1 行:

 第 1 行是整数 n,表示自然数的个数。

 第 2~n+1 行每行一个自然数。

【输出】

 输出文件 count.out 包含 m 行(m 为 n 个自然数中不相同数的个数),按照自然数从小到大

的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。

【输入输出样例】

【限制】

 40%的数据满足:1<=n<=1000

 80%的数据满足:1<=n<=50000

 100%的数据满足:1<=n<=200000,每个数均不超过 1 500 000 000(1.5*10^9)

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int N=1e5;</p><p style="text-align: left;">long long a[N];</p><p style="text-align: left;">struct s</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>long long num;</p><p style="text-align: left;"><span style="white-space:pre"> </span>long long sum;</p><p style="text-align: left;">}s[100001];</p><p style="text-align: left;">bool cmp(struct s a,struct s b)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>return a.num&lt;b.num;</p><p style="text-align: left;">}</p><p style="text-align: left;">long long n,m,i;</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>map&lt;long long,int&gt;mp;</p><p style="text-align: left;">    cin&gt;&gt;n;</p><p style="text-align: left;">    for(i=1;i&lt;=n;i++)</p><p style="text-align: left;">    {</p><p style="text-align: left;">    <span style="white-space:pre"> </span>cin&gt;&gt;a[i];</p><p style="text-align: left;">    <span style="white-space:pre"> </span>mp[a[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>sort(a+1,a+n+1); </p><p style="text-align: left;"><span style="white-space:pre"> </span>n=unique(a+1,a+1+ n)-(a+1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(i=1;i&lt;=n;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>s[i].num=a[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>s[i].sum=mp[a[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>sort(s+1,s+1+n,cmp);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(i=1;i&lt;=n;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>cout&lt;&lt;s[i].num&lt;&lt;" "&lt;&lt;s[i].sum&lt;&lt;endl;</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>
这道题暂未补解析。
2. 简答题

字符串的展开

【问题描述】

在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串中,含有类似于“d-h”或“4-8”的子串,我们就把它当作一种简写,输出时,用连续递增的字母或数字串替代其中的减号,即,将上面两个子串分别输出为“defgh”和“45678”。在本题中,我们通过增加一些参数的设置,使字符串的展开更为灵活。具体约定如下:

(1)遇到下面的情况需要做字符串的展开:在输入的字符串中,出现了减号“-”,减号两侧同为小写字母或同为数字,且按照 ASCII 码的顺序,减号右边的字符严格大于左边的字符。

(2)参数 p1:展开方式。p1=1 时,对于字母子串,填充小写字母;p1=2 时,对于字母子串,填充大写字母。这两种情况下数字子串的填充方式相同。p1=3 时,不论是字母子串还是数字子串,都用与要填充的字母个数相同的星号“*”来填充。

(3)参数 p2:填充字符的重复个数。p2=k 表示同一个字符要连续填充 k 个。例如,当 p2=3时,子串“d-h”应扩展为“deeefffgggh”。减号两侧的字符不变。

(4)参数 p3:是否改为逆序:p3=1 表示维持原有顺序,p3=2 表示采用逆序输出,注意这时仍然不包括减号两端的字符。例如当 p1=1、p2=2、p3=2 时,子串“d-h”应扩展为“dggffeeh”。

(5)如果减号右边的字符恰好是左边字符的后继,只删除中间的减号,例如:“d-e”应输出为“de”,“3-4”应输出为“34”。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符,输出时,要保留中间的减号,例如:“d-d”应输出为“d-d”,“3-1”应输出为“3-1”。

【输入】

输入文件 expand.in 包括两行:

第 1 行为用空格隔开的 3 个正整数,依次表示参数 p1,p2,p3。

第 2 行为一行字符串,仅由数字、小写字母和减号“-”组成。行首和行末均无空格。

【输出】

输出文件 expand.out 只有一行,为展开后的字符串。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【限制】

 40%的数据满足:字符串长度不超过 5

 100%的数据满足:1<=p1<=3, 1<=p2<=8, 1<=p3<=2。字符串长度不超过 100

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int maxn=1e6+7;</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int p1,p2,p3,n;</p><p style="text-align: left;"><span style="white-space:pre"> </span>char a[maxn],b[maxn];</p><p style="text-align: left;"><span style="white-space:pre"> </span>cin&gt;&gt;p1&gt;&gt;p2&gt;&gt;p3&gt;&gt;a;</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=strlen(a);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=0;i&lt;n;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>if(a[i]=='-'&amp;&amp;i&amp;&amp;i&lt;=n-2)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(a[i-1]=='-'||a[i+1]=='-')cout&lt;&lt;'-';//这些是只能打印-号的情况</p><p style="text-align: left;"><span style="white-space:pre"> </span>else if(a[i-1]+1==a[i+1])continue;//这些是只能打印-号的情况,或者不能打印</p><p style="text-align: left;"><span style="white-space:pre"> </span>else if(a[i-1]&gt;=a[i+1]||(a[i-1]&lt;='9'&amp;&amp;a[i+1]&gt;='A'))cout&lt;&lt;'-';//这些是只能打印-号的情况</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>{    int l=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p1==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>for(int j=a[i-1]+1;j&lt;a[i+1];j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=0;i&lt;p2;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>b[l++]=tolower((char)j);</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 if(p1==2)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int j=a[i-1]+1;j&lt;a[i+1];j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=0;i&lt;p2;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>b[l++]=toupper((char)j);</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>{</p><p><span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int j=a[i-1]+1;j&lt;a[i+1];j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=0;i&lt;p2;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>b[l++]='*';</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p><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>if(p3==2)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>reverse(b,b+l);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=0;i&lt;l;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>cout&lt;&lt;b[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><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>cout&lt;&lt;a[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span> </p><p style="text-align: left;">}</p>
这道题暂未补解析。
3. 简答题

矩阵取数游戏

【问题描述】

 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元素 aij均为非负整数。游戏规则如下:

1. 每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素;

2. 每次取走的各个元素只能是该元素所在行的行首或行尾;

3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值*2i,其中 i 表示第 i 次取数(从 1 开始编号);

4. 游戏结束总得分为 m 次取数得分之和。

帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。

【输入】

 输入文件 game.in 包括 n+1 行:

 第 1 行为两个用空格隔开的整数 n 和 m。

 第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。

【输出】

 输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。

【输入输出样例 1】

【输入输出样例 1 解释】

第 1 次:第 1 行取行首元素,第 2 行取行尾元素,本次得分为 1*21+2*21=6

第 2 次:两行均取行首元素,本次得分为 2*22+3*22=20

第 3 次:得分为 3*23+4*23=56。总得分为 6+20+56=82

【输入输出样例 2】

【输入输出样例 3】

【限制】

 60%的数据满足:1<=n, m<=30, 答案不超过 10^16

 100%的数据满足:1<=n, m<=80, 0<=aij<=1000

查看答案与解析
答案:<p style="text-align: left;">#include &lt;cstdio&gt;</p><p style="text-align: left;">#include &lt;cstring&gt;</p><p style="text-align: left;">#include &lt;algorithm&gt;</p><p style="text-align: left;">#include &lt;iostream&gt;</p><p style="text-align: left;">#include &lt;iomanip&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int maxnum = 35;</p><p style="text-align: left;">const int M = 100000000;</p><p style="text-align: left;">typedef unsigned long long ll;</p><p style="text-align: left;">int n, m, map[81][81];</p><p style="text-align: left;">struct highNum</p><p style="text-align: left;">{</p><p style="text-align: left;">    ll num[maxnum];</p><p style="text-align: left;">    highNum(int length = 1)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        memset(num, 0, sizeof(num));</p><p style="text-align: left;">        num[0] = length;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    highNum operator = (highNum b)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        memcpy(num, b.num, sizeof(b.num));</p><p style="text-align: left;">        return *this;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    highNum operator = (int b)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        *this = highNum();</p><p style="text-align: left;">        num[num[0]] = b;</p><p style="text-align: left;">        return *this;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    bool operator &lt; (const highNum&amp; b) const</p><p style="text-align: left;">    {</p><p style="text-align: left;">        if(num[0] &lt; b.num[0]) return true;</p><p style="text-align: left;">        if(num[0] == b.num[0])</p><p style="text-align: left;">        {</p><p style="text-align: left;">            for(int i = num[0]; i &gt;= 1; --i)</p><p style="text-align: left;">            {</p><p style="text-align: left;">                if(num[i] &gt; b.num[i]) return false;</p><p style="text-align: left;">                if(num[i] &lt; b.num[i]) return true;</p><p style="text-align: left;">            }</p><p style="text-align: left;">        }</p><p style="text-align: left;">        return false;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    highNum operator + (const highNum&amp; b) const</p><p style="text-align: left;">    {</p><p style="text-align: left;">        highNum c = highNum(max(num[0], b.num[0]));</p><p style="text-align: left;">        for(int i = 1; i &lt;= c.num[0]; ++i)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            c.num[i] += num[i] + b.num[i];</p><p style="text-align: left;">            c.num[i + 1] += c.num[i] / M;</p><p style="text-align: left;">            c.num[i] %= M;</p><p style="text-align: left;">        }</p><p style="text-align: left;">        while(c.num[c.num[0] + 1] &gt; 0)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            ++c.num[0];</p><p style="text-align: left;">            c.num[c.num[0] + 1] += c.num[c.num[0]] / M;</p><p style="text-align: left;">            c.num[c.num[0]] %= M; </p><p style="text-align: left;">        }</p><p style="text-align: left;">        return c;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    highNum operator * (const int b) const</p><p style="text-align: left;">    {</p><p style="text-align: left;">        highNum c = highNum(num[0]);</p><p style="text-align: left;">        for(int i = 1; i &lt;= c.num[0]; ++i)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            c.num[i] += num[i] * b;</p><p style="text-align: left;">            c.num[i + 1] += c.num[i] / M;</p><p style="text-align: left;">            c.num[i] %= M;</p><p style="text-align: left;">        }</p><p style="text-align: left;">        while(c.num[c.num[0] + 1] &gt; 0)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            ++c.num[0];</p><p style="text-align: left;">            c.num[c.num[0] + 1] += c.num[c.num[0]] / M;</p><p style="text-align: left;">            c.num[c.num[0]] %= M;</p><p style="text-align: left;">        }</p><p style="text-align: left;">        while(c.num[c.num[0]] == 0 &amp;&amp; c.num[0] &gt; 1) --c.num[0];</p><p style="text-align: left;">        return c;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    highNum operator * (const highNum&amp; b) const</p><p style="text-align: left;">    {</p><p style="text-align: left;">        highNum c = highNum(num[0] + b.num[0]);</p><p style="text-align: left;">        for(int i = 1; i &lt;= num[0]; ++i) for(int j = 1; j &lt;= b.num[0]; ++j)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            c.num[i + j - 1] += num[i] * b.num[j];</p><p style="text-align: left;">            c.num[i + j] += c.num[i + j - 1] / M;</p><p style="text-align: left;">            c.num[i + j - 1] %= M;</p><p style="text-align: left;">        }</p><p style="text-align: left;">        while(c.num[c.num[0] + 1] &gt; 0)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            ++c.num[0];</p><p style="text-align: left;">            c.num[c.num[0] + 1] += c.num[c.num[0]] / M;</p><p style="text-align: left;">            c.num[c.num[0]] %= M;</p><p style="text-align: left;">        }</p><p style="text-align: left;">        while(c.num[c.num[0]] == 0 &amp;&amp; c.num[0] &gt; 1) --c.num[0];</p><p style="text-align: left;">        return c;</p><p style="text-align: left;">    }</p><p style="text-align: left;">};</p><p style="text-align: left;">ostream&amp; operator &lt;&lt; (ostream&amp; o, highNum&amp; b)</p><p style="text-align: left;">{</p><p style="text-align: left;">    o &lt;&lt; b.num[b.num[0]];</p><p style="text-align: left;">    o.setf(ios::fixed);</p><p style="text-align: left;">    o.width(8);</p><p style="text-align: left;">    o.fill('0');</p><p style="text-align: left;">    for(int i = b.num[0] - 1; i &gt;= 1; --i) o &lt;&lt; b.num[i];</p><p style="text-align: left;">    return o;</p><p style="text-align: left;">}</p><p style="text-align: left;">highNum ans, f[81][81], pw[81];</p><p style="text-align: left;">void init()</p><p style="text-align: left;">{</p><p style="text-align: left;">    cin &gt;&gt; n &gt;&gt; m;</p><p style="text-align: left;">    for(int i = 1; i &lt;= n; ++i) for(int j = 1; j &lt;= m; ++j)</p><p style="text-align: left;">        cin &gt;&gt; map[i][j];</p><p style="text-align: left;">    pw[1] = 2;</p><p style="text-align: left;">    for(int i = 2; i &lt;= m; ++i) pw[i] = pw[i - 1] * 2;</p><p style="text-align: left;">}</p><p style="text-align: left;">void work(int row)</p><p style="text-align: left;">{</p><p style="text-align: left;">    for(int i = 1; i &lt;= m; ++i) for(int j = 1; j &lt;= m; ++j)</p><p style="text-align: left;">        f[i][j] = highNum();</p><p style="text-align: left;">    for(int i = 1; i &lt;= m; ++i) f[i][i] = pw[m] * map[row][i];</p><p style="text-align: left;">    for(int p = 1; p &lt; m; ++p) for(int i = 1; i &lt;= m - p; ++i)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        int j = i + p;</p><p style="text-align: left;">        f[i][j] = max(f[i + 1][j] + pw[m - p] * map[row][i], f[i][j - 1] + pw[m - p] * map[row][j]);</p><p style="text-align: left;">    }</p><p style="text-align: left;">    ans = ans + f[1][m];</p><p style="text-align: left;">}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;">    init();</p><p style="text-align: left;">    for(int i = 1; i &lt;= n; ++i) work(i);</p><p style="text-align: left;">    cout &lt;&lt; ans;</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
4. 简答题

树网的核

【问题描述】

设 T=(V, E, W) 是一个无圈且连通的无向图(也称为无根树),每条边带有正整数的权,我们称 T 为树网(treenetwork),其中 V, E 分别表示结点与边的集合,W 表示各边长度的集合,并设 T 有 n 个结点。

路径:树网中任何两结点 a,b 都存在唯一的一条简单路径,用 d(a,b)表示以 a,b 为端点的路径的长度,它是该路径上各边长度之和。我们称 d(a,b)为 a,b 两结点间的距离。一点 v 到一条路径 P 的距离为该点与 P 上的最近的结点的距离:

d(v,P)=min{d(v,u),u 为路径 P 上的结点}。

树网的直径:树网中最长的路径称为树网的直径。对于给定的树网 T,直径不一定是唯一的,但可以证明:各直径的中点(不一定恰好是某个结点,可能在某条边的内部)是唯一的,我们称该

点为树网的中心。

偏心距 ECC(F):树网 T 中距路径 F 最远的结点到路径 F 的距离,即

任务:对于给定的树网 T=(V, E,W)和非负整数 s,求一个路径 F,它是某直径上的一段路径(该路径两端均为树网中的结点),其长度不超过 s(可以等于 s),使偏心距 ECC(F)最小。我们称这个路径为树网 T=(V,E,W)的核(Core)。必要时,F 可以退化为某个结点。一般来说,在上述定义下,核不一定只有一个,但最小偏心距是唯一的。

下面的图给出了树网的一个实例。图中,A-B 与 A-C 是两条直径,长度均为 20。点 W 是树网的中心,EF 边的长度为 5。如果指定 s=11,则树网的核为路径 DEFG(也可以取为路径 DEF),偏心距为 8。如果指定 s=0(或 s=1、s=2),则树网的核为结点 F,偏心距为 12。

【输入】

 输入文件 core.in 包含 n 行:

第 1 行,两个正整数 n 和 s,中间用一个空格隔开。其中 n 为树网结点的个数,s 为树网的核的长度的上界。设结点编号依次为 1, 2, ..., n。

从第 2 行到第 n 行,每行给出 3 个用空格隔开的正整数,依次表示每一条边的两个端点编号和长度。例如,“2 4 7”表示连接结点 2 与 4 的边的长度为 7。

所给的数据都是正确的,不必检验。

【输出】

 输出文件 core.out 只有一个非负整数,为指定意义下的最小偏心距。

【输入输出样例 1】

【输入输出样例 2】

【限制】

 40%的数据满足:5<=n<=15

 70%的数据满足:5<=n<=80

 100%的数据满足:5<=n<=300, 0<=s<=1000。边长度为不超过 1000 的正整数

查看答案与解析
答案:<p style="text-align: left;">#include&lt;cstdio&gt;</p><p style="text-align: left;">#include&lt;algorithm&gt;</p><p style="text-align: left;">#include&lt;cstring&gt;</p><p style="text-align: left;">const int inf=0x3f3f3f3f;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">int n,s,a,b,c,maxx=0,mxi,mxj;</p><p style="text-align: left;">int dis[305][305];</p><p style="text-align: left;">int read(){</p><p style="text-align: left;">    int ans=0,f=1;char c=getchar();</p><p style="text-align: left;">    while(c&lt;'0'||c&gt;'9'){</p><p style="text-align: left;">    <span style="white-space:pre"> </span>if(c=='-')f=-1;</p><p style="text-align: left;">    <span style="white-space:pre"> </span>c=getchar();</p><p style="text-align: left;">    }</p><p style="text-align: left;">    while(c&gt;='0'&amp;&amp;c&lt;='9'){</p><p style="text-align: left;">    <span style="white-space:pre"> </span>ans=ans*10+c-48;</p><p style="text-align: left;">    <span style="white-space:pre"> </span>c=getchar();</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return ans*f;</p><p style="text-align: left;">} </p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    n=read();s=read();</p><p style="text-align: left;">    for(int i=1;i&lt;=n;i++)</p><p style="text-align: left;">        for(int j=1;j&lt;=n;j++)</p><p style="text-align: left;">            if(i!=j)dis[i][j]=inf;</p><p style="text-align: left;">    for(int i=1;i&lt;=n-1;i++){</p><p style="text-align: left;">        a=read();b=read();c=read();dis[a][b]=dis[b][a]=c;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for(int k=1;k&lt;=n;k++)</p><p style="text-align: left;">        for(int i=1;i&lt;=n;i++)</p><p style="text-align: left;">            for(int j=1;j&lt;=n;j++){</p><p style="text-align: left;">                if(dis[i][k]&gt;=inf||dis[k][j]&gt;=inf)continue;</p><p style="text-align: left;">                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);</p><p style="text-align: left;">                if(dis[i][j]&gt;maxx){</p><p style="text-align: left;">                    maxx=dis[i][j];</p><p style="text-align: left;">                    mxi=i;mxj=j;</p><p style="text-align: left;">                }</p><p style="text-align: left;">            }</p><p style="text-align: left;">    int ans=inf;</p><p style="text-align: left;">    for(int i=1;i&lt;=n;i++){</p><p style="text-align: left;">        if(dis[mxi][i]+dis[i][mxj]!=dis[mxi][mxj])continue;</p><p style="text-align: left;">        for(int j=1;j&lt;=n;j++){</p><p style="text-align: left;">            if(dis[mxi][j]+dis[j][mxj]!=dis[mxi][mxj]||dis[i][j]&gt;s)continue;</p><p style="text-align: left;">            int ecc=0;</p><p style="text-align: left;">            ecc=max(min(dis[mxi][i],dis[mxi][j]),min(dis[mxj][i],dis[mxj][j]));</p><p style="text-align: left;">            ans=min(ans,ecc);</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    printf("%d",ans);</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。