# POJ 3070-Fibonacci

POJ 3070-Fibonacci

Fibonacci
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14933 Accepted: 10500

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

An alternative formula for the Fibonacci sequence is

.

Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

0
9
999999999
1000000000
-1

Sample Output

0
34
626
6875

Hint

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

.

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

.

Source

Stanford Local 2006

typedef long long LL;
LL Fib1(int n) {
if (n == 0)return 0;
if (n == 1)return 1;
return Fib1(n - 1) + Fib1(n - 2);
}


LL Fib2(int n) {
if (n == 0)return 0;
if (n == 1)return 1;
LL fn_2 = 0, fn_1 = 1, ans = 0;
for (int i = 2; i <= n; ++i) {
ans = fn_1 + fn_2;
fn_2 = fn_1;
fn_1 = ans;
}
return ans;
}


const int MAXN = 2;
vector<vector<LL>> multi(const vector<vector<LL>> &mat1, const vector<vector<LL>> &mat2) {
vector<vector<LL>> mat(MAXN, vector<LL>(MAXN, 0));
for (int i = 0; i < MAXN; ++i) {
for (int j = 0; j < MAXN; ++j) {
for (int k = 0; k < MAXN; ++k) {
mat[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
return mat;
}
vector<vector<LL>> fastPow(vector<vector<LL>> &mat1, int n) {
vector<vector<LL>> mat(MAXN, vector<LL>(MAXN, 0));
for (int i = 0; i < MAXN; ++i)mat[i][i] = 1;
while (n != 0) {
if (n & 1)mat = multi(mat, mat1);
mat1 = multi(mat1, mat1);
n >>= 1;
}
return mat;
}
LL Fib3(int n) {
if (n == 0)return 0;
if (n == 1)return 1;
vector<vector<LL>> mat = { {1,1},{1,0} };
vector<vector<LL>> matN = fastPow(mat, n);
return matN[0][1];
}


POJ这题的代码如下，古老的POJ居然不支持第37行的vector初始化，崩溃。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
const int MAXN = 2;
const int MOD = 10000;
vector<vector<LL>> multi(const vector<vector<LL>> &mat1, const vector<vector<LL>> &mat2) {
vector<vector<LL>> mat(MAXN, vector<LL>(MAXN, 0));
for (int i = 0; i < MAXN; ++i) {
for (int j = 0; j < MAXN; ++j) {
for (int k = 0; k < MAXN; ++k) {
mat[i][j] = (mat[i][j] + mat1[i][k] * mat2[k][j]) % MOD;
}
}
}
return mat;
}
vector<vector<LL>> fastPow(vector<vector<LL>> &mat1, int n) {
vector<vector<LL>> mat(MAXN, vector<LL>(MAXN, 0));
for (int i = 0; i < MAXN; ++i)mat[i][i] = 1;
while (n != 0) {
if (n & 1)mat = multi(mat, mat1);
mat1 = multi(mat1, mat1);
n >>= 1;
}
return mat;
}
LL Fib3(int n) {
if (n == 0)return 0;
if (n == 1)return 1;
//vector<vector<LL>> mat = { { 1,1 },{ 1,0 } };
//-----------------------
vector<vector<LL>> mat;
vector<LL> r1;
r1.push_back(1), r1.push_back(1);
vector<LL> r2;
r2.push_back(1), r2.push_back(0);
mat.push_back(r1);
mat.push_back(r2);
//----------------------
vector<vector<LL>> matN = fastPow(mat, n);
return matN[0][1];
}
int main() {
int n;
while (scanf("%d", &n) && n != -1) {
LL ans = Fib3(n);
printf("%d\n", ans%MOD);
}
return 0;
}


# POJ 2369-Permutations

POJ 2369-Permutations
Permutations
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2792 Accepted: 1473
Description
We remind that the permutation of some final set is a one-to-one mapping of the set onto itself. Less formally, that is a way to reorder elements of the set. For example, one can define a permutation of the set {1,2,3,4,5} as follows:

This record defines a permutation P as follows: P(1) = 4, P(2) = 1, P(3) = 5, etc.
What is the value of the expression P(P(1))? It’s clear, that P(P(1)) = P(4) = 2. And P(P(3)) = P(5) = 3. One can easily see that if P(n) is a permutation then P(P(n)) is a permutation as well. In our example (believe us)

It is natural to denote this permutation by P2(n) = P(P(n)). In a general form the defenition is as follows: P(n) = P1(n), Pk(n) = P(Pk-1(n)). Among the permutations there is a very important one — that moves nothing:

It is clear that for every k the following relation is satisfied: (EN)k = EN. The following less trivial statement is correct (we won't prove it here, you may prove it yourself incidentally): Let P(n) be some permutation of an N elements set. Then there exists a natural number k, that Pk = EN. The least natural k such that Pk = EN is called an order of the permutation P.
The problem that your program should solve is formulated now in a very simple manner: "Given a permutation find its order."
Input
In the first line of the standard input an only natural number N (1 <= N <= 1000) is contained, that is a number of elements in the set that is rearranged by this permutation. In the second line there are N natural numbers of the range from 1 up to N, separated by a space, that define a permutation — the numbers P(1), P(2),…, P(N).
Output
You should write an only natural number to the standard output, that is an order of the permutation. You may consider that an answer shouldn't exceed 109.
Sample Input
5
4 1 5 2 3
Sample Output
6
Source
Ural State University Internal Contest October'2000 Junior Session

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 1005;
bool visited[kMaxN];
int permutation[kMaxN];
//最大公约数
int gcd(int x, int y)
{
int tmp;
while (y)
{
tmp = y;
y = x % y;
x = tmp;
}
return x;
}
int main()
{
int n,ans,len;
while (scanf("%d", &n)!=EOF)
{
ans = 1;
memset(visited, false, n + 1);
for (int i = 1; i <= n; i++)
scanf("%d", &permutation[i]);
for (int i = 1; i <= n; i++)
{
if (!visited[i])
{
visited[i] = true;
int j = permutation[i];
len = 1;
while (j!=i)
{
visited[j] = true;
j = permutation[j];
len++;
}
ans = len*ans/gcd(ans, len);//gcd(a, b)×lcm(a, b) = ab
}
}
printf("%dn", ans);
}
return 0;
}


# POJ 2352-Stars

POJ 2352-Stars
Stars
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 36453 Accepted: 15852
Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.

For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
Source
Ural Collegiate Programming Contest 1999

#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 32005;//NOT 15005;
int n;
int level[kMaxN];
int c[kMaxN];
int lowbit(int x)
{
return x&(-x);
}
int sum(int i)
{
int rs = 0;
while (i > 0)
{
rs += c[i];
i -= lowbit(i);
}
return rs;
}
{
while (i <= kMaxN)
{
c[i]+=val;
i += lowbit(i);
}
}
int main()
{
scanf("%d", &n);
int x, y;
for (int i = 0; i < n; i++)
{
scanf("%d %d", &x, &y);
x++;
level[sum(x)]++;
}
for (int i = 0; i < n; i++)
printf("%dn", level[i]);
return 0;
}


[1]. http://www.cnblogs.com/Creator/archive/2011/09/10/2173217.html

# POJ 1386-Play on Words

POJ 1386-Play on Words
Play on Words
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10039 Accepted: 3441
Description
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm'' can be followed by the word motorola''. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".
Sample Input
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
Sample Output
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
Source
Central Europe 1999

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int M=26;
int n,used;
vector<vector<string> > s;
//vector<string> rs;//rs内字符串的先后顺序就是这个游戏的先后顺序
bool dfs(string last)
{
//rs.push_back(last);//记录字符串
used++;
if(used==n)
return true;
else
{
int c=last[last.size()-1]-'a';
int sz=s.size();
for(int i=0;i<sz;i++)
{
if(dfs(s[i]))
return true;
else
used--;//rs.pop_back();//回溯
}
return false;
}
}
int main()
{
//freopen("input.txt","r",stdin);
int t;
string tmp;
cin>>t;
while(t--)
{
cin>>n;
s.clear();
s.resize(M);
for(int i=0;i<n;i++)
{
cin>>tmp;
s[tmp[0]-'a'].push_back(tmp);
}
bool success=false;
for(int i=0;i<M;i++)
{
int sz=s[i].size();
for(int j=0;j<sz;j++)
{
used=0;
success=false;
if(dfs(s[i][j]))
{
success=true;
break;
}
}
if(success)
break;
}
if(success)
cout<<"Ordering is possible."<<endl;
else
cout<<"The door cannot be opened."<<endl;
}
return 0;
}


1.无向连通图G是欧拉图，当且仅当G不含奇数度结点(G的所有结点度数为偶数)；
2.无向连通图G含有欧拉通路，当且仅当G有零个或两个奇数度的结点；
3.有向连通图D是欧拉图，当且仅当D的基图（即其无向图）为连通图且D中每个结点的入度=出度
4.有向连通图D含有欧拉通路，当且仅当D的基图（即其无向图）为连通图且D中除两个结点外，其余每个结点的入度=出度，且此两点满足deg－(u)－deg+(v)=±1。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的入度=出度）
5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环。
6.如果图G是欧拉图且 H = G - uv，则H有奇数个u,v-迹仅在最后访问v；同时，在这一序列的u,v-迹中，不是路径的迹的条数是偶数。(Todia[1973])

#include<iostream>
#include<string>
using namespace std;
const int M=26;
int n;
int showed[M];//showed[i]表示点i出现过，也就是有边连在i点
int G[M][M];//图
int father[M];//并查集
int degree[M][2];//degree[i][0]入度；degree[i][1]出度
void init_data()
{
for(int i=0;i<M;i++)
{
father[i]=i;
showed[i]=0;
degree[i][0]=0;
degree[i][1]=0;
for(int j=0;j<M;j++)
G[i][j]=0;
}
}
int find_father(int x)
{
return x==father[x]?x:(father[x]=find_father(father[x]));
}
void union_father(int x,int y)
{
father[find_father(x)]=find_father(y);
}
//判断有边的点是否属于一个集合
bool is_one_set()
{
int root=-1;
for(int i=0;i<M;i++)
{
if(showed[i]==1)//有边
{
int tmp=find_father(i);
if(root==-1)
root=tmp;
else if(tmp!=root)
return false;
}
}
return true;
}
bool judge()
{
if(!is_one_set())
return false;
else
{
for(int i=0;i<M;i++)
{
for(int j=0;j<M;j++)
{
if(G[i][j]!=0)
{
degree[i][1]+=G[i][j];
degree[j][0]+=G[i][j];
}
}
}
int a=0,b=0;//a:入度-出度=-1的个数；b:入度-出度=1的个数
for(int i=0;i<M;i++)
{
int rs=degree[i][0]-degree[i][1];
if(rs==-1)
a++;
else if(rs==1)
b++;
else if(rs!=0)
return false;
}
if((a==1&&b==1)||(a==0&&b==0))//欧拉回路或欧拉通路
return true;
return false;
}
}
int main()
{
//freopen("input.txt","r",stdin);
int t,a,b;
string tmp;
cin>>t;
while(t--)
{
cin>>n;
init_data();
for(int i=0;i<n;i++)
{
cin>>tmp;
a=tmp[0]-'a';
b=tmp[tmp.size()-1]-'a';
showed[a]=1;
showed[b]=1;
G[a][b]++;//首字母指向尾字母的边
union_father(a,b);//首字母指向尾字母的边
}
if(judge())
cout<<"Ordering is possible."<<endl;
else
cout<<"The door cannot be opened."<<endl;
}
return 0;
}


# POJ 1061-青蛙的约会

POJ 1061-青蛙的约会

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 92723 Accepted: 17043
Description

Input

Output

Sample Input
1 2 3 4 5
Sample Output
4
Source

(1)式和(2)式的解是完全等价的。

#include<stdio.h>
#define LL long long
LL x,y,m,n,L,k0,t0,d;//k0,t0为某一组解，d为最大公因数
//求a,b的最大公因数
LL gcd(LL a,LL b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
//扩展欧几里得算法求ax+by=gcd(a,b)的一组解(x,y)
void extended_euclid(LL a,LL b,LL& x,LL& y)
{
if(b==0)
{
x=1;
y=0;
}
else
{
extended_euclid(b,a%b,x,y);
LL tmp=x;
x=y;
y=tmp-(a/b)*y;
}
}
int main()
{
//freopen("input.txt","r",stdin);
LL a,b;
while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L)!=EOF)
{
if(m==n)//因为青蛙起点不一样，如果速度一样，肯定不可能相遇
{
printf("Impossible\n");
continue;
}
a=m-n;
b=y-x;
if(a<0)//扩展欧几里得需要非负数
{
a=-a;
b=-b;
}
d=gcd(a,L);
if(b%d!=0)
{
printf("Impossible\n");
continue;
}
a/=d;
L/=d;
b/=d;
extended_euclid(a,L,k0,t0);
k0*=b;
t0*=b;//无需求解，没用到
if(k0>0)
k0=k0%L;
else
k0=k0%L+L;
printf("%lld\n",k0);
}
return 0;
}


# POJ 1163-The Triangle

POJ 1163-The Triangle
The Triangle
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 38525 Accepted: 23126
Description

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Source
IOI 1994

DP水题一个，如果将等边三角形转换成Sample Input里的等腰直角三角形，设则某一点的路径和为sum[i][j]，则因为只能从(i-1,j)和(i-1,j-1)这两个点到达(i,j)，所以sum[i][j]=max{sum[i-1][j],sum[i-1][j-1]}+triangle[i][j]。如果为了节省空间，j可以从i downto 0循环，也就是DP表从右往左填，这样只需要一行空间。

#include<iostream>
using namespace std;
const int MAX_N=101;
int triangle[MAX_N][MAX_N];
int sum[MAX_N]={0};
int DP(int n)
{
int rs=0;
for(int i=0;i<n;i++)
{
for(int j=i;j>=0;j--)//从右往左填表，只需一行空间
{
if(j>0)
{
sum[j]=(sum[j]>sum[j-1]?sum[j]:sum[j-1])+triangle[i][j];
}
else if(j==0)
{
sum[j]+=triangle[i][j];
}
if(sum[j]>rs)//记录最大值
rs=sum[j];
}
}
/*int rs=0;
for(int i=0;i<n;i++)
if(sum[i]>rs)
rs=sum[i];*/
return rs;
}
int main()
{
//freopen("input.txt","r",stdin);
int n;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
cin>>triangle[i][j];
cout<<DP(n);
return 0;
}


# POJ 1330-Nearest Common Ancestors

POJ 1330-Nearest Common Ancestors
Nearest Common Ancestors
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 19432 Accepted: 10292
Description
A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.
For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.
Write a program that finds the nearest common ancestor of two distinct nodes in a tree.
Input
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.
Output
Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.
Sample Input
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
Sample Output
4
3
Source
Taejon 2002

#include<iostream>
#include<vector>
using namespace std;
int main()
{
//freopen("input.txt","r",stdin);
int t,n;
int node1,node2;
cin>>t;
while(t--)
{
cin>>n;
vector<int> s_f(n+1,0);//s_f[i]为第i个节点的父亲，开始时所有节点的父亲为0
for(int i=0;i<n-1;i++)
{
cin>>node1>>node2;
s_f[node2]=node1;//保存输入关系
}
cin>>node1>>node2;
vector<int> node1_father(n+1,0);//node1的父亲
node1_father[node1]=1;//自己是自己的祖先
while(s_f[node1]!=0)
{
node1_father[s_f[node1]]=1;//记录哪些点是node1的父亲
node1=s_f[node1];
}
if(node1_father[node2]!=0)//node2也是自己的祖先
{
cout<<node2<<endl;
continue;
}
while(s_f[node2]!=0)
{
if(node1_father[s_f[node2]]!=0)//从下网上找node2的祖先是否出现在node1的祖先里
{
cout<<s_f[node2]<<endl;
break;
}
else
node2=s_f[node2];
}
}
return 0;
}


# POJ 1080-Human Gene Functions

POJ 1080-Human Gene Functions
Human Gene Functions
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17334 Accepted: 9637
Description
It is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for them.
A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determine its function.
One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions – many researchers have been submitting their genes and functions to the database and the database is freely accessible through the Internet.
A database search will return a list of gene sequences from the database that are similar to the query gene.
Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed.
Your job is to make a program that compares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one.
Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity
of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of
the genes to make them equally long and score the resulting genes according to a scoring matrix.
For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in –GT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal
length. These two strings are aligned:
AGTGAT-G
-GT--TAG
In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.
![](http://poj.org/images/1080/1080_1.gif)
denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.
Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):
AGTGATG
-GTTA-G
This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the
similarity of the two genes is 14.
Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each test case consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The length of each gene sequence is at least one and does not exceed 100.
Output
The output should print the similarity of each test case, one per line.
Sample Input
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
Sample Output
14
21
Source
Taejon 2001

1. s1取第i个基因，s2取'-'，则f[i,j]=f[i-1,j]+score[s1[i]],'-'];
2. s1取'-'，s2取第j个基因，则f[i,j]=f[i,j-1]+score['-',s2[j]];
3. s1取第i个基因，s2取第j个基因，则f[i,j]=f[i-1,j-1]+score[s1[i],s2[j]];

#include<iostream>
#include<string>
using namespace std;
int score['T'+1]['T'+1];
int inf=-5;//负无穷
const int MAX_N=101;//基因最大长度
int f[MAX_N][MAX_N];//f[i][j]表示s1[0...i-1]和s2[0...j-1]的相识度
//初始化分数表
void init_score()
{
score['A']['A']=score['C']['C']=score['G']['G']=score['T']['T']=5;//可以连续赋值
score['-']['-']=inf;//负无穷
score['A']['C']=score['C']['A']=-1;
score['A']['G']=score['G']['A']=-2;
score['A']['T']=score['T']['A']=-1;
score['A']['-']=score['-']['A']=-3;//'-'的ASCII小于'T'
score['C']['G']=score['G']['C']=-3;
score['C']['T']=score['T']['C']=-2;
score['C']['-']=score['-']['C']=-4;
score['G']['T']=score['T']['G']=-2;
score['G']['-']=score['-']['G']=-2;
score['T']['-']=score['-']['T']=-1;
}
//动态规划求值
int DP(string s1,int n1,string s2,int n2)
{
f[0][0]=0;
for(int i=1;i<=n1;i++)
//f[0][i]=f[0][i-1]+score['-'][s1[i-1]];//注意顺序不要弄错了，这里表示i,s1为纵轴；j,s2为横轴
f[i][0]=f[i-1][0]+score[s1[i-1]]['-'];
for(int j=1;j<=n2;j++)
//f[j][0]=f[j-1][0]+score[s2[j-1]]['-'];
f[0][j]=f[0][j-1]+score['-'][s2[j-1]];
for(int i=1;i<=n1;i++)
{
for(int j=1;j<=n2;j++)
{
int a=f[i-1][j]+score[s1[i-1]]['-'];
int b=f[i][j-1]+score['-'][s2[j-1]];
int c=f[i-1][j-1]+score[s1[i-1]][s2[j-1]];
int rs=a>b?a:b;
f[i][j]=rs>c?rs:c;//三者最大值
}
}
return f[n1][n2];
}
int main()
{
//freopen("input.txt","r",stdin);
int t;
cin>>t;
init_score();
while(t--)
{
int n1,n2;
string s1,s2;
cin>>n1>>s1>>n2>>s2;
cout<<DP(s1,n1,s2,n2)<<endl;
}
return 0;
}


# POJ 1094-Sorting It All Out

POJ 1094-Sorting It All Out
Sorting It All Out
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 28397 Accepted: 9814
Description
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
Sample Input
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
Sample Output
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
Source
East Central North America 2001

Kahn算法

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)


L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
select an unmarked node n
visit(n)
function visit(node n)
if n has a temporary mark then stop (not a DAG)
if n is not marked (i.e. has not been visited yet) then
mark n temporarily
for each node m with an edge from n to m do
visit(m)
mark n permanently
unmark n temporarily


#include<iostream>
//#include<set>
#include<list>
#include<string>
#include<vector>
using namespace std;
int n,m;
const int MAX_N=26;
const int MAX_DIS=10000;
//*******这些都是维基百科关于拓扑排序（DFS版）里的变量含义
int temporary[MAX_N];
int permanent[MAX_N];
int marked[MAX_N];
//*******************************
int path[MAX_N][MAX_N];
//int dfs_visited[MAX_N];
list<int> L;//拓扑排序生产的顺序链
bool isDAG;//DAG=directed acyclic graph，无回路有向图
//每一个测试用例都要初始化路径
void init_path()
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
path[i][j]=0;
}
//每一次拓扑排序都要初始化temporary，permanent，marked
void init_tpm()
{
isDAG=true;
L.clear();
for(int i=0;i<n;i++)
{
temporary[i]=0;
permanent[i]=0;
marked[i]=0;
}
}
//递归访问。具体看维基百科
void visit(int i)
{
if(temporary[i]==1)
{
isDAG=false;
return;
}
else
{
if(marked[i]==0)
{
marked[i]=1;
temporary[i]=1;
for(int j=0;j<n;j++)
{
if(path[i][j]==1)
{
visit(j);
}
}
permanent[i]=1;
temporary[i]=0;
L.push_front(i);
}
}
}
/*
void init_dfs()
{
for(int i=0;i<n;i++)
dfs_visited[i]=0;
}*/
/*
//DFS有缺陷
void DFS(int v)
{
if(dfs_visited[v]==0)
{
dfs_visited[v]=1;
for(int i=0;i<n;i++)
{
if(dfs_visited[i]==0&&path[v][i]==1)
{
DFS(i);
}
}
}
}*/
//使用Floyd算法来判断生产的拓扑排序是否是严格有序的
bool Floyd()
{
int copy_path[MAX_N][MAX_N];
for(int i=0;i<n;i++)//首先复制一份路径图
for(int j=0;j<n;j++)
{
copy_path[i][j]=path[i][j];
if(i!=j&&copy_path[i][j]==0)//如果原来两点距离为0，说明他们是不直接连通的
copy_path[i][j]=MAX_DIS;//置为无穷
}
//floyd算法
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) if(copy_path[i][j]>copy_path[i][k]+copy_path[k][j])
copy_path[i][j]=copy_path[i][k]+copy_path[k][j];
vector<int> seq;//把原来用链表的拓扑序列转换成数组，方便后面的操作
list<int>::iterator it=L.begin();
while(it!=L.end())
{
seq.push_back(*it);
it++;
}
//如果这个拓扑链是严格有序的话，则前面的元素到后面的元素一定是可达的。
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++) { if(copy_path[seq[i]][seq[j]]>=MAX_DIS)//如果不可达，则不是严格有序的。
return false;
}
}
return true;
}
//拓扑排序DFS版本。返回0：有回路；1：虽然是拓扑排序，但非连通（不是严格有序）；2：是拓扑排序且连通（严格有序）（即任意两个元素都可以比较大小）
int topological_sorting()
{
for(int i=0;i<n;i++)
{
if(marked[i]==0)
{
visit(i);
}
}
if(!isDAG)
return 0;
else
{
/*init_dfs();
DFS(*L.begin());
for(int i=0;i<n;i++) { if(dfs_visited[i]==0) { return 1; } }*/ if(Floyd()) return 2; else return 1; } } int main() { //freopen("input.txt","r",stdin); string tmp; while(cin>>n>>m&&n&&m)
{
init_path();
vector<string> relations(m);
int i;
for(i=0;i<m;i++)//一次性把所有输入都存起来，免得后续麻烦 { cin>>relations[i];
}
int rs=-1;
for(i=0;i<m;i++)//每增加一个关系，都要重新拓扑排序一次
{
init_tpm();//每次都要初始化
tmp=relations[i];
path[tmp[0]-'A'][tmp[2]-'A']=1;
rs=topological_sorting();
if(rs==0)
{
cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
break;//如果是回路的话，后续的输入可以跳过
}
else if(rs==2)//成功
{
cout<<"Sorted sequence determined after "<<i+1<<" relations: ";
list<int>::iterator it=L.begin();
while(it!=L.end())
{
char c='A'+*it;
cout<<c;
it++;
}
cout<<"."<<endl;
break;//后续输入跳过
}
}
if(i==m&&rs==1)//如果处理完所有输入都没有形成严格有序的拓扑序列
cout<<"Sorted sequence cannot be determined."<<endl;
}
return 0;
}


