竞赛讨论区 > 【题解】2020牛客NOIP赛前集训营-普及组(第一场)

【题解】2020牛客NOIP赛前集训营-普及组(第一场)

头像
四糸智乃
编辑于 2020-10-17 22:46:22 APP内打开
赞 10 | 收藏 3 | 回复5 | 浏览1845

before contest

这套题并没有涉及太多的算法或者数据结构。
更多的还是偏思维和基础。
本场隔壁提高组也是本人负责,感兴趣可以过去看一看。

T1 牛牛的密码

签到题,暴力模拟,考察语言基础。

100pt

输入字符串循环遍历处理,由于我们知道字符的ASCII码中,小写英文字母,大写英文字母,数字,都是连续的。
所以可以设计一个分支结构判断,这样做的好处是可以最后用else来表示其他特殊字符。

T2 牛牛的跳跳棋

思维题,简单贪心

20pt

dfs爆搜之

40pt

如果碰到连续的1,肯定对最后一个出现的1把它变成2,然后如果后面还是0,就改成1。
比如"0 0 1 1 0 1 1 1 0 0 0"修改后变成"1 1 1 2 0 1 1 2 0 1 1"。
(换句话说就是修改后变成连续若干个1,把末尾的1变成2,后面接一个0,然后依次类推,最后变成1 1 1...1 1 2 0...的模式)

100pt

原本不要求修改,质问你能不能到达的话是一个青蛙跳的经典问题。
原题是这样做的,首先贪心的想,往回跳是不必要的,因为如果可以走到第i个格子,那么必定可以在最后一次跳格子的时候力度小一点走到第i-1个格子。
这样的话易知在不修改数字的情况下,从第一个格子开始走可以到达的格子是连续的。
所以这样设计算法,记录一个r,表示当前能够到达的最靠右的格子。
然后遍历过去,更新r=max(p[i]+i,r)。过程中发现i>r的情况就说明不可达,反之说明可达。

本题其实还是相同的思路,只不过在更新右边界的同时,我们还需要知道右边界是谁提供的,一边更新r,同时储存更新右边界的格子pos。
一旦发现i>r的情况,首先让a[pos]+1。因为首先pos提供了当前右边界,所以当a[pos]+1时可以立即更新边界r,而其他格子即使增加也不一定能够使得边界扩充,这就保证了题目中的“修改次数最少”这个要求,同时由于是顺序遍历,pos是第一个达到右边界r的格子,所以也同时保证了“最小字典序”这个要求。

在更新后我们令pos=i,然后继续遍历,这样在算法结束后就得到了一个“最小操作次数并且最小字典序”的操作序列。

T3 牛牛的最大兴趣组

简单数学题

20pt

dfs爆搜之

40pt

40pt是一个二分图染色算法。虽然普及组不考图论,但是二分图染色就是个dfs。

首先两重for循环枚举i,j,如果i*j是某个数字的三次方,就把i和j连一条边。
然后对于每个联通块进行二分图染色,假设红色有a个节点,蓝色有b个节点。那么就令ans+=max(a,b)。

100pt

对于任何一个正整数都可以表示成的形式,其中最大的立方因子。
如果a是n去掉最大立方因子后的结果,b是m去掉最大立方因子后的结果,如果nm是立方数,则ab也是立方数,且a和b是唯一配对的。
例如2,16,54,686在去除立方因子后全部等于2,然后4,32,108,1372在去除立方因子后全部等于4。
所以{2,16,54,686}中的任意一个数字乘上{4,32,108,1372}中的任意一个数字都是一个立方数。

一开始输入数字,筛除掉它们的立方因子,然后统计每种数字出现次数。
然后对于每一对出现的种类,都是两两互斥的,所以贪心的取出现次数较多的部分即可。

在实际处理上是有细节的,筛除立方因子可以只枚举立方根以内的质数,这样的话单次去除立方因子的复杂度可以压到200次运算左右。

T4 牛牛的滑动窗口

简单数据结构,简单算法题
大概普及T3,T4会稍微上一点难度。

一般有个说法,题目标题中出现的算法名都是用来骗人的。
这个题的话,有一半是骗人的吧,写个划窗能拿一半分。
但是std也确实是从滑动窗口算法得到的启示。

30pt

暴力三重for循环。

50pt

真的写划窗或者RMQ啥的优化掉一层for

100pt

滑动窗口的使用条件正如题目中介绍的那样,需要保证每个查询的端点值是“双单调”的。
实际上划窗算法,或者叫尺取法。的使用条件就是“双单调”。(实际上有部分选手懒得管它到底几个单调,一般看见一个单调就直接二分上了,反正没人卡log)

首先需要掌握一个技巧,“单调队列O(n)求滑动窗口极值”,这个算法

如图,假设这是一个用划窗扫描数组5,7,4...的场景,假设求最大值。

在继续扫描到7的时候,我们想一下5这个数据有没有用。
因为是滑动窗口求最大值,当前的最大值已经是7了,它有没有可能再变回5?
显然不可能,因为滑动窗口要求端点递增,所以5将会先比7被舍弃。

接下来继续扫描,4要不要保留,显然保留,因为根据滑动窗口的定义,7一定比4先被舍弃。

然后当7被划窗划过后,4上位变成当前最大值。

有了这个算法以后,我们开两个单调栈,分别维护最大值和最小值,然后从左到右遍历过去。
这样的话就可以知道当r单调向右滑动的时候,l端点落在不同的位置时最大值最小值各是多少。

由于值域不超过100,那么栈内的元素数目肯定是不会多于100的。
所以我们可以暴力穷举栈内元素。
然后因为两个单调栈都是有序的,在这里再次借助双指针划窗。提取出max*min相同的区间长度是L到R。

使用差分维护一个数组a,a[k]表示区间长度为k的答案。
然后将使用差分将a[L]~a[R]这段区间全部加max*min即可。

最后对差分数组求前缀和,就得到了每一个区间长度的答案。

after contest

没提前准备大样例,最近比较忙忘了这回事了。

从下一场开始会有大样例给大家测。(虽然并不是我的场了)

啊这,没人ak可还行。

下一场的话是我朋友鸡尾酒出的,他这场我验过比我的简单(。
可能有点难了...后面的场应该会比我这个简单多。

std

5条回帖

回帖
加载中...
话题 回帖