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

比赛时由于内测下来大家都觉得 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;
}