2X岁，是学生です

0%

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

好久没有写博客了，回学校了也没啥时间可以摸鱼了（主要还是懒🤣）

晚上参加了东哥家的笔试，30道选择+两道编程。整体难度还好，（Ball Ball 东哥给孩子一个机会吧！看在老PLUS会员的份上）

但是第二道编程题想要记录一下，最后一分钟才调出来，刺激！🤪

题目

从CSDN上扒了张题图。

alt

思路：

第一眼看过去，这就是一道典型的完全背包求方案数的问题呀！刷刷把完全背包写了一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 110, M = 1010, mod = 1e9 + 7;
int vals[N];
LL f[N][M];//f[i][j]表示只从前i张卡片中选，恰好可以打掉BOSS的血量为j的方案数

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> vals[i];
    for(int i = 0; i <= n; ++i)
        f[i][0] = 1;//魔王0滴血，不用出牌也算一种方案
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            for(int k = 0; k <= j / vals[i]; ++k)
                f[i][j] = (f[i][j] + f[i - 1][j - k * vals[i]]) % mod;
    cout << f[n][m] << endl;
    return 0;
}

信心满满自测样例……（淦，咋对不上？尴尬）没事，可能是我完全背包太久没写哪里出了点差错，调就完事儿了。

30 Minutes Later~~

淦，这完全背包没毛病呀？到底啥情况？样例倒是为什么会是5，我手工模拟也是3（黑人问号？？？）

终于想起来再读一遍题目。

“使用的牌的种类或数量不同代表不同的方案，改变牌的顺序同样代表不同的方案”

真想扇死自己，题都没读完直接开敲，hh。

AC代码及思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 110, M = 1010, mod = 1e9 + 7;
int vals[N];
//LL f[N][M];//f[j][i]，注意是f[j][i],表示只从前j张卡片中选，恰好可以打掉BOSS的血量为i的方案数
LL f[M];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> vals[i];
    sort(vals + 1, vals + n + 1);//后来想想没有必要
    //f[j][i]此时可以理解为当BOSS的血量为i时，小明的最后一次攻击使用的是第j张牌的总方案数
    /*for(int i = 0; i <= n; ++i)
        f[i][0] = 1;//魔王0滴血，不用出牌也算一种方案
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            if(i >= vals[j])
                f[j][i] = (f[j][i] + f[j - 1][i - vals[j]]) % mod;*/
    //优化成一维的，同层转移
    f[0] = 1;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            if(i >= vals[j])
                f[i] = (f[i] + f[i - vals[j]]) % mod;
    cout << f[m] << endl;
    return 0;
}

稍微解释一下为什么要把背包体积放第一维，物品编号放第二维就可以算出考虑顺序的方案数。

原始状态表示为f[j][i]，即当BOSS的血量为 i 时，小明的最后一次攻击能恰好击杀时使用的是第 j 张牌的总方案数。此时在BOSS血量为某一确定值的前提下，需要循环遍历所有牌并判断其是否能作为此时的最后一击，这里其实就暗含了一个出牌的顺序。

优化成一维也很显然，即满足公式f[i] += f[i - vals[j]]，含义为血量为 i 时考虑顺序差异的方案总数。

发表于 更新于 分类于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

指数级别的时间复杂度，因此数据范围稍大点的就不是状态压缩 $DP$。

状态压缩 $DP$ 有着一种解题的流程模式，一般是先预处理出各状态及其转移的合法性，再利用动态规划的一般方法求解。

蒙德里安的梦想

求把 $N \times M$ 的棋盘分割成若干个 $1 \times 2$ 的的长方形，有多少种方案。

例如当 $N=2$, $M=4$ 时，共有 $5$ 种方案。当$N=2$, $M=3$ 时，共有 $3$ 种方案。

alt

数据范围

$1 ≤ N, M ≤ 11$

思路：

首先为棋盘的每一列编号，为了便于状态的表示，编号从 $0$ 开始，一直编号到 $m$，即棋盘最后一列的下一列。（是一种技巧，之后说明）

$f[i][j]$ 的 $j$ 在本题中表示：在第 $i$ 列，由第 $i - 1$ 列的横置方块伸出部分在第 $i$ 列的覆盖情况的二进制表示，其中为 $0$ 的位表示当前列的上一列在该行没有伸出的方块覆盖当前列，为 $1$ 的位表示上一列该行的横置方块有伸出到当前列。

