DBLOG
Astar 2016 邀请赛 简要题解
Doveccl
  2016-05-16 01:50:00   2020-12-18 02:49:51   1.9k 字  10 分钟  

题目链接：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=690

Problem A

题意

给一个数列，多次求数列子区间的区间积

解法

维护一个线段树，我用的是 zkw 线段树，做乘法的时候注意取模

另外一种解法是乘法逆元，似乎会更快一些，可是我数学太渣不会

注意：这道题非常坑，百“毒”的数据是有问题的。数据存在 a,b>length(string)a, b > length(string) 的情况，这个时候输出上一次的答案就对了……

代码

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

#define N 131072
#define MOD 9973

using namespace std;

long long ans, a[2 * N];
int n, len, s, t;
char str[N];

int main() {
	while (~ scanf("%d", &n)) {
		scanf("%s", str);
		len = strlen(str);

		memset(a, 0, sizeof(a));
		for (int i = 0; i < len; i++)
			a[i + N + 1] = str[i] - 28;

		for (int i = N - 1; i; i--)
			a[i] = a[2 * i] * a[2 * i + 1] % MOD;

		while (n--) {
			scanf("%d%d", &s, &t);
			if (s > len || t > len) {
				printf("%I64d\n", ans);
				continue ; //deal with wrong data
			}
			if (s > t) swap(s, t);
			s += N - 1; t += N + 1;
			for (ans = 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
				if (~ s & 1) ans *= a[s ^ 1];
				ans %= MOD;
				if (t & 1) ans *= a[t ^ 1];
				ans %= MOD;
			}
			printf("%I64d\n", ans);
		}
	}
	return 0;
}

Problem B

题意

nn 个 11 组成的字符串，可以任意合并相邻的两个 11 成为 22 ，问有多少种不同的字符串组合

例如串 111111 就可以变成 1212 和 2121 ，加上自己，一共三种组合

再例如串 1111111111 可以变成 1112,1121,1211,2111,122,212,2211112, 1121, 1211, 2111, 122, 212, 221 ，加上自己，一共八种组合

解法

对于 n=5n=5 ，很容易发现要计算的是

C50+C41+C32=1+4+3=8C_5^0 + C_4^1 + C_3^2 = 1 + 4 + 3 = 8

所以实际上

Answern=Cn0+Cn−11+⋯+C(n+1)/2n/2Answer_n = C_n^0 + C_{n - 1}^1 + \cdots + C_{(n + 1) / 2}^{n / 2}

其实最后的递推式就是

A1=1,A2=2,An=An−1+An−2(n>2)A_1 = 1, A_2 = 2, A_n = A_{n - 1} + A_{n - 2} (n > 2)

（就是斐波那契数列啊）

考虑到要用高精度并且完全可以打表，所以就打表呀~

代码

1
2
3
4
5
6
7
8
9
10
#!/usr/bin/env python
# encoding: utf-8

a, b = 2, 3
print '\tif (n <= 3)\n\t\tprintf("%d", n);'
for i in range(4, 201):
	a, b = b, a + b
	print '\telse if (n == %d)\n\t\tprintf("%d");' % (i, b)

# 剩下的不用多说了吧

Problem C

题意

维护一个 可插入单词，查询某前缀的单词是否存在，删除某前缀的所有单词 的字典

解法

似乎就是个字母树啊，只是一般的字母树并不需要删除单词

删除某前缀时，把前缀路径上最后一个点的子树清空，然后从路径尾部开始遍历

若该点没有其他子树就清空，直到有其他子树停止遍历

代码

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
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

struct TrieNode {
	struct TrieNode *children[26];
	bool isLeaf;

	TrieNode() {
		isLeaf = false;
		memset(children, 0, sizeof(children));
	}

	bool no_child() {
		for (int i = 0; i < 26; i++)
			if (children[i])
				return false;
		return true;
	}

	void insert(const char *s) {
		TrieNode *p = this;
		int len = strlen(s);
		for (int i = 0; i < len; i++) {
			if (!p->children[s[i] - 'a'])
				p->children[s[i] - 'a'] = new TrieNode();
			p = p->children[s[i] - 'a'];
		}
		p->isLeaf = true;
	}

	bool find(const char *s) {
		TrieNode *p = this;
		int len = strlen(s);
		for (int i = 0; i < len; i++)
			if (!p->children[s[i] - 'a'])
				return false;
			else p = p->children[s[i] - 'a'];
		return true;
	}

	void del_pre(const char *s);
} root, *link[40];

void TrieNode::del_pre(const char *s) {
	TrieNode *p = this;
	int len = strlen(s);
	for (int i = 0; i < len; i++) {
		link[i] = p;
		if (!p->children[s[i] - 'a'])
			return ;
		else p = p->children[s[i] - 'a'];
	}
	link[len - 1]->children[s[len - 1] - 'a'] = 0;
	for (int i = len - 1; i; i--)
		if (link[i]->no_child())
			link[i - 1]->children[s[i - 1] - 'a'] = 0;
		else break ;
}

char cmd[10], s[40];
int n;

int main() {
	scanf("%d", &n);
	while (n--) {
		scanf("%s%s", cmd, s);
		if (cmd[0] == 'i')
			root.insert(s);
		else if (cmd[0] == 'd')
			root.del_pre(s);
		else
			printf(root.find(s) ? "Yes\n" : "No\n");
	}
	return 0;
}

Problem D

题意

顺次给你 nn 个字符串，问该字符串的任意排列在之前出现过多少次

