竞赛讨论区 > 2022牛客OI赛前集训营-普及组(第六场)题目解析
头像
Johnson_sky
编辑于 2022-10-21 09:15 山东
+ 关注

2022牛客OI赛前集训营-普及组(第六场)题目解析

A-座位

题目大意

给一个长度为的01串,需要添加尽可能多的1,使得没有相邻的两个1存在,求方案数(对998244353取模)。

题目解析

10%:n≤15

枚举每个位置是否为1,然后判断有无相邻的两个1存在。注意,你不可以把1改为0

时间复杂度:

10%:字符串至多有15个位置为0,其余位置为1

枚举每个0是否改为1,然后判断有无相邻的两个1存在。判断时只需要判断从0改为1的那些位置的前后两个是否为1即可。

时间复杂度:,其中0的个数。

10%:字符串只包含0

输出

10%:字符串只包含1

输出

10%:字符串只包含1个1

设第个位置为1,则这个位置前面有0,后面有0,考虑的奇偶性:

  • 偶数,则这一段0有且仅有一种形如101010...10的方案

  • 奇数,则这一段0种方案。

    • 考虑在为偶数的基础上插入一个01

      • 无法插入1,因此满足尽可能多的要求

      • 每个1后可以再插入一个0,共可形成种方案

      • 最开始的位置可以插入一个0,计种方案

同理于

二者显然满足乘法原理,相乘即可得到最终答案。

10%:字符串只包含2个1

在前一个10%的基础上,考虑两个1中间一段长度为0对答案的贡献:

  • 奇数,则这一段0有且仅有一种形如010101...010的方案

  • 偶数,则这一段0种方案。

    • 考虑在为奇数的基础上插入一个01

      • 无法插入1,因此满足尽可能多的要求

      • 每个1后可以再插入一个0,共可形成种方案

      • 这一段最开始的位置可以插入一个0,计种方案

结合上一个10%的原理,运用乘法原理将三者相乘即可得到最终答案。

100%

在前面几个部分分的提示下,已经介绍了最开始一段0、最后一段0和中间一段0的计算方法。

当中间存在若干段0时,仍然满足乘法原理,将每一段对答案方案数的贡献相乘即可。

注意,若存在两个相邻的1,则答案应为

没想到吧!标程并没有进行上述讨论!

标程并没有考虑上述复杂而又繁琐的讨论。

将给定的字符串前方加一个10,后方加一个01,你就会发现只需要考虑两个1中间的0的情况!

这样就避免了对于很多种特殊情况的讨论。

B-几何

题目大意

给定一个整数g,在第一象限内画出所有端点分别在两个坐标轴上,且端点横纵坐标和为g的所有线段,计算出这些线段与坐标轴围成的图形中包含的三角形个数。建议参考题目中的样例图片以进一步理解题目含义。

题目解析

10%

输出样例。

20%

可以手玩,但是很麻烦。

40%

提供了一档的部分分,供选手自由发挥。

70%

,考虑从增加的三角形数量。

参看题目描述和题目样例3的解释,随着增大,相当于在原有三角形数量的基础上,增加最下面一层产生的三角形数量。而最下面一层所产生的三角形数量为,则有递推公式,按照此公式递推,可以获得此部分分。

时间复杂度:

100%

考虑在的部分分的基础上进行优化。

展开递推公式,得:

其中,对于,可以利用题目中给出的提示进行计算。具体的,提示,累加求和得到,也即,即

得到的通项公式后,可以巧妙运用避免求除法逆元,也即判断能否被整除,并提前进行除法。

时间复杂度:

C-定点数

题目大意

给出两个浮点数,先把他们转换成整数部分24位、小数部分8位的32位定点数,然后作定点数加、减、乘、除中的一种运算,并把定点数以浮点形式输出。

题目解析

出题动机是参考去年IP地址的科普,本题科普定点数的相关知识。

由于选手可能会选择模拟来完成本题,因而对四种运算各给了25%的部分分,且在每一种运算的部分分中,均至少包含10%的数据转换时没有精度损失,20%的计算不出现下溢、20%的运算不出现上溢,以区分不同选手模拟此题的功能性是否正确。

但是,模拟解决本题会占用较长的时间,因而会浪费其他题目思考、编码、调试的时间。选手可以通过位运算来解决本题。

注意到,本题运算均为无符号运算。考虑将浮点数转为定点数(以unsigned int存储),实际上有d=(unsigned)(c * (1 << 8) + 0.5),其中+0.5是保证满足题目四舍五入的要求。不难发现,定点数的运算本质上都是在通过位运算对一个unsigned类型的量进行计算。

特别的,对于乘法和除法,在处理四舍五入时需要谨慎运算。

D-异或

题目大意

长度为的数组初值为,有次操作,每次将下标为l xor p(l+1) xor p(l+2) xor p、……、r xor p的数组元素异或q,求最后数组中每个元素的值。

题目解析

  • 对于的数据:暴力拿下。
  • 对于的数据:使用前缀和的技巧可以轻松拿下。
  • 对于为整数、的数据:注意到这种操作的区间,异或后,仍然会得到一个完整的区间,再运用前缀和的技巧即可拿下。
  • 对于全部数据:
    • 由上一个部分分可以意识到,对一个区间的操作可以拆分为至多个区间,满足每个区间异或p的结果仍然为一个新的区间
    • 拆分方法是:如果当前待拆分区间的前缀相同,且最长不相同的后缀一个全0另一个全1,则当前区间无需继续进行拆分。
    • 拆分这个区间,并运用前缀和思想进行标注即可。时间复杂度
    • 如果拆分未记录当前拆分的比特位,重新暴力拆分的话,时间复杂度会退化为

参考代码

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