Thy's Blog

图的存储与遍历 直接存边法 做法 建立三个数组 u[N]，v[N]，w[N]，对于每一次读入的起点，出点和权值存储即可。 初始化 12struct Edge { int u, v, w; };vector<Edge> graph; 存储 1234void add(int a, int b, int c){ graph.push_back({a, b, c});} 遍历 123456789void dfs(int ver){ if (vis[ver]) return; vis[ver] = true; for (auto t : graph) if (t.u == ver) dfs(t.v);} 复杂度 查询两点之间是否连通：O(m)O(m)O(m)。 遍历一个点所有出边：O(m)O(m)O(m)。 遍历整张图：O(n×m)O(n \times m)O(n×m)​。 适用于最小生成树 Kruskal 算法。 邻接矩阵 做法 ...

最近公共祖先（LCA） 定义 最近公共祖先（Lowest Common Ancestor）简称 LCA。对于一个树上的两个节点的最近公共祖先，是这两个点中的公共祖先里面离根最远的一个。性质可见 OI Wiki。 向上标记法 过程 在两点中取得深度较大的一个点，让它不停的向上跳，同时标记所经过的每一个点，直到根节点，接着让另一个点不断向上跳，跳到的第一个被标记的点就是这两个点的 LCA。 时间复杂度 预处理树的深度的时间复杂度为 O(n)O(n)O(n)，单次查询的时间复杂度最坏情况下为 O(n)O(n)O(n)。 倍增算法 过程 我们可以定义一个数组 prei,kpre_{i, k}prei,k​ 表示编号为 iii 的点向上跳 2k2^k2k 次所到达的点。不难看出 prei,0pre_{i, 0}prei,0​ 表示的是节点 iii 的父亲。对于任意的 k≥1k \ge 1k≥1，prei,kpre_{i, k}prei,k​ 都相当于连续上跳两次 2k−12^{k - 1}2k−1，满足以下的递推式： prei,k=preprei,k−1,k−1pre_{i, k} = pre_ ...

解题思路 先看到第一个条件 ai+aj≡0 (mod x)a_i + a_j \equiv 0\ ({\rm mod}\ x)ai​+aj​≡0 (mod x)，可以推出如下性质： ai mod x+aj mod x≡0 (mod x)a_i \ {\rm mod} \ x + a_j \ {\rm mod} \ x \equiv 0 \ ({\rm mod} \ x) ai​ mod x+aj​ mod x≡0 (mod x) 这样我们就可以在范围为 0∼x−10 \sim x - 10∼x−1 中查找满足条件的值，及对于每一个 aia_iai​，符合条件的 aja_jaj​ 为 (x−(ai mod x)) mod x(x - (a_i \ \rm mod \ x)) \ \rm mod \ x (x−(ai​ mod x)) mod x 而对于条件 ai−aj≡0 (mod y)a_i - a_j \equiv 0\ ({\rm mod}\ y)ai​−aj​≡0 (mod y)，只需要让 aia_iai​ 和 aja_jaj​ 同余即可。即： ai≡aj (mod y)a_i ...

