【题解】牛客练习赛44
A.小y的序列
对于每种颜色，只要找到出现的最靠右的位置和最靠左的位置输出即可。如果找不到，那就藏在下一种颜色下面。
其实可以做到数据范围受限于
B.小y的线段
画出图来，可以发现具有单调性，只要计算出有多少个位置回到了源点就行了。
C.小y的质数
首先换个姿势看这个问题
求有多少个满足
，并且
众所周知，与
等价。
所以问题转化为求区间内有多少
满足
因为区间比较大。所以可以对分解质因子。
然后容斥一下公因数，假设当前枚举到的质因子个数为。那就暴力搜索出来所有可能的公因数。然后计算
内为当前公因数倍数的数字个数。然后容斥就行了。
D.小y的盒子
此题为送温暖题目。。
把所有的数字转换为三进制，对于每个卡片都是形如的形式
所以为
的形式，共有
位
然后考虑当第位上为
的时候，表示这一位上需要选
个
的卡片，同样，为
时需要
个，为
时只需一个。
当需要个时，有两种选择，其他的都只有一种选择。
又因为的形式是
我们从枚举到
，只需考虑哪些位置上面是2即可。
如果当前有个位置为
那么共有
种情况，且贡献为
，然后其他位置可以为
，也可以为
.所以贡献为
。所以当前的贡献就是
所以最终答案为
将提出来。那就是
。
用二项式定理合并那个，其实就是
，所以最终答案为
.
注意到当时是不符合题目要求的，所以要减去他的贡献
.
所以真正的最后答案是
E.小y的工资
首先树形一下,用
表示以
为根的子树最大收益是多少。
询问的简单路径中，有些边是必须跑的，所以j把这些边从里面单独拿出来。然后再强制加回去就行了。
F.小y的纸牌
题目大意：
给出一个序列，分成两个子序列(长度可以不相同，位置可以不连续)，使得两个序列各个位置的前缀最大值的和最小。
一道非常巧妙的dp + 非常套路的分块题
首先考虑的dp怎么做
可以发现两个性质：
设原数组为
性质：假设分成的两个序列为
,
。若其中某个位置时，a中的最大值比b小，那么以后肯定一直都是a中的最大值比b小。因为要使a中的最大值比b大，那么只能是有一个
且s被分到了a数组中。显然，s分到b数组中会更优秀
性质:假设a数组中的最大值一直比b小，那么所有分到b数组中的数字的贡献是原序列中该数字前面所有数字的最大值。因为b中的最大值一直比a大，所以这个很显然。
根据上面的两个性质，我们就可以设出状态。设表示第i个数字分到了a数组且作为a数组中的最大值最终的贡献。
那么对于原序列S中第i个元素我们可以分成以下两种情况，
1.将该元素放到b数组中。
显然，只有当比a数组中的最大值大时，我们才可能会选择这种情况。所以我们对于每个
将
2.将放到a数组中。
如果放到a数组中且a数组中的最大值不变，即
,那么将
即可
如果放到a数组中a数组中的最大值变为
，这时
，只要找到前面最小的一个
来更新
即可
考虑得到了这个的dp之后怎么优化，可以直接对着代码考虑
现在相当于一道数据结构题，需要支持：
- 查询满足
的
的最小值
- 让
的
- 让
的
这是一个经典的分块维护凸包的模型，对于每个转移点，我们可以将其看做
的形式，
是常量，
是被执行过操作
的次数
接下来可以将每个按照分块，因为
，所以只要分为
块即可
对于每一块，可以通过打标记来维护操作(相同块内加的值是相同的)。同时我们可以将块内的每个转移点看做一个函数(也就是
)，其中自变量
每次只会
，现在我们只需要知道对于每个
，这些函数对应的最小值。
也就是说我们只需要维护出红色的线段
这又是个经典模型，，而且考虑到该题比较好的性质，对于每一块只需要从前往后扫一遍，判断一下相邻点的位置关系即可。
查询的时候由于单增，只需要判断第一个元素和第二个元素的关系，如果不满足弹出队首即可
复杂度
代码
A: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569856
B: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569861
C: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569871
D: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569872
E: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569877
F: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40570772
