【题解】2021年牛客寒假集训营第三场题解

怎么样，我说特别简单吧（不是）

赛前难度预计：
D是签到，其次是CGHI，再其次是FJ，最后是ABE。
没想到高估了J，低估了C。。。

先说一下G的事情，开场有好多人问我朋友的朋友算不算朋友，所以我就发了广播说明（而且我在题面中从头到尾没有说过朋友的朋友算朋友，所以不知道为什么会yy出这样一个条件，你做过一道题不代表所有类似的题都是一样的鸭），如果有人因为看了广播然后改了自己的做法而wa，我觉得你wa的一点都不冤，因为你不是真的会做这题。
举个大家都问我的例子：

3 2
1 2 3
1 2 
2 3

很多人好奇这组数据分糖果应该是2 3 3还是3 3 3，那么请大家想想，如果是2 3 3，第一个人和第二个人是朋友，而第一个人的糖果数小于第二个，那第一个人是不是不开心呢？那跟朋友的朋友是不是朋友有什么关系呢？
题面我觉得已经写得清清楚楚了，所以问这个的我都回了请认真读题。

J题数据造的弱了一点，放过了一种情况，实在抱歉。

D.Happy New Year！

如果n=2030，输出2102，否则输出n+10-1。
打个暴力也可以。

G.糖果

并查集/
如果我们把朋友关系当成无向边建图，每个小朋友得到的糖果数等于他所在联通块里需要糖果数最大的那个人需要的糖果数，最后累计一下和就行了。因为这个本身就具有传递性，可以想想为什么。

H.数字串

构造题
首先考虑一个字符能否拆分，例如17拆成1和7
其次考虑相邻两个字符能否合并，例如1和7合成17
否则无解
注意10和20不能拆，1和20也不能合，20和1也不能合等等

J.加法和乘法

博弈题

需要特判（很重要）
如果不等于，可以发现，如果最后一次操作是后手进行，则后手必胜。（奇数+奇数=偶数，偶数乘以任何数都等于偶数）。
否则如果初始状态有至多一个偶数，先手总有办法把局面变成全部都是奇数然后交给后手，后手至多产生一个偶数，因此给先手时局面不变。在最终时由于最多只有一个偶数，所以先手必胜。
反之，如果初始状态有至少两个偶数，无论先手怎么操作，后手还给先手的时候一定还有至少两个偶数，所以先手最后面对的局面就是两个偶数，后手必胜。
我后台测的时候以为牛客会自动测样例。。所以就没放样例一这种数据，导致有的人没注意特判但是很迷的加上了是奇数且都是奇数就判牛牛赢，然后过了。。是我的失误，实在抱歉。

I.序列的美观度

贪心/动态规划
法： 代表考虑前个数字，以第个数字作为末尾的子序列的美观度最大是多少。则有以下转移 且
且
这个复杂度是的，无法通过，但是对于第二个方程我们可以直接取前项的最大值，对于第一个方程我们可以直接取前个里面最后一个等于的位置，然后取和的较大值，注意不存在的情况，并在求完以后更新数组。
法：
可以发现，每次贪心的找最近的两个相同数字拼接在当前序列末尾是最优的。
设当前考虑了前个数字，下一次取得相同数字的位置可选在或，其中，。不妨设，则我们获得 和 美观度至少是一样的，但以做结尾时可以有更多的选择，所以贪心是正确的。

C.重力坠击

/暴力枚举
攻击的点也一定在范围内，否则不优。 一下攻击的位置取最大值即可。

F.匹配串

思维
答案要么为要么为无穷大。
首先筛出所有串第一个#之前的前缀和最后一个#之后的后缀，如果这些前缀都是最长前缀的前缀，这些后缀都是最长后缀的后缀，那么答案就是无穷大。否则答案为。
我们将除了第一个和最后一个#替换为空，那么如果所有字符串的形式形如：
abcde#X#fghjk
abc#Y#ghjk
a#Z#jk
abcd#W#k
那么：
匹配的上abcde#XYZW#fghjk的都可以匹配上上面的。
所以可以筛出所有的前缀/后缀串然后哈希或者排完序暴力去匹配一下试试就可以了。
挑战：可以考虑如果模式串中可以没有'#'该怎么办，需要前置知识：后缀自动机，序，线段树上二分

E.买礼物

数据结构
用代表与相同且小于的最大的还没被买走的礼物位置，如果没有则置为。
用代表与相同且大于的最小的还没被买走的礼物位置，如果没有则置为。
（实质上就是链表）
对于修改操作，设被买走的位置是，则



对于查询操作，实际上就是询问到范围内是否有位置的值小于等于即可。
于是问题变成了单点更新，区间查询最小值，用线段树就可以完成任务了。

B.内卷

尺取
用三元组分别代表分数，学生编号，是否是等级下的分数，按照排序，实际上就是要找一段区间，满足区间内每个学生编号都至少出现过一次且只能取等级的学生数量不超过个。
这个问题是可以在我们排好序的三元组上尺取的，维护好每个学生编号出现的次数和他的等级是否出现过，尺取后取最小值就可以了。

A.模数的世界

根据猜想/观察可知除非a=b=0，答案为0，否则答案必为p-1,下面给出证明并假设a0且a b。
若b=0,那么设x=(p-a)*(p-1),y=p(p-1),
则x%p=a,y%p=0,gcd(x,y)=p-1,显然是最大的。
若b0,设k1(p-1)%p=a, k2(p-1)%p=b。 则k1=p-a,k2=p-b是满足上述等的解,,而k1k2。
但此时k1和k2可能并不互质。此时设
x=(mp+k1)(p-1), y=k2(p-1)
注意到k2!=0且k2必然和p互质，那么 mp+nk2=1必有解。利用exgcd解出系数，并让m大于0,此时该式子等价于m*p1(mod k2)。
构造((k2+1-k1)mp+k1)(p-1)=x, k2(p-1)=y为解,可证满足上述方程，且二者gcd为p-1。

std：
A：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46739950
B：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46739959
C：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46739997
D：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46740069
E：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46740077
F：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46740103
G：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46740111
H：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46740117
I：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46740126
J：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46740140