hiho一下第230周《Smallest Substring》题目分析

0
0

《Smallest Substring》题目分析

这道题标题起得不好，应该叫Subsequence比较准确。不过描述和样例都说明了其实是要找一个sequence。

比较容易想到一个贪心算法：

为了描述方便，我们认为S的长度是N，S[0] .. S[N-1]是每一个字符。

答案的第一个字符一定是S[0] .. S[N-K]中字典序最小的字符；如果有多个，我们一定找其中最靠前的，不妨设为S[P1]。

例如对于样例S=cacbbac，第一个字符是cacb中字典序最小的，即S[1] = 'a'。

答案的第二个字符一定是S[P1+1] .. S[N-K+1]中字典序最小的字符；如果有多个，我们一定找其中最靠前的，不妨设为S[P2]。

例如对于样例S=cacbbac，第二个字符是cbb中字典序最小的，即S[3] = 'b'。

……

答案的第i个字符一定是S[P(i-1) + 1] .. S[N-K+i-1] 中字典序最小的字符；如果有多个，我们一定找其中最靠前的，不妨设为S[Pi]。

重复以上步骤，即可确定答案的每个字符。

注意到每次我们都是要找一个字符集合中(字典序, 序号)最小的字符，同时这个集合会随时插入和删除元素，总计插入和删除不超过N次。

所以我们可以自己实现一个带删除的堆来实现以上的贪心算法。总时间复杂度是O(NlogN)的。(当然也可以借用set的平衡二叉树性质来实现以上的贪心算法。)

  • 不好意思啊，这题我好像不怎么明白题目含义。。。lexicographically smallest string，指的是“字典序最小”？ 那样例S=cacbbac 满足条件的不应该是abba吗？

  • abb aba的字典序谁大？

  • 哦 我以为是总的字典序最小(*/ω＼*)

  • 添加评论
  • ✖reply

8 answer(s)

0

贴个单调队列的做法： 长度为m的串中要找长度为k的子串，那么最晚可在长串的第m-k+1个字符处一定要找出第一个子串字符，以此类推，m-k+i处找到第i个字符。那么使用单调队列维护之前的最小字符即可，且队列的性质保证了其顺序的正确。

#include <bits/stdc++.h>
using namespace std;
char s[100010];
int q[100010];
int main()
{
    int n,m,head,rail,i;
    scanf("%d %s",&n,s+1);
    m=strlen(s+1);
    head=0;rail=-1;
    for(i=1;i<=m-n;i++){
        while(head<=rail&&s[i]<s[q[rail]])rail--;
        q[++rail]=i;
    }
    for(;i<=m;i++){
        while(head<=rail&&s[i]<s[q[rail]])rail--;
        q[++rail]=i;
        printf("%c",s[q[head++]]);
    }
    return 0;
}
2

先把所有字符按顺序压入链表内。

每次找到当前链表内位置最靠前的字符 S[i]，使得 S[i] > S[i + 1]，将 S[i] 从链表中删除，若没有符合条件的字符则将链表末尾的字符删除。直到链表内字符数为 K。

复杂度 O(N)。

#include <fstream>
#include <iostream>
#include <list>

using namespace std;

string s;

list <char> team;

int main(void)
{
    size_t k;
    for (; cin >> k >> s;)
    {
        team.clear();
        for (auto i: s)
            team.push_back(i);
        auto now = team.begin();
        for (; team.size() > k;)
        {
            auto lst = now, nxt = now;
            if (lst == team.begin())
                ++lst;
            else
                --lst;
            for (++nxt; nxt != team.end() && *now <= *nxt; lst = now++, ++nxt);
            if (nxt == team.end())
                team.pop_back();
            else
                team.erase(now);
            now = lst;
        }
        for (auto i: team)
            putchar(i);
        putchar('\n');
    }
    return 0;
}
0

贴一个短代码，可以把set当堆使

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

typedef pair<char, int> p;

