本次题目因为比较简单，除了个别题目，其余题目我只写一个思路不再贴代码。
先是Div.2的题解
A题奇怪的优化，把递归函数改成2*fun(...)即可，其实看懂程序也不难，就是求a*2b；
B题你会string吗，直接String变量比较大小即可
C题数数，没有卡正常方法，可以直接把数转成二进制找1个数，此时复杂度为O(logN)，更快的方法是使用__builtin_popcount函数，复杂度为O(m（m为数二进制中1的个数）)；
D，E题，看Div.1中本题解释
所有代码都可以10行内写出，所以我不再给出代码；
Div.1题解
A题简单代码优化，区间求和，直接再弄一个sum数组即可
B题简单字符串处理，因为只能在字符串尾部加字符，所以我的做法是把每个字符给个序号（既位置）存入容器，再分别做三个操作。
对于1操作，删除存储那个字符的集合即可。
对于2操作，对应集合加上序号即可。
对于3操作，在1操作时候维护一个树状数组即可。
整体时间复杂度为O(QlogN),N为字符个数。但这种写法常数略大，有更优化的思路可以和我探讨一下。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 set<int> dis[26]; 5 vector<pair<int,int>> vis(26,make_pair(0,0)); 6 int q,x,k,tot = 0; 7 char ch; 8 int c[100005] = {0}; 9 10 inline int lowbit(int x){ 11 return x&(-x); 12 } 13 14 int update(int i){ 15 while(i <= 100000){ 16 c[i] += 1; 17 i += lowbit(i); 18 } 19 } 20 21 int sum(int i){ 22 int res = 0; 23 while(i > 0){ 24 res += c[i]; 25 i -= lowbit(i); 26 } 27 return res; 28 } 29 30 int main(){ 31 ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); 32 freopen("test6.in","r",stdin); 33 freopen("test6.out","w",stdout); 34 int f1 = 0; 35 cin>>q; 36 generate(vis.begin(),vis.end(),[&f1](void)->pair<int,int>{return make_pair(f1++,0);}); 37 while(q--){ 38 cin>>x; 39 if(x == 1){ 40 cin>>k; 41 if(k > 26) 42 continue; 43 sort(vis.begin(),vis.end(), 44 [](pair<int,int> a,pair<int,int> b)->bool{ 45 if(a.second == b.second) 46 return a.first < b.first; 47 return a.second > b.second; 48 }); 49 vis[k-1].second = 0; 50 for(auto it:dis[vis[k-1].first]){ 51 update(it); 52 } 53 dis[vis[k-1].first].clear(); 54 } 55 else if(x == 2){ 56 cin>>ch; 57 dis[ch-'a'].insert(++tot); 58 for(auto& a:vis){ 59 if(a.first == ch-'a'){ 60 a.second++; 61 break; 62 } 63 } 64 } 65 else if(x == 3){ 66 cin>>ch; 67 if(dis[ch-'a'].empty()) 68 cout << -1 << endl; 69 else 70 cout << *(dis[ch-'a'].begin())-sum(*(dis[ch-'a'].begin())) << endl; 71 } 72 } 73 cerr << clock() << endl; 74 return 0; 75 }
C题简单信息检索，标记初次出现位置即可
D题高级信息检索，把每个前缀都存入map，此时可以使用unordered_map更快，或者建立Trie树即可。好像还有人写exKMP，也没问题，毕竟100+100数据量。
E题密码破解，马拉车算法裸题。
