2022 保研机试复习

CS 保研机试复习记录

2022-5-2

UVA193 点染色,要求染成黑的点最多。乍一看是二分图染色,其实不然,但是\(n=100\)的时候做\(O(2^n)\)搜索还是很奇怪的。

SP4580 给出集合\(S\),求满足\(\frac{a\times b+c}d-e=f\)的六元组个数。前几天招行的比赛好像考了 meet in the middle,就简单刷了几道,这个是移项然后等号两边分别\(O(n^3)\)

leetcode1755 从数列中选若干个数,使其和最接近\(goal\)\(n\leq 40\)。把数列切两半,排序去重,然后两个指针分别从前向后和从后向前扫。

洛谷 P5691 对于方程\(\sum_{i=1}^nk_ix_i^{p_i}=0, x_i\in[1,m]\),求整数解的个数。也是\(n\)切两半,存map里找。

2022-5-4

UVA1326 给定\(n\)个大写字母组成的字符串,选择尽量多的串,使得每个大写字母都出现偶数次。二进制表示字母的奇偶个数,然后切两半map里找。

CF888E 给一个数列以及\(m\),在数列任选若干个数,使得他们的和对\(m\)取模后最大。和上面 lc 的题类似,切半双指针扫。

洛谷 P4799 给一个数列以及\(m\),在数列选子序列,使其和不超过\(m\),求方案数。切半扫存vector里,排序不去重,用upper_bound统计个数就行。

CF510B 二维图中求最长的环。简单跑图搜索,记录上一步的位置。

CF698B 每个点一条出边,求将这个图改成树的方案。主要是树根的特判比较复杂,dfs 找到环就拉到树根即可。

2022-5-5

洛谷 P1608 最短路径数量统计。主要复习下 dijkstra,这题要处理重边,路径统计就是记忆化搜索。

洛谷 P1434 二维矩阵找最长下降子串。记忆化搜索。

洛谷 P1034\(k\)个矩形覆盖平面上的\(n\)个点,要求矩形不相交,总面积最小。搜索每个点在哪个矩形当中,稍微加一点剪枝和回溯。

洛谷 P2258\(n\times m\)的矩阵中选出\(r\times c\)的子矩阵,使得相邻元素差的绝对值之和最小。搜索枚举行是否选,之后预处理行之间的差和每两列之间的差,然后 DP\(f[i][j]\)表示前\(i\)列已经选了\(j\)列,并且选了第\(i\)列的最小的和:\(f[i][j]=\min_{k=0}^{i-1}\{f[k][j-1]\}\)

CF659E 无向图变有向图,使得入度为 0 的点最少。并查集找环,找到以后将集合的根标记一下,最后没有被标记的根就是入度为 0 的点。

2022-5-6

洛谷 P3956 走棋盘,棋盘上有颜色,跨不同颜色 1 费用,无色的格子花 2 费用临时改成相同颜色,不能连走两个无色,求最小步数。BFS 记录当前步数以及无色改成啥颜色,类似 dijkstra 的做法用优先队列,每个点只搜一次。

洛谷 P3052 给出\(n\)个物品,体积为\(w[i]\),现把其分成若干组,要求每组总体积\(\leq W\),问最小分组,\(n\leq 18\)。状态为物品是否已经分好组,压缩。\(f[i]\)表示状态\(i\)的最小分组,\(g[i]\)表示最后一个分组已经用的体积。转移是\(\leq\)有点奇怪,因为\(g[i]\)也要取尽量小。

洛谷 P2704 二维地图上有一部分格子可以摆放炮兵,攻击范围是上下左右各两个格子共 8 个,要求各个炮兵不能攻击到对方,问最多能摆多少个。\(f[i][j][k]\)表示前\(i\)行,第\(i\)行的状态是\(j\),第\(i-1\)行的状态是\(k\),最多摆多少炮兵,枚举三行的状态转移即可。

2022-5-7

洛谷 P1896 类似 P2704,但是是攻击范围是周围 8 个,统计方案数。这里只需要管上面一行就行。\(f[i][j][k]\)表示前\(i\)行,摆了\(j\)个国王,第\(i\)行状态是\(k\)的方案数。

