CodeForcesGym 100524J Jingles of a String

Jingles of a String

Time Limit: 2000ms

Memory Limit: 524288KB

This problem will be judged on CodeForcesGym. Original ID: 100524J
64-bit integer IO format: %I64d Java class name: (Any)

解题：题目很厉害啊！借鉴某大牛的思路。

由于都是小写字母，所以对任意一个区间，最多只有26个，用二进制表示该区间出现过的字母

然后就是固定一个左边界，可以算出左边界到字符串末这区间中1个个数，那么枚举这些1的个数，进行二分查找出现这么多个1的区间的最大右边界。

RMQ st可以这么用，也是涨姿势了

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 100005;
 5 int st[maxn][20];
 6 char str[maxn];
 7 int query(int L,int R) {
 8     int lg = 31 - __builtin_clz(R - L + 1);
 9     return st[L][lg]|st[R - (1<<lg) + 1][lg];
10 }
11 unordered_map<int,int>ump;
12 int main() {
13 #define NAME "jingles"
14     freopen(NAME".in","r",stdin);
15     freopen(NAME".out","w",stdout);
16     int kase;
17     scanf("%d",&kase);
18     while(kase--) {
19         scanf("%s",str);
20         int len = strlen(str);
21         for(int i = 0; i < len; ++i)
22             st[i][0] = 1<<(str[i] - 'a');
23         for(int j = 1; (1<<j) <= len; ++j) {
24             for(int i = 0; i + (1<<j) <= len; ++i)
25                 st[i][j] = st[i][j-1]|st[i+(1<<(j-1))][j-1];
26         }
27         ump.clear();
28         for(int i = 0; i < len; ++i) {
29             int x = query(i,len - 1);
30             ump[x] = max(ump[x],len - i);
31             int cnt = __builtin_popcount(x);
32             for(int j = 1; j < cnt; ++j) {
33                 int low = i,high = len-1,ret;
34                 while(low <= high) {
35                     int mid = (low + high)>>1;
36                     int y = __builtin_popcount(query(i,mid));
37                     if(y <= j) {
38                         low = mid + 1;
39                         ret = mid;
40                     } else high = mid - 1;
41                 }
42                 ump[query(i,ret)] = max(ump[query(i,ret)],ret - i + 1);
43             }
44         }
45         LL ans = 0;
46         for(auto &it:ump)
47             ans += __builtin_popcount(it.first)*(LL)it.second;
48         printf("%d %I64d
",ump.size(),ans);
49     }
50     return 0;
51 }

View Code