Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) D. Dense Subsequence ST表+贪心

My Solution

ST表+贪心

ST表，用O(nlogn)的预处理，然后O(1)查询，找出ans中出现的最大的字母，

然后把比它小的字母都从小到大push到ans里，

然后贪心的去那个需要的最大字母的个数，

每次if(maxv == query_min(i, i + m - 1)) 则在这个 [ i, i + m -1 ]区间内找出最右端的一个maxv + 'a'  字母，//如果优先选左边的，则右边的还会取到，所以取区间最右边的maxv+'a'

就好。

复杂度 O(nlogn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

const int MAXN = 1e5 + 8;
int stTable[MAXN][32], preLog2[MAXN], arr[MAXN];

inline void st_prepare(const int &n)
{
    preLog2[1] = 0;
    for(int i = 2; i <= n; i++){
        preLog2[i] = preLog2[i-1];
        if((1 << (preLog2[i] + 1)) == i){ preLog2[i]++; } } for(int i = n - 1; i >= 0; i--){
        stTable[i][0] = arr[i];
        for(int j = 1; (i + (1 << j) - 1) < n; j++){
            stTable[i][j] = min(stTable[i][j - 1], stTable[i + (1 << j - 1)][j - 1]);
        }
    }
}

inline int query_min(const int &l, const int r)
{
    int len = r - l + 1, k = preLog2[len];
    return min(stTable[l][k], stTable[r - (1 << k) + 1][k]);
}



int cnt[26];
string s, ans;
//bool flag[maxn];

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
    for(int i = 0; i < maxn; i++){ arr[i] = 1e9 + 7; } int m, sz; cin >> m;
    cin >> s;
    sz = s.size();
    ans.clear();
    for(int i = 0; i < sz; i++){
        cnt[s[i] - 'a']++;
        arr[i] = s[i] - 'a';
        //cout << arr[i+1];
    }

    st_prepare(sz);
    int maxv = -1;
    for(int i = 0; i < sz; i++){
        if(i + m - 1 < sz){
            maxv = max(maxv, query_min(i, i + m - 1));
        }
        else break;
    }

    for(int i = 0; i < maxv; i++){
        while(cnt[i]){
            ans += 'a' + i;
            cnt[i]--;
        }
    }

    for(int i = 0; i < sz; i++){
        //cout << i << endl;
        if(i + m - 1 < sz){ if(maxv == query_min(i, i + m - 1)){ for(int j = i + m - 1; j >= i; j--){         //在区域内找到最右边的maxv, 比赛的时候找的最左边的 maxv 尴尬
                    if(s[j] - 'a' == maxv){

                        ans += 'a' + maxv;
                        i = j;
                        //i += m - 1;      //不能跳跃，看样例
                        //cout << i << endl;
                        break;
                    }
                }
            }
        }
        else break;
    }

    cout << ans << endl;


    #ifdef LOCAL
    memset(cnt, 0, sizeof cnt);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx