2020-02-06 20:21 已编辑偶像大师灰姑娘女孩后端

关注

【题解】2020牛客寒假算法基础集训营第一场

注：每道题的参考cf难度分指codeforces.com对题目的难度评分（出题人自己估计）

写在题解前面的话

首先这次的题目难度并不大，大概是codeforces的div3水平（因为出题人rating只有1900太菜了QAQ）。比赛进行相对比较顺利，值得庆幸的是数据并没有出什么问题。
另外A题的样例描述有个小错误(坐标(3,2)写成了(3,3))，G题的题面容易引起歧义(“k个相同字母”)。
J题的测试样例仍然不够强，放过了部分错误代码。
这些都是我要检讨的，这里向大家说一声抱歉QAQ

J的样例已经加强，之前ac的童鞋们可以重新提交试试（不会影响排名）

J原来的标程也有错，不能通过加强后的样例，已更新标程。

level 1 hanayo和米饭

知识点： 数组循环

签到题。有多种方法可以做，最省事的方法是把每个数标记一下，然后遍历输出没标记的那个数就可以了。
参考cf难度分：700

level 1 kotori和bangdream

知识点：概率论

签到题。每个音符的得分期望是 $x\%*a+(100-x)\%*b$ ， $n$ 个音符的总得分期望为每个音符的期望乘以 $n$ 。
参考cf难度分：900

level 2 rin和快速迭代

知识点：数论模拟

只要会 $O($ $\sqrt{n}\$ $)$ 复杂度处理每一次迭代就行。是一道披着假数论的implementation
参考cf难度分：1000

level 3 eli和字符串

知识点：字符串前缀和双指针

可以单独处理每种字母找 $k$ 个的长度（双指针），然后求最小值。
或者也可以开26个前缀和，然后双指针找区间维护最小值。
参考cf难度分：1300

level 4 honoka和格点三角形

知识点：计数

可以把面积为 $1$ 的“好三角形”分为两类分开统计：两条边和两个坐标轴平行；只有一条边和某个坐标轴平行。
对于第一种情况，一定是 $1*2$ 或者 $2*1$ 的形式，一个 $1*2$ 的矩形中含有4个不同的三角形。总数是 $4*((n-2)*(m-1)+(m-2)*(n-1))$
对于第二种情况，可以分别统计底边为 $2$ 、高为 $1$ 和底边为 $1$ 、高为 $2$ 的情况。要注意底边靠近边界时的特殊讨论。
①对于底边为2，高为1的情况：
若底边和x轴平行，那么底边横向移动（指x轴水平移动，下同）有 $n-2$ 种可能，“对点”（指底边相对的点）的某一面选择有 $n-2$ 种可能（某一面选择，指的是底边固定的情况，对点在一条直线上移动所做出的选择），而底边纵向移动有 $m$ 种情况，其中有 $(m-2)$ 种情况对点可以选择两个面，2种情况对点只能选择一个面（当底边移动到格点阵边界的时候）。因此纵向移动折合为 $2*(m-2)+2$ ，即 $2*(m-1)$
以上可计算为 $2*(m-1)*(n-2)*(n-2)$
若底边和y轴平行，同理可推出 $2*(n-1)*(m-2)*(m-2)$
②对于底边为1，高为2的情况，推理方法和上面类似，请选手们自行推理。
参考cf难度分：1500

level 4 nozomi和字符串

知识点：字符串贪心

显然操作要么全1变0，要么全0变1。
分别处理两种操作即可。对于1变0的情况，可以分别统计每个1的前缀1和后缀1的位置（第一个1的前缀为 $0$ ，最后一个1的后缀为 $n+1$ ），那么 $k$ 次操作，即变换连续 $k$ 个1，最终的字符串长度就是第 $i$ 个1的前缀1到第 $i+k$ 个后缀1之间的距离。
对于0变1的情况同理。
参考cf难度分：1600

level 5 maki和tree

