【自主命题】牛客小白月赛 89 题解

这是第一场所有赛题都由我命制的公开比赛,也是第二场我参与命题的公开比赛。

比赛时由于内测下来大家都觉得 D 比 E 难,就更换了 DE 的顺序,本篇题解中没有发生更换,望读者注意。

比赛链接:Link.

A. 伊甸之花

题目链接:Link.

若乐曲中同时存在 $1$ 和 $m$ 则无解,否则一定可以通过整体上移/下移一个音调来满足条件,时间复杂度 $O(n)$​。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,f1,f2;
int main(){
    f1=0;f2=0;
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x==1) f1=1;
        if(x==m) f2=1;
    }
    if(f1&f2) printf("No\n");
    else printf("Yes\n");    
    return 0;
}

B. 显生之宙

题目链接:Link.

考虑贪心。将所有数从小到大排列。然后依次遍历,如果是负数,就把他加给剩下的所有数,可以用一个变量维护这个加的值。如果是正数,就只把他加给下一个数。容易验证这是正确的,时间复杂度 $O(n)$​。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int T;
int n,a[N],now;
signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);now=0;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            a[i]+=now;
            if(a[i]<0) now+=a[i];
            else a[i+1]+=a[i];
        }
        printf("%lld\n",a[n]);
    }    

    return 0;
}

C. 太阳之华

题目链接:Link.

观察发现如果红方能一次吃完蓝方,就是红胜,否则一定是平局。故遍历所有红四连通块,寻找是否存在一个块能够一次性吃完蓝即可,时间复杂度 $O(nm)$。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int T,n,m,cnt,tot,blue,why;
int col[N][N];
char c[N][N];
bool vis[N][N],flag;
int px[4]={0,0,1,-1},py[4]={1,-1,0,0};
void dfs(int x,int y){
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+px[i],yy=y+py[i];
        if(xx<1||yy<1||xx>n||yy>m) continue;
        if(c[xx][yy]=='.'){
            if(col[xx][yy]!=cnt){
                col[xx][yy]=cnt;tot++;
            }
        }
        else{
            if(!vis[xx][yy]) dfs(xx,yy);
        }
    }
}
int main(){                                  
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);flag=0;blue=0;
        for(int i=1;i<=n;i++){
            scanf("%s",c[i]+1);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                vis[i][j]=0;
                if(c[i][j]=='.') blue++;
            }
        }
        if(blue==n*m){
            printf("Blue\n");
            continue;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(c[i][j]=='#'&&(!vis[i][j])){
                    cnt++;tot=0;
                    dfs(i,j);
                    if(tot==blue){flag=1;break;}
                }
            }
            if(flag) break;
        }
        if(flag) printf("Red\n");
        else printf("Draw\n");
    }       
    return 0;
}

D. 神性之陨(赛时为 E 题)

题目链接:Link.

观察发现,每一列的通路块都只能与上一列有且仅有 $1$ 个格子相连接。

故我们可以分为 $a_i=1$ 与 $a_i \neq 1 $ 讨论。

对于前者,可以放在上一列能够有通路块的所有行,可以用差分维护一下保证时间复杂度。

对于后者,可以放在上一列的所有可能的通路块的最上一格的更上(最下格与上一列的最上格为同一行)或最下一格的更下(最上格与上一列的最下格为同一行)。

可以用一个数组 $tag_{i,j}$ 进行记录,$tag_{i,j}=1$ 表示第 $i$ 列第 $j$ 行可以作为该列通路块的上端点,否则表示不行。时间复杂度为 $O(nm)$。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int T,n,m;
int a[N],b[N],ans;
bool tag[N][N];
int main(){ 
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);ans=0;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++) tag[i][j]=0;
        for(int i=1;i<=m;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) tag[1][i]=1;
        for(int i=1;i<=m-1;i++){
            if(a[i+1]!=1){
                for(int j=1;j<=n;j++){
                    if(!tag[i][j]) continue;
                    int below=j+a[i]-1;
                    if(j-(a[i+1]-1)>=1) tag[i+1][j-(a[i+1]-1)]=1;
                    if(below+(a[i+1]-1)<=n) tag[i+1][below]=1;
                }   
            }
            else{
                for(int j=1;j<=n;j++) b[j]=0;
                for(int j=1;j<=n;j++){
                    if(!tag[i][j]) continue;
                    b[j]++;b[j+a[i]]--;
                }               
                for(int j=1;j<=n;j++){
                    b[j]=b[j-1]+b[j];
                    if(b[j]>=1) tag[i+1][j]=1;
                }
            }
        }
        for(int i=1;i<=n;i++) if(tag[m][i]) ans++;
        printf("%d\n",ans);
    }
    return 0;
}

E. 冥古之潮(赛时为 D 题)

题目链接:Link.

首先发现我们并不关心每个点的具体位置,只关心其与点 $x$ 的最短距离。本图所有边长度均为 $1$,因此我们可以先用 bfs 求出所有点到 $x$ 的最短距离。

我们记与点 $x$ 距离为 $i$ 的点的数量为 $b_i$。又发现我们可以每次先选定 $k$ 个距离 $j_1,j_2\dots j_k$,然后其对应的方案数就是 $b_{j_1}b_{j_2}\dots b_{j_k}$。则问题转化为对于所有选择距离的方式,求其方案数的和即为总方案数,可以用 dp 解决。

记 $f_{i,j}$ 为考虑到距离 $i$,已经选择了 $j$ 个点的总方案数,则根据选不选择当前点,得到转移方程 $f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times b_i$。

