研究生机试备考练习(2)- 落谷

TODO 还没学明白 TEX 公式格式导出到博客时还要更改

[mathjax]

目录 展开

分治专题

1 快速幂 AC

将指数变成二进制数字,分别求每个 1 的结果

看了大佬题解发现,自己很多空间都是多余的。最后只要一个计数的答案,因此中间结果并不需要记录下来:

2 幂次方 AC

分治,递归,主要是括号格式问题

对于这道题,一开始的几个不需要括号的我单独列出来了,而大佬救是不同凡响,一句话解决

大佬题解

3 逆序对

线段树 # TODO

入门 详解

· 在数组表示🌲的时候,通常左孩子 2*v 在代码中写成 v<<1;右孩子 2*v+1 写成 v<<1|1

4 画图

杨辉三角是真的秀。 常规方法:建一个 1024 * 2048 的 char 矩阵,将图腾先倒置处理,最后倒序输出。

递归专题

1 台阶问题 AC

# TEX 最原始的思路是 $(a_n = a_{n-1} + … + a_{n-k})$ 代码如下

大佬的高级方法:

  1. 高级递归 O( n ) : ( a_n = 2 * a_{n-1} – a_{i-k-1} )
  2. 矩阵乘法 O( n * logk ):设 n = 4,

$$\begin{matrix} let \quad A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{bmatrix} &
B = \begin{bmatrix} a_n \\ a_{n-1} \\ a_{n-2} \\ a_{n-3} \end {bmatrix}\end{matrix}$$

那么

$$\begin{matrix} B &* &A &= &\begin{bmatrix} a_{n+1} \\ a_{n} \\ a_{n-1} \\ a_{n-2} \end {bmatrix} \end{matrix}$$

所以 $( a_n = (B * A^{n-k})[1] )$ ,此处就可以使用快速幂的方法

  1. 树状数组 O( n * logk ):树状数组可以解决的问题都可以用线段树解决,但是树状数组的系数要少很多

2 数的划分 AC

这个题做的太奇妙了,我都还没弄懂具体细节,写了个 dfs,题目样例对了,交上去竟然一次 AC

看到有人用 #include <bits/stdc++.h>,意思是包含所有的 C++ 头文件,百炼 OJ 亲测可用!然鹅本地 XCode 的 GCC 竟然不行==

3 传球游戏 AC

太爽了,又是一次 AC

我的想法就是模拟一次次传播,看到一位大佬和我方法差不多,但是代码风格很新奇:

4 电梯 AC

DFS,有个小错找了好久。记得一定要回溯!不然本条路线的 vis 会被其它路线影响

5 数字三角形 AC

这道题就是 POJ 2760,也是《引导》第十章第一题,当时做太难了,于是放弃了这本书,开始刷落谷的递归动态规划,没想到现在竟然秒杀。之前其实是粗心的错误,结点的父节点并不是 <<1,这不是二叉树!!

然而大佬就厉害了:用一维数组做,妙哉!

首先是边读边做,第一层循环 i 从 n 到 1,第二层循环 j 从 i 到 n(为了每次都能取到上次的值),每次读入一个变量 p,

状态转移方程:a[j] = max{a[j],a[j+1]}+pa[j]表示走到第 i 层第 j 个时的最大值)。最后输出 a 数组的最大值即可。

下面我来用测试数据模拟一下 (注意:要开1002的数组,不然会越界):

代码(c/c++):

一些其他的没啥用的概念:

  • register 关键字:请求编译器尽可能的将变量存在 CPU 内部寄存器中,而不是通过内存寻址访问,以提高效率。
  • inline用法

6 数字分段 TODO

7 丢瓶盖 TODO

这两题都是二分法

8 过河卒 AC

用DFS超时

递推 AC

9 出栈序列 AC

由于x是最后一个出栈的,所以可以将已经出栈的数分成两部分

比x小

比x大

比x小的数有x-1个,所以这些数的全部出栈可能为f[x-1]

比x大的数有n-x个,所以这些数的全部出栈可能为f[n-x]

这两部分互相影响,所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]

