vegeone
0%

题意

给定一串字符串,求其中有多少长度>=3子串,且该子串中某个字符只出现一次。

思路

最终答案的求取可以通过遍历以i位置为所要求的只出现一次的字符所对应的子串数量来求取。

然后显然我们不可能直接对于每个字符c,都暴力的去找左边有多少个相邻的连续的连续的字符与c不同,以及右边有多少个相邻的连续的连续的字符与c不同。于是,我们需要通过预处理,来记录每个字符左右两边分别有多少个相邻的、连续的、与此字符不同的字符,最终的答案也可以理解为左边挑,右边取,然后相乘即可。假设左边的个数为l,右边的个数为r。那么对于该字符,它的贡献为:

由于还有一个限制是长度>=3,所以对某一边没有符合要求的字符时,需要另一边减去只取一个字符的情况,即:

阅读全文 »

BFS

BFS介绍

BFS,即宽度优先搜索,经常用于图上遍历等。相比于dfs,bfs是横向的搜索,是一层一层找的。

BFS通过队列进行依次处理,对于每个结点的子节点,将它通过排队的形式排在这一层的后面而非直接遍历,对于一颗BFS树,它的BFS序便是一层一层的向下拓展。

同时BFS由于是层层遍历,先访问到的一定是距离初始点最短的。

bfs的常规遍历顺序

阅读全文 »

DFS

DFS介绍

DFS,即深度优先搜索,经常用于暴力以及图上遍历等。相比于bfs,dfs是纵向的搜索,是一次性找到底的。从根找到底,然后退回来换条路继续走到底,直到走完。

DFS可以理解为是递归+回溯。对于一棵DFS树,其搜索的方式是从根结点开始,沿着一条边一直走到底,层层递归,每次进入一个子节点就可以理解为一个新的以此子节点为根的DFS树,称之为递归。当访问到叶子结点时,又需要将叶子结点的信息返回并总结到该叶子节点的父亲节点,称之为回溯。

DFS大部分分为树上DFS与图上DFS,但其实两者是相通的,图上DFS可以将上下左右四个方向的遍历结果转化为该位置的四个儿子结点,此时还需要一个vis数组用来记录该儿子结点是否在别的分支出现过,尽管从一个点到另一个点会有多条路径,但如果不是要求最短路径的情况下,往往只需要记录一次即可。

dfs的常规遍历顺序

阅读全文 »

题意

给定一张二维图,图上有两个连通块,求使得两个连通块相连的最短路径。

思路

由于无法区分两个连通块,所以通过dfs对两个连通块中的元素分别赋值0/1,然后对于两个连通块中的所有点分别求曼哈顿距离-1即可。(曼哈顿距离:水平距离+竖直距离)

阅读全文 »

前言

由于前缀和和差分一个加一个减,两个在写法上差距不大而且具有一定共同点,所以放在一块进行描述。

前缀和

前缀和介绍

前缀和顾名思义,就是一段数列前面某一段连续数列的和。

他经常用于预处理区间和的信息,通过预处理前缀和,我们可以快速的得到某段连续数列的和是多少。

当我们需要求取的区间和时,我们可以用来获取,经常会有人将减号后面写成,但是我们需要保留的和,需要减去的重复部分应该是之前的部分

阅读全文 »

题意

给定,求与范围内与互质的数的个数

思路

​ 这个就是欧拉函数的定义。

首先根据唯一分解定理可得:设,其中为质数,有

,其中后面连乘的部分与 无关,那么可以直接由来获取所有,直接分解质因数即可。对于,根据同余,可以通过快速幂得到。答案要求对大质数取余,除某个数等于乘该数的余数减二次方,即就是逆元。

阅读全文 »

题意

给定n位字符串,可以对连续的几位都进进行+1/-1的操作,求变成目标串最少的操作次数

思路

这里涉及到一个概念叫做相对距离,对于从起始串到目标串的变化可以转化为0000串到某个串的变化,每一位的相对距离保持不变即可。

这样我们就只需要预处理求出0000串到所有状态的最小操作次数即可,可以通过BFS来求出并记录。

阅读全文 »

题意

给定长度为n的数列,求出连续序列和为k的倍数的序列个数。

思路

首先,对于每一段前缀和都进行对k取余。

那么根据同余定理,,如果一段前缀和如果和前面的某段前缀和的值相同,那么前面的那个前缀所缺少的几个数(除最后一个元素)的和一定是k的倍数,对于每个余数所对应的前缀和数量,用一个map记录一下即可。

最后记得再加上,因为每次前缀和所得的那几个数并不包括尾部,所以当遍历到最后一个元素时,并无法得出包括最后一个元素的符合条件的连续序列数量,而是包括最后一个前面的那个元素的符合条件的连续序列数量

阅读全文 »

题意

几间房间有各自的温度,每次操作可以对连续的几间房间+1/-1度,请问使每个房间都到达目标温度的最小操作次数

思路

​ 将目标温度减去起始温度后会得到一串数列a,目标就是求使这串数列全部为0的操作次数,由于需要实现区间加,比较容易联想到使用差分来进行操作。

​ 转化为差分数组后,每次操作就可以转化为对于某个位置+1/-1,在对某个位置-1/+1,或者不存在后者(就是位置为数列尾部+1)。

​ 这样就只需要比较到底是+1的次数多还是-1的次数多即可

阅读全文 »

题意

对一些墙壁进行作画,被作画的墙不会毁掉,只有和一面墙相邻的会被毁掉,每天可以画一面墙,每天画的墙必须和昨天画的相邻,然后会有一面墙被毁掉,每堵墙都有美观分,求使最终剩下的墙美观分能够到达的总和最高的值。

思路

首先只有和一面墙相邻的会被毁掉意思就是从两端开始毁掉,由于每天画一面墙,毁一面墙,那最终是能保留面墙,那么题目就是求长度为的连续序列和的最大值。

然后,我们就需要枚举每个起点,来比较以此为起点的连续序列和。其实循环下去每次减一个头元素,再加一个尾元素也可以。但是这边用前缀和来处理,每个连续序列和的计算公式为,需要注意的是,虽然是以为起点,但是号元素还是需要的,想要获取以为起点的连续序列和,需要减去前面的前缀和。

阅读全文 »