单词背诵

题目链接： /

题目大意

有一些要的单词，然后有一个句子，问你这个句子中选一个段，使得竟可能包含更多种你要的单词，其次长度要尽可能短。

问你最多能包含的要的单词种数，和此时最短的长度。

思路

首先，我们看第一个输出怎么求。

很明晰，因为首先就是要让包含的单词种树尽可能多，那就是在句子中出现的要的单词都一定要。

那这个我们可以用 hash 把字符串转换成数字，然后通过把要的单词组成的字符串按 hash 值排序后二分，就可以得到一个单词是否是要的单词，而且还可以得出是哪个要的单词。

那第一个输出就做出来了。

然后看第二个。

我们考虑用尺取法。

尺取法通常是指对数组保存一对下标(起点,终点),然后根据实际情况交替推进两个端点直到得出答案的方法,这种操作很像是尺取虫爬行的方式故得名。

其作用就是对给定的一个序列，在序列中寻找包含全部需求的，长度最小的一段子序列的O(n)的优秀算法。当然，它还有很多别的作用。

代码

#include
   
    #include
    
     #include
     
      #define ull unsigned long long#define mi 131ullusing namespace std;struct hhash {
   	ull hash;	int num;}hash[1001];int n, m, size, ans, place[100001], l, r, mid, num, in[1001], answer;char rem[1001][14], pas[100001][14];bool have[1001];ull thash;bool cmp(hhash x, hhash y) {
   	return x.hash < y.hash;}int getplace() {
   //通过二分找到要背的单词种是否有这个 hash 值	l = 0;	r = n;	while (l <= r) {
   		mid = (l + r) >> 1;		if (hash[mid].hash > thash) {
   			r = mid - 1;		}		else if (hash[mid].hash < thash) l = mid + 1; 			else return hash[mid].num;	}	return -1;}int main() {
   	scanf("%d", &n);	for (int i = 1; i <= n; i++) {
   		scanf("%s", &rem[i]);		size = strlen(rem[i]);		hash[i].num = i;//记录原有的位置		hash[i].hash = rem[i][0] - 'A' + 1;		for (int j = 1; j < size; j++)			hash[i].hash = hash[i].hash * mi + rem[i][j] - 'A' + 1;//得到hash值	}		sort(hash + 1, hash + n + 1, cmp);//排序，让后面可以二分查找是否是这个字符串		scanf("%d", &m);	for (int i = 1; i <= m; i++) {
   		scanf("%s", &pas[i]);		size = strlen(pas[i]);		thash = pas[i][0] - 'A' + 1;		for (int j = 1; j < size; j++)			thash = thash * mi + pas[i][j] - 'A' + 1;		place[i] = getplace();		if (place[i] != -1 && !have[place[i]]) {
   			ans++;			have[place[i]] = 1;		}	}		printf("%d\n", ans);		if (!ans) {
   		printf("0");		return 0;	}		l = 1;	answer = 2147483647;//尺取法得到最小长度	for (int i = 1; i <= m; i++) {
   		if (place[i] != -1) {
   			if (!in[place[i]]) {
   				num++;			}			in[place[i]]++;						if (num == ans) {
   				while (l <= i && num == ans) {
   					if (place[l] != -1) {
   						in[place[l]]--;						if (!in[place[l]]) {
   							num--;							answer = min(answer, i - l + 1);						}					}					l++;				}			}		}	}		printf("%d", answer);		return 0;}

转载地址：http://qpvh.baihongyu.com/

你可能感兴趣的文章