竞赛讨论区 > 【题解】牛客挑战赛36
头像
reek
发布于 2020-01-17 22:02
+ 关注

【题解】牛客挑战赛36


A

设环上点的编号依次为pi,各边长度依次为Vi

Wp1+Wp2=V1——①

Wp2+Wp3=V2——②

Wp3+Wp4=V3——③

……

Wpn+Wp1=Vn——(n)

①-②+③...+(n),得2Wp1=V1-V2+V3-...+Vn

解出Wp1后再依次推出Wpi

B

如果m不小于n,当且仅当m是n的正整数倍时存在可行解,否则必须满足n-m不是n的因数时才有解。

C

首先,最小链覆盖等于最长反链,故答案为不包括第i个数的最长不下降子序列长度。设整个序列的最长不下降子序列长度L,若存在不包括i的最长不下降子序列,则答案为L,否则为L-1。可以通过统计可作为最长不下降子序列每一位的数的个数快速判断。

由于个人疏忽,C题原数据范围有误,造成了不少选手的罚时,对此我表示十分抱歉。感谢JOHNKRAM指出错误。

D

令pi表示排名为第n-i时出现这种情况的概率。则pi=(i/(n-1))m

答案即为n-(Σi*pi)/(Σpi)=n-Σim+1/Σim。由于题目只要求O(n^2)效率的算法,可以直接递推求解自然数幂和。

E

首先对每个人按bi排序,对于每个人维护两个值hi(表示n再减小hi,Ta能允许的考得Ta差的最小人数就要减小1)和gi(表示当前考得比Ta差的人数与Ta能允许的考得Ta差的最小人数的差)。每次考试查询gi的最小值,对一个区间的gi加1并将所有hi减小。当hi减为零时单点修改gi。因为题目保证了所有大于1的正整数在ai中至多出现2次,所以单点修改的次数不超过O(nlnn),故总的复杂度是O(nlog2n)。

F

设f[i]为收入增长曲线斜率为i时纵截距的最大值。从小到大枚举斜率和土地类型进行转移,最终可以得到O(maxc)条直线。将询问离线,按斜率限制排序,单调栈维护半平面交,二分可得答案。

G

后手必胜当且仅当所取栈物品个数异或和为0。

考虑多项式(bixai+1),其异或卷积的常数项即为答案,可对ai分治,FWT求解。在分治时,因为区间内的ai在二进制下的前若干位是相同的,所以只需记录选取了多少个数就可以知道其异或和的前若干位。这样每次分治区间长度减半时,FWT的长度也减半,复杂度为O(nlog2n)。

jiangly似乎有不同于题解的做法。


全部评论

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

等你来战

查看全部

热门推荐