洛谷 P2622 所有灯一开始都是开的,有\(m\)个按钮,每个按钮对某一个灯有三种作用,0->1 或 1->0 或不变,问把所有灯都关的最小按按钮次数。状压 BFS,步数都是 1 所以普通队列即可。

洛谷 P2381 从原点射出的抛物线,覆盖第一象限的\(n\)个点,问最少需要多少个抛物线。原点和任意两个其他的点确定一条抛物线,预处理线还能覆盖哪些点,另外还有只经过一个点的情况。\(f[i]\)表示覆盖状态为\(i\)的点最少需要多少条线,根据预处理转移即可。

洛谷 P4059 题面略。\(f[i][j]\)表示\(a[i]\)匹配\(b[j]\)的相似程度,\(g[i][j]\)表示空格匹配\(b[j]\)的相似程度,\(h[i][j]\)表示\(a[i]\)匹配空格的相似程度,互相转移,注意初始条件的处理。

洛谷 P1833 混合背包。

2022-5-8

洛谷 P4342 有负数和乘法的能量项链。注意因为有负负得正,所以需要记录最小值,乘法的转移要分四种情况。

UVA12991 题面略。类似区间 DP,\(f[0][i]\)\(f[1][j]\)转移来,表示\([j+1,i]\)区间放 0,\(i+1\)\(j\)放 1,需要预处理很多个复杂的前缀和,之后可以\(O(1)\)转移。

2022-5-9

洛谷 P3478 给定一个\(n\)个点的树,请求出一个结点,使得以这个结点为根时,所有结点的深度之和最大,根的深度为 0。树形 DP,\(f[i]\)表示\(i\)的子树的贡献,\(g[i]\)表示除了\(i\)的子树之外其他部分的贡献,两次 DFS 转移。

2022-5-11

洛谷 P2016 树上最小点覆盖。树形 DP,\(f[i][0/1]\)表示\(i\)结点不放/放能够覆盖\(i\)的子树的最小点覆盖数量。

CF149D 配对的括号序列染色,一个括号可以染成红色、蓝色或者不染色;一对匹配的括号有且仅有一个染色,相邻两个括号颜色不能相同(但都可以不染色)。区间 DP,\(f[i][j][0-2][0-2]\)表示\([i,j]\),两端点不染/染红/染蓝的情况,DP 过程类似最长回文子序列。

2022-5-21

洛谷 P2014 树形依赖背包的模板题。\(f[u][j]\)表示以\(u\)为根的子树选了\(j\)门课的最大学分,\(f[u][j]=\max\{f[v][j-k]+f[u][k]\}\)\(v\)\(u\)的儿子,\(j\)要倒着枚举,\(f[u][1]=s[u]\)

洛谷 P1273 和上面类似,转移的时候需要减去当前的边权,其他主要是边界处理。

2022-5-22

洛谷 P3435 规定字符串\(Q\)(可以是空串)表示\(a\)的周期,当且仅当\(Q\)\(a\)的不等于\(a\)前缀且\(a\)\(Q+Q\)的前缀。求给定字符串所有前缀的最大周期长度之和。答案是每个前缀的长度减最短公共前后缀的长度,先 KMP 求\(next\),之后每次往前跳,并且更改\(next\)为最短公共前后缀。

洛谷 P1470 枚举题,\(f[i]\)表示\(1\sim i\)的前缀是否可以表示,枚举\(j\),从\(f[i-j]\)转移即可。

洛谷 P1195 最小生成树。

洛谷 P1359 单向边 Floyd。

洛谷 P5651 无向图,路径权值为边权异或和。有一个性质:“保证\(G\)中不存在简单环使得边权异或和不为 0”,因此每个简单环的异或和都为 0,因此两点之间的任何路径权值都是一样的,跑 BFS 就行。

洛谷 P1122 求树上的联通块,使得点权和最大(有负点权)。树形 DP,\(f[i]\)表示\(i\)的子树且一定选\(i\)的最大联通块,从子树转移即可,类似最大子段和。

2022-5-23

洛谷 P6599 题意略。分别考虑每个位的贡献,都为\(2^k\times \lfloor l/2\rfloor\times (l- \lfloor l/2\rfloor)\)

作者

xqmmcqs

发布于

2022-05-02

更新于

2022-06-09

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×