主播想要练习一下，故花了两个小时模拟了一下23级的C7赛特意买了个学校机房同款包浆古董慢回弹键盘A 选择题第1题KMP算法的提出者是哪几位___。A. D.E.KnuthB. J.H.MorrisC. V.R.PrattD. htunK.E.DE. sirroM.H.JF. ttarP.R.V[...]
发现发题解能加平时分，之前都没有交过，最后一次赶紧水两道题，防止我的期末挂挂~C 前缀数组题目题目描述在植物理想国中有很多种类的仙人掌（Cactus），例如「可爱仙人掌」（Cutetus），「拐弯抹角仙人掌」（Pointless Cactus）。下面将给出 $n$ （$1 \le n \le 1000$）个名字（一个名字由若干个单词组成，单词是指由空格分割的字符串），Yuki 想知道其中哪些名字是仙人掌的名字。由于 Yuki 对仙人掌并不熟悉，所以只能认为名字中有至少一个单词满足以下至少一个条件的，都是仙人掌：单词以 cac 开头（不区分大小写）单词以 tus 结尾（不区分大小写）单词含有 cactus 作为子串（不区分大小写）例如，Cattus 是「仙喵掌」，当然是仙人掌，但 Tree Tree 是「好多树」，不是仙人掌。输入描述输入包含不定的若干行（不超过 $1000$ 行），每一行一个字符串（仅包含大写字母，小写字母，空格或连字符）表示一个植物的名字。形式化的来说，大写字母是指 ASCII 码在 $[65, 90]$ 之间的字符（A-Z）；小写字母是指 ASCII 码在 $[97, 122]$ 之间的字符（a-z）；空格是 ASCII 码为 $32$ 的字符（ ）；连字符是 ASCII 码为 $45$ 的字符（-）；单词是指由空格分割的字符串。输出描述输出一个正整数，表示有多少个植物是仙人掌。[...]
我的算法资料开源仓库：https://github.com/lixu10/algorithm-template上课的英文PPT这的看不懂（中文我都不一定看的懂），用AI按章节转成了说人话版（仅保留算法核心部分）：算法PPT按章节总结.pdf自己结合学长板子、AI、自己代码，写了一套非常完整的板子，包含所有课上算法、常用算法等（与这篇文章下面内容相同）。下载：板子ver5.pdfRecommend：ACM算法模板(吉林大学).pdf算法模板.mdC STL超全汇总-2023.12.11.pdfAcwing代码总结算法选择题复习.pdf算法模板 (1).md模板.pdf算法板子 - RainelC++算法板子积累 - OnlyAR以下为我自己的代码模板：[...]
再也不想上机的时候手写堆了。万能头：#include <bits/stdc++.h>vector 变长数组动态数组，可以变长。头文件：#include <vector>初始化// 一维 vector<int> a; // <>里面写数据类型 vector<int> v(n); // 指定长度为n，初始值均为0 vector<int> v(n, 114514); // 指定长度为n、初始值都是n-1 vector<int> a{1,2,3,4,5}; // 初始化，数组长度为5 // 拷贝初始化 vector<int> a(n, 1); vector<int> b(a); // b也是长度为n、初始值为1的数组 vector<int> c = a; // 另一种拷贝初始化方法 // 二维 vector<int> v[5]; // 第一维固定长度5，第二位可变长 vector<vector<int>> v; // 二维长度均可变，可以直接push_back进去一个数组 vector<vector<int>> a(n, vector<int>(n, 0)); // 行列均长度n且初始值为0[...]
A Yuki 的连通块题目描述Yuki 有一个无向图，这个无向图有 $n$ 个点和 $m$ 条边，Yuki 希望知道这个无向图有多少个不同的连通块？两个连通块不同，当且仅当两连通块的点集不同。输入第一行包含两个正整数 $n$ 和 $m$（$1 \le n, m \le 10^6$），分别表示无向图的点数和边数。 接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示编号为 $u$ 和 $v$ 的点之间有一条无向边。输出输出一行，表示该无向图的连通块数量。输入样例6 3 1 2 2 3 4 5输出样例3[...]
做的跟shit一样，被虐爆了F wiki数星星题目背景wiki正在一条直线上数星星，她想知道，哪里是离星星最近的地方呢？题目描述有一个函数 $ f(x) $，初始为常数函数 $ f(x) = 0 $。接下来 $ Q $ 次操作：更新 1 a b：给定整数 $ a, b $，令 $ g(x) = f(x) + |x - a| + b $，然后把 $ f(x) $ 替换为 $ g(x) $。例如：若当前 $ f(x) = 0 $，执行操作更新操作 1 2 1（即 $ a=2, b=1 $），则新的函数为 $ f(x) = |x-2| + 1 $；接着再执行操作 1 3 2（即 $ a=3, b=2 $），新的函数为$ f(x) = |x-2| + 1 + |x-3| + 2 $。查询 2：输出使 $ f(x) $ 最小的整数 $ x $ 以及最小值 $ f(x) $。如果有多个使得最小的 $ x $，选择最小的那个整数。例如：当 $ f(x) = |x - 2| + 1 $ 时，$ x = 2 $ 使得 $ f(x) $ 最小为 1。已知询问时输出的值总是整数，请以整数格式输出。[...]
软院大二上的算法课真是离谱，课上PPT几乎全是英文（怀疑完全是从算法导论原版书粘贴的），也听不懂。上机考试和上课讲的内容也没有关系，被纯纯虐杀，有的算法听都没听过...第二章 算法基础2.1 插入排序基本算法：​ 当选择循环下标j时，数组的A[1, j-1]已经排好序，剩余子数组为A[j+1, n]，将j下标的元素插入到前j-1个元素之中的合适位置：查找对应位置需要从j-1到1一个一个找到第一个小于等于A[j]的元素，找过的元素都往后移一位，A[j]放在停止的位置上。而循环下一次下标为j+1。而当证明算法的正确性时，书中给出了需要证明的三条性质：初始化： 循环的第一次迭代之前，它为真；保持： 如果循环的某次迭代之前它为真，那么下次迭代之前它仍然为真；终止： 在循环终止时，不变是为我们提供了一个有用的性质，该性质有助于证明算法是正确的。[...]
A题目描述AndroidNeko 听说在计算复杂度的重要性刻进主题，想希望你以样写写一个程序来计算满足特定形式递归式的算法复杂度。具体来说，给定正整数 $a, b, k$，所求递归式为：$$ T(n) = aT\left(\frac{n}{b}\right) + O\left(n^k\right) $$根据主定理，有：$$ T(n) = \begin{cases} O\left(n^{\log_b a}\right), & \log_b a > k \\ O\left(n^k \log n\right), & \log_b a = k \\ O\left(n^k\right), & \log_b a < k \\ \end{cases} $$输入格式第一行一个正整数 $t$ $(1 \leq t \leq 2 \times 10^5)$，表示数据组数。对于每组数据，一行三个正整数 $a, b, k$ $(1 \leq a, k \leq 10^9,\, 2 \leq b \leq 10^9)$，含义同题目描述。输出格式对于每组数据，输出一行：若 $T(n)=O(n^{\log_b a})$，输出 n^{\log_ba}若 $T(n)=O(n^k \log n)$，输出 n^klog n若 $T(n)=O(n^k)$，输出 n^k[...]
线性DP：递推方程有明显的线性的顺序。考虑两个问题：如何状态表示（集合+属性）、如何状态计算（划分状态转移集合）T1：状态表示： 记录所有从起点走到(i,j)的路径中的路径数字之和的最大值。状态计算：f[i,j] = max(f[i-1][j], f[i-1][j-1]) + a[i,j]需要注意需要把f[i,j]初始化为极小值，避免算到三角形右边的元素。T2：最长上升子序列状态表示：使用一维数组，f[i]表示以第i个数结尾的上升子序列的长度的最大值。状态计算：计算f[i]，去看倒数第二个数是哪个数，共i种可能，以编号1、2、3、……、i-1结尾或原本没有数（记为0）。每个循环先看是否满足上升的条件，若满足，则这个f[i]_j = f[j]+1，最后计算一个最大的f[i]_j就得出了f[i]的值。时间复杂度计算：状态数量 × 转移的数量。此时是$n^2$。#include <iostream> #include <algorithm> using namespace std; int n; int a[N], f[N]; int main(){ scanf(“%d”, &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++){ f[i] = 1; //先全部赋值为1，只有a[i]一个数 for(int j = 1; j < i; j++) if (a[j] < a[i]) 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\n", res); return 0; }如何保存最长序列？创建一个数组g[i]，存储每个转移是怎么转移过来的（记录上一个状态的id，也就是找f[i,j]最大值时找到的位置）。[...]
本章主要介绍动态规划的常用思路，并介绍了背包问题里面的01背包、多重背包的解题思路和代码01背包01背包问题为：给定背包总体积，给N个物品，每个物品有一个体积和重量，只能用一次或不用，问最大重量是多少？下面是思路，定义函数f(i,j)代表：仅包含前i个物品且总体积小于等于j的背包的最大价值是多少，故最终需要的结果是f(N,V)。初始时把所有值都设为0，且i或j等于0的本身值就为0。对于一个新的状态f(i,j)，可能的值有下面两种可能，如果包含i，则答案为f(i-1，j-vi) + wi；如果不包含i，则为f(i-1,j)。这两个值取最大值就可以算出f(i,j)。代码：#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N][N]; int main(){ cin >> n >> m; for(int i=1; i <= n; i++) cin >> v[i] >> w[i]; for(int i=1; i <= n; i++)｛ for(int j = 1; j <= m; j++){ f[i][j] = f[i-1][j]; if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]); } ｝ cout << f[n][m] << endl; }[...]