当前位置：首页 > article >正文

蓝桥杯备赛(基础语法3)

article 2025/3/18 10:47:17

·双指针

双指针简介

双指针算法是一种常用的算法技巧，它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。
双指针并非真的用指针实现，一般用两个变量来表示下标（在后面都用指针来表示）。

双指针算法使用两个指针在数据结构上进行迭代，并根据问题的要求移动这些指针。双指针往往也和单调性、排序联系在一起，在数组的区间问题上，暴力法的时间复杂度往往是O(n^2)的，但双指针利用“单调性”可以优化到O(n)。常见的双指针模型有：

1)对撞指针
2)快慢指针

对撞指针

简介

指的是两个指针 left、right (简写为 l , r )分别指向序列第一个元素和最后一个元素。然后 l 指针不断递增，r不断递减，直到两个指针的值相撞或错开（即1>=r),或者满足其他要求的特殊条件为止。
对撞指针一般用来解决有序数组或者字符串问题（常见于区间问题）：
查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。

字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

求解步骤

1.使用两个指针left,right。left指向序列第一个元素，即：left=1,right指向序列最后一个元素，即：right=n。
2.在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，left++。当满足另外一定条件时，将右指针左移，right--。
3.直到两指针相撞（即left==right),或者满足其他要求的特殊条件时，跳出循环体。

例题

对撞指针，每次判断s[l]和s[r]是否相等，如果相等就都移动一步，否则直接判断为“不是回文串”

快慢指针

简介

快慢指针一般比对撞指针更难想，也更难写。
指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。
移动快的指针被称为快指针，移动慢的指针被称为慢指针。
为了方便理解，我们称快指针为r,慢指针为l，这样慢指针和快指针构成区间[l，r|。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。

求解步骤

1.使用两个指针l、r。l一般指向序列第一个元素，即：l=1，r一般指向序列第零个元素，即：r=0。即初始时区间[l，r] = [1,0]表示为空区间。
2.在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即l ++。当满足另外一定条件时（也可能不需要满足条件），将快指针右移，即 r++,保持[l，r]为合法区间。
3.到指针移动到数组尾端（即l == n且r == n),或者两指针相交，或者满足其他特殊条件时跳出循环体

例题

（1）

利用快慢指针，保持区间[ i, j ]尽可能小且和 >= S.在这里当[i, j]的sum >= S后，再增加j没有意义，所以i，j都不动了，当i增大后sum可能<S,此时j不可呢左移，所以只能右移，于是i, j都只能右移，

从来不会出现左移。

（2）

利用快慢指针，保持区间 [ i ,j ] 中大于等于k的个数至少有k个，且区间尽可能小，得到区间 [ I, j] 后，说明对于这个左端点i,有 n - j + 1 个右端点可取。思路和例题1类似，这里也是 i, j 都只能右移。

·构造

（1）

为使得序列乘积不为零，那么序列中就不能存在0，所以第一步就是将所有0先修改为1，这一步不可能省略，所以这一个操作的代价是0的数量。
在修改完成后，若序列之和不为零则直接输出答案：0的数量。若序列之和为零，说明序列中一定存在正数和负数（因为没有0了)，只需要任意将一个正数+1即可，所以答案是0的数量+1。

（2）

x = y * y - z * z = ( y + z )( y - z )
不妨令 A = y + z , B = y - z ,设x,z均为非负整数,则有 A >= B , A - B = 2z.
说明AB之差是个偶数。
于是A,B只能是奇奇或偶偶的形式。
对于任何一个奇数x,我们都可以构造 B = 1 , A = x ,来使得x=A*B成立，
且 A - B 为偶数，满足条件。
对于一个偶数 x ,若其质因数分解之后的2的个数 >= 2，就一定可以写成两个偶数的乘积，反之一定不能。
最后结合前缀和思想O(1)求到答案。

方法一：

方法二：

（3）

