TopCoder SRM 435 Summary

February 14, 2009 — gnarlycow

CellRemoval
简单题

?View Code CPP
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
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int c[55][55],num[55];
 
void dfs(int v)
{
	if(c[v][0]==0)
	{
		num[v]=1;
		return;
	}
	dfs(c[v][1]);
	dfs(c[v][2]);
	num[v]=num[c[v][1]]+num[c[v][2]];
}
 
class CellRemoval
{
public:
    int cellsLeft(vector <int> parent, int deletedCell)
    {
		memset(c,0,sizeof(c));
		memset(num,0,sizeof(num));
		int n=parent.size();
		int root=-1;
		for(int i=0;i<n;++i)
			if(parent[i]==-1) root=i;
			else c[parent[i]][++c[parent[i]][0]]=i;
		dfs(root);
		return num[root]-num[deletedCell];
    }
};

DNADeletion
本题难度比通常的Division1 500要大。num[i]表示前i个字符构成的字符串一定要用上最后一个字符时的答案数目，初始时num[0]=1。每个氨基酸可能对应多个“三碱基”，而我们在递推时，要尽可能用前面的碱基，这样能使后面的碱基得到充分利用，得到更长的蛋白质，还可以避免重复。把所有的num值加在一起，去掉空蛋白质的情况就可得到正确结果。

?View Code CPP
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <climits>
#include <cstring>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int next[3333][4],num[3333];
 
class DNADeletion
{
public:
    int differentProteins(vector <string> DNASequence, vector <string> codonTable)
    {
		const string S="AGCT";
		const int M=1000000007;
		string s,t,str;
		int n=codonTable.size();
		map <string,vector<vector<int> > > d;
		for(int i=0;i<DNASequence.size();++i) str+=DNASequence[i];
		for(int i=0;i<n;++i)
		{
			istringstream sin(codonTable[i]);
			sin>>s>>t;
			vector <int> m;
			for(int j=0;j<3;++j) m.push_back(S.find(s[j]));
			d[t].push_back(m);
		}
		int len=str.size();
		for(int i=0;i<4;++i) next[len][i]=-2;
		for(int i=len-1;i>=0;--i)
		{
			for(int j=0;j<4;++j) next[i][j]=next[i+1][j];
			next[i][S.find(str[i])]=i;
		}
		memset(num,0,sizeof(num));
		num[0]=1;
		for(int i=0;i<len;++i)
			for(map<string,vector<vector<int> > >::iterator it=d.begin();it!=d.end();++it)
			{
				int minP=INT_MAX;
				for(int j=0;j<it->second.size();++j)
				{
					int p=i;
					for(int k=0;k<3&&p>-1;++k) p=next[p][it->second[j][k]]+1;
					if(p>-1) minP=min(minP,p);
				}
				if(minP!=INT_MAX) num[minP]=(num[minP]+num[i])%M;
			}
		int ans=0;
		for(int i=1;i<=len;++i) ans=(ans+num[i])%M;
		return ans;
    }
};
Posted in SRM, TopCoder. Tags: , , . RSS feed for comments on this post.. TrackBack URL.

No Comments

1 Trackbacks

Leave a comment

«
»