AtCoder Beginner Contest 372 补题记录

A - delete

题意：

输出删除字符串中 . 后的字符串

思路：

只输出字符串中不是 . 的字符

void solve()
{
    string s = sread();
    for(auto it:s) if(it!='.') cout<<it;
    cout<<endl;
}

B - 3^A

题意：

给出 M , 求将M拆分成 N 个 3的 \(A_i\) 次方 相加

思路：

贪心，从大到小用 \(A_i\) 减M，最后一定能在 N<=20 范围内将M减为0

void solve()
{
    int m = read();
    int a = 10;
    vector<int> ans;
    while(m>0){
        if(m >= pow(3,a)){
            ans.push_back(a);
            m -= pow(3,a);
        }else {
            a--;
        }
    }

    cout<<ans.size()<<endl;
    for(auto it:ans) write(it); ED;
}

C - Count ABC Again

题意：

给定字符串 \(S\) 和 \(Q\) 次询问，每次询问将字符串 \(S\) 的第 \(X\) 个字符更改为 \(C\)，并输出每次更改后字符串中包含子串 \(ABC\) 的个数

思路：

－ 每次询问都去统计子串的个数肯定会超时
－ 只在初始统计一次子串的个数

• 考虑到每次修改都只会影响周围的几个字符，所以每次修改只会让子串的个数加一或减一或不加不减
  － 当修改破坏了原本的子串时，\(cnt\) 减一
  － 当修改形成了新的子串时， \(cnt\) 加一

void solve()
{
    int n = read(), q = read();
    string s = sread();

    int cnt = 0;
    for(int i=0;i<n-2;i++){
        if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C'){
            cnt++;
        }
    }

    auto del = [&](int x){
        if((s[x] == 'A' && x < n-2 && s[x+1] == 'B' && s[x+2] == 'C')
        || (s[x] == 'B' && (x>0 && x<n-1) && s[x-1] == 'A' && s[x+1] == 'C')
        || (s[x] == 'C' && x > 1 && s[x-1] =='B' && s[x-2] == 'A'))
            cnt --;
    };

    auto add = [&](int x,char c){
        if((c == 'A' && x < n-2 && s[x+1] == 'B' && s[x+2] == 'C')
        || (c == 'B' && (x>0 && x<n-1) && s[x-1] == 'A' && s[x+1] == 'C')
        || (c == 'C' && x > 1 && s[x-1] =='B' && s[x-2] == 'A')){
            cnt ++;
        }
        s[x] = c;
    };

    while(q--){
        int x = read() - 1;
        char c; cin>>c;
        if(s[x] == c){
            cout<<cnt<<endl;
            continue;
        }
        del(x);
        add(x, c);
        cout<<cnt<<endl;
        //cout<<s<<endl;
    }
}

D - Buildings

题意：

给定 \(N\) 个建筑，依次求当 \(i = 1,2,...N\) 的时候 符合以下条件的 \(j\) 的个数
－ \(i\) 和 \(j\) 之间没有比\(j\)更高的建筑物

思路：

－ 考虑到 \(i\) 从1到N在不断删减元素比较复杂，就从后往前处理，每次增加一个元素
－ 维护一个递增的序列，每次新增元素就把新元素前面的元素（比该元素小的元素）都删除，因为新的元素比这些元素考前而比他们大，必定不能符合条件（类似于优先队列的思想）该序列的大小就是每次符合条件的个数

• 具体用 \(set\) 容器来实现，每次新增元素就 lower_bound 找到该元素在递增序列的位置，并用迭代器将查到的位置前面的元素全部删除，时间复杂度 \(O(nlongn)\)

void solve()
{
    int n = read();
    vector<int> v;
    for(int i=0;i<n;++i) v.emplace_back(read());
    
    set<int> st;
    vector<int> ans(n);
    ans[n-1] = 0;
    for(int i=n-1;i>0;i--){
        auto it = st.lower_bound(v[i]);
        if(it != st.end() && it != st.begin()){
            it--;
            while(it != st.begin()){
                it--;
                st.erase(next(it));
            }
            st.erase(it);
        }else if(it == st.end()){
            st.clear();
        }
        st.insert(v[i]);
        ans[i-1] = st.size()
    }
    for(auto it:ans) write(it); ED;
}