容易想到二分，枚举一个mid,检查大小为mid的字符集能够使得这n个字符串字典序升序。难点在于check函数如何设计。若字符集大小为1很容易判断，只需要判断a序列是否是升序即可。但是ai最大可能到1e9,这里我们就要考虑如何存储下这些字符串，字符串中的元素应该要用数字来表示，但是我们肯定开不下长度为le9的数组，发现字符串中大部分都是0，于是我们可以用一个vector来描述当前的字符串，即除了0以外的所有位置。
例如字符串10000202可以描述为：[{1,1}，{6,2}，{8,2}]，假设字符集大小为3（即超过3就要进位）。
当次数又来了一个长度为6的字符串，应该要在6的位置+1，并在变大的位置之后的所有位置全部置0（即从vector中删除），得到10001000,[{1,1},{5,1}],这个操作直接模拟即可。

·位运算

位运算简介

位运算的概念和作用

位运算是一种对二进制数的位进行操作的运算方式。
它直接对二进制数的每一位进行逻辑操作,而不考虑整个数的数值大小,一般情况下,位运算中每一位都相互独立,各自运算得出结果(左右移除外)。
在计算机科学和编程中，位运算常用于优化算法、位掩码操作、位字段处理等领域。在竞赛中，位运算经常考察异或的性质、状态压缩、与位运算有关的特殊数据结构、构造题等。
注意：位运算只能应用于整数，且一般为非负整数，不能应用于字符、浮点等类型。

整数的二进制表示

在计算机中，整数是通过补码表示的，但是一般情况下，我们对负数进行位运算意义不大，99%情况下都是对正整数进行处理，而正数的原码=补码，所以我们直接考虑二进制数的原
码，也就是直接地表示二进制数。
例如整数10，在计算机中存储如下（按照书写习惯，一般认为右边为低位，在左右移时尤为
重要)：

常见的位运算

按位与AND(&)

按位与运算符(&)用于对两个操作数的对应位进行逻辑与操作。它的运算规则是,只有当两个位都为1时,结果位才为1,否则为0。两个数字做与运算,结果不会变大

按位或OR( | )

按位或运算符 ( | ) 用于对两个操作数的对应位进行逻辑或操作。它的运算规则是，只要两个位中有一个为1，结果位就为1，否则为0。两个数字做或运算，结果不会变小。

按位异或XOR( ^ )

按位异或运算符 ( ^ ) 用于对两个操作数的对应位进行逻辑异或操作。它的运算规则是，当两个位不同时，结果位为1，否则为0。两个数字做异或运算，结果可能变大也可能变小，也可能不变。

（两边同时异或y，抵消掉）

按位取反( ~ )

用于对操作数的每一位进行取反操作，即将0变为1，将1变为0。
按位取反操作通常用于无符号整数(unsigned int/long long),这是为了避免符号位取反造成干扰。
假设某个无符号整数只有4位，结果如下（长度不同结果也会不同，需要具体情况具体分析)：

按位左移( << )

左移 ( << ) 操作将一个数的二进制表示向左移动指定的位数。
移动后，低位补0，如果数据类型为有符号整型，注意移动的时候不要移动到符号位上，或者干脆使用无符号整型。1会移动到符号位上。

左移操作相当于对原数进行乘以2的幂次方的操作。
例如，对于整数5（二进制表示为00000101），执行左移3位操作，相当于执行 5 * ( 2 ^ 3 ) 。

按位右移( >> )

左移(>>)操作将一个数的二进制表示向右移动指定的位数。
移动后，一般情况高位补0，如果数据类型为有符号整型，注意移动的时候让符号位为0，或者干脆使用无符号整型。如果符号位上有1不会被移走，这是负数位移的规则。
右移操作相当于对原数进行除以2的幂次方的操作。例如，对于整数13（二进制表示为00001101）执行左移2位操作，相当于执行13/4向下取整。