锐客网

  1. 首页 > it技术 > >

比赛题解|牛客练习赛 51 （DEF题解）

数据结构牛客比赛题解

题目链接
D 羊吃草（二分图最大匹配） 题意：
有 n n n个羊， m m m个草，每只羊可以吃 [ l i , r i ] [l_i,r_i] [li?,ri?]的草，有 Q Q Q次询问，每次询问 [ l i , r i ] [l_i,r_i] [li?,ri?]区间的草最多可以给多少只羊吃，每次询问独立。 ( n , m < = 400 ) (n,m< =400) (n,m<=400)
思路：
我们可以从草往羊进行连边，那么每次询问就是求 [ L i , R i ] [L_i,R_i] [Li?,Ri?]区间的草的最大匹配，用匈牙利算法就行。
代码：

#include using namespace std; const int N=500; vectore[N]; int vis[N]; int match[N]; bool pp(int u,int time){ for(int v:e[u]){ if(vis[v]==time)continue; vis[v]=time; if(match[v]==-1||pp(match[v],time)){ match[v]=u; return 1; } } return 0; } int n,m; int a[N],b[N]; int main() { cin>>n>>m; for(int i=1; i<=n; i++)cin>>a[i]; for(int i=1; i<=n; i++)cin>>b[i]; int cnt=0; for(int i=1; i<=n; i++){ for(int j=a[i]; j<=b[i]; j++)e[j].push_back(i); } for(int i=1,l,r; i<=m; i++){ cin>>l>>r; for(int j=1; j<=n; j++)match[j]=-1; int ans=0; for(int j=l; j<=r; j++){ if(pp(j,++cnt))ans++; } cout<

E 数列（二分+思维） 题意：
给定 n ， m n，m n，m要求构造一个长度为 n n n 正整数序列 { a i } \{a_i\} {ai?}，使得 ∑ a i < = m \sum{a_i}< =m ∑ai?<=m，并且使得价值最大，价值为 a [ i ] = a [ i ? 1 ] + 1 a[i]=a[i-1]+1 a[i]=a[i?1]+1的出现次数。
思路：
我们可以发现序列最终一个是 1 , 2 , 3....1 , 2 , 3.....1 , 2 , 3... 1,2,3....1,2,3.....1,2,3... 1,2,3....1,2,3.....1,2,3...这种形式，那么我们假设我们将数列分成 k k k段，每一段的长度为 l e n i len_i leni?，那么每一段的和就是 l e n i ? ( l e n i + 1 ) / 2 len_i*(len_i+1)/2 leni??(leni?+1)/2，价值为 n ? k n-k n?k，我们要使得和尽量小，就是让每一段的长度尽量平均分配，那么对于每一个 k k k我们都可以求出其数字的总和(通过k , n / k , n % k k,n/k,n\%k k,n/k,n%k)，我们只要求出满足题意的最小的k即可使得价值最大，并且还原序列。
代码：
#include #define ll long long using namespace std; const int N=1e5+10; ll n,m; vector v[N]; bool check(ll x){ int len=n/x,yu=n%x; ll temp=x*(len)*(len+1)/2+yu*(len+1); return temp<=m; } int main() { scanf("%d%d",&n,&m); ll l=1,r=n,ans; while(l<=r){ ll mid=(l+r)/2; if(check(mid)){ ans=mid; r=mid-1; } else l=mid+1; } ll len=n/ans,yu=n%ans; for(ll i=1; i<=ans; i++){ for(ll j=1; j<=len; j++)v[i].push_back(j); } for(ll i=1; i<=yu; i++){ v[i].push_back(len+1); } for(ll i=1; i<=ans; i++){ for(ll x:v[i]){ cout<

