对于 60% 的数据 n<=300,m<=5000;
对于 100% 的数据 n<=1000,m<=100000;
题解 :
把每一个都 hash 一下然后直接判断第一问解决;
对于第二问, 我们可以贪心地考虑, 我们在所选择的区间里有这个字符, 那么我们就可以舍弃一个;
于是我们可以每次移动右端点, 然后把所有单词找完之后停止, 吧左端点往前缩, 即如果这个字符串不止出现一次, 我们就可以舍弃他;
然后不一定你选择的第一个区间一定是最优的, 所以我们要遍历整个区间;
然后 hash 取进制数的时候要慎重, 我因为这个 wa 了好几遍;
- Code:
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <cstring>
- #include <map>
- using namespace std;
- #define base 26
- const int mod = 100007;
- int n;
- long long a[1010];
- long long b[100010];
- bool hash[100010], vis[100010];
- int num[100010];
- inline int HASH(string x)
- {
- int ans = 0;
- int len = x.length();
- for (register int i = 0; i <len; i ++)
- {
- ans = (ans * base + x[i]) % mod;
- }
- return ans;
- }
- int ans;
- int minn = 1e9;
- int main()
- {
- scanf("%d", &n);
- for (register int i = 1; i <= n; ++i)
- {
- string s;
- cin>> s;
- a[i] = HASH(s);
- hash[a[i]] = 1;
- }
- int m;cin>> m;
- for (register int i = 1 ; i <= m ; i ++)
- {
- string s;
- cin>> s;
- b[i] = HASH(s);
- if (hash[b[i]] and !vis[b[i]]) ans++, vis[b[i]] = 1;
- }
- cout <<ans << endl;
- int r = 1, l = 1;
- int nn = 0;
- while (r <= m)
- {
- while (r <= m)
- {
- if (vis[b[r]] and num[b[r]] == 0) nn ++;
- num[b[r]]++;
- r++;
- if (nn == ans) break;
- }
- while ((vis[b[l]] == 0 or num[b[l]]>= 2) and l < r) num[b[l]]--, l++;
- minn = min(r - l, minn);
- }
- cout << minn;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2664602.html