$f[i][j]$ 表示当第 $i$ 列的覆盖情况为 $j$ 时的合法摆放方案数。

什么是非法情况？

这道题比较难理解的是非法情况。

记第 $i - 1$ 列在第 $i$ 列的覆盖情况为 $j$，第 $i - 2$ 列在第 $i - 1$ 列的覆盖情况为 $k$。

而覆盖情况 $j$ 可以看作第 $i$ 列在第 $i - 1$ 列的覆盖情况，两者是相对的，因此我们利用 $j$ 和 $k$ 对第 $i-1$ 列进行非法情况检查。

非法情况分为两种：

  1. j & k != 0：非零即意味着第 $i$ 列和 $i - 2$ 列在第 $i - 1$ 列重复覆盖，这是非法的。

  2. j | k的结果中有连续奇数个零：要明确一点，$j$ 或者 $k$ 表示的都是横置方块的摆放情况，即每一个 $j$ 或者 $k$ 都代表着一种已经确定的方块横置情况，之后的方块只能竖直摆放。因此若第 $i - 1$ 列除去了横置方块的剩余位置有连续奇数个零，就意味着无法用 $1 \times 2$ 的方块竖放填满。

还有两个特殊情况需要考虑。

  1. 开始时的状态：由于第一列不可能有来自上一列的横置方块，因此 $f[0][0] = 1$，其余 $f[0][x]$ 均初始化为零。

  2. 结果的表示：之前所说的技巧就是这里。由于最终是填满棋盘，这个状态可以表示成 $f[m][0]$，即在棋盘的最后一列的下一列上，棋盘的最后一列没有横置方块的伸出覆盖。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 12, M = 1 << N;
long long f[N][M];//有爆int可能
bool st[M];//状态预处理

int main()
{
    int n, m, cnt;
    scanf("%d%d", &n, &m);
    while(n || m)
    {
        //先预处理的意义：降低时间复杂度由11*2^11*2^11*11降到11*2^11*2^11
        for(int i = 0; i < 1 << n; ++i)
        {
            cnt = 0, st[i] = true;//统计连续的0的个数
            for(int j = 0; j < n; ++j)
            {
                if((i >> j) & 1)
                {
                    if(cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                    cnt = 0;
                }
                else ++cnt;
            }
            if(cnt & 1) st[i] = false;
        }
        memset(f, 0, sizeof(f));
        f[0][0] = 1;//i=0其实是第一列，对于第一列，只有前一列在此列伸出的方块数为0这一种放法
        for(int i = 1; i <= m; ++i)
            for(int j = 0; j < 1 << n; ++j)
                for(int k = 0; k < 1 << n; ++k)
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        printf("%lld\n", f[m][0]);
        scanf("%d%d", &n, &m);
    }
    return 0;
}

最短Hamilton路径

给定一张 $n$ 个点的带权无向图，点从 $0$ 到 $n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短 $Hamilton$ 路径。

$Hamilton$路径的定义：从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

数据范围

$1≤n≤20$

$0≤a[i,j]≤10^7$

思路：

按照最朴素、最暴力的做法，这道题应该有 $O(n!)$ 级别的时间复杂度。（那哪行啊！）

采用状态压缩 $DP$ 来优化。采用 $DP$ 来求解最值，表明并不对具体的路径顺序感兴趣，只对某一状态以及该状态从何处转移而来有兴趣。使用二进制数来表示某一节点是否已经经过，已经过置 $1$，还未经过置 $0$，$n$ 个节点只需使用 $n$ 位二进制数就可描述其经过状态。

时间复杂度从 $O(n!)$ 级别降低至 $O(n^2 \times 2^n)$。（至少还是个INT范围内的数）

$f[i][j]$ 中 $i$ 为记录各节点是否已经走过的二进制数，$j$ 表示当前所在的节点编号。

$f[i][j]$ 表示从 $0$ 走到 $j$，已经经过的节点二进制数记录为 $i$ (包括第 $j$ 个点)时的最短Hamilton路径长度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 21, M = 1 << N;
int myweight[N][N], f[M][N];

int main() 
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> myweight[i][j];
    memset(f, 0x3f, sizeof(f));
    //[i][j]表示从0走到j时，走过的点为i的二进制表示
    f[1][0] = 0;//i的状态表示到达了0点，经过的路径为只过了0这个点
    for (int i = 0; i < 1 << n; ++i)
        for (int j = 0; j < n; ++j)
            if ((i >> j) & 1)//i的状态为0到j点的路径记录，因此第j位必须为1
            {
                int temp = i - (1 << j);
                for (int k = 0; k < n; ++k)//k表示到达点j的路径上到达j点前经过的最后一点
                    if ((temp >> k) & 1)
                        f[i][j] = min(f[i][j], f[temp][k] + myweight[k][j]);
            }
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输出格式

输出一个整数，表示最大的路径数字和。

思路：

主要难点是坐标系的建立，三角形的行仍是每一行，列则是从左至右每一条斜边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 510, INF = 1e5;
int val[N][N], f[N][N];

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= i; ++j)
			scanf("%d", &val[i][j]);
	for (int i = 0; i <= n; ++i)//[0,n]
		for (int j = 0; j <= i + 1; ++j)//[0,j+1]
			f[i][j] = -INF;//边界也要设置为-INF
	f[1][1] = val[1][1];//起点特殊处理
	for(int i = 2;i <= n; ++i)//第一行已经特殊处理
		for (int j = 1; j <= i; ++j)
			f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + val[i][j];
	int res = -INF;
	for (int i = 1; i <= n; ++i)//答案需要遍历才能找到
		res = max(res, f[n][i]);
	printf("%d", res);
	return 0;
}

