Codeforces Round 910 (Div. 2)

https://codeforces.com/contest/1898

B. Milena and Admirer

题意

给定一个长度为 $n$ 的数组 $a$。每次操作可以选择一个 $a_i$，并选择一个 $x$ 满足 $1\leq x<a_i$。用 $x,a_i-x$ 替换 $a_i$。求最小操作次数，使得 $a$ 单调不降。

数据范围：$1\leq n\leq 2\times10^5,1\leq a_i\leq 10^9$。

题解

倒着考虑，当遇到 $a_i>a_{i+1}$ 时， $a_i$ 需要拆成 $x=\lceil\dfrac{a_i}{a_{i+1}}\rceil$ 份，那么其中最小的数 $y=\lfloor\dfrac{a_i}{x}\rfloor$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        ll ans=0;
        for(int i=n-1;i;i--)
            if(a[i]>a[i+1])
            {
                ll x=(a[i]+a[i+1]-1)/a[i+1];
                ll y=a[i]/x;
                ans+=x-1;
                a[i]=y;
            }
        cout<<ans<<'\n';
    }
    return 0;
}

D. Absolute Beauty

题意

给定两个数组 $a,b$，长度为 $n$。可以交换一次 $b$ 中的两个元素，使得

$$\sum_{i=1}^n|a_i-b_i|$$

最大。

数据范围：$2\leq n\leq 2\times10^5$。

题解

将位置分为 $a_i\geq b_i$ 和 $a_i\leq b_i$ 两类。分类讨论一下交换的两个位置属于哪一类即可。

E. Sofia and Strings

题意

给定两个串 $s,t$。每次操作可以删除 $s$ 中的一个元素或将 $s$ 的一段区间按升序排列。问是否能将 $s$ 变成 $t$。

题解

考虑维护 $s$ 每个字符的位置。枚举 $t$ 的每一位进行匹配。每次选择了一个 $s$ 的字符后，要将它前面且字典序比它小的字符都删掉（因为它们无法通过排序移动到该字符后面，无法再用于匹配）。

代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n,m;cin>>n>>m;
    string s,t;cin>>s>>t;
    set<int> pos[26];
    for(int i=0;i<n;i++) pos[s[i]-'a'].insert(i);
    for(int i=0;i<m;i++)
    {
        int x=t[i]-'a';
        if(pos[x].empty()) 
        {
            cout<<"NO"<<'\n';
            return;
        }
        auto y=*pos[x].begin();
        pos[x].erase(pos[x].begin());
        for(int j=0;j<x;j++)
            while(!pos[j].empty()&&*pos[j].begin()<y) pos[j].erase(pos[j].begin());
    }
    cout<<"YES"<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}