250.IndicatorMotionReverse

给你由’|', ‘/’, ‘-’, ‘\’组成的字符串,从第一个开始算,’|'到’/'是左转L,’|'到’\'是右转R,’|'到’|'是停止S,’|'到’-'是翻转F(依此类推)然后将这些LRSF命令符按一定规则缩写,得到最后字典序最小的一个

string getMinProgram(vector <string> actions)

这道250相对来说代码量略显大了点,不过按其规则模拟就好,最后注意99这比较容易出错的地方~

450.EscapingJail

给你一张完全图,求出距离最远的两点

int getMaxDistance(vector <string> chain)

直接一个floyd,然后找个最大值就好了,比250还简单=3=

1000.ContextFreeGrammars

告诉你一个结点可以生成的子树方案,现在给你根结点和最后叶子结点的序列,问你一共有多少种生成方案.

例如:
A ::= BD
B ::= bB | b | Bb
D ::= dD
D ::= d
告诉你根A,最后的叶子接顺序是bdd
那么有一种生成方案:
       A
     /   \
    B    D
    |   /  \
    b  d   D
            d

int countParsingTrees(vector<string> rules, char seed, string word)

绝对的难题啊~~一开始看到还以为解析字符比较恶心,但后来发现解析字符和后便的两个记忆化搜索比起来简直是太简单了,想了很久,主要是想到这种sample造成困扰

A ::= B | a
B ::= A
然后根是A,叶子顺序是a
这样子就会造成无限的循环XD,于是我就脑残掉了.
后来发现不存在这样的情况,也可能是我题目没读仔细= =

看了解题报告,写两个dfs(记忆化DP)不断的调用
long long dfs(int seed,int left,int right) //表示由根生出从left到right的叶子顺序的个数
long long DFS(int r,int pos,int left,int right) //表示由生长规则r从pos点开始衍生出从left到right的叶子顺序的个数
这题研究了好长时间，贴下代码纪念一下:

?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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

const int maxRule = 600;
const int maxPosRule = 50*50;
const int maxSeed = 26;
const int maxRuleLength = 50;
const LL limit = 1000000000;
 
char rule[maxRule][maxRuleLength];
int len[maxRule];
int offset[maxRule];
int start[maxSeed];
int end[maxSeed];
LL dp[maxSeed][35][35];
LL DP[maxPosRule][35][35];
string word;
 
 
LL dfs(int seed,int left,int right);
 
LL DFS(int r,int pos,int left,int right) {//从rule[r]的pos开始生成left到right
	if(pos >= len[r] || left > right)	return 0;
 
	LL &ret = DP[offset[r]+pos][left][right];
 
	if(ret != -1)	return ret;
	ret = 0;
	if(islower(rule[r][pos])) {
		if(rule[r][pos] == word[left]) {
			if(left == right && pos+1 == len[r]) {	//生成结束
				ret = 1;
			} else {
				ret = DFS(r,pos+1,left+1,right);
			}
		}
	} else {
		if(pos+1 == len[r]) {
			ret += dfs(rule[r][pos]-'A',left,right);
			if(ret > limit) {
				ret = limit + 1;
			}
		} else {
			for(int i = left ; i < right ; i ++) {
				ret += dfs(rule[r][pos]-'A',left,i) * DFS(r,pos+1,i+1,right);
				if(ret > limit) {
					ret = limit + 1;
					break;
				}
			}
		}
	}
	return ret;
}
 
LL dfs(int seed,int left,int right) {//由根seed生成left到right
	LL &ret = dp[seed][left][right];
	if(ret != -1) {
		return ret;
	}
	ret = 0;
	for(int r = start[seed] ; r < end[seed] ; r ++) {
		ret += DFS(r,0,left,right);
		if(ret > limit) {
			ret = limit + 1;
			break;
		}
	}
	return ret;
}
 
int ContextFreeGrammars::countParsingTrees(vector <string> rules, char Seed, string _word) {
	word = _word;
	int n = rules.size();
	int rulesNum = 0;
	FF(seed,26) {
		start[seed] = 99999;
	}
	FF(seed,26) {
		FF(i,n) {
			if(seed + 'A' != rules[i][0])	continue;
			int m = rules[i].size() - 1;
			FF(j,m) {
				if(rules[i][j] == ' ' && isalpha(rules[i][j+1]))  {
					if(start[seed] == 99999) {
						start[seed] = rulesNum;
					}
					j ++;
					int k = 0;
					while(j <= m && isalpha(rules[i][j])) {
						rule[rulesNum][k++] = rules[i][j++];
					}
					if(rulesNum == 0) {
						offset[0] = 0;
					} else {
						offset[rulesNum] = offset[rulesNum-1] + len[rulesNum-1];
					}
					len[rulesNum] = k;
					rule[rulesNum][k] = 0;
					end[seed] = ++rulesNum;
				}
			}
		}
	}
	CC(dp,-1);
	CC(DP,-1);
	int ans = dfs(Seed-'A',0,word.size()-1);
	return ans <= limit ? ans : -1;
}

Popularity: 7% [?]