题目大意 给定一个数组 a。进行至多一次操作，使得 a 数组中所有元素相同。如果代价为改变元素数量，求最小代价。 思路 非常简单的贪心，对于每次修改的区间 ai∼aja_i \sim a_jai​∼aj​，可以分为以下三种情况： 如果 a1≠ana_1 \neq a_na1​=an​，那么要修改的区间一定包括这两个点之一，我们只需要选择连续区间长度最长的即可。 如果 a1=ana_1 = a_na1​=an​，那么我们只要修改除了两端连续区间的所有点。 单词询问时间复杂度为 O(n)O(n)O(n)。 AC Code 1234567891011121314151617181920212223void solve(){ int res1 = 1, res2 = 1; cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; for (int i = 2; i <= n; i ++) { if (a[i] = ...

栈 STL模板 STL 中的 stack 容器提供了一众成员函数以供调用，常见的包括但不限于如下： 创建一个栈： stack<int> stk; 修改元素： stk.push(x); 将传入的参数插入到栈顶。 stk.pop(); 将栈顶的元素弹出。 查询： stk.top(); 返回栈顶的元素。 stk.empty(); 返回栈是否为空。 stk.size(); 返回栈中元素的数量。 123456789101112// 新建两个栈 st1 和 st2std::stack<int> st1, st2;// 为 st1 装入 1st1.push(1);// 将 st1 赋值给 st2st2 = st1;// 输出 st2 的栈顶元素cout << st2.top() << endl;// 输出: 1 数组模拟 通过两个变量 stk[N] 和 top 分别模拟栈的存储和栈顶下标，从而达到实现的目的。 创建一个栈： int stk[N], top; 修改元素： stk[++ top] = x; 将传入的参数插入到栈顶。 top ...

题目大意 给定两个长度均为 nnn 的序列 A,BA,BA,B。你可以进行任意次如下操作： 选择两个正整数 i,j∈[1,n]i,j \in [1,n]i,j∈[1,n]，交换 Ai,AjA_i,A_jAi​,Aj​ ，再交换 Bi,BjB_i,B_jBi​,Bj​。 请最小化两个序列中逆序对个数之和。 解题思路 贪心方式： 先将 AAA 序列由小到大排序，将 BBB 以对应的下标重新排序，此时 AAA 和 BBB 的逆序对之和最小。 证明： 对于任意的两对元素 aia_iai​ 和 aja_jaj​，bib_ibi​ 和 bjb_jbj​，无论如何交换，他们之间对应的数永远是固定的，不难看出，每对数对于逆序对的贡献只有 000 或 111 两种，则交换两对数对于逆序对的影响有三种： 从贡献为 000 到贡献为 222。 从贡献为 222 到贡献为 000。 不变，贡献均为 111。 通俗来说，只要让每对下标 iii 和 jjj 中最多只有 111 个贡献，那么任何一对数的贡献都不会多于交换后的贡献。 那么应该如何做到呢，贪心的核心就在于排序，让 AAA 序列由 ...

解题思路 很显然的贪心题，只需要判断每一个路程耗电量的大小进行选择即可，但是这道题同样可以用 DP 做（其实思路是一样的）。 我们定义一个数组 dpdpdp 表示到第 wiw_iwi​ 时候所耗费的最小电量，由于 dpidp_idpi​ 只可以通过 dpi−1dp_{i - 1}dpi−1​ 转移而来，并且分为两种情况：一直打开或者先关机后打开。可以得到： dpi=min⁡(dpi−1+(wi−wi−1)×a,dpi−1+b)dp_i = \min(dp_i - 1 + (w_i - w_{i - 1}) \times a, dp_{i - 1} + b) dpi​=min(dpi​−1+(wi​−wi−1​)×a,dpi−1​+b) 这时候便可以愉快的写代码了。 AC Code 1234567891011121314151617181920212223242526272829303132333435363738394041// Problem: C. Sending Messages// Contest: Codeforces - Codeforces Round 920 (Div. ...

题目大意 给定一个长度为 nnn 的 010101 序列，一共三种操作： 取一只新猫并将其放入盒子中（对于 iii 中的 bi=0b_i = 0bi​=0，指定 bi=1b_i = 1bi​=1）。 从盒子中取出一只猫，让它退休（对于 iii 中的 bi=1b_i = 1bi​=1，指定 bi=0b_i = 0bi​=0）。 将一只猫从一个盒子移到另一个盒子（对于 i,ji,ji,j 中的 bi=1,bj=0b_i = 1,b_j = 0bi​=1,bj​=0，指定 bi=0,nj=1b_i = 0,n_j = 1bi​=0,nj​=1）。 要求用最小的代价将该系列转换为指定序列。 解题思路 十分明显的贪心题，既然每一种操作都是等价的，我们就要让第一种操作和第二种操作的数量尽量减少，所以我们要让第三种情况尽可能多。不难想出以这种方式的话，第一种和第三种操作之和即为两个序列中 111 的个数之差，剩下需要改变的数量即为第三种操作。 AC Code 123456789101112131415161718192021222324252627282930313233343536 ...

题目大意 给定一个序列 a1,a2,…,ana_1, a_2,\ldots, a_na1​,a2​,…,an​，首先 A 先选择至多 kkk 个数删除，然后 B 在剩下的数中选择至多 xxx 个数乘上 −1-1−1，加上剩余的数后，A 想要和尽可能大，B 想要和尽可能小。若两者都通过最佳决策，求结果为多少。 解题思路 不难看出这是一道贪心题，数组中较大的数对结果的影响更大，因此我们可以进行从大到小的排序。但是不可以想当然让两者都选择当前序列中最大的数进行操作（样例中有反例）。 仔细分析样例后不难看出，A 选择的个数不大相同，但是 B 一定是尽可能选择完最大的，这样子最后的结果才会最小化。 到这里思路就很显然了，遍历枚举一遍 A 选择的个数，把每一个结果取一个 max⁡\maxmax 即可。 你说循环求和会超时？用前缀和优化即可。 单次询问时间复杂度 O(nlog⁡n)O(n \log n)O(nlogn)。 公式详推 定义 prei=a1+a2+a3+…+aipre_i = a_1 + a_2 + a_3 + \ldots + a_iprei​=a1​+a2​+a3​+…+ai​，得出 ...

A* 算法 定义 A* 搜索算法（A*search algorithm\text{A*search algorithm}A*search algorithm）是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历（英文：Graph traversal\text{Graph traversal}Graph traversal）和最佳优先搜索算法（英文：Best-first search\text{Best-first search}Best-first search），亦是 BFS 的优化，用到了启发式搜索的思维。 启发式搜索（英文：heuristic search\text{heuristic search}heuristic search）是一种在普通搜索算法的基础上引入了启发式函数的搜索算法。 启发式函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。 过程 确定了起点 ststst 和终点 ededed，对于每个点 xxx，计算出从 ststst 开始的距离函数 ...