比赛心得 - ABC392

· · 算法·理论

\tt ABC392

精巧玲珑的题，让人很舒服。

除了费用流。

Ivan422 唐又唐又唐，F 题细节打错最终遗憾离场。

\tt A\ \color{FE4C61} \tiny RM

《重生之 2 只高桥被毒死了》

唐题，大力 if 即可。

string s1,s2;
signed main(){
    io;
    cin>>s1>>s2;
    if(s1=="sick"&&s2=="sick")cout<<1;
    else if(s1=="sick"&&s2=="fine")cout<<2;
    else if(s1=="fine"&&s2=="sick")cout<<3;
    else cout<<4;
    return 0;
}

\tt B\ \color{FE4C61} \tiny RM

大力模拟即可。

你想中心扩展法也可以。

string s;
int n,ans;
signed main(){
    io;
    cin>>s;n=s.size();s=" "+s;
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)for(int k=j+1;k<=n;k++){
        ans+=(s[i]=='A'&&s[j]=='B'&&s[k]=='C'&&j-i==k-j);
    }
    cout<<ans;
    return 0;
}

\tt C\ \color{F39C11} \tiny \texttt{PJ-}

简单图判定。

直接上 set 即可。

set<pair<int,int> >st;
int n,m,u,v;
signed main(){
    io;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        if(u==v)continue;
        if(u>v)swap(u,v);
        st.insert({u,v});
    }
    cout<<m-st.size();  
    return 0;
}

\tt D\ \color{FFC116} \tiny \texttt{PJ/TG-}

前缀和思想，可以放 J T3。

考虑枚举哪个点集中，那么我们就可以预处理出一个点左边的点往 i 聚集，求出 l_i，r_i 同理，最后求出答案即可。

ll ans,l[N],r[N],su,sz,nl,nr;
string s;
signed main(){
    io;
    cin>>n>>s;s=" "+s;  
    su=0,sz=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')su+=i,sz++;
        nl=i-sz+1,nr=i;
        l[i]=(nr+nl)*sz/2-su;
    }
    su=0,sz=0;
    for(int i=n;i>=1;i--){
        if(s[i]=='1')su+=i,sz++;
        nl=i,nr=i+sz-1;
        r[i]=su-(nr+nl)*sz/2; 
    }
    ans=1e18;
    for(int i=1;i<n;i++)ans=min(ans,l[i]+r[i+1]);
    cout<<ans;
    return 0;
}

\tt E\ \color{3498DB} \tiny \texttt{TG+/SX-}（个人差异题）

直接枚举因数，对倍数统计一下。

注意到 k 是固定的，那么每个因数可以直接判定是否有 \ge k 倍数，要是有就可以选，那么更新每一个 ans。

抽象题。

int n,k,a[N],d[N],cnt[M],m,ans[M];
int mp[M];
signed main(){
    io;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],m=max(m,a[i]);
    for(int i=1;i<=n;i++)mp[a[i]]++;
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j+=i)cnt[i]+=mp[j];
    }
    for(int i=1;i<=m;i++)if(cnt[i]>=k){
        for(int j=i;j<=m;j+=i)ans[j]=max(ans[j],i);
    }
    for(int i=1;i<=n;i++){
        cout<<ans[a[i]]<<"\n";
    }
    return 0;
}

\tt F\ \color{52C41A} \tiny \texttt{PJ+/TG}

前言：

我是奶龙

我是奶龙！
我是奶龙！
我才是奶龙！

今夜星光闪闪~
我爱你的心满满
想你一晚又一晚
把爱你的心都填满
想吃爱情的苦
做你的小公主
月亮不睡我不睡
我是人间小美味
先擦鼻涕后提裤
后提裤后提裤
从此走向社会步
社会步社会步
先擦鼻涕后提裤
先擦鼻涕后提裤
从此走向社会步
从此走向发岁

写个 LIS，然后离线下来，二分即可。

int n,q,a[N],cur,f[N],l[N],ans[N],r,x;
vector<pair<int,int>>qr[N];
signed main(){
    io;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=q;i++){
        cin>>r>>x;
        qr[r].push_back({i,x});
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++){
        int fd=lower_bound(f+1,f+n+1,a[i])-f;
        f[fd]=a[i];
        for(auto v:qr[i])ans[v.first]=upper_bound(f+1,f+n+1,v.second)-f-1;
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    return 0;
}