F ABCBA（主席树） 题意：
给一棵树，每一个节点是一个字符，每次询问 u , v u,v u,v，从 u u u沿最短路到 v v v形成一个字符串，问该字符串中有多少个子序列(不用连续)为 “ a b c b a ” “abcba” “abcba”。
思路：
【比赛题解|牛客练习赛 51 （DEF题解）】参考自橘子猫的题解链接
首先将每一个节点到其叶子节点的区间用主席树来维护，我们要求 a b c b a abcba abcba的出现次数，由于其是一个回文串，我们可以直接维护 a , b , c , b a , a b , b c , c b , a b c , c b a , b c b , a b c b , b c b a , a b c b a a,b,c,ba,ab,bc,cb,abc,cba,bcb,abcb,bcba,abcba a,b,c,ba,ab,bc,cb,abc,cba,bcb,abcb,bcba,abcba的数量。
其中 a b c b a abcba abcba=&ls.abcba+rs.abcba+ls.a*rs.bcba+ls.ab*rs.cba+ls.abc*rs.ba+ls.abcb*rs.a&
剩下的也类似。
那么在查询 u , v u,v u,v的时候我们只要求出 l c a ( u , v ) lca(u,v) lca(u,v)，把两端进行合并即可，要注意当 l c a lca lca不是 u , v u,v u,v时，合并的时候 u → l c a u \to lca u→lca的字符串应该时反的。
学习大佬博客中对节点加法运算符的重定义是真的很好用。
代码：
#include using namespace std; #define ll long long const int N=3e4+10; const int mod=10007; char s[N]; int n,q,u,v; vectorE[N]; //主席树 int ls[N*20],rs[N*20]; struct node{ int a,b,c,ba,ab,bc,cb,abc,cba,bcb,abcb,bcba,abcba; }e[N*20]; node operator +(const node &x,const node &y){//要小心检查，错了一个找了1个小时 node z; z.a=(x.a+y.a)%mod; z.b=(x.b+y.b)%mod; z.c=(x.c+y.c)%mod; z.ba=(x.ba+y.ba+x.b*y.a)%mod; z.ab=(x.ab+y.ab+x.a*y.b)%mod; z.bc=(x.bc+y.bc+x.b*y.c)%mod; z.cb=(x.cb+y.cb+x.c*y.b)%mod; z.abc=(x.abc+y.abc+x.a*y.bc+x.ab*y.c)%mod; z.cba=(x.cba+y.cba+x.c*y.ba+x.cb*y.a)%mod; z.bcb=(x.bcb+y.bcb+x.b*y.cb+x.bc*y.b)%mod; z.abcb=(x.abcb+y.abcb+x.a*y.bcb+x.ab*y.cb+x.abc*y.b)%mod; z.bcba=(x.bcba+y.bcba+x.b*y.cba+x.bc*y.ba+x.bcb*y.a)%mod; z.abcba=(x.abcba+y.abcba+x.a*y.bcba+x.ab*y.cba+x.abc*y.ba+x.abcb*y.a)%mod; return z; } int rt[N*20],cnt=0; void update(int &root,int pre,int l,int r,int pos,char c){ root=++cnt; ls[root]=ls[pre]; rs[root]=rs[pre]; if(l==r){ if(c=='A')e[root].a=1; else if(c=='B')e[root].b=1; else if(c=='C')e[root].c=1; return ; } int mid=(l+r)/2; if(pos<=mid)update(ls[root],ls[pre],l,mid,pos,c); else update(rs[root],rs[pre],mid+1,r,pos,c); e[root]=e[ls[root]]+e[rs[root]]; }node query(int root,int l,int r,int LL,int RR){ if(l>=LL&&r<=RR){ return e[root]; } int mid=(l+r)/2; if(LL>mid)return query(rs[root],mid+1,r,LL,RR); else if(RR<=mid)return query(ls[root],l,mid,LL,RR); else return query(ls[root],l,mid,LL,RR)+query(rs[root],mid+1,r,LL,RR); //加法很好用 } //树剖int deep[N],fa[N],son[N],tot[N]; int dfs1(int u,int f,int dep){ deep[u]=dep; fa[u]=f; tot[u]=1; int pd=-1; update(rt[u],rt[f],1,n,deep[u],s[u]); //以深度做为位置 for(int v:E[u]){ if(v==f)continue; tot[u]+=dfs1(v,u,dep+1); if(tot[v]>pd)pd=tot[v],son[u]=v; } return tot[u]; } int top[N],idx[N],cnt1=0; void dfs2(int u,int f){ idx[u]=++cnt1; top[u]=f; if(!son[u])return ; dfs2(son[u],f); for(int v:E[u]){ if(!idx[v])dfs2(v,v); } } int Lca(int x,int y){ while(top[x]!=top[y]){ if(deep[top[x]]deep[y])swap(x,y); return x; }int main() { scanf("%d%d",&n,&q); scanf("%s",s+1); for(int i=1; i

    推荐阅读


    上一篇：荒

    下一篇：《工作细胞》之（肺炎链球菌）