七海ノ心象素描

所有的为时已晚都是恰逢其时

ABC416

题解

如月七海
如月七海 局外人
2025年07月27日
预计阅读 12 分钟
2442 字

真身败名裂了。

A

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int n, l, r;
string s;
signed main() {
    n=read(), l=read(), r=read();
    cin>>s;
    int fg=1;
    rep(i,l-1,r-1) if(s[i]!='o') fg=0;
    puts(fg? "Yes":"No");
    return 0;
}

B

想死了。

自己的做法是这样的。肉眼看出我们可以在每个#两边极远处的.放o，单调栈出来加上一堆判断就行。

因为实现不好导致浪费了 50min……

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
string s;
int n, l[105], r[105];
int top, st[105];
signed main() {
    cin>>s;
    n=s.size();
    s=" "+s;
    rep(i,1,n) {
        while(top&&s[st[top]]!='#') {
            --top;
        }
        l[i]=st[top];
        st[++top]=i;
    }
    top=0;
    per(i,n,1) {
        while(top&&s[st[top]]!='#') --top;
        r[i]=st[top];
        st[++top]=i;
    }
    int cnt=0, L=0, R=n;
    rep(i,1,n) if(s[i]=='#') {
        if(!l[i]) l[i]=0;
        if(!r[i]) r[i]=n+1;
        int fg=1;
        rep(j,l[i]+1,i) if(s[j]=='o') fg=0;
        if(fg&&s[l[i]+1]!='#') s[l[i]+1]='o', cnt++;
        fg=1;
        rep(j,i,r[i]-1) if(s[j]=='o') fg=0;
        if(fg&&s[r[i]-1]!='#') s[r[i]-1]='o', cnt++;
    }
    if(!cnt) {
        rep(i,1,n) {
            if(s[i]=='.') s[i]='o';
            break;
        }
    }
    // cout<<s;
    for(auto x:s) if(x!=' ') printf("%c",x);
    return 0;
}

事实上，答案不唯一，是不是极远处根本无所谓，所以直接在每个#后面的.放o就能满足条件。

在最前面加上一个字符#即可。

给出题解代码吧，太耻辱了……

#include <bits/stdc++.h>
using namespace std;


int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<char> t(n);
    for (int i = 0; i < n; i++) {
        if (s[i] == '#') {
            cout << '#';
        } else if (i == 0 || s[i - 1] == '#') {
            cout << 'o';
        } else {
            cout << '.';
        }
    }
    cout << endl;
    return 0;
}

C

痛。

我在那算方案，直接爆搜再排序就行。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int n, k, x;
string s[20];
vector<string> ans;
void dfs(int now,string t) {
    if(now==k) {
        ans.eb(t);
        return;
    }
    rep(i,1,n) {
        dfs(now+1,t+s[i]);
    }
}
signed main() {
    n=read(), k=read(), x=read();
    rep(i,1,n) cin>>s[i];
    dfs(0,"");
    sort(ans.begin(),ans.end());
    cout<<ans[x-1];
    return 0;
}

D

注意到 Ai,Bi∈[0,M)A_i,B_i \in [0,M)，那么当且仅当 Ai+Bi≥MA_i + B_i \ge M，会让答案减小一个定值 MM。问题转化为对于尽可能多的 AiA_i，找 BjB_j 与其匹配，满足 Ai+Bj≥MA_i+B_j \ge M。

显然较大的 AiA_i 更易满足条件。从大到小考虑，用std::multiset维护 Bi{B_i}，找到大于等于 M−AiM-A_i 的最小的 BjB_j。如果不存在，那么取最小值一定最优。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=3e5+5;
int T, n, mod, a[N], b[N];
multiset<int> s;
void solve() {
    s.clear();
    n=read(), mod=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n) b[i]=read(), s.insert(b[i]);
    sort(a+1,a+n+1);
    ll ans=0;
    per(i,n,1) {
        auto p=s.lower_bound(mod-a[i]);
        if(p!=s.end()) {
            ans+=(a[i]+(*p))%mod;
            s.erase(p);
        } else {
            ans+=a[i]+(*s.begin());
            s.erase(s.begin());
        }


    }
    cout<<ans<<endl;
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

E

Trick 都忘光了……

没有机场怎么做？先跑 Floyd\text{Floyd}。对于加边操作，枚举 (i,j)(i,j)，用 d(i,x)+z+d(y,j)d(i,x)+z+d(y,j) 和 d(i,y)+z+d(x,j)d(i,y)+z+d(x,j) 更新 d(i,j)d(i,j) 即可。

有机场怎么办？建一个虚点。机场到达虚点需要时间 TT，虚点到达任何机场需要时间 00。这样就能描述从某点到机场，再中转其他点，再到另一个点的过程。

