2022-10-21 09:15 已编辑 Hogwarts School 前端工程师发布于山东

关注

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

A-座位

题目大意

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

题目解析

10%：n≤15

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

时间复杂度： $O(n2^n)$

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

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

时间复杂度： $O(k2^k)$ ，其中 $k$ 为0的个数。

10%：字符串只包含0

输出 $\frac{n+2}{2}$ 。

10%：字符串只包含1

输出 $0$ 。

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

设第 $k$ 个位置为1，则这个位置前面有 $l=k-1$ 个0，后面有 $r=n-k$ 个0，考虑 $l$ 的奇偶性：

若 $l$ 为偶数，则这一段0有且仅有一种形如101010...10的方案
若 $l$ 为奇数，则这一段0有 $\frac{l+1}{2}$ 种方案。
- 考虑在 $l$ 为偶数的基础上插入一个0或1：
  - 无法插入1，因此满足尽可能多的要求
  - 每个1后可以再插入一个0，共可形成 $\frac{l-1}{2}$ 种方案
  - 最开始的位置可以插入一个0，计 $1$ 种方案

同理于 $r$ 。

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

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

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

若 $len$ 为奇数，则这一段0有且仅有一种形如010101...010的方案
若 $len$ 为偶数，则这一段0有 $\frac{len}{2}$ 种方案。
- 考虑在 $len$ 为奇数的基础上插入一个0或1：
  - 无法插入1，因此满足尽可能多的要求
  - 每个1后可以再插入一个0，共可形成 $\frac{l-2}{2}$ 种方案
  - 这一段最开始的位置可以插入一个0，计 $1$ 种方案

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

100%

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

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

注意，若存在两个相邻的1，则答案应为 $0$ 。

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

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

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

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

B-几何

题目大意

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

题目解析

10%

输出样例。

20%

可以手玩，但是很麻烦。

40%

提供了一档 $O(n^2)$ 的部分分，供选手自由发挥。

70%

设 $n=g-1$ ，考虑从 $n-1$ 到 $n$ 增加的三角形数量。

参看题目描述和题目样例3的解释，随着 $g$ 增大 $1$ ，相当于在原有三角形数量的基础上，增加最下面一层产生的三角形数量。而最下面一层所产生的三角形数量为 $\frac{n(n+1)}{2}$ ，则有递推公式 $a_n=a_{n-1}+\frac{n(n+1)}{2}$ ，按照此公式递推，可以获得此部分分。

时间复杂度： $O(n)$

100%

考虑在 $70\%$ 的部分分的基础上进行优化。

展开递推公式，得：

$a_n=\frac{1}{2}[1\times 2+2\times 3+\cdots +n\times (n+1)]$

$a_n=\frac{1}{2}(\sum n +\sum n^2)$

$a_n=\frac{1}{2}[\frac{n(n+1)}{2}+\frac{n(n+1)(2n+1)}{6}]$

$a_n=\frac{n(n+1)(n+2)}{6}$

其中，对于 $\sum n^2=\frac{n(n+1)(2n+1)}{6}$ ，可以利用题目中给出的提示进行计算。具体的，提示 $(n+1)^3-n^3=3n^2+3n+1$ ，累加求和得到 $(n+1)^3-1=3\sum n^2+3\sum n+n$ ，也即 $\sum n^2=\frac{(n+1)^3-1-3\sum n-1}{3}$ ，即 $\sum n^2=\frac{2n^3+3n^2+n}{6}$ 。

得到 $a_n$ 的通项公式后，可以巧妙运用 $6=2\times 3$ 避免求除法逆元，也即判断 $n$ 、 $n+1$ 、 $n+2$ 能否被 $2$ 或 $3$ 整除，并提前进行除法。

时间复杂度： $O(1)$

C-定点数

题目大意

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

题目解析

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

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

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

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

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

D-异或

题目大意

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

题目解析

对于 $n\le 2^{10}$ 或 $m\le 2^{10}$ 的数据：暴力拿下。
对于 $p=0$ 的数据：使用前缀和的技巧可以轻松拿下。
对于 $log_2(l)$ 为整数、 $log_2(r+1)=log_2(l)+1$ 的数据：注意到这种操作的区间，异或 $p$ 后，仍然会得到一个完整的区间，再运用前缀和的技巧即可拿下。
对于全部数据：
- 由上一个部分分可以意识到，对一个区间的操作可以拆分为至多 $2log_2(len)$ 个区间，满足每个区间异或p的结果仍然为一个新的区间
- 拆分方法是：如果当前待拆分区间的前缀相同，且最长不相同的后缀一个全0另一个全1，则当前区间无需继续进行拆分。
- 拆分这个区间，并运用前缀和思想进行标注即可。时间复杂度 $O(nlogn)$
- 如果拆分未记录当前拆分的比特位，重新暴力拆分的话，时间复杂度会退化为 $O(nlog^2n)$ 。

参考代码

全部评论

推荐最新楼层

leiwenda

华二前滩游戏测试

有代码吗

1 回复分享

发布于 2022-10-20 19:45 上海

Try_harder_one

天津仁爱学院 C++

学算法，就上牛客，XCPC铜牌不是梦，心动不如行动，点此下方链接报名立减20元：基础算法入门班：https://www.nowcoder.com/courses/cover/live/724?coupon=ARgGejk 进阶数据结构专题课：https://www.nowcoder.com/courses/cover/live/707?coupon=AQDlsi4

点赞回复分享

发布于 2022-12-02 20:51 天津