Logo

菜单

2025.6.26模拟赛-来点不一样的做法吧

wjyppm
发布于 2025-06-26 / 31 阅读
0
0
#题解

2026.6.26 15:03 我 H 题解在狗叫，已修复。

我没有 AK 因为这是模拟赛，我不可能 AK 的。

还是太菜了(｡ŏ_ŏ)，二本说它们能 AK，不过这时间真的可以吗？

还有可能是因为今天运气不太好？

1750920394113.png

本场比赛你能见到：

  1. 一直在狗叫的 ppm。
  2. 最后 10 分钟发疯的 ppm。
  3. 3小时拼手速。

1.题解

A - Letter Home

如果 s 在左右端点中间，那么先走左再走右要么先走右在走左。如果不再中间那么走最远的一定能覆盖到，时间复杂度为 O(n) \to O(n \log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e5+15;
int n,m,a[MN];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    if(m<=a[1]) cout<<a[n]-m<<'\n';
    else if(m>=a[n]) cout<<m-a[1]<<'\n';
    else cout<<a[n]-a[1]+min(m-a[1],a[n]-m)<<'\n';
}

signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

B - Above the Clouds

能满足 a+b+c=s，并且 b 是 a,c 子串的的话，那么这个字符串显然不是凭空构造出来了，只能由原字符串构造出来，如果存在除首尾以外的字符在字符串中出现至少两次则存在，否则不存在。

#include<bits/stdc++.h>
using namespace std;
int cnt[27],n;
string s;

void solve(){
    cin>>n>>s;
    memset(cnt,0,sizeof(cnt));
    for(auto c:s){
        cnt[c-'a']++;
    }
    for(int i=1;i<s.size()-1;i++){
        if(cnt[s[i]-'a']>=2){
            cout<<"Yes\n";
            return;
        }
    }
    cout<<"No\n";
}


int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

C - Those Who Are With Us

注意到一次只能减一个十字，考虑暴力枚举我们要减的十字位置，如果这个十字在行和列上能覆盖所有的最大值位置，那么答案就是 maxx-1，否则为 maxx，其中 maxx 为矩阵的最大值，时间复杂度 O(nm) \to O(nm \log n) 因为我用 map 了。

#include<bits/stdc++.h>
#define pir pair<int,int>
using namespace std;
int T,n,m,maxx,mxcnt,tcnt;
map<int,int> mph,mpl;

void solve(){
    cin>>n>>m;
    mph.clear();
    mpl.clear();
    maxx=-1e9;
    mxcnt=0;
    vector<int> a[n+5];
    for(int i=1;i<=n;i++){
        a[i].resize(m+5);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            maxx=max(maxx,a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==maxx){
                mph[i]++;
                mpl[j]++;
                mxcnt++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mph[i]+mpl[j]+(a[i][j]==maxx?-1:0)>=mxcnt){
                cout<<maxx-1<<'\n';
                return;
            }
        }
    }
    cout<<maxx<<'\n';
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

D - 1709

考虑将 a,b 存新数组 c,d 让后排序，让后按照从大到小的顺序将 a,b 给交换成 c,d 的顺序。让后在进行 c_{i}>d_{i} 的交换，容易证明交换次数为 n(n-1)+n=n^2=1600，可以通过。

为什么赛时不给 checker 啊还要我手模。

#include<bits/stdc++.h>
#define pir pair<int,int>
using namespace std;
constexpr int MN=1e5+15;
int T,a[MN],b[MN],c[MN],d[MN],n;
bool vis[MN];
vector<pir> op;

void clear(){
    op.clear();
    for(int i=1;i<=2*n;i++) vis[i]=0;
}

