竞赛讨论区 > 【题解】牛客练习赛51
头像
匿名牛油
编辑于 2020-03-06 12:29
+ 关注

【题解】牛客练习赛51

A-abc

做一个前缀和一个后缀和,前缀和sum1[i]记录位置1...i中a的个数,后缀和sum2[i]记录i...n中c的个数。从前往后枚举字符串的所有位置,如果当前位置i的字符为'b',答案加上sum1[i-1]*sum2[i+1]即可,时间复杂度O(n)。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41227760

B-子串查询

设nex[i][j]表示s串中第i后面第一个字符为(j+'a')的位置(0<=j<26),规定s串的下标从1开始,如果不存在这样的位置则nex[i][j]=-1。对于每次查询,按顺序枚举串t的所有字符,每次优先匹配可以匹配的最小位置进行贪心。更正式的说,最开始我们设now=0,每次枚举到串t的位置i,我们使得now=nex[now][t[i]-'a'],如果中途now=-1了,说明串t不是s的子串,否则串t是s的子串。因此我们可以用一个队列辅助来求出nex数组,就可以在线性时间内解决这道题。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41227770

C-勾股定理

对小范围数据进行打表,即可发现存在以下规律:
1.当n>2时总有方法可以构造
2.当n是奇数总存在两条边b,c使得c-b==1并且n^2+b^2=c^2
3.当n是偶数总存在两条边b,c使得c-b==2并且n^2+b^2=c^2
因此我们可以设边c=x,分n是奇数和偶数的情况,有
1.n是奇数,b=x-1->n^2+(x-1)^2=x^2->x=(n^2+1)/2
2.n是偶数,b=x-2->n^2+(x-2)^2=x^2->x=(n^2+4)/4
于是可以O(1)求出答案
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41227778

D-羊吃草

设坐标轴的整点1...400属于集合A,羊1...n属于集合B,对于编号为i的羊喜欢的区间a[i],b[i],我们在集合B的i点和集合A中的a[i]...b[i]的点之间连一条边,可以发现这样的图是一张二分图。于是对于每次查询l,r,我们枚举集合A中l...r之间的所有点,求出其最大匹配集合。可以用匈牙利算法或足够优秀的最大流。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41227784

E-数列

对于一个数列,如果其一个子数列a[i],a[i+1]...a[j-1],a[j]满足a[k]=a[k-1]+1(i+1<=k<=j),同时,也满足i-1<1或者a[i]!=a[i-1]+1,j+1>n或者a[j+1]!=a[j]+1,则我们称这样的子数列为一段。我们可以发现,假如数列中有sum个这样的段,则小乔对数列的喜爱度为n-sum。因为数列是可以自由填数的,所以对与每一段我们使得a[i]=1是最优的,a[i],a[i+1]...a[j-1],a[j]显然。于是对于每一段,如果这段的长度为s,按最优的方法填数,则这一段的总和为s*(s+1)/2。
于是问题转换为:
把数列n分成sum个段,要求最小化sum,并且所有段的总和<=m。
设这sum段中长度最小的段长度为mn,长度最大的段长度为mx,可以发现如果我们已知了sum,那么要使这sum段的总和最小,就要使得mn和mx尽可能的接近,因为如果mx-mn>=2,那么段mx的最后一个元素的值为mx,段mn最后一个元素的值为mn,那么我们使段mx的长度-1,mn的长度加1。那么总和的变化就是总和=总和-mx+mn+1。因为mx-mn>=2,所以mx>mn+1。
因此如果得知sum,最优的策略就是均分所有段的长度。
均分的方法就是,首先使每一段的长度为n/sum,剩余n%sum个匀速均分配到n%sum个段上去。
于是有n%sum个段的长度为n/sum+1,n-n%sum个段的长度为n/sum。
对于sum,我们二分答案,因为答案具有单调性,分段越多,可以使总和越小。
通过二分答案求出sum再构造数列即可。时间复杂度O(logn+n)
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41227790

F-ABCBA

首先,我们可以用线段树维护序列中子串ABCBA的个数。定义f(i,j),表示把子串ABCBA编号12345,f(i,j)表示把编号i...j之间的字符按顺序接起来的字符串。我们可以在线段树每个结点维护dp[i][j],表示在当前结点表示的区间l,r内,子串f(i,j)的个数。设计了这个状态,线段树的合并显然。
普遍到树的情况,我们对树进行树链剖分,按树链剖分的标号序列建立两颗线段树。第一颗线段树维护小标号到大标号的dp,第二颗维护大标号到小标号的dp。对于每次查询u,v,ansu表示查询u所在链的答案,ansv表示查询v所在链的答案,如果u,v在不同链,不断爬其top合并答案,如果u,v在相同链,分类讨论合并ansu,ansv即可。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41227851

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