知识点：图论
经过一个黑点的路径有两种：两个端点都是白点；其中一个端点是黑点。
因此我们可以先预处理，将每个白点连通块上的白点个数统计出来。这样我们就可以得知每个黑点所连接的白点的权值（即连通块白点数）。
设某黑点连接了 $k$ 个白点，第 $i$ 个白点的权值为 $f(i)$ 。
这样第一种路径的数量为 $\mathop{ \sum }\limits_{{i=1}}^{{k}}{{\mathop{ \sum }\limits_{{j=i+1}}^{{k}}{f \left( i \left) *f \left( j \right) \right. \right. }}}$ ，第二种路径的数量为 ${\mathop{ \sum }\limits_{{i=1}}^{{k}}{f \left( i \right) }}$ 。第一种可以用前缀和处理达成 $O(k)$ 计算
参考cf难度分：1900

level 5 umi和弓道

知识点：计算几何双指针

首先确定umi所在位置的象限。很明显同一象限的点是不可能用挡板挡掉的，对于剩下的点找出线段和 $x$ 轴或 $y$ 轴的交点，统计坐标位置（如果存在交点的话）。
之后双指针维护 $x$ 轴上或者 $y$ 轴挡住 $n-k$ 个点的挡板长度最小值。注意 $x$ 轴和 $y$ 轴要分开计算。
参考cf难度分：2000

level 5 nico和niconiconi

知识点：动态规划

计 $dp[i]$ 代表前 $i$ 个字符的计数最大值。
那么可得转移方程：

$if(substring(i-3,i)==nico)then$ $dp[i]=max(dp[i],dp[i-4]+a)$
$if(substring(i-5,i)==niconi)then$ $dp[i]=max(dp[i],dp[i-6]+b)$
$if(substring(i-9,i)==niconiconi)then$ $dp[i]=max(dp[i],dp[i-10]+c)$

最后输出 $dp[n]$ 即可。
参考cf难度分：1800

level 6 μ's的影响力

知识点：数论矩阵快速幂

显然 $f(n)$ 可以用 $x$ , $y$ 和 $a$ 这三个因子表达出来。
每一项a的幂次分别是 $0、0、b、2b、4b、7b、12b……$ 从第三项开始每一项为前两项之和加1。
而x和y的幂次构成斐波那契数列：x的幂次第一项是1，第二项是0；y的幂次第一项是0，第二项是1。之后每一项均为前两项之和。
根据费马小定理，由于1e9+7是素数，有 ${a\mathop{{}}\nolimits^{{1e9+6{\text{ }}}} \equiv 1 \left( mod\text{ }1e9+7 \right) }$ 。因此幂的指数对1e9+6取模即可。要注意a是1000000007的倍数的特殊情况。
可以用矩阵快速幂O(logn)求出x、y、a幂次的第n项。
矩阵快速幂求斐波那契数列的第n项方法如下:
假设 $f(i)$ 代表斐波那契数列的第 $i$ 项，显然有：
$图片说明$
因此
$图片说明$
而 $图片说明$ 的值可以用快速幂算出来，这样就可以O(logn)实现计算斐波那契数列的第n项了。
有关快速幂的知识：
要求 $a^b$ mod p，我们可以得出
①若b为偶数， $a^b=({a^{b/2}})^2$
②若b为奇数， $a^b=({a^{(b-1)/2}})^2*a$
可以看到幂是指数级别下降的，因此最终复杂度是 $O(logn)$ 而不是朴素算法的 $O(n)$
参考cf难度分：2200

标程：

全部评论

推荐最新楼层

肖战公关团队

没上过大学 C++

感觉F题的数据有点水，如果这样生成的数据能让 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42775397 tle。上面的做法是抠掉所有的黑色节点，然后对每一个黑色节点都进行dfs，下面这组数据所有的白色节点在每一次dfs的时候都会被找一遍，从而卡掉上面的做法。 #include<bits/stdc++.h> using namespace std; int main() { // freopen("test.txt", "w", stdout); int n = 32222 << 1; cout << n << "\n"; for(int i = 1; i <= n / 2; i++) cout << "W"; for(int i = 1; i <= n / 2; i++) cout << "B"; cout << "\n"; for(int i = 1; i < n / 2; i++) cout << i << " " << i + 1 << "\n"; for(int i = n / 2 + 1; i <= n; i++) cout << 1 << " " << i << "\n"; } 加上这样的数据会更好一点。

3 回复分享

