首页 > ACM题库 > HDU-杭电 > HDU 2875-DNA Sequence-待解决[解题报告]HOJ
2014
02-17

HDU 2875-DNA Sequence-待解决[解题报告]HOJ

DNA Sequence

问题描述 :

Deoxyribonucleic acid (DNA) is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms and some viruses. The main role of DNA molecules is the long-term storage of information. DNA is often compared to a set of blueprints or a recipe, or a code, since it contains the instructions needed to construct other components of cells, such as proteins and RNA molecules. The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in regulating the use of this genetic information.DNA structure can be described as DNA sequence, which can only be those consist of following four nucleotides named Adenine, Guanine, Cytosine and Thymine (We can address them A, G, C, T for simplicity). Property varies while the combination of nucleotide changes, thus even a tiny change in the chain of DNA sequence may lead to completely different appearance.

Prof. Adam C. Murphy is now working on a kind of DNA sequence that has more restrictions than ordinary ones. If a sequence’s substring matches any one of set {‘AA’, ‘CC’, ‘GG’, ‘TT’,‘AC’, ‘CA’, ‘CG’, ‘GC’, ‘GT’, ‘TG’}, the sequence is considered illegal.

Besides, an extra restriction comes: diving all the position of the sequence in groups as the sets indicate, every nucleotide must be unique in its set. For example, for given set {{1, 5, 11}, {2, 4}}, the nucleotide in position 1, 5 and 11 must be different for each pair. So is position 2 and 4.

Professor Adam C. Murphy wonders, with so many kinds of restrictions, whether a legal DNA sequence exists.

输入:

There are several cases in the input.For each case:

* The first line: two integers, N (1=<N<=100000) and M (1<=M<=1000). N represents the length of a DNA sequence; M represents the number of restrictions of the second kind.

* Line 2 to line M+1: each line contains one restriction. An integer ki (ki<=100), followed by ki integers a1,a2…aki,(1<=aki<=N) describing a set we mentioned above.

The position of nucleotides is numbered from 1, and all the numbers are separated by a space.

输出:

There are several cases in the input.For each case:

* The first line: two integers, N (1=<N<=100000) and M (1<=M<=1000). N represents the length of a DNA sequence; M represents the number of restrictions of the second kind.

* Line 2 to line M+1: each line contains one restriction. An integer ki (ki<=100), followed by ki integers a1,a2…aki,(1<=aki<=N) describing a set we mentioned above.

The position of nucleotides is numbered from 1, and all the numbers are separated by a space.

样例输入:

7 2
3 1 2 4
4 2 4 5 7

样例输出:

Yes
Hint

Hint ATAGATC is a legal DNA sequence for the sample.

 


  1. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了