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

# Problem A

# 题意

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

# 解法

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

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

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

# 代码

#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

# 题意

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

例如串 111111 就可以变成 12122121 ,加上自己,一共三种组合

再例如串 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+Cn11++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=An1+An2(n>2)A_1 = 1, A_2 = 2, A_n = A_{n - 1} + A_{n - 2} (n > 2)

(就是斐波那契数列啊)

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

# 代码

#!/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

# 题意

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

# 解法

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

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

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

# 代码

#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 里就好了

# 代码

#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

# 题意

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

# 解法

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

# 代码

#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;
}
更新于 阅读次数