另外,由于x有n个取值,所以

ans = f[0]*f[n-1] + f[1]*f[n-2] + … + f[n-1]*f[0];

这,就是传说中的卡特兰数

10 数的计算 AC

我的方法过于暴力,但是也能过

大佬的 DP 方法:

11 蜜蜂采蜜 AC

看到范围 1000,用高精!

12 铺瓷砖 AC

这种题考数学,写出前几项,找规律

线性数据结构

1 报数淘汰 AC

非常简单的数组模拟

2 最大子段和 AC

其中,第一次写的时候遗漏了最大和为负的情况,例如数据“1 -1”答案就不对,于是分类进行讨论

而大佬的方法就厉害了,先判断大于零,再加当前的数字,就能统一算法了!!

3 括号匹配 AC

送分题

4 链表优化 40 TLE TODO

我直接用的 stl 里面的 vector,我想不到有什么优化的方法。找的过程如果用 hashtable,可以缩短到 O(1) 时间找到,但是在插入的时候,hashtable 就要花费 O(n) 的时间来修改,我现在这样是花费多个 O(logn),改 hash 难道不是得不偿失吗?

5 后缀表达式 AC

一开始担心除法,用的 float,67分,改成 long long,AC

6 水list AC

7 map AC

hash 空间不够,改成 map

8 模拟栈 AC

🌲

1 FBI 树 AC

简单的二叉树概念题,递归建树,后序遍历

但是看了大佬题解,发现自己的想法有多处冗余:

  1. 建树传参时,无需每次都新建子串。只需要每次规定子串的起始位置,随机访问即可;
  2. 判断 FBI 时,if (exist1 == 0 && exist0 != 0) 直接写为 if (exist0) 就够了(本来前半段也是冗余的)
  3. 建树和后序遍历可以在同一个递归中完成,即在当前函数里,先遍历建树,再打印 root->value;也可以是在后序遍历的过程中加一些操作。

参考代码如下两种:

另外有个小技巧:

在输入长串的时候,写 A+1 就能从 A[1] 开始输入了: scanf("%s", A+1);; 此时若想测长度,则需要用 strlen(A+1)

本题还有一个很巧的想法:

  1. 直接将 0101 字符串转换为 BIBI 字符串,0->b,1->i
  2. 倒着建树:一开始字符串为叶节点,父节点的 FBI 可以根据两个孩子直接决定(妙),这样每一层一个字符串,直接合并,就是完全二叉树的层序遍历
  3. 后序遍历,按照下标访问完全二叉树的元素即可
  4. 以上想法其实就是线段树的想法 = =

☆ 很多🌲的题目根本不需要事实上把🌲建出来!

2 中序 + 后序 求先序 AC

基础送分题

但是为什么我的代码就要 40 行,大佬的代码只要 20 行呢?

先附上大佬的代码:

对比发现有如下原因:

  1. 只需要一轮递归:在前序遍历的基础上更改即可
  2. 根本不需要真正建树,只需要递归输出 root 即可
  3. 变量和函数名,在能表示意义的前提下,越短越好

3 新二叉树 AC

送分题,记住二叉树模板,按照规则建树即可

但是实际上,仍然,“很多🌲的题目根本不需要事实上把🌲建出来”:

或者树,直接用 n*3 的二维数组来存储:

而这个方法可以有改进:

先补充一下 map:

  1. map第一个好处是作为一个数组,可以开很大!比如:map<int,int>x;,可以把x数组当成普通数组用,不过要注意一点:定义了x数组后,就不能使用c++的数组函数,比如 memset
  2. map第二个好处下标不一定是一个整数,可以甚至可以是一个字符串!map<下标类型,数值类型>; 比如:map<string,char>a; string st="123"; a[st]='1';
  3. map不仅可以开一维数组,还可以开二维数组。比如:map<int,map<int,int>;注意这里是一定要有空格的,否则会编译错误

于是,此题可以用 map + 并查集解决(就不用了 O(n) 寻找了):

4 对称二叉树 52

思路有错,懒得继续改了

4 先序+中序 求后续 AC

