相关链接
题目传送门:http://codeforces.com/contest/212/problem/B
中文题面:http://www.tsinsen.com/A1470
解题报告
这题你需要观察到一个非常重要的结论:
以字符串某个特定位置为开头的字符串,至多只有26个会产生贡献
于是我们就可以暴力枚举这$O(26n)$的字符串
然后去更新答案
时间复杂度:$O(26n \log q)$
Code
这份代码我写挫了
时间复杂度是:$O(676n \log q)$的
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1000009; const int SGZ = 26; const int M = 10009; int n, m, nxt[N][SGZ], crt[N][SGZ], q[M], ans[M]; vector<int> val; char s[N], qy[SGZ]; inline int read() { char c = getchar(); int ret = 0, f = 1; while (c < '0' || c > '9') { f = c == '-'? -1: 1; c = getchar(); } while ('0' <= c && c <= '9') { ret = ret * 10 + c - '0'; c = getchar(); } return ret * f; } inline int index(int x) { for (int l = 0, r = val.size() - 1, mid; l <= r; ) { mid = l + r >> 1; if (val[mid] == x) { return mid; } else if (val[mid] < x) { l = mid + 1; } else { r = mid - 1; } } return -1; } int main() { scanf("%s", s); n = strlen(s); m = read(); for (int i = 1; i <= m; i++) { scanf("%s", qy); int len = strlen(qy); for (int j = 0; j < len; j++) { q[i] |= 1 << qy[j] - 'a'; } val.push_back(q[i]); } sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin()); int last_position[SGZ]; fill(last_position, last_position + SGZ, n); for (int i = n - 1; ~i; i--) { last_position[s[i] - 'a'] = i; for (int j = 0; j < SGZ; j++) { nxt[i][j] = last_position[j]; } } memset(crt, -1, sizeof(crt)); for (int i = 0; i < n; i++) { for (int j = 0, p = i, sta = 0; j < 26 && p < n; j++) { int np = n, c = -1; for (int k = 0; k < 26; k++) { if ((sta >> k & 1) == 0) { if (np > nxt[p][k]) { c = k; np = nxt[p][k]; } } } if (~c) { sta |= 1 << c; p = np; crt[i][j] = sta; if (!i || crt[i - 1][j] != sta) { int idx = index(sta); if (~idx) { ans[idx]++; } } } } } for (int i = 1; i <= m; i++) { printf("%d\n", ans[index(q[i])]); } return 0; }