小 S 的 ARC191 参赛记-1

ARIS2_0 · 2025-01-26 22:40:54 · 题解

又是一场 ARC，继上次 ARC189 0A 的惨状，小 S 决定，要再次找回属于自己的荣誉。

开赛了，读题后，有一个还算好想的结论：如果 m 个数中有些可以扔掉而不用全部覆盖，是可以用贪心去做的，即从小到大对于每一个 i，看是否有 a_i 不小于（注意不是大于）当前 b 中的最大值，如果是，这一位就选 a_i，否则选 b 中的最大值，然后将这个最大值去掉。

注意下文中的 a 皆为使用贪心策略覆盖后的 a。

不久，小 S 又意识到了一个重要结论：

• 对于贪心地覆盖，最后如果正确答案与贪心出来的答案不一样，肯定只有 b_m 的值会影响答案。因为答案不一样的话，无非就是覆盖的时候没有用到 b_m，导致 b_m 要强制覆盖在一个数上。而对于其他没有覆盖到的数，它们都可以覆盖在 b_m 要覆盖的地方，这样它们就没有影响了。

小 S 想：如果 b_m 在贪心覆盖的时候有用到，那直接输出 a 即可；如果 b_m 覆盖的时候没有用到，那 b_m 肯定是不大于 a 中所有其他数的。也就是说，我们要找到一个 a 上的数位，使得用 b_m 覆盖这个数位之后，a 减少的大小最小。

显然，a 上如果有 i 满足 a_i=b_m，直接覆盖即可；否则，b_m 覆盖在 a_n 上一定是最优的。

做法直接按上述过程模拟即可。

于是小 S 愉快地以两发罚时通过了此题，真是与 ARC189B 的 -10 截然不同的结局啊。

也许，这就是小 S 每天殷切地对着卫星许愿的原因吧。

S.A.T.E.L.L.I.T.E.

Code

#include<algorithm>
#include<bitset>
#include<deque>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector> 
#include<chrono>
#include<random>
#include<tuple>
#include<unordered_map>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define debug1(x) cerr<<#x<<"="<<x<<" "
#define debug2(x) cerr<<#x<<"="<<x<<"\n"
const int inf=1e16,maxn=1e6+10;
int a[maxn],ans[maxn],cnt[10];
struct node{int id,v;}b[maxn];
bool vis[maxn];
bool cmpv(node a,node b){return a.v>b.v;}
bool cmpid(node a,node b){return a.id<b.id;}
int read(){
    char c;cin>>c;
    return c-'0';
}
signed main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++)b[i].id=i,b[i].v=read();
    sort(b+1,b+m+1,cmpv);
    int tot=1;
    for(int i=1;i<=n;i++){
        if(a[i]>=b[tot].v or tot==m+1)ans[i]=a[i],vis[i]=1;
        else{
            ans[i]=b[tot].v;
            cnt[b[tot].v]++;
            tot++;
        }
    }
    sort(b+1,b+m+1,cmpid);
    bool g=cnt[b[m].v];
    for(int i=1;i<=n;i++){
        if(vis[i] and a[i]==b[m].v){
            g=1;break;
        }
    }
    if(!g)ans[n]=b[m].v;
    for(int i=1;i<=n;i++)cout<<ans[i];
    cout<<"\n";
    return 0;
}
/*
clang++ -std=c++14 -Wall -Wextra -Wshadow -Wconversion -Wl,-stack_size -Wl,512000000
*/

后记

小 S 的 ARC191 参赛记-2（即 ARC191B 题解）