最长公共子序列

给定两个长度分别为 $N$ 和 $M$ 的字符串 $A$ 和 $B$，求既是 $A$ 的子序列又是 $B$ 的子序列的字符串长度最长是多少。

数据范围

$1 ≤ N ≤ 1000$

思路：

$f[i][j]$ 表示所有在第一个字符串的前 $i$ 个字符中出现且在第二个字符串前 $j$ 个字符中出现的字符串集合中的最长字符串的长度。

状态划分：两个字符串的最长公共子串是否分别含有第 $i$ 位和第 $j$ 位（$A$ 串 $i$ 位 $B$ 串 $j$ 位）。根据排列组合，可以划分为四种状态。

alt

其中 $0$ 表示不包含该位，$1$ 表示含有该位。事实上，这样划分并不严谨，划分出的状态之间存在交集。如中间两种状态，按照状态方程的含义应当是一定含有 $A[i] \, or \, B[j]$，但事实上此时的最长公共子序列可能不含有这个字符。状态划分的第一项更是直接完全包含于状态二与状态三的并集。

但是由于是求最值，因此重复并不影响结果。

转移方程

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1010;
char a[N], b[N];
int f[N][N];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	scanf("%s%s", a + 1, b + 1);
	for(int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			if (a[i] == b[j])
				f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
	printf("%d", f[n][m]);
	return 0;
}

最短编辑距离

给定两个字符串 $A$ 和 $B$，现在要将 $A$ 经过若干操作变为 $B$，可进行的操作有：

  1. 删除–将字符串A中的某个字符删除。
  2. 插入–在字符串A的某个位置插入某个字符。
  3. 替换–将字符串A中的某个字符替换为另一个字符。

现在请你求出，将A变为B至少需要进行多少次操作。

数据范围

$1≤n,m≤1000$

思路：

$f[i][j]$表示所有第一个字符串的前 $i$ 个字符编辑成第二个字符串的前 $j$ 个字符时所有的编辑方法中操作次数最少的方法的操作次数。

状态划分：根据最后一次操作的类型进行划分。

alt

以删除为例：$A$ 需要删除掉 $A[i]$ 才能与 $B$的前 $j$ 个匹配，因此此时有 $A[0 \rightarrow i-1]$ 已经与 $B[0 \rightarrow j]$ 匹配。因此有 $f[i][j] = f[i - 1][j] + 1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1010, INF = 2e3;
char a[N], b[N];
int f[N][N];

