牛客小白月赛89（A,B,C,D,E,F）

本文主要是介绍牛客小白月赛89（A,B,C,D,E,F），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛链接

官方视频讲解（个人觉得讲的还是不错的）

这把BC偏难，差点就不想做了在这里插入图片描述，对小白杀伤力比较大。后面的题还算正常点。

A 伊甸之花

思路：

发现如果这个序列中最大值不为 $k$ ，我们可以把序列所有数都加 $1$ ，这样所有数一定不会超出范围，也就得到了一种可行解。同理，若序列中最小值不为 $1$ ，就可以给序列所有数减 $1$ 。

但是如果序列最小值顶到了 $1$ ，最大值顶到了 $k$ ，那么序列就完全无法整体上下移动，也就无解。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int inf=1e9;int n,m,minn=inf,maxx=-inf;int main(){cin>>n>>m;for(int i=1,t;i<=n;i++){cin>>t;minn=min(minn,t);maxx=max(maxx,t);}if(minn==1 && maxx==m)puts("No");else puts("Yes");return 0;
}

B 显生之宙

思路：

手玩一下，其实不难发现操作的顺序是固定的：先操作当前剩余序列的最小的负数，给其他所有数加上这个负数，操作完负数后，正数加起来就是答案。

因为我们处理元素是从小到大，所以先排个序。最后一个数一定留着不操作，所以我们把正数都累加到 $a_n$ 上，最后的答案就是 $a_n$ 了。

但是这里元素值是在时刻变化的，而且处理负数的时候是区间操作。考虑我们设置一个累加变量，给后面加上的数我们先存放在这个变量里，到后面处理到某个元素的时候，再把影响附加到这个元素上。

或者你也可以直接上线段树。赛时调到红温差点就用了。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;ll T,n,a[maxn];int main(){cin>>T;while(T--){cin>>n;for(int i=1,t;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);ll add=0;for(int i=1;i<=n;i++){a[i]+=add;if(i==n){cout<<a[n]<<endl;break;}if(a[i]<0)add+=a[i];else a[n]+=a[i];}}return 0;
}

C 太阳之华

思路：

手玩一会其实会发现一个规律，就是如果某一方无法一次就决定胜局，那么这一方一定不会赢。

因为如果你一次操作后，若对方还有剩的格子，对方任选一个操作一下，这个格子周围就会出现一圈 “护盾”，你下次操作后只能剥离这个 “护盾”，而内部的格子不会受到影响。因此就会无限循环起来，这时候就会平局。

而进一步研究发现，除非蓝方赢在了起跑线上——地图上全是蓝格子。就只有红方有可能会赢，因为红方先手操作就会导致被操作的红格子周围出现 “护盾”，之后蓝方肯定不可能赢。所以我们暴力枚举红方操作的哪一个连通块，模拟一下涂色过程，看看红方能不能一局定胜负，不能就是平局。

不过检查图是否被涂满红色不能暴力来验证，最坏情况下每个连通块都验证一下，需要 $O(n^2m^2)$ 。考虑预先统计一下蓝色点的个数，之后涂色的时候记录一下涂了几个点，涂色结束后看一下个数对不对的上就行了，为了不重复可以用set存储被涂色的点。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int maxn=2005;int T,n,m,cnt;
string mp[maxn];int fx[]={1,-1,0,0},fy[]={0,0,1,-1};bool vis[maxn][maxn];
set<pair<int,int> > S;
void dfs(int ux,int uy){
//	cout<<ux<<" "<<uy<<endl;vis[ux][uy]=true;for(int i=0,x,y;i<4;i++){x=ux+fx[i];y=uy+fy[i];if(x<1 || x>n || y<1 || y>m)continue;if(mp[x][y]=='#'){if(!vis[x][y]){dfs(x,y);}}else S.insert(make_pair(x,y));}
}
void solve(){if(cnt==n*m){puts("Blue");return;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)vis[i][j]=false;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!vis[i][j] && mp[i][j]=='#'){S.clear();dfs(i,j);if(S.size()==cnt){puts("Red");return;}}}}puts("Draw");
}int main(){cin>>T;while(T--){cin>>n>>m;cnt=0;for(int i=1;i<=n;i++){cin>>mp[i];for(auto x:mp[i])if(x=='.')cnt++;mp[i]=" "+mp[i];}solve();}return 0;
}

D 冥古之潮

思路：

题面虽然规定了选出点后的顺序必须从小到大，但是实际上这可以看作是一种选点的集合。因为选点集合和从小到大的排列是可以一一对应的。所以这个题其实就是在问：选择 $k$ 个到点 $x$ 的距离不同的结点的方案数。