其实也是不用建树的

背包问题

背包九讲

模板

  1. 01 背包:n 件物品,背包容量 V,第 i 件物品费用 w[i],价值 v[i]​for (int i = 1; i <= n; i++) ​for (int j = V; j >= w[i]; j--) ​ f[j] = max(f[j], f[j - w[i]] + v[i]); 初始化:
    • 恰好装满背包:f[0] = 0;f[1] = ... = f[V] = -∞;
    • 无需恰好装满:f[0] = f[1] = ... = f[V] = 0;
  2. 完全背包:n 种物品,每种无限个,背包容量 V,第 i 件物品费用 w[i],价值 v[i]
    • 转换为 01 背包:第 i 种物品拆成费用为 w[i]∗2^k、价值为 v[i]∗2^k 的若干件物品,即每种物品拆成 log(V/w[i]) 件物品
    • O(VN) 的算法:for (int i = 1; i <= n; i++) for (int j = w[i]; j <= V; j++) f[j] = max(f[j], f[j - w[i]] + v[i]);
  3. 多重背包问题:有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 p[i] 件可用,每件费用是 w[i],价值是 v[i]转化为 01 背包问题for (int i = 1; i <= n; i++) { int num = min(p[i], V / w[i]); for (int k = 1; num > 0; k <<= 1) { if (k > num) k = num; num -= k; for (int j = V; j >= w[i] * k; j--) f[j] = max(f[j], f[j - w[i] * k] + v[i] * k); } }
  4. 混合背包问题:综合起来p[i]:每个物品的件数,0代表无穷个 for (int i = 1; i <= n; i++) if (p[i] == 0) for (int j = w[i]; j <= V; j++) f[j] = max(f[j], f[j - w[i]] + v[i]); else for (int k = 1; k <= p[i]; k++) for (int j = V; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]);
  5. 二维背包问题:for (int i = 1; i <= n; i++) for (int j = V; j >= w[i]; j--) for (int k = T; k >= g[i]; k--) f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);
  6. 分组背包问题:有N件物品和一个容量为V的背包。第i件物品的费用是w[i],价值是v[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。for (所有的组k) for (int j = V; j >= 0; j--) for (所有属于组k的i) f[j] = max{f[j], f[j - w[i]] + v[i]}

1 01背包 AC

2 小A点菜 AC

见题解: https://www.luogu.com.cn/blog/user23325/solution-p1164

贪心

1 合并果子 AC

用优先级队列,当下最小的两个

2 数列分段Section I AC

3 混和牛奶 AC

4 排队接水 AC

总时间要用 long long,相等时按序号排序

还有一个好方法,不需优先队列或结构体排序:

因为 n <= 1000,所以给每个 ti 都 * 1001,在加上当前序号,可以保证排序的时候序号不干扰排序,又可以方便输出序号(只需 mod 1001 输出序号,/1001 输出时间)

5 纪念品分组 AC

6 线段覆盖 AC

每个线段按结束点从小到大排序,按照这个顺序贪心放置即可

7 移动纸牌 AC

第一堆只能从第二堆索取或者给予,满足第一堆后,就可以删去这一堆,以此类推,删去所有堆

8 高精度 AC

高精度直接用 python!同时注意 // 的使用

9 水题 AC

10 水题 AC

11 铺设道路 AC

并查集

1 联通

并查集 + Kruskal:按照时间从小到大排序,每修一条路,如果这条路的两端本身 father 不同(即不连通),则联通的区域数 -1,当联通区域数 == 1 时,则成功

2 种类并查集 100

种类并查集,两种,开二倍数组

初始化:

关键步骤:

同时,此题的路径压缩也是非常之妙

3 种类并查集 AC

同上,这里的写法终于让我明白了:

  1. 由于有压缩路径,所以 fa[n] 和 findfa(n) 是等价的
  2. 谁是谁的爸爸都可以,因此本题解这样写也是可以滴,以后就以这个为准:

4 种类并查集 AC

三类,就开三倍的数组并查集:

捕食的关系这样维护:

前面如果用了 find(),那么后面可以直接用 f[]