int main()
{
	int n, m;
	scanf("%d%s%d%s", &n, a + 1, &m, b + 1);
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= m; ++j)
			f[i][j] = INF;
	for (int i = 0; i <= n; ++i)
		f[i][0] = i;//长为i的a串要与长度与0的b串匹配，需要i次删除
	for (int i = 0; i <= m; ++i)
		f[0][i] = i;//长为0的a串要与长度与i的b串匹配，需要i次插入
	for(int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
			if (a[i] == b[j])
				f[i][j] = min(f[i][j], f[i - 1][j - 1]);
			else
				f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
		}
	printf("%d", f[n][m]);
	return 0;
}

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

动态规划时间复杂度计算

朴素版 $O(n^2)$

$f[i]$表示以第 $i$ 个字符为结尾的最长上升子序列长度。

转移方程：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int f[N], val[N];

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &val[i]);
	for (int i = 1; i <= n; ++i)
	{
		f[i] = 1;
		for (int j = 1; j < i; ++j)
			if (val[i] > val[j])
				f[i] = max(f[i], f[j] + 1);
	}
	int res = 0;
	for (int i = 1; i <= n; ++i)
		res = max(res, f[i]);
	printf("%d", res);
	return 0;
}

优化版 $O(nlogn)$

朴素版性能较差，仅适用于数据范围在 $1000$ 左右。

优化版并不是 $DP$，而是一种贪心算法。

数据范围

$ 1 ≤ N ≤ 100000 $,

$ −10^9 ≤ 数列中的数 ≤ 10^9 $

思路：

一个数列中的上升子序列长度在 $1, 2, …, L_{max}$ 内，任意一种长度的序列都可以在该集合中找到。

因此，可以利用以数组存储各长度子序列当前最后一个数的值；

  1. 在数列中遍历到一个值时，使用二分法，查找各长度的子序列中最后一个值小于当前值的最大值;

  2. 比较找到的子序列长度 $l_{find}$ 加 $1$ 后是否大于当前最长的上升子序列长度;

  3. 更新长度为 $l_{find}+1$ 的子序列的最后一个值为当前值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int vals[N], q[N];//q用于存储每种长度的子序列的最后一个值的大小

int main()
{
  int n, len = 0;
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i)
    scanf("%d", &vals[i]);
  q[0] = -2e9;//根据数据范围选定，同时除了空序列，任何序列的长度都大于0
  for(int i = 1; i <= n; ++i)
  {
    int l = 0, r = len;
    while(l < r)
    {
      int mid = l + r + 1 >> 1;
      if(q[mid] < vals[i]) l = mid;
      else r = mid - 1;
    }
    len = max(len, r + 1);
    q[r + 1] = vals[i];
  }
  printf("%d", len);
  return 0;
}

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

满足条件的01序列

求给定 $n$ 个 $0$ 和 $n$ 个 $1$，它们将按照某种顺序排成长度为 $2n$ 的序列，满足任意前缀中 $0$ 的个数都不少于1的个数的序列的数量，答案对 $10^9+7$ 取模。

思路：

alt

可以发现，在第一次穿过红线的点开始做关于红线的对称，发现非法解都会走到 $(n - 1, n + 1)$，显然有：

这是卡特兰数的一个重要变形式，即在所有可能选法中去除非法的选法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

const int mod = 1e9 + 7;
typedef long long ll;

int qmi(int x, int k, int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1)
			res = (ll) res * x % mod;
		x = (ll) x * x % mod;
		k >>= 1;
	}
	return res;
}