我们预处理出到点 $x$ 距离为 $i$ 的点的个数 $co u n t [i]$ 。然后就可以先枚举 $k$ ，对每个 $k$ ，去计算选择方案数。

不过这样复杂度是爆炸的，考虑如何优化。考虑对每种距离的点，我们可以选或不选，所以考虑动态规划。设 $d p [i] [j]$ 为考虑了距离小于等于 $i$ 的所有点，从中选取 $j$ 个的方法数。状态转移方程也好想： $d p [i] [j] = d p [i - 1] [j] + co u n t [i] * d p [i - 1] [j]$

实际上发现 $dp_{i}$ 只和 $dp_{i-1}$ 有关，所以第一维可以优化掉，类似于 $01$ 背包的优化方式。

code：

#include <iostream>
#include <cstdio>
#include <queue>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int maxk=5e5+5;
const ll inf=1e9;
const ll linf=1e18;
const ll mod=1e9+7;int n,m,q,x;int head[maxn],cnt;
struct edge{int v,nxt;
}e[maxn<<1];
void add(int u,int v){e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}int d[maxn],count[maxk];
void dijkstra(){for(int i=1;i<=n;i++)d[i]=inf;queue<int> q;//假dij，因为边权都是1，直接bfs就行了q.push(x);d[x]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u],v;i;i=e[i].nxt){v=e[i].v;if(d[v]==inf){d[v]=d[u]+1;count[d[v]]++;q.push(v);}}}
}ll dp[maxk];//dp[i] 选择i个数的方法数 int main(){cin>>n>>m>>q>>x;for(int i=1,u,v;i<=m;i++){cin>>u>>v;add(u,v);add(v,u);}dijkstra();dp[0]=1;for(int i=1;i<=5000;i++){if(count[i]){for(int j=5000;j>=1;j--)dp[j]=(dp[j]+count[i]*dp[j-1])%mod;}}while(q--){int k;cin>>k;cout<<dp[k]<<endl;}return 0;
}

其实还有别的理解方式，比如生成函数，详细讲解可以看这个大佬的。

多项式某一项的系数就表示方法数，指数表示选择个数。比如选择 $k$ 个点的方法数就是 $x^k$ 的系数。

这个题的生成函数其实就是 $\prod_{i=1}^{5000}(1+count_i*x^{1})$ 上面的 $d p$ 递推过程其实相当于在算这个式子的展开式。

E 神性之陨

思路：

发现一个竖条旁边接另一个竖条的话，两个相邻的竖条只能有一个格子是相邻的，这样在前面竖条走到后面竖条的路径一定是唯一的。否则在这上面就会出现多条路径。

因此后一个竖条的上端点要接在前一个竖条的下端点，或者后一个竖条的下端点要接在前一个竖条的上端点。不过有个特殊情况就是如果后一个竖条的宽度就是 $1$ 的话，那么它放在前一个竖条的哪里都可以。

一个比较明显的想法就是保存第 $i$ 列所有可以放竖条的位置，然后枚举每个可能的情况，算出第 $i + 1$ 列的情况，一直算到最后一列即可。代码如下：

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=5005;int T,n,m,a[maxn];int main(){cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=m;i++)cin>>a[i];set<int> S,t;for(int i=1;i<=n;i++)S.insert(i);for(int i=2,l,r;i<=m;i++){t.clear();if(a[i]==1){int tl=0,l,r;for(auto x:S){l=x;r=x+a[i-1]-1;for(int j=max(tl,l);j<=r;j++)t.insert(j);tl=r+1;}}else {for(auto x:S){l=x;r=x+a[i-1]-1;if(l-a[i]+1>=1)t.insert(l-a[i]+1);if(r+a[i]-1<=n)t.insert(r);}}S=t;}cout<<S.size()<<endl;}return 0;
}

结果T了， $n * m * l o g m$ 会被卡。考虑到可以用桶的思想来存储，我们用 $v i s [i] [j]$ 表示第 $i$ 行第 $j$ 列是否可以作为第 $j$ 列竖条的上端点。我们用第 $j - 1$ 列的竖条可能在的位置的信息就可以算出第 $j$ 列的信息，这样就可以优化掉一个 $l o g$ 。

code：