void solve(){
    cin>>n;
    clear();
    for(int i=1;i<=n;i++){
        cin>>a[i];
        c[i]=a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        d[i]=b[i];
    }
    sort(c+1,c+1+n);
    sort(d+1,d+1+n);
    for(int i=n;i>=1;i--){
        int pos;
        for(int j=1;j<=n;j++){
            if(a[j]==c[i]){
                pos=j;
                break;
            }
        }
        if(pos>i){
            for(int j=pos-1;j>=i;j--){
                op.push_back(pir(1,j));
                swap(a[j],a[j+1]);
            }
        }else if(pos<i){
            for(int j=pos;j<i;j++){
                op.push_back(pir(1,j));
                swap(a[j],a[j+1]);
            }
        }
    }
    for(int i=n;i>=1;i--){
        int pos;
        for(int j=1;j<=n;j++){
            if(b[j]==d[i]){
                pos=j;
                break;
            }
        }
        if(pos>i){
            for(int j=pos-1;j>=i;j--){
                op.push_back(pir(2,j));
                swap(b[j],b[j+1]);
            }
        }else if(pos<i){
            for(int j=pos;j<i;j++){
                op.push_back(pir(2,j));
                swap(b[j],b[j+1]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(c[i]>d[i]) op.push_back(pir(3,i));
    }
    cout<<op.size()<<'\n';
    for(auto p:op){
        cout<<p.first<<" "<<p.second<<'\n';
    }
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

E - Sponsor of Your Problems

考虑从大到小分类讨论，分类讨论如下：

  • 若 l_{i}=r_{i}，则只能硬取，答案加 1。
  • 若 r_{i}-l_{i}>1，那么我们取 l_{i}+1，后面我们就随便取了。
  • 若 r_{i}-l_{i}=1：
    • 若当前位取 l_{i}，那么若接下来 l_{j}=9，那么只能取 9，反之可以取 l_{j}+1（注意 l_{j}=8,r_{j}=9 的时候答案加 1），让后随便取。
    • 若当前位取 r_{i}，那么若接下来 l_{j}=0，那么只能取 0，反之可以取 r_{j}+1（注意 l_{j}=1,r_{j}=0 的时候答案加 1），让后随便取。

让后就做完了，时间复杂度 O(\log_{10} n) 但根本跑不满。

数位 DP 也可以做，模板题，不是哥们这是 DIV 3？

能不能再给力一点啊！

考虑暴力枚举在 [l_{i},r_{i}] 暴力随机数，随机 x 最坏情况下就是位数相同，概率为 (\dfrac{4}{5})^9，大约为百分之 13，考虑随机 100 个数取最小的 f(l,x)+f(x,r)，那么答案是 WA 的概率为 (1-(\dfrac{4}{5})^9)^{100}，约为 5\times 10^{-7}，随机 1000 个将为 10^{-25}，忽略不计 AC。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=520;
int l[MN],r[MN],n,lans,rans;
string lst,rst;

void solve(){
    cin>>lst>>rst;
    n=lst.length();
    for(int i=0;i<n;i++){
        l[i]=lst[i]-'0';
        r[i]=rst[i]-'0';
    }
    for(int i=0;i<n;i++){
        if(l[i]==r[i]) continue;
        if(r[i]-l[i]>1){
            cout<<(i)*2<<'\n';
            return;
        }else{
            int lv=1,rv=1;
            for(int j=i+1;j<n;j++){
                if(l[j]==9){
                    lv+=1+(r[j]==9);
                }else{
                    if(l[j]==8&&r[j]==9) lv++;
                    break;
                }
            }
            for(int j=i+1;j<n;j++){
                if(r[j]==0){
                    rv+=1+(l[j]==0);
                }else{
                    if(l[j]==1&&r[j]==0) rv++;
                    break;
                }
            }
            cout<<min(lv,rv)+(i)*2<<'\n';
            return;
        }
    }
    cout<<n*2<<'\n';
}

signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F - Yamakasi

考虑没有 \max 的限制的时候怎么做，有一个显然的想法就是双指针，右端点不断往右扫，若扫到 >s 的位置就让左端点缩小。想法很美好现实很骨感，因为有负数所以前缀和不单调。

但是我们可以这么考虑，我们还是右端点不断往右拓展，让后用 map 记录前缀和为 sum 时的出现次数，每次扫的时候我们答案加上 map[sum-s]，即可。

但现在有最大值啦，怎么办，这个时候我们不能只维护出现次数了，我们必须维护前缀和为 sum 的端点，多了最大值的限制后，我们需要维护最后一个值为 x 出现的下表 posl 和最后一个值大于 x 的下表 posr，那么在遍历位置的时候，我们只需要前缀和为 sum-s 在 [posl,posr] 出现的次数即可，map+vector+二分即可做到。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2e5+15;
int n,s,x,a[MN],ans,posl,posr,sum;
map<int,vector<int>> mp;

void clear(){
    mp.clear();
    mp[0].push_back(0);
    posr=posl=-1e9;
    sum=ans=0;
}

void solve(){
    cin>>n>>s>>x;
    clear(); 
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(a[i]==x) posr=i;
        else if(a[i]>x) posl=i;
        if(posr!=-1e9&&mp.count(sum-s)&&posr>=posl){
            auto r=lower_bound(mp[sum-s].begin(),mp[sum-s].end(),posr),l=lower_bound(mp[sum-s].begin(),mp[sum-s].end(),posl);
            ans+=r-l;
        }
        mp[sum].push_back(i);
    }
    cout<<ans<<'\n';
}

signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

G - 没写

没时间写了啊( •́ὤ•̀)

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2e5+15;
int ans,pre[MN],n;
string s;

void solve(){
    cin>>n>>s;
    ans=0;
    for(int i=0;i<n;i++){
        pre[i+1]=pre[i];
        if(s[i]=='0') pre[i+1]--;
        else pre[i+1]++;
    }
    for(int i=1;i<=n;i++){
        ans+=i*(n-i+1);
    }
    sort(pre,pre+1+n);
    for(int i=0;i<=n;i++){
        ans+=pre[i]*(i-(n-i));
    }
    cout<<ans/2<<'\n';
}

signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

H - Ice Baby

这一点都不好玩，拼手速局吗？

考虑什么时候能取到长度最大值，显然对于每一个 a_{i} 有两个决策，要么就是取下界 l_{i}，要么就是延伸末尾的值取等，就是令当前值为 a_{j}，注意 j<i,a_{j}\ge l_{i}。

  • 取 l_{i}，那么对于序列中在区间 [1,i-1] 结尾值 \le l_i 的最长不下降字序列长度 +1，让后丢到 l_i 上。
  • 不取 l_{i}，那么只能取 [l_{i}+1,r_{i}]，那么对于序列中在区间 [1,i-1] 结尾值 [l_{i}+1,r_{i}] 的最长不下降字序列长度 +1。

这是线段树维护 \max 和区间加和单点修改，时间复杂度 O(n \log n)，注意要离散化不然会炸掉。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=5e5+15;
int T,n,tot,b[MN],L[MN],R[MN];

struct Segment{
#define ls p<<1
#define rs p<<1|1
    struct Node{
        int l,r,val,add;
    }t[MN<<2];

    void doadd(int p,int k){
        t[p].val+=k;
        t[p].add+=k;
    }

    void pushdown(int p){
        if(t[p].add){
            doadd(ls,t[p].add);
            doadd(rs,t[p].add);
            t[p].add=0;
        }
    }

    void pushup(int p){
        t[p].val=max(t[ls].val,t[rs].val);
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        t[p].add=0;
        if(l==r){
            t[p].val=0;
            return;
        }
        int mid=(t[p].l+t[p].r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }

    void modify(int p,int fl,int fr,int k){
        if(t[p].l>=fl&&t[p].r<=fr){
            doadd(p,k);
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) modify(ls,fl,fr,k);
        if(mid<fr) modify(rs,fl,fr,k);
        pushup(p);
    }

    void modify(int p,int pos,int k){
        if(t[p].l==t[p].r){
            t[p].val=k;
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=pos) modify(ls,pos,k);
        else modify(rs,pos,k);
        pushup(p);
    }

    int query(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            return t[p].val;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1,ret=-1e9;
        if(mid>=fl) ret=query(ls,fl,fr);
        if(mid<fr) ret=max(ret,query(rs,fl,fr));
        return ret;
    }

#undef ls
#undef rs
}sg;

void clear(){
    tot=0;
}

void solve(){
    cin>>n;
    clear();
    for(int i=1;i<=n;i++){
        cin>>L[i]>>R[i];
        b[++tot]=L[i];
        b[++tot]=R[i];
    }
    sort(b+1,b+1+tot);
    tot=unique(b+1,b+1+tot)-b-1;
    for(int i=1;i<=n;i++){
        L[i]=lower_bound(b+1,b+1+tot,L[i])-b;
        R[i]=lower_bound(b+1,b+1+tot,R[i])-b;
    }
    sg.build(1,1,tot);
    for(int i=1;i<=n;i++){
        int c=sg.query(1,1,L[i])+1;
        sg.modify(1,L[i],c);
        if(L[i]!=R[i]) sg.modify(1,L[i]+1,R[i],1); // 因为没判炸缸2.5
        cout<<sg.t[1].val<<" ";
    }
    cout<<'\n';
}

signed main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

2.后言

DIV3 的题对我来说应该是难度比较小的，但是赛前心态崩了，因为自己模拟赛打得少而且总是沉溺于过去的成绩（没错说的就是橙题没切导致差点自暴自弃）。

还是马克思的话好：

后悔过去，不如奋斗将来！——马克思

还是太菜了，加训！

Mr.Tenna's TV Time!

评论