int c(int a, int b)
{
	if (a < b)
	  return 0;
	int res = 1;
	for (int i = 1, j = a; i <= b; ++i, --j)
	{
		res = (ll) res * j % mod;
		res = (ll) res * qmi(i, mod - 2, mod) % mod;
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	int res = (ll) c(2 * n, n) * qmi(n + 1, mod - 2, mod) % mod;
	cout << res << endl;
	return 0;
}

不同的二叉搜索树(LeetCode96.不同的二叉搜索树)

给定一个整数 $n$，求以 $1,…,n$ 为节点组成的二叉搜索树有多少种？

结果对 $10^9+7$ 取模后输出。

思路：

这道题没有思路，看了答案才发现这也是一道卡特兰数相关的问题。

二叉搜索树的定义：

二叉搜索树(BST,Binary Search Tree)，或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

二叉树结构上的不同，可以表现为其根节点的左右子树形式上的不同（根节点的值也不一定相同），即考虑左子树有 $0, 1, …, n - 1$ 个节点时的二叉搜索树结构数。而且只要满足二叉搜索树的性质，就能构成二叉搜索树，因此 $1$ 到 $n$ 这些数是一定可以构成 BST 的，并且不用考虑谁是根节点，以及每个节点的值是多少。

我们以 $f[i]$ 表示有从 $1$ 到 $i$ 这 $i$ 个值时能够组成的二叉搜索树的数量。同时，零个值时可以构成一颗空二叉搜索树，即 $f[0] = 1$。因此所有二叉树为：

（总共 $n$ 个点，根节点有一个点，其中一颗子树拿走 $i$ 个点，另一子树拿走剩余的 $n - 1 - i$ 个点）

该公式为卡特兰数的递推公式。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int f[N];

int main()
{
    int n;
    cin >> n;
    f[0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= i - 1; ++j)
            f[i] = (f[i] + (long long) f[j] * f[i - j - 1]) % mod;
    cout << f[n] << endl;
    return 0;
}

一道简单卡特兰数应用

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。 

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。

宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

宁宁考虑的是这样一个问题：一个操作数序列，从$1,2…$一直到 $n$，栈A的深度大于 $n$。 

现在可以进行两种操作：

1、将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）。
2、将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）。

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列。

你的程序将对给定的 $n$，计算并输出由操作数序列 $1,2,…,n$ 经过操作可能得到的输出序列的总数。

输入格式
输入文件只含一个整数 n。

输出格式
输出文件只有一行，即可能输出序列的总数目。

数据范围
$ 1≤n≤18$

思路：

很显然的卡特兰数题，数据范围很小，可以直接递推出结果。

用到组合数的递推式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

const int N = 20;
int c[2 * N][N];

int main()
{
    int n;
    cin >> n;
    c[0][0] = c[1][0] = c[1][1] = 1;
    for(int i = 2; i <= 2 * n; ++i)
    {
        c[i][0] = 1;
        for(int j = 1; j <= i; ++j)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
    cout << c[2 * n][n] - c[2 * n][n - 1] << endl;
    return 0;
}

参考资料

二叉搜索树

发表于 更新于 分类于
本文字数： 935 阅读时长 ≈ 1 分钟

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;

int qmi(int ai, int bi, int pi)
{
	long long res = 1;
	while (bi)
	{
		if (bi & 1)//位与，判断当前最低位是否为1
			res = res * ai % pi;
		ai = (long long) ai * ai % pi;
		//根据公式推到，a^k被拆分，
		//且后一个ai值为当前值的平方（bi被当作二进制数处理的原因）
		bi >>= 1;
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int ai, bi, pi;
		scanf("%d%d%d", &ai, &bi, &pi);
		printf("%d\n", qmi(ai, bi, pi));
	}
	return 0;
}

快速幂求逆元

快速幂也可以用于求解逆元。原理为费马定理：若n为质数，整数a不是n的倍数，。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;

int qmi(int ai, int bi, int pi)
{
	long long res = 1;
	while (bi)
	{
		if (bi & 1)
			res = res * ai%pi;
		bi >>= 1;
		ai = (long long)ai*ai%pi;
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int ai, pi;
		scanf("%d%d", &ai, &pi);
		int res = qmi(ai, pi - 2, pi);
		if (ai%pi)
			printf("%lld\n", res);
		else
			puts("impossible");
	}
	return 0;
}

发表于 更新于 分类于
本文字数： 904 阅读时长 ≈ 1 分钟

欧几里德算法

GCD，也叫辗转相除法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

int gcd(int ai, int bi)
{
	return bi ? gcd(bi, ai % bi) : ai;
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int ai, bi;
		scanf("%d%d", &ai, &bi);
		printf("%d\n", gcd(ai, bi));
	}
	return 0;
}

扩展欧几里德算法

扩展欧几里德算法可以用于求解逆元，利用的原理就是 $a \times x + b \times y = 1 $。

如求 的逆元:

有

即

此时就可使用扩展欧几里德算法求解，公式为 其中求出的 $x$ 就是逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;

int exgcd(int ai, int bi, int &xi, int &yi)
{
	if (!bi)
	{
		xi = 1, yi = 0;
		return ai;
	}
	int res = exgcd(bi, ai % bi, yi, xi);
	yi -= ai / bi * xi;
	return res;
}
//如何理解这里的递归和yi的更新

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int ai, bi, xi, yi;
		scanf("%d%d", &ai, &bi);
		exgcd(ai, bi, xi, yi);
		printf("%d %d\n", xi, yi);
	}
	return 0;
}

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

