毕设的东西做不下了，做点其他东西调节一下，翻出USACO Trainning继续做，到Contact这道题了，光荣地挂在了第7组数据了，写的稍微有点暴力，过段时间再把它过掉吧。
题意是这样的，有一个01串，长度200,000，有1<=A,B<=12,1<=N<=50，求的是串中长度在A,B之间的子串出现次数的统计问题。
想了个最糟糕情况为12*200000=2.4*10^6的算法，最暴力的方法，遍历所有的子串，主要是要怎么hash一个子串，将一个子串唯一映射成一个整数，0011和11是不同的子串，想了个比较巧妙的方法，把空串想为字符0，于是0011可以用1122来表示11用1122来表示，即可以压缩成一个三进制数，然后就可以方便实现了。
PS：题目好烦人，输入拆成若干行，输出又乱拆。
TLE：遍历子串有点暴力，可以尝试下记录之前的信息来递归，小小优化一下到LEN*(B-A)。
TLE的代码如下：
/* ID: litstrong PROG: contact LANG: C++ */ #include <iostream> #include <string> #include <algorithm> #include <vector> #include <set> #include <stdio.h> using namespace std; const int MAX = 600005; const int LEN = 200005; int A, B, N; char ch[LEN]; class CNODE { public: string num; int cnt; public: CNODE () : cnt(0) {} void AddCnt() { cnt++; } bool operator < (const CNODE &t) const { if(cnt != t.cnt) return cnt > t.cnt; if(num.length() != t.num.length()) return num.length() < t.num.length(); return num < t.num; } }node[MAX]; int main() { freopen("contact.in", "r", stdin); freopen("contact.out", "w", stdout); string mo = ""; scanf("%d%d%d", &A, &B, &N); while(scanf("%s", ch) != EOF) mo += ch; int len = mo.length(); int len_max = 0; for(int i = 0; i <= len - A; i++) { string dq = ""; int tmp = 0, thr = 1; for(int j = 0; j < B; j++) { dq.push_back(mo[i + j]); tmp += (mo[i + j] - '0' + 1) * thr; thr *= 3; if(j < A - 1) continue; if(i + j >= len) break; node[tmp].num = dq; node[tmp].AddCnt(); len_max = max(len_max, tmp); } } sort(node, node + len_max + 1); int before = 0, in = 0, first = 0, dqCnt = 1; int zNum = 0; for(int i = 0; i <= len_max; i++) { if(node[i].cnt) { if(node[i].cnt != before && first) { if(++dqCnt > N) break; printf("\n"); in = 0; zNum = 0; } first = 1; if(in == 0 && zNum == 0) printf("%d\n", node[i].cnt); if(in == 0) cout << node[i].num; else cout << " " << node[i].num; in = 1; zNum++; if(zNum % 6 == 0) { in = 0; printf("\n"); } before = node[i].cnt; } } printf("\n"); }转载于:https://www.cnblogs.com/litstrong/archive/2011/03/24/1994419.html
相关资源：数据结构—成绩单生成器