14122: 【原4122】单词背诵
题目
题目描述
author: Ca. 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4122
Description
小X有n个单词想要背，但他想通过一篇文章中的一段来记住这些单词。文章由m个单词构成，他想在文章中找出连续的一段，其中包含最多的他想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样他就可以用尽量短的时间学习尽可能多的单词了。
Input Format
第一行包含一个整数n。 接下来n行，每行包含一个长度不超过10的字符串，表示一个要背的单词。 接下来一行包含一个整数m。 接下来m行，每行包含一个长度不超过10的字符串，表示文章中的一个单词。
Output Format
第一行包含一个整数，表示文章中最多包含的要背的单词数。 第二行包含一个整数，表示在文章中包含最多要背单词的最短的连续段的长度。
Sample Input
3
hot
dog
milk
5
hot
dog
dog
milk
hot
Sample Output
3
3
Data Range
30%的数据，1≤n≤50，1≤m≤500。 60%的数据，1≤n≤300，1≤m≤5000。 100%的数据，1≤n≤1000，1≤m≤10^5。
q4x3's solution
/**
* 字符串hash + 尺取法
**/
#include <iostream>
#include <cstring>
#define ull unsigned long long
using namespace std;
int n, m, ans1, ans2, cur[100233];
char wor[1233][15], txt[100233][15];
bool wor_bool[100233];
ull wor_hash[100233], txt_hash[100233];
const ull base = 131;
template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
T* A = a + lo;
int lb = mi - lo;
T* B = new T[lb];
T* BB = B;
for(int i = 0;i < lb;++ i)
B[i] = A[i];
int lc = hi - mi;
T* C = a + mi;
int cnt = 0;
while(1) {
if ((lb == 0) && (lc == 0)) break;
if (lb == 0) {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
else if (lc == 0) {
A[cnt] = B[0];
++ cnt; ++ B; --lb;
}
else {
if(B[0] < C[0]) {
A[cnt] = B[0];
++ cnt; ++ B; -- lb;
}
else {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
}
}
delete []BB;
}
template <typename T>
void mergeSort(int lo, int hi, T* A)
{
if(hi - lo < 2) return;
int mi = (lo + hi) / 2;
mergeSort(lo, mi, A); mergeSort(mi, hi, A);
merge(lo, mi, hi, A);
}
ull myhash(char *s) {
int len = strlen(s);
ull tmp = 0;
for(int i = 0;i < len;++ i) {
tmp = tmp * base + (ull)s[i];
}
return tmp;
}
int binary_search(ull a) {
int l = 1, r = n + 1;
while(l < r) {
int mid = (l + r) >> 1;
if(wor_hash[mid] >= a) {
r = mid;
} else {
l = mid + 1;
}
}
if(wor_hash[l] == a) return l;
else if(wor_hash[r] == a) return r;
else return 0;
}
bool check() {
for(int i = 1;i <= n;++ i) {
if(wor_bool[i]) {
if(cur[i] == 0) return 0;
}
}
return 1;
}
int main() {
scanf("%d", &n);
for(int i = 1;i <= n;++ i)
scanf("%s", wor[i]);
scanf("%d", &m);
for(int i = 1;i <= m;++ i)
scanf("%s", txt[i]);
for(int i = 1;i <= n;++ i)
wor_hash[i] = myhash(wor[i]);
for(int i = 1;i <= m;++ i)
txt_hash[i] = myhash(txt[i]);
mergeSort(1, n + 1, wor_hash);
for(int i = 1;i <= m;++ i) {
int tmp = binary_search(txt_hash[i]);
if(tmp && (! wor_bool[tmp])) {
wor_bool[tmp] = 1;
++ ans1;
}
}
int p = 1, q = ans1;
ans2 = m;
for(int i = p;i <= q;++ i) {
int tmp = binary_search(txt_hash[i]);
if(tmp) ++ cur[tmp];
}
if(ans1 == 0) ans2 = 0;
else {
while(q <= m) {
if(check()) {
ans2 = (q - p + 1 < ans2) ? q - p + 1 : ans2;
int tmp = binary_search(txt_hash[p]);
if(tmp) -- cur[tmp];
++ p;
}
else {
++ q;
int tmp = binary_search(txt_hash[q]);
if(tmp) ++ cur[tmp];
}
}
}
cout << ans1 << endl << ans2 << endl;
}
victrid's solution
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
//???Why?
unsigned long long bhash(char* c) {
unsigned long long pc = 0;
while (*c != '\0') {
pc *= 131;
pc += *c;
c++;
}
return pc;
}
template <typename T1, typename T2>
struct paar {
T1 __hash;
T2 index;
bool operator>(paar<T1, T2>& p) {
return __hash > p.__hash;
}
bool operator<(paar<T1, T2>& p) {
return __hash < p.__hash;
}
bool operator==(paar<T1, T2>& p) {
return __hash == p.__hash;
}
};
template <typename T>
class AVL {
protected:
struct node {
node* left;
node* right;
int height;
T value;
};
node* data;
int __size;
node* i_query(node* root, T& to_query) {
if (root == nullptr)
return nullptr;
if (root->value == to_query)
return root;
if (root->value > to_query) {
return i_query(root->left, to_query);
}
if (root->value < to_query) {
return i_query(root->right, to_query);
}
}
void setrootheight(node* root) {
if (root == nullptr)
return;
root->height = max((root->left == nullptr ? 0 : root->left->height), (root->right == nullptr ? 0 : root->right->height)) + 1;
}
node* right_rotate(node*& root) {
node* nl = root->left;
root->left = nl->right;
nl->right = root;
root = nl;
setrootheight(root->left);
setrootheight(root->right);
setrootheight(root);
return root;
}
node* left_rotate(node*& root) {
node* nr = root->right;
root->right = nr->left;
nr->left = root;
root = nr;
setrootheight(root->left);
setrootheight(root->right);
setrootheight(root);
return root;
}
inline int getfactor(node*& root) {
if (root == nullptr)
return 0;
return (root->left == nullptr ? 0 : root->left->height) - (root->right == nullptr ? 0 : root->right->height);
}
int balance(node*& root) {
if (root == nullptr)
return 0;
setrootheight(root->left);
setrootheight(root->right);
setrootheight(root);
while (abs(getfactor(root->left)) > 1) {
balance(root->left);
setrootheight(root->left);
setrootheight(root);
}
while (abs(getfactor(root->right)) > 1) {
balance(root->right);
setrootheight(root->right);
setrootheight(root);
}
int p = getfactor(root);
if (abs(p) <= 1)
return 0;
if (p > 0) {
if (getfactor(root->left) == 1) {
right_rotate(root);
return 0;
} else {
left_rotate(root->left);
right_rotate(root);
return 0;
}
} else {
if (getfactor(root->right) == -1) {
left_rotate(root);
return 0;
} else {
right_rotate(root->right);
left_rotate(root);
return 0;
}
}
}
int insert(node*& root, T& to_insert) {
if (root == nullptr) {
root = new node{nullptr, nullptr, 1, to_insert};
__size++;
return 0;
}
if (root->value < to_insert)
insert(root->right, to_insert);
else
insert(root->left, to_insert);
balance(root);
return 0;
}
node* erasemin(node*& root) {
if (root == nullptr)
return nullptr;
node* to_erase;
if (root->left == nullptr) {
to_erase = root;
root = root->right;
} else {
return erasemin(root->left);
}
balance(root);
return to_erase;
}
int erase(node*& root, T& to_delete) {
if (root == nullptr)
return -1;
if (root->value < to_delete)
erase(root->right, to_delete);
else if (root->value > to_delete)
erase(root->left, to_delete);
else if (root->value == to_delete) {
__size--;
node* rr = root;
if (root->right == nullptr && root->left == nullptr) {
root = nullptr;
} else if (root->right == nullptr) {
root = root->left;
} else if (root->left == nullptr) {
root = root->right;
} else {
node*& pp = root->right;
node* bl = root->left;
root = erasemin(root->right);
root->right = pp;
root->left = bl;
}
delete rr;
}
balance(root);
return 0;
}
public:
AVL() : data(nullptr), __size(0){};
int insert(T dat) {
if (i_query(data, dat) != nullptr)
return -1;
else {
insert(data, dat);
return 0;
}
}
int find(T dat) {
return (i_query(data, dat) != nullptr);
}
int erase(T dat) {
if (i_query(data, dat) == nullptr)
return -1;
else {
erase(data, dat);
return 0;
}
}
int size() {
return __size;
}
};
class AVLtr : public AVL<paar<unsigned long long, int>> {
public:
int test(unsigned long long t) {
paar<unsigned long long, int> fp{t, __size + 1};
node* f = i_query(data, fp);
if (f == nullptr) {
return -1;
} else {
return f->value.index;
}
}
};
int book[100005] = {0};
int toremem[1005] = {0};
int book_rem[1005] = {0};
inline bool checkrem(int n) {
for (int i = 0; i < n; i++) {
if (!toremem[i])
continue;
if (!book_rem[i])
return false;
}
return true;
}
int main() {
int n, m;
scanf("%d", &n);
char ch[100];
AVLtr torem;
for (int i = 0; i < n; i++) {
scanf("%s", ch);
torem.insert(paar<unsigned long long, int>{bhash(ch), i});
}
scanf("%d", &m);
int exist_torem = 0;
for (int i = 0; i < m; i++) {
scanf("%s", ch);
book[i] = torem.test(bhash(ch));
if (book[i] != -1 && !toremem[book[i]]) {
toremem[book[i]] = 1;
exist_torem++;
}
}
if (!exist_torem) {
printf("0\n0");
return 0;
}
// I was wrong.
// two pointer method.
// missing unchecked
int *ptrl = book, *ptrr = book;
book_rem[*ptrr]++;
int flag = 0;
int maxl = m;
while (ptrr < book + m) {
if (!checkrem(n)) {
if (flag != 0) {
maxl = min(maxl, flag);
}
ptrr++;
if (*ptrr != -1) {
book_rem[*ptrr]++;
}
flag = 0;
} else {
flag = ptrr - ptrl + 1;
book_rem[*ptrl]--;
ptrl++;
}
}
printf("%d\n%d", exist_torem, maxl);
return 0;
}