题目名称 35. [POI 1999] 遗传密码
输入输出 pie.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2008-04-24加入
开放分组 全部用户
提交状态
分类标签
图论 并查集 欧拉路径
分享题解
通过:47, 提交:159, 通过率:29.56%
GravatarFaller 100 0.000 s 0.00 MiB C++
GravatarFancy、 100 0.000 s 0.00 MiB C++
GravatarShirry 100 0.000 s 0.00 MiB C++
Gravatar残镖书生 100 0.001 s 1.15 MiB C++
Gravatar根管理员 100 0.002 s 0.58 MiB C++
GravatarQw 100 0.002 s 1.15 MiB C++
GravatarFaller 100 0.003 s 1.15 MiB C++
Gravataryuan 100 0.008 s 1.73 MiB C++
GravatarOIdiot 100 0.010 s 1.18 MiB C++
Gravatarxuedi 100 0.012 s 1.73 MiB C++
本题关联比赛
2008haoi模拟训练4
4043级NOIP2022欢乐赛5th
关于 遗传密码 的近10条评论(全部评论)
c语言回更好用
Gravatar{iomanip}
2016-11-23 20:12 3楼
father数组的初始化边界判断真是门学问QAQ
Gravatar安呐一条小咸鱼。
2016-08-10 21:08 2楼
当前连通块为欧拉回路时,答案为 n + 1
当前连通块为欧拉道路时,答案为 n + 1
当前连通块为其他形式时,先构成欧拉道路,再加一,答案为 n + (sum[i]/2 - 1) + 1
欧拉回路的+1是因为那条回边是实边,而构成欧拉道路后,再构成欧拉回路的话,加的那条回边是虚边,不需要再数列中加入新的元素
Gravatarcodewaysky
2012-10-07 21:20 1楼

35. [POI 1999] 遗传密码

★★☆   输入文件:pie.in   输出文件:pie.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

原始生物的遗传密码是一个自然数序列 $K = ( a_1,...,a_n )$。

原始生物的特征是指在遗传密码中连续出现的数对 $( l , r )$ ,即存在自然数 $i$ 使得 $l = a_i$ 且 $r = a_{i+1}$ 。

在原始生物的遗传密码中不存在形如 $( p , p )$ 的特征。

请根据读入的特征列表,计算包含这些特征的最短的遗传密码。

【输入格式】

第一行有一个正整数 $n$ ,表示遗传密码的特征数。

在接下来的 $n$ 行中,每行有一对自然数 $l$ 和 $r$ ,数对 $( l , r )$ 是原始生物的特征之一,特征不会在输入文件中重复出现。

【输出格式】

输出文件包含一个整数,表示包含输入的所有特征的最短遗传密码的长度。

【样例输入1】

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 

【样例输出1】

15

【样例输入输出2】

点击下载样例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$ ;