题目名称 | 35. [POI 1999] 遗传密码 |
---|---|
输入输出 | pie.in/out |
难度等级 | ★★☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试数据 | 10 |
题目来源 | cqw 于2008-04-24加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:47, 提交:159, 通过率:29.56% | ||||
Faller | 100 | 0.000 s | 0.00 MiB | C++ |
Fancy、 | 100 | 0.000 s | 0.00 MiB | C++ |
Shirry | 100 | 0.000 s | 0.00 MiB | C++ |
残镖书生 | 100 | 0.001 s | 1.15 MiB | C++ |
根管理员 | 100 | 0.002 s | 0.58 MiB | C++ |
Qw | 100 | 0.002 s | 1.15 MiB | C++ |
Faller | 100 | 0.003 s | 1.15 MiB | C++ |
yuan | 100 | 0.008 s | 1.73 MiB | C++ |
OIdiot | 100 | 0.010 s | 1.18 MiB | C++ |
xuedi | 100 | 0.012 s | 1.73 MiB | C++ |
本题关联比赛 | |||
2008haoi模拟训练4 | |||
4043级NOIP2022欢乐赛5th |
关于 遗传密码 的近10条评论(全部评论) | ||||
---|---|---|---|---|
c语言回更好用
{iomanip}
2016-11-23 20:12
3楼
| ||||
father数组的初始化边界判断真是门学问QAQ
安呐一条小咸鱼。
2016-08-10 21:08
2楼
| ||||
当前连通块为欧拉回路时,答案为 n + 1
当前连通块为欧拉道路时,答案为 n + 1 当前连通块为其他形式时,先构成欧拉道路,再加一,答案为 n + (sum[i]/2 - 1) + 1 欧拉回路的+1是因为那条回边是实边,而构成欧拉道路后,再构成欧拉回路的话,加的那条回边是虚边,不需要再数列中加入新的元素 |
原始生物的遗传密码是一个自然数序列 $K = ( a_1,...,a_n )$。
原始生物的特征是指在遗传密码中连续出现的数对 $( l , r )$ ,即存在自然数 $i$ 使得 $l = a_i$ 且 $r = a_{i+1}$ 。
在原始生物的遗传密码中不存在形如 $( p , p )$ 的特征。
请根据读入的特征列表,计算包含这些特征的最短的遗传密码。
第一行有一个正整数 $n$ ,表示遗传密码的特征数。
在接下来的 $n$ 行中,每行有一对自然数 $l$ 和 $r$ ,数对 $( l , r )$ 是原始生物的特征之一,特征不会在输入文件中重复出现。
输出文件包含一个整数,表示包含输入的所有特征的最短遗传密码的长度。
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
15
点击下载样例2
下面的遗传密码包含了所有特征: (8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)
对于 $50\%$ 的数据,$1 \leq n \leq 100, 1 \leq l \lt r \leq 1000$ ;
对于 $100\%$ 的数据,$1 \leq n \leq 50000, 1 \leq l \lt r \leq 1000$ ;