建立机场，拿着这两条边更新即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const ll inf=1e15;
const int N=505;
int T, n, m, k, Q;
ll f[N][N];
vector<int> ap;
void Floyd() {
    rep(k,1,n+1) rep(i,1,n+1) rep(j,1,n+1) {
        f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    }
}
signed main() {
    n=read(), m=read();
    rep(i,1,n+1) {
        rep(j,1,n+1) f[i][j]=inf;
        f[i][i]=0;
    }
    rep(i,1,m) {
        int x=read(), y=read(), z=read();
        f[x][y]=f[y][x]=min(f[x][y],1ll*z);
    }
    k=read(), T=read();
    rep(i,1,k) {
        int x=read();
        f[x][n+1]=T, f[n+1][x]=0;
        // ap.eb(x);
    }
    for(auto x:ap) for(auto y:ap) f[x][y]=f[y][x]=min(f[x][y],1ll*T);
    Floyd();
    Q=read();
    while(Q--) {
        int op=read();
        if(op==1) {
            int x=read(), y=read(), z=read();
            rep(i,1,n+1) rep(j,1,n+1) f[i][j]=min({f[i][j],f[i][x]+z+f[y][j],f[i][y]+z+f[x][j]});
        }
        if(op==2) {
            int x=read();
            f[x][n+1]=T, f[n+1][x]=0;
            rep(i,1,n+1) rep(j,1,n+1) {
                f[i][j]=min(f[i][j],f[i][x]+T+f[n+1][j]);
                f[i][j]=min(f[i][j],f[i][n+1]+f[x][j]);
            }
        }
        if(op==3) {
            ll ans=0;
            rep(i,1,n) rep(j,1,n) if(f[i][j]<1e15) ans+=f[i][j];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

F

桑之未落，其叶沃若。

不难发现，对于一棵子树，其根节点只有三种情况。

  1. 不在任何一条链中。

  2. 在一条链的末端。

  3. 在一条链的中间。

考虑子树合并的过程：以 yy 为根的子树加入以 xx 为根的子树。前者链数为 jj，后者链数为 ii。

如果不连接 x,yx,y，那么新子树的链数就是 i+ji+j。我们取其最大值即可。

如果连接 x,yx,y，那就要分两种情况。

  1. xx 在一条链的末端。此时链数为 i+j∈[1,k]i+j \in [1,k]。

  2. xx 在一条链的中间。此时链数为 i+j−1∈[1,k]i+j-1 \in [1,k]。

都要求 yy 必须在一条链的末端。

因此，设 f(x,i,0/1/2)f(x,i,0/1/2) 表示，以 xx 为根的子树，选出了 ii 条链，其中 xx 的情况是 无限制/必须在链的末端/必须在链的中间，所能得到的最大收益。

转移就是朴素的树上背包，比上述讨论多了在不连接的情况下，对应状态的继承。具体细节见代码。

为啥 00 状态时这个意思呢？相当于包含了情况 1 并取了个 max⁡\max，便于转移。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=2e5+5;
const ll inf=1e18;
int n, k, a[N];
ll f[N][6][3], g[6][3];
vector<int> p[N];
void dfs(int x,int fa) {
    rep(i,0,k) rep(j,0,2) f[x][i][j]=-inf;
    f[x][0][0]=0;
    for(auto y:p[x]) if(y!=fa) {
        dfs(y,x);
        rep(i,0,k) {
            g[i][0]=f[x][i][0];
            g[i][1]=f[x][i][1];
            g[i][2]=f[x][i][2];
        }
        for(int i=0;i<=k;i++) for(int j=0;j<=k;j++) {
            if(i+j<=k) {
                g[i+j][0]=max(g[i+j][0],f[x][i][0]+f[y][j][0]);
                // 无限制，随便转移，反正不连接
                g[i+j][1]=max({g[i+j][1],f[x][i][1]+f[y][j][0],f[x][i][0]+a[x]+f[y][j][1]});
                // 不连接，x要求1状态，y无所谓
                // 连接不再赘述
                g[i+j][2]=max(g[i+j][2],f[x][i][2]+f[y][j][0]);
                // 不连接，同上
            }
            if(i+j-1>0&&i+j-1<=k) g[i+j-1][2]=max(g[i+j-1][2],f[x][i][1]+f[y][j][1]);
            // 连接，会共用一条链。要求二者都得在末端
        }
        rep(i,0,k) {
            f[x][i][0]=g[i][0];
            f[x][i][1]=g[i][1];
            f[x][i][2]=g[i][2];
        }
    }
    rep(i,1,k) f[x][i][1]=max(f[x][i][1],f[x][i-1][0]+a[x]);
    rep(i,0,k) f[x][i][0]=max({f[x][i][0],f[x][i][1],f[x][i][2]});
}
signed main() {
    n=read(), k=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n-1) {
        int x=read(), y=read();
        p[x].eb(y);
        p[y].eb(x);
    }
    dfs(1,0);
    ll ans=0;
    rep(i,0,k) ans=max(ans,f[1][i][0]);
    printf("%lld\n",ans);
    return 0;
}

G

不会。

觉得这篇文章怎么样？

点个赞，让更多人看到！

分享这篇文章

知识因分享而增值

Twitter Telegram 微博 QQ Facebook LinkedIn

分类

比赛
算法竞赛
题解

标签

dp
图论
最短路
树形dp
背包
贪心

版权声明：本文作者为 如月七海，首发于nanami7.top。

遵循 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

评论区

本评论区由 EveSunMaple自主开发