Lskkkno1

题解

/ 注册

全部文章 / 题解（共25篇）

题解 [牛客IOI周赛17-提高组 B] 卷积

卷积题目描述给定序列的递推公式。令为序列的生成函数，求的第项对取模。正解最终答案是一个等比数列求和的形式，等价于。现在直接多项式求逆就可以做到了，感觉卡卡就能过。比赛的时候不会生成函数真的自闭了啊，然后想起了 rqy 博客里求通项 / 递推公式的方...

2020-06-06

6 1254

题解 [牛客练习赛64 D] 宝石装箱

宝石装箱题目描述有个带标号盒子和球，每个球都有一个盒子不能放进去（不一定是排列）。问每一个盒子里都有一个球的方案数。正解每一个球都有一个限制（一个盒子不能放）。这个问题类似于错排，而错排有一种容斥的解法。设表示至少有条限制不满足的方案数, 表示恰好有条限制不满...

2020-05-22

9 1346

[VMware校园挑战赛-牛客挑战赛40 C]小V和字符串

小V和字符串题目描述直接点开题目看描述吧。正解数位 dp。设表示考虑前位，两串的差值为的方案数（后面两个表示两个串分别是否顶上界）。再设一个辅助数组表示考虑前位，两串的差值为，的所有方案下，需要移动的步数（后面两个与上面定义相同）。发现如果当前两...

2020-05-15

6 956

[VMware校园挑战赛-牛客挑战赛40 E] 小V和gcd树

小V和gcd树题目描述给定一棵树，树带点权，树的边权等于边两端点权的。有两种操作：更改一个点的点权，同时与之相连的边权也跟着改变。询问两个点的链上边权小于等于的个数。正解先将一下复杂度吧，挺暴力的。考虑根号分治。修改：对于一个度数大于的点，修改时只修改点...

2020-05-15

5 997

[VMware校园挑战赛-牛客挑战赛40 A] 小V和方程

小V和方程题目描述给定 , 。求的本质不同解（可重集合）的个数。正解考虑把表示成的形式，其中再也不能再进行拆分（没有平方因子）了。那么一定要是的倍数。现在题目就是一个划分数问题了（把个相同的球放在个相同的盒子内），递推即可。代码 #include ...

2020-05-15

4 965

题解 [牛客练习赛63 F] 牛牛的树行棋

牛牛的树行棋题目描述给定一棵树，树上每一个节点都有一枚棋子。 Alice 和 Bob 在这棵树上玩一个这样子的游戏： Alice 和 Bob 轮流操作，每次把一枚棋子移动到其子树内的节点（显然一枚棋子在叶子节点就不能移动了），不能移动的人算输。问 Alice 先手是否有必胜策略，若先手必胜...

2020-05-09

8 1745

题解 [牛客IOI周赛16-提高组 B] 小L扔垃圾

小L扔垃圾题目描述给定一个序列，每次在其左端点或者右端点加入一个元素。求这个序列的最长子段满足这个子段的 'W' 元素的个数等于 'D' 元素的个数。正解把 'W' 看成 1，把 'D' 看成 -1，若一个子段满足条件，则这个子段的和为 0。记录前缀和，然后要满足条件的话，。离线...

2020-05-02

1 1085

题解 [牛客IOI周赛16-提高组 C] 最小鸽

最小鸽题目描述给定一个序列，每次询问包含一个位置的最小区间，满足这个区间元素的或（or）大于这个区间元素的最大值。正解在线肯定不太可行，想离线做法。对于每一个数作为区间的最大值（不一定唯一），求它对这个区间产生的影响。然后这个位置作为最大值的区间要合法的话，需要包含一个数二进制位与它不...

2020-05-02

1 841

题解 [牛客练习赛62 F] 牛牛的繁星

牛牛的繁星题目描述给定一个长度为的序列，有次询问。每次询问一个区间内，"元素出现次数" 的第大的 "出现次数"。强制在线。正解如果可以离线，有一个经典的莫队 + 值域分块做法可以做到严格。（而且常数很小就直接暴力移动左右端点，移动端点的修改复杂度是的，然后单次查询是...

2020-04-26

1 1000

题解 [牛客练习赛62 D] 牛牛的呱数

牛牛的呱数题目描述给出个数和一个模数。问选若干个数（可以重复选择）拼在一起，并且整除时，最短的长度。正解显然这个数有用的信息只有长度和模意义下的值，那就先预处理这些东西。考虑每次把新加进来的数放在已有的数的左边。加入后的值是原来的值加上新增的值。设 ...

2020-04-24

3 1060