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)\)。
2022-6-25
洛谷 P6686 \(n\)个木棍，求能构成等腰三角形的方案数。排序，扫一遍，枚举两个相同的木棍统计答案。等边三角形单独统计。
2022-6-28
POJ1860 \(n\)种货币，\(m\)个兑换点，兑换有汇率和手续费，问从一种货币兑一圈，能否变多。\(n\)个点\(m\)条边，SPFA 找环。
POJ3259 图上有正权边和负权边，问能否找到负权环。SPFA 找。
POJ1062
一个物品可以由另一个物品+一些钱买（多种选择），也可以直接买。问 1
号物品最少花多少钱买。建边，边权为加的钱的数量，跑最短路的dis[u]加上u物品的价值就是一种可行解。
POJ2253 二维平面从 1
号点到 2
号点，路径的权值为经过的最大边权，问所有可行的路径中最小的权值。SPFA
的转移把加改成max就行。
POJ1125 选择一个点到其他所有点的最大距离最小。Floyd。
POJ1789 给定\(N\)个字符串，某个字符串转为另一个字符串的花费为他们每一位不相同的字符数。求最小花费\(Q\)。求出每两个字符串的距离，用 Prim 跑最小生成树。
POJ3026 二维迷宫的最小生成树，先用 BFS 暴力跑两两距离，然后 Prim。
POJ1094 对于\(n\)个变量，给出\(m\)个小于关系，依次添加每个关系，问经过多少个关系后可以得出这些变量的线序关系，或者发生矛盾。添加关系的同时拓扑排序。
POJ2388 排序水题。
POJ2299 归并排序求逆序对，\(a_i>a_j\)的时候\(a_i\sim a_{mid}\)都大于\(a_j\)。
POJ3253 欧拉图，但是点的名字是字符串，需要用 Trie 统计。
2022-7-1
洛谷 P1993 差分约束模版题。建图 SPFA 找负环。注意要加\(x_i>=0\)的限制。
POJ1201 \([a_i,b_i]\)中至少选\(c_i\)个数。差分约束的\(x_i\)表示前\(i\)个里面选几个，除了题目的限制条件还要加上\(0\leq x_i-x_{i-1}\leq 1\)。
POJ2983 和前面的题差不多。
2022-7-2
POJ2828 每次向队伍的指定位置插入一个值，问最后队伍长啥样。逆向思维，设一个数组\(a[i]=1\)表示这个位置有人，然后逆推回去，查找的时候就找前缀和大于一个值的位置，用线段树维护。
POJ2528 刷墙，每次刷一个区间，问最后能看到多少颜色。线段树，用标记维护一下刷墙，统计的时候在树上一直往下找，直到刚好一个标记指示这个区间被覆盖了，然后暴力统计。
POJ2777 同上一道题。
洛谷 P1706
next_permutation。
洛谷 P4305
set。
2022-7-9
2022 保研机试复习