【题解】牛客寒假算法基础集训营3
A. 处女座与线性代数
题目分析
我们将列举出本题所使用到的结论：
1.处女座点的数量最多为 1
证明：
2. 若K维空间一个点集{
}存在处女座点，则𝑵≤𝑲+𝟐≤𝟐𝑲+𝟏
严格的证明需要利用高等代数。但是利用数学归纳法或线性代数方法证明同条件下证明𝑁≤2𝐾+1是显然的。 （提示：将处女座点的定义弱化为向量夹角为钝角或直角后即可证明）
综上所述，若𝑁>𝐾+2则直接输出0，否则暴力检查即可。由于𝐾≤10，用𝑁>2𝐾+1判断也是可以的。
时间复杂度𝑂(𝐾^3)。
B. 处女座的比赛资格
题目分析
有向无环图（DAG）上的最短路。
注意：负权值边的存在使得 Dijkstra 算法不适用，特殊 DAG 的性质使得 SPFA 算法无法在规定的时间限内求解出答案。 考虑到 DAG 的特殊性，按照原图节点的拓扑顺序依次递推距离即可求解。
令𝑑𝑖表示节点1到i的最短路，𝑝𝑟𝑒𝑣_𝑖表示节点的先驱集合。则有：
其中𝑗∈𝑝𝑟𝑒𝑣_𝑖，其中𝑐𝑜𝑠𝑡(𝑗,𝑖)表示从节点j到节点i的有向边的边权。
按照节点拓扑顺序计算d即可。
时间复杂度：𝑂(𝑁+𝑀)
C. 处女座点名
题目分析
题目已经保证了输入顺序，只需要判断读入的数是否比上一个数大1即可。如果都满足，就是最后一个数没有出现。
BONUS：这题如果不给学生人数，不顺序读入怎么做呢？
时间复杂度：𝑂(𝑁)
D. 处女座的训练
题目分析
贪心思想。按照 作为关键字进行排序，按顺序完成作业即可。
时间复杂度：𝑂(𝑁 log N)
E. 处女座和小姐姐
题目分析
本题相当于只要求按照开火车的顺序，从(1,1)到(𝑛,𝑚)一共有几个人。
答案和m的奇偶性有关，如果m是偶数，答案是nm-n-1；如果m是奇数，答案是nm-2。
时间复杂度：𝑂(1)
F. 处女座和小姐姐（二）
题目分析
本题分为两个子问题。
1. 求一个数组连续p个数mod P的乘积
把序列按照长度m分成若干段，计算每段内的前缀和后缀乘积。
这样任意划窗位置的答案可以看成前一段的后缀和后一段的乘积拼出。
时间复杂度𝑂(𝑛∗𝑚+𝑝−1)
2. 找出长度为k的符合条件的链的个数
使用dfs进行搜索，复杂度〖400∗3〗^20显然会超时，因此使用枚举起点然后双向dfs的方法，一次往两边进行搜索，从而把复杂度降低到400∗〖2∗3〗^10，可以使用状压等方式记录状态。
G. 处女座和小姐姐（三）
题目分析
本题要求一个区间内含有6的数字的个数。
将ans[l,r]转换为ans[0,r]-ans[0,l-1]，另外我们可以计算不含6的数字总数，再用总数减去即可，即只需要计算不含6的ans’[0,k]，令，考虑10^n以内的不含6的个数，即每一位为012345689，所以共
个，再考虑!
，则加上第一位的可选方案，若
，则可选
，若
，则可选
，依此计算每一位即可。
时间复杂度：𝑂(𝑙𝑒𝑛)，其中len代表数的位数。
H.处女座的百日理财计划
题目分析
首先题目要求按照期望估算收益，则借钱的收益是，***的收益是
。
显然如果***概率>50%一定会去玩。对于借钱直接进行dp即可。由于收益固定，每次一定是全部都进行投入的。
注意由于题目里要取max，且涉及到乘法操作，只能全程用高精度计算最后进行取模。
时间复杂度：𝑂(200𝑁)
I.处女座的约会
题目分析
显然处女座十分牛逼，因此输出“cnznb”即可
咳咳……至于正确的做法。首先因为每次在右边砍掉一个头就相当于在左边会多出来一个头，所以可以把每𝑛次操作看作一轮，每轮的操作都是从01串右边向左边对每个位置在原位依次进行操作。我们考虑这种做法，从右到左我们首先看到1就把他变成0，0的话让他随机，直到第一次出现有0变成了1的情况。如果没有出现这种情况那么这个串已经符合了要求，如果有0变成1发生，那么在这之后的1我们都继续变成1。这样一轮结束之后，这个01串所表示的二进制数的的大小一定是严格增加了的（因为虽然你可能把一些1变成了0但是有一个高位的0变成了1）而这个二进制数的大小是有限的，因此在有限步内一定可以把这串数变成全0串。
时间复杂度：𝑂(1)
J. 处女座的比赛
题目分析
题目要求找出在给定的hash函数下hash值相同的答案。
注意到对于长度是1-4的小写字母的字符串一共共475254个，已经可以包含[0,9983)的范围，因此暴力对每个hash值记录两个字符串输出即可。记两个是防止输出和输入串相同判错，从而使用另一种替换。
时间复杂度：𝑂()
std：
- A： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40259860
- B： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40259879
- C： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40253290
- D： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40259904
- E： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40259919
- F： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40259930
- G： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40259954 （因为最一开始数的范围是1e1000所以用的高精度）
- H： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40259971
- J： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40259983
