牛客小白月赛89 命题人题解
好像题目命的有那么一点点难了，谢罪，下次一定出简单一点（确信），或者去出练习赛（bushi）。
炸鸡块君老师的视频题解讲得比较详细，欢迎大家移步 https://space.bilibili.com/414380929 进行观看~
A. 伊甸之花
若乐曲中同时存在 和
则无解，否则一定可以通过整体上移/下移一个音调来满足条件，时间复杂度
。
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. 显生之宙
考虑贪心。将所有数从小到大排列。然后依次遍历，如果是负数，就把他加给剩下的所有数，可以用一个变量维护这个加的值。如果是正数，就只把他加给下一个数。容易验证这是正确的，时间复杂度 。
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. 太阳之华
观察发现如果红方能一次吃完蓝方，就是红胜，否则一定是平局。故遍历所有红四连通块，寻找是否存在一个块能够一次性吃完蓝即可，时间复杂度 。
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. 冥古之潮
首先发现我们并不关心每个点的具体位置，只关心其与点 的最短距离。本图所有边长度均为
，因此我们可以先用 bfs 求出所有点到
的最短距离。
我们记与点 距离为
的点的数量为
。又发现我们可以每次先选定
个距离
，然后其对应的方案数就是
。则问题转化为对于所有选择距离的方式，求其方案数的和即为总方案数，可以用 dp 解决。
记 为考虑到距离
，已经选择了
个点的总方案数，则根据选不选择当前点，得到转移方程
。
记 ，最终时间复杂度为
。
#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;
}
E. 神性之陨
观察发现，每一列的通路块都只能与上一列有且仅有 个格子相连接。
故我们可以分为 与
讨论。
对于前者，可以放在上一列能够有通路块的所有行，可以用差分维护一下保证时间复杂度。
对于后者，可以放在上一列的所有可能的通路块的最上一格的更上（最下格与上一列的最上格为同一行）或最下一格的更下（最上格与上一列的最下格为同一行）。
可以用一个数组 进行记录，
表示第
列第
行可以作为该列通路块的上端点，否则表示不行。时间复杂度为
。
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;
}
F. 无垢之土
解法一：
我们先随意指定一点为树根，对于任意两个生物 ，点
和
的最近公共祖先为
，有
。因此对于点
，其子树的两个以其为最近公共祖先的结点
的相遇时间的两倍为
。
先撇开 和
，我们记
为以点
为根的子树中，
最小与次小的点，这是容易通过树形 dp 求得的。我们发现如果遍历整棵树，任意两点的最近公共祖先都会被遍历到，因此这样我们一定可以求得最小的
的值。
我们可以通过二分答案消除 和
的影响。对于可能的答案
，我们仅考虑
的结点，并按上段的方法进行树形 dp，若
，我们认为
是一个可行的答案。
即 ，时间复杂度为
。
Q: 没看懂为什么需要二分。
A: 二分是为了防止出现“等”的情况，换言之，最终答案若为 A、B 两个生物，可能出现 A 生物走到 B 生物的出生点了，B 生物还没出生的情况。举个例子：
3 2
1 2
1 3
2 1
3 10
这组数据答案为 .
解法二（idea from tokitsukaze）:
将每个生物视作一个点，将其与其出生的结点连一条长度为出生时间的边。建一个超级源点连向所有生物，然后跑最短路+次短路，并记录次短路经过的生物的出生时间。然后对于每一个非自建的结点，我们依次认为这个点是第一次相遇的两个生物经过的点，那么，如果他的最短路的长度小于生物的出生时间，则取 倍次短路作为可能的答案，否则，取最短路+次短路作为可能的答案。对所有这些可能的答案取
则得到最终答案。
用 Dijkstra 时间复杂度为 。由于除了出生时间，所有树边长度均为
，也可以通过 bfs 做到
。
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;
}