实际上 $v i s$ 可以再加一维，变成 $v i s [i] [j] [0/1]$ 表示第 $i$ 行第 $j$ 列是否可以作为第 $j$ 列竖条的上/下端点，递推的时候可能会比较好推。

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=5005;int T,n,m,a[maxn];
bool vis[maxn][maxn];int main(){cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)vis[i][j]=false;for(int i=1;i<=m;i++)cin>>a[i];for(int i=1;i<=n;i++)vis[i][1]=true;for(int col=2,l,r;col<=m;col++){if(a[col]==1){for(int l,r,x=0,i=1;i<=n;i++){if(!vis[i][col-1])continue;l=i;r=i+a[col-1]-1;for(int j=max(l,x);j<=r;j++)vis[j][col]=true;x=r+1;}}else {for(int i=1;i<=n;i++){if(!vis[i][col-1])continue;l=i;r=i+a[col-1]-1;if(l-a[col]+1>=1)vis[l-a[col]+1][col]=true;if(r+a[col]-1<=n)vis[r][col]=true;}}}int ans=0;for(int i=1;i<=n;i++)ans+=vis[i][m];cout<<ans<<endl;}return 0;
}

F 无垢之土

思路：

考虑树上答案的两个生物怎么相遇：应该是走树上的路径然后相遇，这个路径最短就是一个点先到它们的最近公共祖先（LCA，Least Common Ancestor），再到另一个点。

一对生物想要尽可能快地相遇，它们一定是这样跑：某个生物从一个点出生，并沿着这个最短路径向另一边跑，另一个点上的生物同理，然后两个生物在路上的某个位置相遇了。而这个用时我们可以在它们的最近公共祖先上算出来，也就是这两个生物一定是先后到达这个祖先的，先到达的生物向另一个生物所在的子树跑，于是两个生物总用时的一半就是答案用时。

因为我们只需要知道最快相遇的那对生物，所以我们一个祖先就不需要存储每个子树的点到这个根的用时，只用知道每个子树最快到这个根的时间即可。我们设 $d p [i]$ 表示 $i$ 的子树的点到达根 $i$ 的最快的生物的用时。

我们保存一下这个点出生的生物的时间，每个子树跑过来的最快生物的时间（子树的 $d p$ 值），从中选出时间最小和次小的生物，它们的平均值就是以这个点为 $L C A$ 的最快相遇时间。然后 $d p [i]$ 就等于其中的最小值。

不过这样是有 $b ug$ 的，有的生物用时比较长并不是离 $L C A$ 远，而是出生晚，这样一个生物跑到另一边即使跑到了另一个生物的出生地，也无法相遇，只能等待，直接取平均值就会出错，hack数据：

3 2
1 2
1 3
2 1
3 10正确答案是：20
不考虑出生时间答案是：13

发现一对生物相遇的最快用时是 $用时=max\{通过 LCA 跑出的最短时间,生物1的出生时间，生物2的出生时间\}$
这样验证一个时间是比较方便的（也就是验证在这个时刻上有没有生物已经相遇了）。首先需要这个时间能保证两个生物都能出生，在此基础上通过 $L C A$ 跑出的最短时间小于等于这个时间即可。这样就能验证这两个生物一定是在验证时间之前就相遇了。

所以考虑二分答案，当出生时间比要验证的答案要晚的话，就不再将他出生在点上，这样就能保证两个生物在这个时间点上都出生了。如果跑出来的最短时间小于等于这个时刻，就说明在这个时刻上有生物已经相遇了。

不过中间算时间时有可能会出现 $\sim.5$ 的情况，搞浮点魔法也不好搞。所以我们一开始就对所有跟时间有关的东西都乘上 $2$ ：出生时间乘以 $2$ ，从子节点移动到父节点的用时变成 $2$ 即可。

code：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=1e5+5;
const int inf=1e9;int n,m;
vector<int> tm[maxn];int head[maxn],counter;
struct edge{int v,nxt;
}e[maxn<<1];
void add(int u,int v){e[++counter].v=v;e[counter].nxt=head[u];head[u]=counter;
}int dp[maxn];//子树点最小时间到达i的时间 
int ans;
void dfs(int u,int fa,int bd){int m1=inf,m2=inf;for(int i=head[u],v;i;i=e[i].nxt){v=e[i].v;if(v==fa)continue;dfs(v,u,bd);m2=min(m2,dp[v]+2);if(m1>m2)swap(m1,m2);}for(auto x:tm[u]){if(x>bd)continue;m2=min(m2,x);if(m1>m2)swap(m1,m2);}dp[u]=m1;ans=min(ans,(m1+m2)/2);
}
bool check(int bd){ans=inf;dfs(1,-1,bd);return ans<=bd;
}int main(){cin>>n>>m;for(int i=1,u,v;i<n;i++){cin>>u>>v;add(u,v);add(v,u);}for(int i=1,nd,t;i<=m;i++){cin>>nd>>t;tm[nd].push_back(2*t);}int l=0,r=1e7,mid;while(l<r){mid=(l+r)>>1;for(int i=1;i<=n;i++)dp[i]=inf;if(check(mid))r=mid;else l=mid+1;}cout<<l<<endl;return 0;
}