解法

似乎是所有题目里面最简单的吧，排个序扔 map 里就好了

代码

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
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

map<string, int>::iterator it;
map<string, int> m;
string s;
int n;

int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	while (n--) {
		cin >> s;
		sort(s.begin(), s.end());
		it = m.find(s);
		if (it == m.end()) {
			cout << 0 << endl;
			m[s] = 1;
		} else {
			cout << (it->second) << endl;
			it->second ++;
		}
	}
	return 0;
}

Problem E

题意

依次给一些条件，问这些条件与前面哪些条件有交集

解法

似乎就是暴力，然而读入的难度比暴力本身大

代码

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>

#define MAX 20000
#define MIN -20000

using namespace std;

map < string, pair<int, int> >::iterator it, io;
map < string, pair<int, int> > m[1100];
string ans[1100];

inline bool digital(char x) {
	return ('0' <= x && x <= '9') || x == '-';
}

inline string getvar() {
	string res = "";
	char t = getchar();
	while (t < 'a' || t > 'z')
		t = getchar();
	do {
		res += t;
		t = getchar();
	} while ('a' <= t && t <= 'z');
	ungetc(t, stdin);
	return res;
}

inline int getopt() {
	char t = getchar();
	while (t != '=' && t != '<' && t != '>')
		t = getchar();
	char x = getchar();
	if (t == '=')
		return 0;
	if (x != '=') {
		ungetc(x, stdin);
		return t == '>' ? 1 : -1;
	}
	return t == '>' ? 2 : -2;
}

inline int getint() {
	int res = 0, mul = 1;
	char t = getchar();
	while (!digital(t))
		t = getchar();
	if (t == '-') {
		mul = -1;
		t = getchar();
	}
	do {
		res *= 10;
		res += t - '0';
		t = getchar();
	} while (digital(t));
	ungetc(t, stdin);
	return mul * res;
}

inline bool getdot() {
	char t = getchar();
	while (t != ',' && t != '\r' && t != '\n' && t != EOF)
		t = getchar();
	return t == ',';
}

int main() {
	int n = getint(), opt, val;
	string var;
	char tmp[10];
	int L, R;
	for (int i = 1; i <= n; i++) {
		ans[i] = "";
		do {
			var = getvar();
			opt = getopt();
			val = getint();
			if (ans[i] == "no")
				continue ;
			it = m[i].find(var);
			if (opt == 0) L = R = val;
			if (opt == 1) L = val + 1, R = MAX;
			if (opt == 2) L = val, R = MAX;
			if (opt == -1) R = val - 1, L = MIN;
			if (opt == -2) R = val, L = MIN;
			if (it != m[i].end()) {
				if (
					R < it->second.first ||
					L > it->second.second
				)
					ans[i] = "no";
				else {
					it->second.second = min(R, it->second.second);
					it->second.first = max(L, it->second.first);
//					cout << "Update pair " << var << " " << it->second.first << " " << it->second.second << endl;
				}
			} else {
				m[i][var] = make_pair(L, R);
//				cout << "Insert pair " << var << " " << L << " " << R << endl;
			}
		} while (getdot());

		if (ans[i] == "no")
			continue ;

		for (int j = 1; j < i; j++) {
			if (ans[j] == "no")
				continue ;
			bool uni = false;
			for (it = m[i].begin(); it != m[i].end(); it++) {
				io = m[j].find(it->first);
				if (io != m[j].end())
					if (
						it->second.first > io->second.second ||
						it->second.second < io->second.first
					) {
						uni = true;
						break ;
					}
			}
			if (!uni) {
				sprintf(tmp, "%d", j);
				ans[i] += tmp;
				ans[i] += " ";
			}
		}
	}

	ios::sync_with_stdio(0);
	for (int i = 1; i <= n; i++)
		if (ans[i] == "" || ans[i] == "no")
			cout << "unique" << endl;
		else {
			ans[i].erase(ans[i].length() - 1);
			cout << ans[i] << endl;
		}

	return 0;
}
Astar 2016 邀请赛 简要题解
2016/05/16/Astar2016-Round1/
作者
Doveccl
发布于
2016-05-16 01:50
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 1. Problem A
    1. 1.1. 题意
    2. 1.2. 解法
    3. 1.3. 代码
  2. 2. Problem B
    1. 2.1. 题意
    2. 2.2. 解法
    3. 2.3. 代码
  3. 3. Problem C
    1. 3.1. 题意
    2. 3.2. 解法
    3. 3.3. 代码
  4. 4. Problem D
    1. 4.1. 题意
    2. 4.2. 解法
    3. 4.3. 代码
  5. 5. Problem E
    1. 5.1. 题意
    2. 5.2. 解法
    3. 5.3. 代码
© 2015 - 2024    Doveccl
由 Hexo 驱动 & 主题 Keep
总字数 24.2k 访客数 访问量
  1. 1. Problem A
    1. 1.1. 题意
    2. 1.2. 解法
    3. 1.3. 代码
  2. 2. Problem B
    1. 2.1. 题意
    2. 2.2. 解法
    3. 2.3. 代码
  3. 3. Problem C
    1. 3.1. 题意
    2. 3.2. 解法
    3. 3.3. 代码
  4. 4. Problem D
    1. 4.1. 题意
    2. 4.2. 解法
    3. 4.3. 代码
  5. 5. Problem E
    1. 5.1. 题意
    2. 5.2. 解法
    3. 5.3. 代码