int main() {
    freopen("input", "r", stdin);

    string s;
    int k;
    cin >> k >> s;

    int n = s.size();
    set<p> heap;
    for (int i = 0; i <= n - k; ++i)
        heap.insert({s[i], i});

    string res = "";
    int l = 0, r = n - k;
    for (int i = 0; i < k; ++i) {
        p tmp = *heap.begin();
        res.push_back(tmp.first);

        for (int j = l; j <= tmp.second; ++j)
            heap.erase({s[j], j});
        if (++r < n) 
            heap.insert({s[r], r});
        l = tmp.second + 1;
    }
    cout << res << "\n";
}
0

贴个线段树的解法

#include<cstdio>
#include<iostream>
#include<sstream>
#include<utility>
#include<cmath>
#include<cassert>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<tuple>
using namespace std;

struct Node
{
    char min_val;   // 当前区间字典序最小的字符
    int min_pos;    // 最小字符的索引（在原字符串中的位置）
    int l;
    int r;
    Node * left;
    Node * right;
};

auto top = 0;
Node pool[(100000 + 5) * 4];

// 建树
Node * build(const string & S, int l, int r)
{
    auto root = &pool[top++];
    root->l = l;
    root->r = r;

    if(l + 1 == r)
    {
        root->left = nullptr;
        root->right = nullptr;
        root->min_val = S[l];
        root->min_pos = l;
    }
    else
    {
        auto mid = (l + r) / 2;

        root->left = build(S, l, mid);
        root->right = build(S, mid, r);
        root->min_val = min<int>(root->left->min_val, root->right->min_val);
        root->min_pos = root->left->min_val <= root->right->min_val ? root->left->min_pos : root->right->min_pos;
    }
    return root;
}

// 返回区间[l, r)上字典序最小的字母及其索引
tuple<char, int> find_tree(Node * root, int l, int r)
{
    if(l <= root->l && root->r <= r)
    {
        return make_tuple(root->min_val, root->min_pos);
    }

    auto mid = (root->l + root->r) / 2;

    auto left_res = make_tuple(numeric_limits<int>::max(), -1);
    auto right_res = make_tuple(numeric_limits<int>::max(), -1);

    if(l < mid) left_res = find_tree(root->left, l, r);
    if(mid < r) right_res = find_tree(root->right, l, r);

    if(get<0>(left_res) <= get<0>(right_res))
    {
        return left_res;
    }
    else return right_res;
}

int main()
{
    int K;
    cin >> K;

    string S;
    cin >> S;

    auto root = build(S, 0, S.size());

    string acc;

    auto start = 0;
    for(auto cur_K = K; cur_K > 0; --cur_K)
    {
        auto t = find_tree(root, start, S.size() - cur_K + 1);
        acc += get<0>(t);
        start = get<1>(t) + 1;
    }
    cout << acc << "\n";

    return 0;
}
0 
/*  
 *  题意要求输出S串的长度为n的字典序最小的子串
 *  考虑字典序最小的串中字母一定不存在降序
 *  
 *  把题意改为去掉k=len-n个字符使字典序最小
 *   
 *  贪心思想，如果ans中还能加入字符，那么加入的字符一定不小于加入之前最后一个字符
 *  如果小于则在k允许的情况下去掉所有大于本次加入的字符的字符 
 *  
 *  处理完之后会有两种情况（就是跳出循环的条件不同） 
 *  1）S串的子串已经非降序，但k>=0，则还要去掉ans中最后k个字符（不用解释吧） 
 *  2）k已经用完，但S还有未处理的元素（则要把未处理的元素输出，代码中i表示处理到了哪里）
 *  解释的不清楚，看代码吧 >_< 
 *  大佬们顺便帮我看看这个复杂度怎么算 QwQ 
 */ 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000;