筛质数

线性筛 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool mystate[N];//记录是否为合数，是为true

int cntPrime(int n)
{
    int cnt = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (!mystate[i])
            primes[++cnt] = i;
        for (int j = 1; primes[j] <= n / i; ++j)
        {
            mystate[primes[j] * i] = true;//这里思路要注意，线性筛是用每个合数的最小质因数将其筛去，且每一个数只判断一次
            if (i % primes[j] == 0)//因此这个条件不成立时，说明此时的primes[j]还不是i的最小质因数，但是是primes[j]*i的最小质因数，这样保证不重复也不遗漏
                break;
        }
    }
    return cnt;
}

int main()
{
    int n;
    cin >> n;
    memset(mystate, false, sizeof(mystate));
    memset(primes, 0, sizeof(primes));
    printf("%d", cntPrime(n));
    return 0;
}

埃氏筛 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool mystate[N];//记录是否为合数，是为true

int cntPrime(int n)
{
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (!mystate[i])
        {
            primes[++cnt] = i;
            for (int j = i + i; j <= n; j += i)//2i,3i,4i,...
                mystate[j] = true;
        }
    }
    return cnt;
}

int main()
{
    int n;
    cin >> n;
    memset(mystate, false, sizeof(mystate));
    memset(primes, 0, sizeof(primes));
    printf("%d", cntPrime(n));
    return 0;
}

发表于 分类于
本文字数： 631 阅读时长 ≈ 1 分钟

每天，农夫 John 的 $N$ 头牛总是按同一序列排队。

有一天，John 决定让一些牛玩一场飞盘比赛。

他准备找一群在队列中位置连续的牛来进行比赛，但是为了避免水平悬殊，牛的身高不应该相差太大。

John 准备了 $Q$ 个可能的牛的选择和所有牛的身高。

他想知道每一组里面最高和最矮的牛的身高差别。

输入格式

第一行包含两个整数 $N,Q$。

第二至第 $N+1$ 行，第 $i$ 行是第 $i$ 头牛的身高 $h_i$；

第 $N+2$ 至第 $N+Q+1$ 行，每行两个整数 $A$ 和 $B$，表示从 $A$ 到 $B$ 的所有牛。

牛的编号从 $1$ 到 $N$。

输出格式

第一至第 $Q$ 行，每行一个整数，表示对于询问的回答（即最高和最矮的牛的身高差）。

数据范围

$1≤N≤5×10^4$ ,
$ 1 ≤ Q ≤ 1.8×10^5 $,
$1 ≤ h_i ≤ 10^6$,
$1≤A≤B≤N$

思路：

对于每一个询问都进行线性扫描的总时间复杂度是 $O(Q \times (r - l + 1)) = 5×10^4 × 1.8×10^5 = 9×10^9$，肯定是超时的。这里需要使用RMQ(Range Minimum/Maximum Query)算法优化。

RMQ 预处理

首先，使用$ dp[i][j] $ 表示从 $i$ 开始连续 $2^j$ 个数中的最小（最大）值。

$ dp[i][j] $ 又可以被拆分成两部分，分别为：$[i, i + 2^{j - 1} - 1]$ 和 $[i + 2^{j - 1}, i + 2^j - 1]$

因此有状态转移方程:

类似于区间 $DP$ ，该状态转移方程在循环时，外层应为 $j$ （长度），内层为区间起点 $i$ 。

RMQ 算法预处理的时间复杂度为 $O(nlogn)$。

RMQ 查询

查询时，根据 $dp[i][j]$ 的定义以及根据区间长度得到的 $ t = {\log_2}(r - l + 1)$ （下取整），有：

$ res_{max} = max(dp[l][t], dp[r - (1 << t) + 1][t]) $,

$ res_{min} = min(dp[l][t], dp[r - (1 << t) + 1][t]) $

分析一下，$2 \times 2^t \le r - l + 1$，因此上述公式中虽有重复覆盖的部分，但是不影响区间最值的求取，且一定在 $[l, r]$ 区间内。

RMQ 算法查询的时间复杂度为 $O(1)$。