记 $M=\max_{i=1}^n Dis_i$,最终时间复杂度为 $O(\max(q,n+m,Mk))$。

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int N=1e6+5;
const int M=2e6+5;
const int K=5e3+5;
const int mod=1e9+7;
struct node{
    int to,nxt;
}e[M];
int head[N],cnt;
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,m,Q,x,b[K],dis[N],maxn;
ll f[K][K];
void bfs(int s){
    queue<int> q;q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]==0&&v!=s){
                dis[v]=dis[u]+1;
                maxn=max(maxn,dis[v]);
                q.push(v);b[dis[v]]++;
            }
        }
    }
}
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&Q,&x);
    for(int i=1,u,v;i<=m;i++){
        scanf("%lld%lld",&u,&v);
        add(u,v);add(v,u);
    }
    bfs(x);
    f[0][0]=1;
    for(int i=1;i<=maxn;i++){
        f[i][0]=1;
        for(int j=1;j<=maxn;j++){
            f[i][j]=(f[i-1][j]+f[i-1][j-1]*(ll)b[i])%mod;
        }
    }
    while(Q--){
        int k;scanf("%lld",&k);
        if(k>maxn) printf("0\n");
        else printf("%lld\n",f[maxn][k]);
    }
    return 0;
}

F. 无垢之土

题目链接:Link.

解法一:

我们先随意指定一点为树根,对于任意两个生物 $u,v$,点 $a_u$ 和 $a_v$ 的最近公共祖先为 $L$,有 $dis_{a_u,a_v}=dis_{a_u,L}+dis_{L,a_v}$。因此对于点 $L$,其子树的两个以其为最近公共祖先的结点 $a_u,a_v$ 的相遇时间的两倍为 $\max{2t_u,2t_v,dis_{a_u,L}+t_u+dis_{a_v,L}+t_v}$。

先撇开 $2t_u$ 和 $2t_v$,我们记 $f_{i,0/1}$ 为以点 $i$ 为根的子树中,$dis_{a_u,i}+t_u$ 最小与次小的点,这是容易通过树形 dp 求得的。我们发现如果遍历整棵树,任意两点的最近公共祖先都会被遍历到,因此这样我们一定可以求得最小的 $dis_{a_u,L}+t_u+dis_{a_v,L}+t_v$ 的值。

我们可以通过二分答案消除 $2t_u$ 和 $2t_v$ 的影响。对于可能的答案 $mid$,我们仅考虑 $2t_i\le mid$ 的结点,并按上段的方法进行树形 dp,若 $\min_{i=1}^{n}(f_{i,0}+f_{i,1})\le mid$,我们认为 $mid$ 是一个可行的答案。

即 $T=\max_{i=1}^{m} t_i$,时间复杂度为 $O(n\log T)$​​。

Q: 没看懂为什么需要二分

A: 二分是为了防止出现“等”的情况,换言之,最终答案若为 A、B 两个生物,可能出现 A 生物走到 B 生物的出生点了,B 生物还没出生的情况。举个例子:

3 2
1 2
1 3
2 1
3 10

这组数据答案为 $20$.

解法二(idea from tokitsukaze):

将每个生物视作一个点,将其与其出生的结点连一条长度为出生时间的边。建一个超级源点连向所有生物,然后跑最短路+次短路,并记录次短路经过的生物的出生时间。然后对于每一个非自建的结点,我们依次认为这个点是第一次相遇的两个生物经过的点,那么,如果他的最短路的长度小于生物的出生时间,则取 $2$ 倍次短路作为可能的答案,否则,取最短路+次短路作为可能的答案。对所有这些可能的答案取 $\min$ 则得到最终答案。

用 Dijkstra 时间复杂度为 $O(n\log n)$。由于除了出生时间,所有树边长度均为 $1$,也可以通过 bfs 做到 $O(n+T)$​。

Code of Algorithm 1:

#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=5e5+5;
const int M=1e6+5;
const int inf=1e9;
char name[50];
struct node{
    int to,nxt;
}e[M];
int head[N],cnt;
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
vector<int> a[N];
int n,m,f[N][2],ans;
void dfs(int u,int fa,int mid){
    if(a[u].size()>=2){
        if(2*a[u][0]<=mid) f[u][0]=a[u][0];
        if(2*a[u][1]<=mid) f[u][1]=a[u][1];
    }
    else if(a[u].size()==1){
        if(2*a[u][0]<=mid) f[u][0]=a[u][0];
    }
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==fa) continue;
        dfs(v,u,mid);
        if(f[v][0]+1<f[u][0]){
            f[u][1]=f[u][0];
            f[u][0]=f[v][0]+1;
        }
        else if(f[v][0]+1<f[u][1]) f[u][1]=f[v][0]+1;
        if(f[v][1]+1<f[u][1]) f[u][1]=f[v][1]+1;
    }
    ans=min(ans,f[u][0]+f[u][1]);
}
bool check(int mid){
    for(int i=1;i<=n;i++) f[i][0]=f[i][1]=inf;
    ans=inf;dfs(1,1,mid);
    return ans<=mid;
}
int main(){
    scanf("%d%d",&n,&m);cnt=0;
    for(int i=1;i<=n;i++){
        head[i]=0;a[i].clear();
    }
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        a[x].pb(y);
    }
    for(int i=1;i<=n;i++){
        sort(a[i].begin(),a[i].end());
    }
    int l=0,r=3e6;
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