# POJ 2263-Heavy Cargo

POJ 2263-Heavy Cargo
Heavy Cargo
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3549 Accepted: 1894
Description
Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive.
Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.
Input
The input will contain one or more test cases. The first line of each test case will contain two integers: the number of cities n (2<=n<=200) and the number of road segments r (1<=r<=19900) making up the street network.
Then r lines will follow, each one describing one road segment by naming the two cities connected by the segment and giving the weight limit for trucks that use this segment. Names are not longer than 30 characters and do not contain white-space characters. Weight limits are integers in the range 0 - 10000. Roads can always be travelled in both directions.
The last line of the test case contains two city names: start and destination.
Input will be terminated by two values of 0 for n and r.
Output
For each test case, print three lines:
a line saying "Scenario #x" where x is the number of the test case
a line saying "y tons" where y is the maximum possible load
a blank line
Sample Input
4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0
Sample Output
Scenario #1
80 tons
Scenario #2
170 tons
Source
Ulm Local 1998

#include<iostream>
#include<map>
#include<string>
using namespace std;
const int MAX_N=202;
//初始化数据
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
}
//改造Floyd算法
void Floyd(int n)
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
{
}
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
int n,r;
int case_num=1;
while(cin>>n>>r&&n&&r)
{
map<string,int> city_index;//保存城市和下标的对应关系
string city1,city2;
int w;
int i=0;
while(r--)
{
cin>>city1>>city2>>w;
if(city_index.find(city1)==city_index.end())
city_index[city1]=i++;
if(city_index.find(city2)==city_index.end())
city_index[city2]=i++;