【题解】牛客练习赛64

A：怪盗-1412

将序列排列成,这样可以得到最大化的子序列数量，答案为，时间复杂度。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780345

B：Dis2

与每个点距离为的点为这个点的度数。对于每个点，枚举和它有边相连的点，点对点的贡献为与点距离为的点的个数减去（减掉这个点），时间复杂度。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780359

C：序列卷积之和

设。
设+。
则

预处理前缀和统计前缀和出现的数量，即可得出答案，时间复杂度。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780364

D：宝石装箱

设表示选出个箱子装不合法的宝石的方案数。
设。
那么为至少个箱子装了不合法的宝石的方案数。
根据容斥原理，答案为 。
设表示不可以装入第个箱子的宝石的数量，注意到每个宝石只对应一个箱子。
初始时，。
然后相当于每次加入一个物品，当加入第个箱子，有，那么通过背包就可以求出所有的，最后统计答案即可，时间复杂度，常数很小。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780376

E：红色的樱花

如果，那么答案为。否则：
随机选择一个点，初始时，让，然后执行以下操作：
a.将点染色，再让
b.如果点已经被染色，则跳出，否则回到。
当的时候，被染色的点构成了一个循环。
这样的循环的数量有个。
那么操作1转为花费牛币，跳到点所在的环的任意一个位置。
可以证明，操作1至多只需要执行一次。
如果执行0次操作1，我们只能进行横和列的移动，那么就是分别求
的最小正整数解。
如果执行1次操作1：
1.牛牛和牛妹在同一个环，答案为。
2.牛牛和牛妹不在同一个环，那么通过列或者行的移动移动到牛妹所在的环，答案再加即可，观察环与环在行上移动和列上移动的影响，可以发现只在行上移动或者只在列上移动是最优的，分别求 ， 的最小正整数解即可，时间复杂度。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780369

F：如果我让你查回文你还爱我吗

先求出所有的回文半径，设为第个位置的回文半径，对于一个查询，我们要统计（这里暂时只考虑奇回文）。这样的时间复杂度为。
让，那么我们就只需要对区间查询左回文，对区间查询右回文，消除了的限制。
同样，对于的回文半径，我们把它分成两条线段和，一条线段相当于对区间内的每个点权值加，对于一个查询，我们要求所有区间满足的线段对区间的点的贡献和，对于的查询类似。那么可以将查询离线，用数据结构维护区间和。在线查询可以用可持久化数据结构维护。总的时间复杂度为。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780554