发布于 2020-02-04 20:14

QieQiemin

东南大学 C++

个人感觉 level 5 nico和niconiconi 在CF里大概1600

2 回复分享

发布于 2020-02-04 18:09

三金老师

荔枝FM_交易技术部_Java 工程师

请问A题中在题解中所提到的特殊情况比如说统计边平行与x轴时 s=(s+2*(n-1)*(m-2)%mod*(m-2)%mod+2*(m-1)*(n-2)%mod*(n-2)%mod)%mod; 为何是（m-2）以及（n-2)

2 回复分享

发布于 2020-02-04 20:11

塔子哥学算法

Fleet AntiSubmarine Warfare Training Center (San Diego) C++

J题b的规律找错了。。。手速还是太慢了吖

1 回复分享

发布于 2020-02-04 18:27

FriedChicken

北京理工大学算法工程师

F题这个做法是传说中的dsu on tree吗（无知脸）

1 回复分享

发布于 2020-02-04 19:03

win_the_medal

银山小学

A题第二种情况的规律是什么

1 回复分享

发布于 2020-02-04 19:04

Emcikem

浙江工商大学 Java

请问j题矩阵快速幂时，为什么要特判判断下面的条件 if(x % mod == 0 || y % mod == 0 || a % mod == 0){ printf("0\n"); return; } 可以给一下这个特判数据吗

1 回复分享

发布于 2020-02-05 15:58

QieQiemin

东南大学 C++

level 5 umi和弓道，将与2个坐标轴的交点分别排序后for一边即可，用双指针干嘛的= =？

点赞回复分享

发布于 2020-02-04 18:10

hoi33

西京学院算法工程师

我今天终于发现辐角排序有多慢了。题出得很不错。J题今天差点教我做了人

点赞回复分享

发布于 2020-02-04 18:14

Pyo

字节跳动_Flow_服务端工程师

J特殊情况没考虑，自闭

点赞回复分享

发布于 2020-02-04 18:20

潘小蓝

天津理工大学算法工程师

C题可以用二分写么？

点赞回复分享

发布于 2020-02-04 18:21

大昌哥

深圳职业技术学院 Java

请问有java的吗

点赞回复分享

发布于 2020-02-04 18:26

Mr.Edge

广东工业大学 C++

H题可以二分答案吗

点赞回复分享

发布于 2020-02-04 18:36

冲刺冲

温州科技职业学院 C++

我觉的这次比赛超级棒(๑•̀ㅂ•́)و✧

点赞回复分享

发布于 2020-02-04 18:37

苯磺酸有没有构型异构

kokodayo小学

J题硬推许久，最后竟然发现a^b的指数是两项之和+1，手贱写成两项之和，结果浪费时间了= =

点赞回复分享

发布于 2020-02-04 18:42

牛客666669378号

厦门大学嘉庚学院算法工程师

J 题放过的部分错误代码错在哪里啊..（我看看我错没错

点赞回复分享

发布于 2020-02-04 18:46

学习使我超快乐

湖南工学院 Java

对于我们这种J题如何用矩阵求出第n项这种前置知识都不会的人怎么办，又没有算法基础知识的相关讲解。🤣🤣🤣

点赞回复分享

发布于 2020-02-04 18:49

潘小蓝

天津理工大学算法工程师

大佬,H题您为啥要往容器里面放 -1 和 n 呢？

点赞回复分享

发布于 2020-02-04 18:57

蔡队小迷弟

门头沟学院

关于J题标程 cout<<power(x,feb(n-2,m-1),m)*power(y,feb(n-1,m-1),m)%m*power(a%m,feb2(n-2,m-1)%(m-1),m)%m<<endl; 如果x%(1e9+7)=0，feb(n-2,m-1)=0，那么最终的计算结果是不为0的，但是答案应当为0 所以应当改为 power(x,feb(n-2,m-1)+m-1,m)

点赞回复分享

发布于 2020-02-04 19:21

wased

成都市实验外国语学校（西区） C++

请问A题的“一个 1*21∗2 的矩形中含有4个不同的三角形”是怎么推出来的，能不能说一下是哪四种？

点赞回复分享

发布于 2020-02-04 19:27