题解 P2451 【[SDOI2005]遗传代码】

发表于 | 更新于 | 阅读次数：
本文字数： 1.5k | 阅读时长 ≈ 1 分钟
安利一下本蒟蒻的博客

题意

就是说第一行读入一个数$n$，

从第二行到第$n+1$行，每行读入两个数，分别是$l,r$，

你需要在这$2n$个数中找到一个最短的数列（题目中的遗传代码）使得在这个数列中的任意一个元素$a[i]=l[j]$，且$a[i+1]=r[j]$ ($j<=n$)

题目分析

当我们看到$l，r$这个范围的时候$（1 <= l <= 1000, 1 <= r <= 1000）$，我就想到了暴力 树

好的，让我们开始吧。

用$tl$数组记录$l$出现的次数，用$tr$数组记录$r$出现的次数,

记录初始答案$ans$为$n$，

如果出现了多余的l或r（即$tl>tr$时），

就可以让$ans$减去$tl-tr$,

最后输出$ans$就好了

题目的一个小小小的坑点

在primitivus的遗传代码中没有(p,p)特征。(题目原话)

什么意思呢？就是说如果$r[i]=l[l+1]$，那么$l[i],r[i],l[i+1],r[i+1]$只能算3个

具体栗子

如输入样例中的

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

$(2,8),(8,6)$在遗传代码中只能算成$(2,8,6)$三个数(在输出样例的说明中可以看出来$(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)$)

核心模板

  1. 存入$tr,tl$数组

    1
    2
    3
    4
    5
    6
    for(int i=0;i<n;++i)
    {
    	cin>>l[i]>>r[i];
    	tl[l[i]]++;
    	tr[r[i]]++;
    }

    $tl[l[i]]$是指$l[i]$出现的次数；

    $tr[r[i]]$是指$r[i]$出现的次数；

  2. 处理

    1
    2
    3
    4
    5
    6
    7
    for（int i=1;i<1000+1;++i）
    {
    	if（tr[i]>tl[i]）
    	{
    		sum+=tr[i]-tl[i];
    	}
    }

    如果$tr[i]>tl[i]$，也就是上文所说的多余的$l$和$r$(因为$l$和$r$是一一对应的)

最终的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#pragma GCC optimize(3)

#include<bits/stdc++.h>

using namespace std;

const int FFF=6666;

int n,l[FFF],r[FFF];
int tl[FFF],tr[FFF];
int maxx;
int sum;

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=0;i<n;++i)
	{
		cin>>l[i]>>r[i];
		tl[l[i]]++;
		tr[r[i]]++;
	}
	for（int i=1;i<1000+1;++i）
	{
		if（tr[i]>tl[i]）
		{
			sum+=tr[i]-tl[i];
		}
	}
	cout<<sum+n;
	return 0;
}