char S[maxn + 5], ans[maxn + 5];    //输入S数组，答案存在ans中，ans实时更新 
int fir[26];                        //'a'+i在ans数组中第一次出现的位置 
int main()
{
    int i, n, k, len, lans = 0;
    scanf("%d%s", &n, S);
    len = strlen(S);
    k = len - n;                              
    for (i = 0; i < len && k; ++i) {
        while (k&&lans&&S[i]<ans[lans-1]) {//small
            int have = lans-fir[ans[lans-1]-'a'];
            if (k>=have) {          //enough
                k -= have;
                lans -= have;
            }
            else {                  //Not enough
                lans -= k;
                k = 0;
            }
        }
        if (!lans || ans[lans-1]!=S[i]) fir[S[i]-'a'] = lans;
        ans[lans++] = S[i];
    }
    ans[lans-k] = '\0';             //第一种情况 
    printf("%s",ans);
    if (i<len)  printf("%s", S+i);  //第二种情况 
    putchar('\n');
    return 0;
}

  • 思路中一定不存在降序这个错了，因为假设S串是dcba，k为4，则字典序最小子串就是dcba

  • 添加评论
  • ✖reply
0

思路跟楼上是一致的，只是一次找多个值。比如 5 bcabacc
过程
a_a__
a_a__
a_acc
abacc

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 1;

using ll = long long;

int N, M, K;
string str;
vector<int> pos[30];

bool check(vector<int> &cur, set<int>& ans) {
    int k = 0;
    while (ans.size() != K && k != cur.size()) {
        for (int i = 0; i < 26 && ans.size() != K; i++) {
            auto it = pos[i].rbegin();
            while (it != pos[i].rend() && *it > cur[k] && ans.size() != K) {
                ans.emplace(*it);
                it++;
                pos[i].pop_back();
            }
        }
        k++;
    }
    return ans.size() == K;
}

string Solution() {
    for (int i = 0; i < 26; i++)
        pos[i].clear();
    for (int i = 0; i < str.size(); i++)
        pos[str[i] - 'a'].emplace_back(i);
    set<int> ans;
    for (int i = 0; i < 26; i++) {
        vector<int> cur;
        auto it = pos[i].rbegin();
        while (it != pos[i].rend() && ans.size() != K) {
            cur.emplace_back(*it);
            ans.emplace(*it);
            it++;
            pos[i].pop_back();
        }
        if (check(cur, ans))
            break;
    }
    string ret;
    for (int idx : ans)
        ret += str[idx];
    return ret;
}

int main() {
    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    while (cin >> K) {
        cin >> str;
        cout << Solution() << '\n';
    }
    return 0;
}

  • 你的mini[i][j]表达什么含义啊,看的我一头雾水

  • 标准的RMQ（ST算法），没啥特别的。

  • 遇到和你一样的问题了，我也是rmq= =

  • 添加评论
  • ✖reply
0

RMQ找区间最小值，递归直到长度满足，这是个AC代码。另外希望大佬们看看下一层楼的代码，错在哪？

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 1;

using ll = long long;

int N, M, K;
string S;
int mini[20][MAXN];

inline int Min(int a, int b) {
    if (S[a] < S[b])
        return a;
    else if (S[a] == S[b])
        return (a < b) ? a : b;
    else
        return b;
}

void Build() {
    for (int j = 0; j < S.size(); j++)
        mini[0][j] = j;
    for (int i = 1; (1 << i) <= S.size(); i++) {
        for (int j = 0; j + (1 << (i-1)) < S.size(); j++) {
            mini[i][j] = Min(mini[i-1][j], mini[i-1][j + (1 << (i-1))]);
        }
    }
}

int Search(int l, int r) {
    int k = 0;
    while ((1 << (k + 1)) <= (r - l + 1))
        k++;
    return Min(mini[k][l], mini[k][r + 1 - (1<<k)]);
}

void dfs(int l, int r, set<int> &ans) {
    if (ans.size() == K || l > r)
        return;
    int k = Search(l, r);
    ans.emplace(k);
    dfs(k+1, r, ans);
    dfs(l, k-1, ans);
}

string Solution() {
    Build();
    set<int> ans;
    dfs(0, static_cast<int>(S.size() - 1), ans);
    string ret;
    for (int idx : ans)
        ret += S[idx];
    return ret;
}

int main() {
    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    while (cin >> K) {
        cin >> S;
        cout << Solution() << '\n';
    }
    return 0;
}
1

include

include

include

include

using namespace std; char a[100005]; int main() { set s; set::iterator p; while(scanf("%s",a)) { s.clear(); int n=strlen(a); for(int i=0;i 

return 0;

}

write answer 切换为英文 切换为中文

转发分享

▲