XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 5-9UVa1596 - Bug Hunt

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 3.8k 阅读时长 ≈ 3 分钟

//开学了，好烦啊啊啊啊啊！怎么开个学那么多破事情！！都俩星期了，终于有时间写出来一道题 题意：不难理解，不写了。这几天忙的心累。

代码：（Accepted， 0.010s）

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
//UVa1596 - Bug Hunt
#include<iostream>
#include<sstream>
#include<string>
#include<stack>
#include<map>
using namespace std;

struct o_O {
	int size;
	map<int, int> dim;
};
map<string, o_O> dat;
string line;

bool get(stack<string>& st,int& num) {
	while (!st.empty()) {
		if (num >= dat[st.top()].size) return false;
		if (!dat[st.top()].dim.count(num)) return false;
		num = dat[st.top()].dim[num];
		st.pop();
	}
	return true;
}


bool declare() {//定义数组
	for (auto& r : line)
		if (r == '[' || r == ']') r = ' ';
	istringstream in(line);
	string na;
	int nu;
	in >> na >> nu;
	dat[na].size = nu;
	return nu >= 0;
}

bool solve(){//处理赋值
	for (auto& r : line)
		if (r == '[' || r == ']' || r == '=') r = ' ';
	stack<string> stl, str;
	int numl, numr;
	istringstream in(line);
	string now,sl;
	in >> sl;
	while (in >> now && now[0] > '9') stl.push(now);
	istringstream inl(now);inl >> numl;
	while (in >> now && now[0] > '9') str.push(now);
	istringstream inr(now);inr >> numr;
	if (!get(stl, numl) || !get(str, numr)) return false;
	if (numl >= dat[sl].size) return false;
	dat[sl].dim[numl] = numr;
	return true;
}

int main()
{
	//freopen("in.txt", "r", stdin);//
	while (cin>>line && line[0] != '.') {
		unsigned flag = 0, linenum = 0;
		dat.clear();
		do {
			++linenum;
			if (flag) continue;
			if (!(line.find('=') == string::npos ? declare() : solve()))
				flag = linenum;
		} while (cin>>line && line[0] != '.');
		cout << flag << '\n';
	}
	return 0;
}

分析：给数组找bug，只有赋值和定义两种语句。一开始我想复杂了，以为会有诸如 a[b[c[0]=1]=d[2]]=e[e[e[e[e[e[3]]]=e[1]=e[2]=e[3]=233]]]=1 这种情况发生，于是就用递归做，做了好久，还老是WA（/* 实在难抽出一块一块的时间来学习，断断续续写了一星期，思路老是想到一半就断了。而且事情多烦的脑子疼，想不出东西。妈蛋还不如放假。*/） 结果昨天晚上一个老司机跟我说，干嘛那么烦，一行只有一个赋值。。。。。 好的，瞬间简单了。。今天花了一个小时不知道到不到就做出来了。可能是用了sstream，再转存到stack的原因，比较慢，用时10ms。

附：之前以为一行可以多个赋值的时候写的代码（更新：终于调试的AC了）： 代码：（Accepted， 0.010s）

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
//UVa1596 - Bug Hunt
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<map>
using namespace std;
string line;
queue<string> qu;
struct o_O {
	int len;
	map<int, int> def;
};
map<string, o_O> dat;

int get() {//从qu中get当前index的值，通过递归实现
	string now = qu.front();
	qu.pop();
	if (now[0] > '9') {//若为变量名，说明有嵌套
		int n = get();//得到当前变量的index
		qu.pop();
		if (n >= dat[now].len || n < 0) return -1;//数组越界
		if (qu.empty() || qu.front()[0] == '}') {//不是赋值，直接返回
			if (!dat[now].def.count(n)) return -1;//没初始化
			return dat[now].def[n];
		}
		return dat[now].def[n] = get();//赋值
	}
	int num;//若为数字
	istringstream iin(now);
	iin >> num;
	return num;
}

bool declare() {//定义数组
	for (auto& r : line)
		if (r == '[' || r == ']') r = ' ';
	istringstream in(line);
	string na;
	int nu;
	in >> na >> nu;
	dat[na].len = nu;
	return nu >= 0;
}

bool solve() {//预处理当前行
	for (auto& r : line)
		if (r == '[' || r == '=') r = ' ';
	istringstream in(line);
	string now;
	int num;
	while (in >> now) {
		if (now[0] > '9') qu.push(now);
		else {
			int i = 0;
			for (auto& r : now)
				if (r == ']') r = ' ', ++i;
			qu.push(now);
			while (i--) qu.push("}");//为什么要用}不用]，一开始想的是}的ASCII是125，而]夹在大小写字母之间。然而后来发现并没有什么卵用
		}
	}
	return get() >=0;
}

int main()
{
	//freopen("in.txt", "r", stdin);//
	while (getline(cin, line) && line[0] != '.') {
		unsigned flag = 0, linenum = 0;
		dat.clear();
		while (!qu.empty()) qu.pop();//queue不自带clear()的?!
		do {
			++linenum;
			if (flag) continue;
			if (!(line.find('=') == string::npos ? declare() : solve()))
				flag = linenum;
		} while (getline(cin, line) && line[0] != '.');
		cout << flag << '\n';
	}
	return 0;
}

虽然是我想多了，但是应用到单个赋值也是没问题的呀。但是还是想不通哪里就WA了。。。应该是哪个特殊的格式没考虑到。以后有心情再调试。（更新：终于调试得AC啦，代码已经覆盖更新。竟然也是0.010s。）