时间复杂度

预处理 $\log_2(x)$ 的时间复杂度为 $O(n)$，RMQ 算法预处理的时间复杂度为 $O(nlogn)$，$n$ 次查询的时间复杂度为 $O(n)$，因此总时间复杂度是 $O(nlogn)$ 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 5e4 + 10, K = 16;
int h[N], maxh[N][K], minh[N][K], mylog[N];

int main()
{
    int n, q, l, r;
    scanf("%d%d", &n, &q);
    for(int i = 2; i <= n; ++i)
        mylog[i] = mylog[i / 2] + 1;
    for(int i = 1; i <= n; ++i)
        scanf("%d", &h[i]), maxh[i][0] = minh[i][0] = h[i];
    for(int j = 1; (1 << j) <= n; ++j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            maxh[i][j] = max(maxh[i][j - 1], maxh[i + (1 << (j - 1))][j - 1]);
            minh[i][j] = min(minh[i][j - 1], minh[i + (1 << (j - 1))][j - 1]);
        }
    while(q--)
    {
        scanf("%d%d", &l, &r);
        int t = mylog[r - l + 1];
        int res_max = max(maxh[l][t], maxh[r - (1 << t) + 1][t]);
        int res_min = min(minh[l][t], minh[r - (1 << t) + 1][t]);
        printf("%d\n", res_max - res_min);
    }
    return 0;
}

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

有 $N$ 个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：$N=5$ 时，如下表：

鱼塘编号 1 2 3 4 5
第1分钟能钓到的鱼的数量（1..1000） 10 14 20 16 9
每钓鱼1分钟钓鱼数的减少量（1..100) 2 4 6 5 3
当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟） 3 5 4 4

即：在第 1 个鱼塘中钓鱼第 1 分钟内可钓到 10 条鱼，第 2 分钟内只能钓到 8 条鱼，……，第 5 分钟以后再也钓不到鱼了。

从第 1 个鱼塘到第 2 个鱼塘需要 3 分钟，从第 2 个鱼塘到第 3 个鱼塘需要 5 分钟，……

给出一个截止时间 T，设计一个钓鱼方案，从第 1 个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

数据范围

$1≤N≤100$ ,
$1≤T≤1000$

思路：

首先明确一点，从某一鱼塘中每分钟能钓上的鱼数只有在到达该鱼塘后才会开始减少。

对样例进行分析可以发现，每个鱼塘每分钟能钓上鱼的数量是等差数列。

能用于钓鱼的总时间：

其中：全部时间 ，走到鱼塘 $i$ 花费的总时间。

由于每次都是从$1$号鱼塘出发，因此可以枚举每次最终到达的鱼塘编号$i$， 并求此时的最大钓鱼数。

由于时间间隔都是$1$分钟，接下来的工作就是在等差数列$1$到等差数列$i$的所有数值中，选取前$T_{钓鱼}$个值。这显然是一个多路归并问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
int f[N], d[N], t[N], spend[N];

int get(int i)
{
    return max(0, f[i] - d[i] * spend[i]);//返回当前鱼塘i的每分钟钓鱼数，该值非负
}

int check(int n, int T)
{
    int res = 0;
    memset(spend, 0, sizeof(spend));//spend数组用于记录1~i号鱼塘各自当前已经使用的时间
    while(T--)
    {
        int j = -1;
        //由于数据范围很小，因此每次直接暴力枚举，寻找所有等差数列中剩余数中的最大值
        for(int i = 1; i <= n; ++i)
            if(j == -1 || get(i) > get(j))
                j = i;
        res += get(j), ++spend[j];
    }
    return res;
}

int main()
{
    int n, T, res = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> f[i];//各鱼塘初始每分钟钓鱼数
    for(int i = 1; i <= n; ++i)
        cin >> d[i];//公差
    for(int i = 1; i < n; ++i)
    //由于总是从鱼塘1出发，因此求时间前缀和，即若要能够从第1~i个鱼塘中钓鱼，需要花费在走路上的时间
        cin >> t[i], t[i] += t[i - 1];
    cin >> T;
    for(int i = 1; i <= n; ++i)//枚举终点鱼塘
        res = max(res, check(i, max(0, T - t[i - 1])));
    cout << res << endl;
    return 0;
}