一个简单的整数问题

题目

第一类指令形如 “C-l-r-d”，表示把数列中第 $l-r$ 个数都加 $d$。

第二类指令形如 “Q-X”，表示询问数列中第 $x$ 个数的值。

边带权

银河英雄传说

有 $T$ 条指令，每条指令格式为以下两种之一：

1. $M-i-j$，表示让第 $i$ 号战舰所在列的全部战舰保持原有顺序，接在第 $j$ 号战舰所在列的尾部。

题目

给你两个单词 $a$ 和 $b$，请你计算出将 $a$ 转换成 $b$ 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

1. 插入一个字符

原理

紫色部分为所求区域，黄色区域为当前覆盖的区域。

$d[x1][y1] += w$ 表示将 $[x1, y1]$ 右下部分全部加上增量 $w$。

RMQ（Range Minimum/Maximum Query），区间最值查询问题，是指：对于长度为 $n$ 的数列A，回答若干次询问 $RMQ(i,j)$，返回数列A中下标在区间 $[i,j]$ 中的最小/大值。

这里介绍Tarjan的Sparse-Table算法，预处理时间为 $O(nlogn)$，但查询只需要 $O(1)$，并且常数很小，算法也很容易写出。

1）预处理：

　设 $A[i]$ 是要求区间最值的数列，$d[i, j]$ 表示从第i个数起连续 $2^j$ 个数中的最小值。(DP的状态)

题目

给定一个无向、连通的树。树中有 $N$ 个标记为 $0…N-1$ 的节点以及 $N-1$ 条边 。

第 $i$ 条边连接节点 $edges[i][0]$ 和 $edges[i][1]$ 。

返回一个表示节点 $i$ 与其他所有节点距离之和的列表 $res$。

题目

最少修改几个数，使得数列满足 $a[i + 1] - a[i] = i$。$(n \in [1, 1e5], a[i] \in [-1e9, 1e9])$

Solution

先构造一个长度为 $n$ 满足题意的初始数列，然后将所给的数减去对应的初始构造的数，差值出现的次数最多的就是最长的满足题意的序列，要修改的就是剩余的那些数。

题目

从给定数列中能选出组成的最长等差数列长度为多少？$(n \in [1, 5000], a[i] \in [1, 1e9])$

Solution

$dp[i][j]$ 表示 $a[i]$ 为等差数列最后一个数，$a[j]$ 为倒数第二个数。

题意

最多可以把数组分成几个部分，使得每部分中位数都大于等于$m$。$(n,m,a[i] \in [1,5000])$

Solution

思维题，可以发现答案就是大于等于 $m$ 的个数减去小于 $m$ 的个数。

A. ABB

题意

在给定的字符串后面最少添加多少个字符可以让整个字符串变成一个回文字符串$(n \in [1, 4e5])$。

Solution