584 字 1 分钟

# 拓扑排序的概念 拓扑排序要解决的问题是如何给一个有向无环图的所有节点排序 在一个 DAGDAGDAG （有向无环图）中，将图中的顶点以线性方式进行排序，使得对任何顶点 uuu 到 vvv 的有向边 (u,v)(u,v)(u,v)，都有 uuu 在 vvv 前面 # Kahn 算法求拓扑排序 利用队列求解，不断把入度为 000 的点推入队列，每次从队列中取出一个，对于该点能到的所有边，减去到的点的入度，如果又到 000 了的话，则继续推入队列，直到队列空为止 C++123456789101112131415161718192021222324void solve ()...
6.7k 字 6 分钟

# KMP 算法的定义 KMPKMPKMP 算法常用于在一个文本串 SSS 内查找一个模式串 PPP 出现的位置，算法流程如下： 假设现在文本串 SSS 匹配到 iii 位置，模式串匹配到 jjj 位置： 如果 j = -1 ，或者当前字符匹配成功（ s[i] == p[j] ），都令 i++, j++ ，然后继续匹配下一个字符 如果 j != -1 ，并且当前字符匹配失败（ s[i] != p[j] ），则令 iii 不变， j = next[j] 。此操作意味着当匹配失败时，模式串 PPP 相对于文本串 SSS 向右移动了 j - next[j] 位 # next...
3k 字 3 分钟

# 题目大意 一个车间有 nnn 台设备，构成以 111 为根结点的一棵树，结点 iii 有权值 wiw_iwi​ 叶节点的权值 wiw_iwi​ 表示每单位时间将产出 wiw_iwi​ 单位的材料并送往父结点 根结点的权值 wiw_iwi​ 表示每单位时间内能打包多少单位成品 其他结点的权值 wiw_iwi​ 表示每单位时间最多能加工 wiw_iwi​ 单位的材料并送往父结点。 由于存在某些结点每单位时间收到的材料超过了当前结点的加工能力上限，现计划删除一些结点使得所有结点都能正常运行 请问删除一些结点后，根结点每单位时间内最多能打包多少单位的成品？ # 数据范围 对于...
687 字 1 分钟

# 题目大意 有 nnn 组物品和一个容量 vvv 的背包，每组物品有若干个，同一组内的物品最多只能选一个 每件物品的体积是 vi,jv_{i,j}vi,j​，价值是 wi,jw_{i,j}wi,j​，其中 iii 是组号，jjj 是组内编号 求解，能装下的最大体积是？ # 数据范围 0<N,V≤1000 < N,V \le 1000<N,V≤100 0<Si≤1000 < S_i \le 1000<Si​≤100 0<vi,j,wi,j≤1000 <...
1.3k 字 1 分钟

# 题目大意 有 nnn 种物品和一个容量是 vvv 的背包 第 iii 种物品的体积是 viv_ivi​，价值是 wiw_iwi​，有 sis_isi​ 件 问：你放进背包的最大价值是多少 # 数据范围 小范围（多重背包 III） 0<N,V≤10000 < N, V \le 10000<N,V≤1000 0<vi,wi≤10000 < v_i, w_i \le 10000<vi​,wi​≤1000 大范围（多重背包 IIIIII） 0<N≤10000 <...
1.3k 字 1 分钟

# 题目大意 有 nnn 种物品和一个容量是 vvv 的背包，每种物品都有无限件 第 iii 种物品的体积是 viv_ivi​，价值是 wiw_iwi​ 问：你放进背包的最大价值是多少 # 数据范围 0<N,V≤10000 < N, V \le 10000<N,V≤1000 0<vi,wi≤10000 < v_i, w_i \le 10000<vi​,wi​≤1000 # 思路 显然可以借鉴 010101 背包的思路， dp[i][j] 表示选到第 iii 个物品，背包容量为 jjj...
945 字 1 分钟

# 题目大意 有 nnn 件物品和一个容量是 vvv 的背包，每件物品只能使用一次 第 iii 件物品的体积是 viv_ivi​，价值是 wiw_iwi​ 问：你放进背包的最大价值是多少！ # 数据范围 0<N,V≤10000 < N, V \le 10000<N,V≤1000 0<vi,wi≤10000 < v_i, w_i \le 10000<vi​,wi​≤1000 # 思路 # 变量假设 dp[i][j] 表示前 iii 个物品中，已经用了 jjj 的背包体积时的最大价值 #...
3.1k 字 3 分钟

# B # 题目大意 给你一个长度为 nnn 的排列（包括 000 到 n−1n-1n−1 的所有整数）和一个长度为 nnn 的条状单元格 你需要在 iii 单元格内，填入 MEX(p1,p2,...,pi)MEX(p_1,p_2,...,p_i)MEX(p1​,p2​,...,pi​) MEX(p1,p2,...,pi)MEX(p_1,p_2,...,p_i)MEX(p1​,p2​,...,pi​) 代表 p1,p2,...,pip_1,p_2,...,p_ip1​,p2​,...,pi​ 中的第一个不出现的非负整数 现在给你一个最喜欢的数 xxx，问 xxx 最多出现次数是？ #...
701 字 1 分钟

# 模式分解 把一个关系模式，分解成若干个关系模式（把一张表分解成若干张表） 分解后做自然连接，在内容上是否与原来的表等价 →\to→ 分解的无损连接性 分解后做自然连接，在数据依赖（约束）上是否与原来的表等价 →\to→ 分解的保持依赖性 # 什么情况下需要分解 当关系模式不符合关系范式时，需要分解（一般是 3NF3NF3NF） 分解规则：将每一个函数依赖单独组成一个关系 # 无损连接性 找出分解的两个表（R1,R2R_1,R_2R1​,R2​）的交集 判断这个交集是否包含 R1R_1R1​ 或 R2R_2R2​...