牛客小白月赛 27部分题解

已做BCDEFGJ

B.乐团派对

刚开始想了个贪心，结果不对然后直接转头想dp了。
将能力值排序。
首先我们先分出来一组，能力值最大的分出来一组人数是$a_n$即下标是$n-a_n+1\to n$分出来一组，目前还剩$n-a_n$个人待分配，然后考虑设计dp
状态表示：$f_i$考虑前$1$~$i$个人分成的最多组数
状态转移：目前第$i$个人可以与前面的人一组，也可以把它丢到最开始分出来的那一组于是不难得出：$f_i=max(f_{i-1},f_{i-a_i}+1)$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=100010; const int INF=0x3f3f3f3f; int a[N],f[N]; int n; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);if(a[n]>n) {cout<<-1<<'\n';continue;}n=n-a[n];for(int i=1;i<=n;i++){int j=max(0,i-a[i]);f[i]=max(f[i-1],f[j]+1);}cout<<f[n]+1<<'\n';}return 0; }

C.光玉小镇

由于坏掉的电线杆数目很小，我们可以用bfs预处理以家和每个电线杆为起点到达其他电线杆距离的最小值。
直接枚举电线杆的顺序查表求最值即可。

全排列枚举$(cnt!)$会超时需要状态压缩dp枚举$(2^{cnt})$。

写本题的时候发现unordered_map的键值key不能是pair，举体原因请参考大佬博客加上一些代码就可以使用了。

#include<functional> template <typename T> inline void hash_combine(std::size_t &seed, const T &val) {seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } // auxiliary generic functions to create a hash value using a seed template <typename T> inline void hash_val(std::size_t &seed, const T &val) {hash_combine(seed, val); } template <typename T, typename... Types> inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {hash_combine(seed, val);hash_val(seed, args...); }template <typename... Types> inline std::size_t hash_val(const Types &... args) {std::size_t seed = 0;hash_val(seed, args...);return seed; }struct pair_hash {template <class T1, class T2>std::size_t operator()(const std::pair<T1, T2> &p) const {return hash_val(p.first, p.second);} }; #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=210; const ll INF=1e18; int n,m,t; char g[N][N]; unordered_map<pii,int,pair_hash> mp; pii pos[20]; int dist[20][20],a[20]; bool st[N][N]; int d[N][N]; queue<pii> q; int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; ll f[1<<16][17]; void bfs(int now) {q.push(pos[now]);memset(d,0x3f,sizeof d);memset(st,0,sizeof st);d[pos[now].first][pos[now].second]=0;while(q.size()){int x=q.front().first,y=q.front().second;q.pop();if(st[x][y]) continue;st[x][y]=1;if(g[x][y]!='.') dist[now][mp[{x,y}]]=d[x][y];for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a<1||b<1||a>n||b>m||g[a][b]=='#') continue;if(d[a][b]>d[x][y]+1){d[a][b]=d[x][y]+1;q.push({a,b});}}} } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>m>>t;for(int i=1;i<=n;i++) cin>>g[i]+1;int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(g[i][j]=='S') mp[{i,j}]=0,pos[0]={i,j};else if(g[i][j]=='T') mp[{i,j}]=++cnt,pos[cnt]={i,j};}memset(dist,0x3f,sizeof dist);for(int i=0;i<=cnt;i++) bfs(i);memset(f,0x3f,sizeof f);f[1][0]=0;for(int i=0;i<1<<cnt+1;i++)for(int j=0;j<=cnt;j++)if(i>>j&1) for(int k=0;k<=cnt;k++)if((i-(1<<j))>>k&1) f[i][j]=min(f[i][j],f[i-(1<<j)][k]+dist[k][j]);ll res=INF;for(int i=1;i<=cnt;i++)res=min(res,f[(1<<cnt+1)-1][i]+dist[i][0]);if(res>=0x3f3f3f3f) cout<<-1<<'\n';else{res+=1ll*t*cnt;cout<<res<<'\n';}}return 0;}

D.巅峰对决

数据保证，任何时候这n个数字均互不相同。
这个条件非常重要，有了这个条件直接用线段树维护一下区间最大值和最小值即可：如果最大值和最小值的差等于坐标差就满足题意否则不满足。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=100010; const int INF=0x3f3f3f3f; int a[N]; int n,q; struct node {int l,r;int mx,mn; }tree[N*4]; void pushup(int u) {tree[u].mx=max(tree[u<<1|1].mx,tree[u<<1].mx);tree[u].mn=min(tree[u<<1|1].mn,tree[u<<1].mn); } void build(int u,int l,int r) {tree[u]={l,r,-INF,INF};if(l==r){tree[u].mn=tree[u].mx=a[l];return;}int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u); } void modify(int u,int pos,int val) {if(tree[u].l==tree[u].r) {tree[u].mn=tree[u].mx=val;return;}int mid=tree[u].l+tree[u].r>>1;if(pos<=mid) modify(u<<1,pos,val);else modify(u<<1|1,pos,val);pushup(u); } int querymx(int u,int l,int r) {if(tree[u].l>=l&&tree[u].r<=r) return tree[u].mx;int mid=tree[u].r+tree[u].l>>1;int v=-INF;if(l<=mid) v=max(v,querymx(u<<1,l,r));if(r>mid) v=max(v,querymx(u<<1|1,l,r));return v; } int querymn(int u,int l,int r) {if(tree[u].l>=l&&tree[u].r<=r) return tree[u].mn;int mid=tree[u].r+tree[u].l>>1;int v=INF;if(l<=mid) v=min(v,querymn(u<<1,l,r));if(r>mid) v=min(v,querymn(u<<1|1,l,r));return v; } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>q;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);while(q--){int op,x,y;cin>>op>>x>>y;if(op==1) modify(1,x,y);else {if(y-x==querymx(1,x,y)-querymn(1,x,y)) cout<<"YES\n";elsecout<<"NO\n";}}}return 0; }

F.核弹剑仙

正解是bitset+拓扑排序，由于数据范围很小随便搞都能过
我还是补一补正解吧，正好练习一下bitset使用。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=2010; int h[N],e[N],ne[N],idx; int d[N]; bitset<1005>b[N]; int n,m; void add(int a,int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++; } void topsort() {queue<int> q;for(int i=1;i<=n;i++)if(!d[i]) q.push(i);while(q.size()){int t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];b[j]|=b[t];b[j][t]=1;if(--d[j]==0) q.push(j);}} } int main() {IO;int T=1;//cin>>T;while(T--){memset(h,-1,sizeof h);cin>>n>>m;while(m--){int a,b;cin>>a>>b;add(a,b);d[b]++;}topsort();for(int i=1;i<=n;i++)cout<<b[i].count()<<'\n';}return 0;}

剩下的题待做。

要加油哦~

总结

以上是生活随笔为你收集整理的牛客小白月赛 27部分题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。