2021-02-05 18:22 已编辑北京理工大学研发工程师

关注

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

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

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

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

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

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

D.Happy New Year！

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

G.糖果

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

H.数字串

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

J.加法和乘法

博弈题

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

I.序列的美观度

贪心/动态规划
法 $\text 1$ ： $dp_{i}$ 代表考虑前 $\mathit i$ 个数字，以第 $\mathit i$ 个数字作为末尾的子序列的美观度最大是多少。则有以下转移 $dp_{i}=max\{dp_{j}+1\},j<i$ 且 $a_{i}=a_{j}$
$dp_{i}=max\{dp_{j}\},j<i$ 且 $a_{i}≠a_{j}$
这个复杂度是 $O(n^{2})$ 的，无法通过，但是对于第二个方程我们可以直接取前 $\mathit i-1$ 项 $\mathit dp$ 的最大值 $\mathit Max$ ，对于第一个方程我们可以直接取前 $\mathit i$ 个里面最后一个等于 $a_{i}$ 的位置 $\mathit pos$ ，然后取 $\mathit Max$ 和 $dp_{pos}+1$ 的较大值，注意 $\mathit pos$ 不存在的情况，并在求完以后更新 $\mathit pos$ 数组。
法 $\text 2$ ：
可以发现，每次贪心的找最近的两个相同数字拼接在当前序列末尾是最优的。
设当前考虑了前 $\mathit i$ 个数字，下一次取得相同数字的位置可选在 $\mathit l1,r1$ 或 $\mathit l2,r2$ ，其中 $i \leq l1 \leq r1 \leq n$ ， $i \leq l2 \leq r2 \leq n$ 。不妨设 $\mathit r1 \leq r2$ ，则我们获得 $... i$ $\mathit l1$ $\mathit r1$ $\mathit r2$ 和 $... i$ $\mathit l2$ $\mathit r2$ 美观度至少是一样的，但以 $\mathit r1$ 做结尾时可以有更多的选择，所以贪心是正确的。

C.重力坠击

$\mathit dfs$ /暴力枚举
攻击的点也一定在 $\text [-7,7]*[-7,7]$ 范围内，否则不优。 $\mathit dfs$ 一下攻击的位置取最大值即可。

F.匹配串

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

E.买礼物

数据结构
用 $last_{i}$ 代表与 $a_{i}$ 相同且小于 $\mathit i$ 的最大的还没被买走的礼物位置 $\mathit j$ ，如果没有则置为 $\text 0$ 。
用 $next_{i}$ 代表与 $a_{i}$ 相同且大于 $\mathit i$ 的最小的还没被买走的礼物位置 $\mathit k$ ，如果没有则置为 $\mathit n+1$ 。
（实质上就是链表）
对于修改操作，设被买走的位置是 $\mathit i$ ，则 $\mathit next[last[i]]=next[i]$
$\mathit last[next[i]]=last[i]$
$\mathit last[i]=0$
$\mathit next[i]=n+1$
对于查询操作，实际上就是询问 $\mathit l$ 到 $\mathit r$ 范围内是否有位置 $\mathit i$ 的 $\mathit next$ 值小于等于 $\mathit r$ 即可。
于是问题变成了单点更新，区间查询最小值，用线段树就可以完成任务了。

B.内卷

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

A.模数的世界

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

全部评论

推荐最新楼层

溢流眼泪

浙江师范大学 C++

C题有没有人写状压DP的🤣没想到一个dfs就行了

1 回复分享

发布于 2021-02-05 18:32

iiiiikun

南开大学 Java

ra = ((k2 + 1 - k1) * x * p + k1) * (p - 1); rb = k2 * (p - 1) 这是如何保持互质的？

1 回复分享

发布于 2021-02-05 21:37

黎_明_之_光

西安交通大学 iOS开发

求问c题过了95%的样例是哪里出错了

点赞回复分享

发布于 2021-02-05 18:39

Q_Q_Q_Q

The University of New South Wales C++

H题数据是否存在疏漏? 我一个代码cbcc输出-1也ac了。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46741239（cbcc输出-1的) https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46741211(正确输出的)

点赞回复分享

发布于 2021-02-05 19:06

许愿大厂offer_please

门头沟学院 Java

“挑战：可以考虑如果模式串中可以没有'#'该怎么办，需要前置知识：后缀自动机，\mathit dfsdfs序，线段树上二分” 球球出题人或者哪个大佬能不能给个类似的题目的题号😁

点赞回复分享

发布于 2021-02-05 20:11

滑稽(´・ω・)ﾉ

字节跳动_客户端开发工程师

J主要是数据范围允许模拟，难度就低很多啦

点赞回复分享

发布于 2021-02-05 20:24