「一本通 3.7 练习 6」原始生物 - 省实信息学奥赛 - 在线练习

广东实验中学信息学奥赛评测系统

问题 2814. -- 「一本通 3.7 练习 6」原始生物

2814: 「一本通 3.7 练习 6」原始生物

时间限制: 3 Sec 内存限制: 128 MB
提交: 0 解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p><strong>原题来自：POI 1999</strong></p>
<p>原始生物的遗传密码是一个自然数的序列 <span class="katex"><span class="katex-mathml">K=(a1,⋯,an)K=(a_1,cdots,a_n)</span><span class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em; vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.07153em;">K</span><span class="mrel">=</span><span class="mopen">(</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mclose">)</span></span></span></span>。原始生物的特征是指在遗传密码中连续出现的数对 <span class="katex"><span class="katex-mathml">(l,r)(l,r)</span><span class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em; vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord mathit" style="margin-right:0.01968em;">l</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.02778em;">r</span><span class="mclose">)</span></span></span></span>，即存在自然数 <span class="katex"><span class="katex-mathml">ii</span><span class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.65952em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">i</span></span></span></span> 使得 <span class="katex"><span class="katex-mathml">l=ail=a_i</span><span class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.84444em; vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span><span class="mrel">=</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span> 且 <span class="katex"><span class="katex-mathml">r=ai+1r=a_i+1</span><span class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.79444em; vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">r</span><span class="mrel">=</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mbin">+</span><span class="mord mathrm">1</span></span></span></span>。在原始生物的遗传密码中不存在 <span class="katex"><span class="katex-mathml">(p,p)(p,p)</span><span class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em; vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord mathit">p</span><span class="mpunct">,</span><span class="mord mathit">p</span><span class="mclose">)</span></span></span></span> 形式的特征。</p>
<p>求解任务，请设计一个程序：</p>
<ul>
<li><p>读入一系列的特征。</p>
</li>
<li><p>计算包含这些特征的最短的遗传密码。</p>
</li>
<li><p>将结果输出</p>
</li>
</ul>
</div></div>

输入

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>第一行是一个整数 <span class="katex"><span class="katex-mathml">nn</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> ，表示特征的总数。在接下来的 <span class="katex"><span class="katex-mathml">nn</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 行里，每行都是一对由空格分隔的自然数 <span class="katex"><span class="katex-mathml">ll</span><span class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span></span></span></span> 和 <span class="katex"><span class="katex-mathml">rr</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">r</span></span></span></span> 。数对 <span class="katex"><span class="katex-mathml">(l,r)(l,r)</span><span class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em; vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord mathit" style="margin-right:0.01968em;">l</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.02778em;">r</span><span class="mclose">)</span></span></span></span> 是原始生物的特征之一。输入文件中的特征不会有重复。</p>
</div></div>

输出

提示

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><h4>样例输入</h4>
<div class="ui existing segment"><pre style="margin-top: 0; margin-bottom: 0; "><code class="lang-plain">12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6</code></pre></div>
<h4>样例输出</h4>
<div class="ui existing segment"><pre style="margin-top: 0; margin-bottom: 0; "><code class="lang-plain">15</code></pre></div>
<h4>样例解释</h4>
<p>输入文件中的所有特征都包含在以下遗传密码中：</p>
<p><span class="katex"><span class="katex-mathml">(8,5,1,4,2,3,9,6,4,5,7,6,2,8,6)(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)</span><span class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em; vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord mathrm">8</span><span class="mpunct">,</span><span class="mord mathrm">5</span><span class="mpunct">,</span><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathrm">4</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="mord mathrm">3</span><span class="mpunct">,</span><span class="mord mathrm">9</span><span class="mpunct">,</span><span class="mord mathrm">6</span><span class="mpunct">,</span><span class="mord mathrm">4</span><span class="mpunct">,</span><span class="mord mathrm">5</span><span class="mpunct">,</span><span class="mord mathrm">7</span><span class="mpunct">,</span><span class="mord mathrm">6</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="mord mathrm">8</span><span class="mpunct">,</span><span class="mord mathrm">6</span><span class="mclose">)</span></span></span></span></p>
</div></div>

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p><span class="katex"><span class="katex-mathml">1≤l,r≤10001 le l,r le 1000</span><span class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.01968em;">l</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.02778em;">r</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span></span></span></span></p>
</div></div>

标签

一本通提高篇 10112 POI 早于2010 欧拉回路图论

[上一题][提交][讨论版][状态][下一题]

OI模式 | OJ模式 | 笔记本 | 如果发现题目有问题，请联系管理员：crxis@qq.com OIER
All Copyright Reserved 2010-2015 广东实验中学信息学奥赛评测系统 TEAM