Ponk Warshall(文字列)
練習試合で行った問題を記録してください.以下は問題面です.
Listening to the rock music permutes your nuclear DNA. This astonishing and unbelievablefact was recently published in the Rock Nature Weekly, one of the top scientifific journals onthe planet. Part of the research was to take DNA samples from volunteers, both before andafter the rock concerts season. The samples were processed and various genes isolated from thesamples. For each person, each gene was isolated twice: The variant before the rock season andthe variant after the season. These two variants were paired and in many cases one variant wasfound to be some permutation of the other variant in the pair.
The next step in the research is to determine how the permutations happen. The prevalenthypothesis suggests that a permutation is composed of a sequence of transpositions, so-calledswaps. A swap is an event (its chemistry is not fully understood yet) in which exactly twonucleobases in the gene exchange their places in the gene. No other nucleobases in the geneare affffected by the swap. The positions of the two swapped nucleobases might be completelyarbitrary.
To predict and observe the movement of the molecules in the permutation process, the researchers need to know the theoretical minimum number of swaps which can produce a particular permutation of nucleobases in a gene. We remind you that the nuclear DNA gene is asequence of nucleobases cytosine, guanine, adenine, and thymine, which are coded as C, G, A,and T, respectively. Input Specification
The input contains two text lines. Each line contains a string of N capital letters “A”, “C”, “G”, or “T”, (1≤N≤106)(1 ≤ N ≤ 10^6)(1≤N≤106). The two strings represent one pair of a particular gene versions. The first line represents the gene before the rock season, the second line represents the same gene from the same person after the rock season. The number of occurrences of each nucleobase is the same in both strings. Output Specification
Output the minimum number of swaps that transform the first gene version into the second one.
サンプル入力1
CGATA ATAGC
サンプル出力1
2
サンプル入力2
CTAGAGTCTA TACCGTATAG
サンプル出力2
7
大体の問題:
2つの文字列が与えられ、文字列には4つのアルファベットしか含まれていません.CTAG、題意の4つの塩基を指します.もちろん、これは重要ではありません.それから、設計プログラムに、最初の文字列が少なくとも何回の2つの交換を経て2番目の文字列になることができるかを求めます.
大まかな考え方:
1番目の文字列には、次の4つのケースがあります.
1:自分で上下に対応して、例えばサンプル1の中にAが与えられた时に対応して、このような情况は入力する时continueで、彼を考虑する必要はありません2:1回交换して、2つのアルファベットを消して、例えばサンプル1の出力はこのように得て、2回交换して4つのアルファベットを消しました.3:2回交換して、3つ消します.4:3回交換して、4つ消します.サンプル2の出力は、最初の文字列から2回行う場合3、もう一度行う場合4、すべてのアルファベットを消去し、2+2+3で7になります.
では、この4つの場合、処理順序は異なり、まず第1の場合は直接スキップされ、第2の場合から、明らかに第2の場合は第3の場合より優れ、第3の場合は第4の場合より優れている.だから処理の順序はまずすべての第2の情況を探し出して、それからすべての第3の情況を探して、最後に残りはすべて第4の情況です.
データを格納する際に2次元配列numbers[4][4]を選択し、1番目の文字列と2番目の文字列の各アルファベットの対応関係を表す.
次はACコードです.
Listening to the rock music permutes your nuclear DNA. This astonishing and unbelievablefact was recently published in the Rock Nature Weekly, one of the top scientifific journals onthe planet. Part of the research was to take DNA samples from volunteers, both before andafter the rock concerts season. The samples were processed and various genes isolated from thesamples. For each person, each gene was isolated twice: The variant before the rock season andthe variant after the season. These two variants were paired and in many cases one variant wasfound to be some permutation of the other variant in the pair.
The next step in the research is to determine how the permutations happen. The prevalenthypothesis suggests that a permutation is composed of a sequence of transpositions, so-calledswaps. A swap is an event (its chemistry is not fully understood yet) in which exactly twonucleobases in the gene exchange their places in the gene. No other nucleobases in the geneare affffected by the swap. The positions of the two swapped nucleobases might be completelyarbitrary.
To predict and observe the movement of the molecules in the permutation process, the researchers need to know the theoretical minimum number of swaps which can produce a particular permutation of nucleobases in a gene. We remind you that the nuclear DNA gene is asequence of nucleobases cytosine, guanine, adenine, and thymine, which are coded as C, G, A,and T, respectively. Input Specification
The input contains two text lines. Each line contains a string of N capital letters “A”, “C”, “G”, or “T”, (1≤N≤106)(1 ≤ N ≤ 10^6)(1≤N≤106). The two strings represent one pair of a particular gene versions. The first line represents the gene before the rock season, the second line represents the same gene from the same person after the rock season. The number of occurrences of each nucleobase is the same in both strings. Output Specification
Output the minimum number of swaps that transform the first gene version into the second one.
サンプル入力1
CGATA ATAGC
サンプル出力1
2
サンプル入力2
CTAGAGTCTA TACCGTATAG
サンプル出力2
7
大体の問題:
2つの文字列が与えられ、文字列には4つのアルファベットしか含まれていません.CTAG、題意の4つの塩基を指します.もちろん、これは重要ではありません.それから、設計プログラムに、最初の文字列が少なくとも何回の2つの交換を経て2番目の文字列になることができるかを求めます.
大まかな考え方:
1番目の文字列には、次の4つのケースがあります.
1:自分で上下に対応して、例えばサンプル1の中にAが与えられた时に対応して、このような情况は入力する时continueで、彼を考虑する必要はありません2:1回交换して、2つのアルファベットを消して、例えばサンプル1の出力はこのように得て、2回交换して4つのアルファベットを消しました.3:2回交換して、3つ消します.4:3回交換して、4つ消します.サンプル2の出力は、最初の文字列から2回行う場合3、もう一度行う場合4、すべてのアルファベットを消去し、2+2+3で7になります.
では、この4つの場合、処理順序は異なり、まず第1の場合は直接スキップされ、第2の場合から、明らかに第2の場合は第3の場合より優れ、第3の場合は第4の場合より優れている.だから処理の順序はまずすべての第2の情況を探し出して、それからすべての第3の情況を探して、最後に残りはすべて第4の情況です.
データを格納する際に2次元配列numbers[4][4]を選択し、1番目の文字列と2番目の文字列の各アルファベットの対応関係を表す.
次はACコードです.
#include
using namespace std;
int numbers[4][4];
mapdir;
int FFF(char a,char b,char c)
{
int ans=0;
int x=(min(numbers[dir[a]][dir[b]],min(numbers[dir[b]][dir[c]],numbers[dir[c]][dir[a]])));
int y=(min(numbers[dir[a]][dir[c]],min(numbers[dir[b]][dir[a]],numbers[dir[c]][dir[b]])));
ans+=2*(x+y);
numbers[dir[a]][dir[b]]-=x;
numbers[dir[b]][dir[c]]-=x;
numbers[dir[c]][dir[a]]-=x;
numbers[dir[a]][dir[c]]-=y;
numbers[dir[b]][dir[a]]-=y;
numbers[dir[c]][dir[b]]-=y;
return ans;
}
int main()
{
dir['A']=0;dir['C']=1;dir['G']=2;dir['T']=3;
char check[4]={'A','C','G','T'};
for(int i=0;i<4;i++)for(int j=0;j<4;j++)numbers[i][j]=0;
string A,B;cin>>A>>B;
int len=A.size();
int ans=0;
for(int i=0;i=numbers[j][i])
{
numbers[i][j]-=numbers[j][i];
ans+=numbers[j][i];
numbers[j][i]=0;
}
else
{
numbers[j][i]-=numbers[i][j];
ans+=numbers[i][j];
numbers[i][j]=0;
}
}
}
for(int i=0;i<2;i++)
{
for(int j=i+1;j<3;j++)
{
for(int k=j+1;k<4;k++)
{
ans+=FFF(check[i],check[j],check[k]);
}
}
}
for(int i=1;i<4;i++)
{
ans+=3*numbers[0][i];
}
cout<