【题解】P10412 钟声远带斜阳
题目大意
给定一个长度为 nnn 的序列 aaa，花费不同代价进行一下若干操作：
选择其中一个元素 aia_iai（0≤i<n0 \le i \lt n0≤i<n） 增加一，花费 ppp 的代价。
选择其中一个元素 aia_iai（0≤i<n0 \le i \lt n0≤i<n） 删除，花费 qqq 的代价（序列长度不可为 000）。
选择其中两个元素 ai,aja_i,a_jai,aj（0≤i<j<n0 \le i \lt j \lt n0≤i<j<n）进行交换，花费 rrr 的代价。
最小化代价，使得 ∃k0(0≤k0<n)\exists k_0(0 \le k_0 \lt n)∃k0(0≤k0<n)，将子序列 a0∼ak0−1a_0 \sim a_{k_0 - 1}a0∼ak0−1 拼接在原序列后端，当前序列任意前缀和非负。
Solution
定义 sumsumsum 表示整个序列元素之和，不难看出，对于任意一个序列，若 sum≥0sum \ge 0sum≥0，必然至少存在一个 k0k_0k0 使 ...
【笔记/模板】Tarjan 算法与有向图的强连通分量
有向图的强连通分量
定义
对于一张有向图 G=(V,E)G = (V, E)G=(V,E)，对于两点 u,v∈Vu,v \in Vu,v∈V，都存在一条路径可以使得 uuu 达到 vvv，vvv 也可以达到 uuu，则称该两个点是互相可达的。
如果一张有向图上的任意两个节点之间可以互相可达，则称这张图是 强连通的（Strongly Connected）。
对于一张子图 H∈GH \in GH∈G，并且不存在其他的连通图 FFF 使得 H∉F∈GH \notin F \in GH∈/F∈G，则称子图 HHH 是有向图 GGG 的一个 强连通分量（Strongly Connected Component，SCC），叫做极大的连通分量。
应用
对于一个较为复杂的图论问题中，利用强连通分量的缩点技巧，将每一个强连通分量中的所有点看作一个点，最终使得图转化为 有向无环图（DAG），大大的减少了时间复杂度和解题难度。
Tarjan 算法
DFS 生成树
对于一张图的深度优先遍历，根据节点的先后遍历顺序，我们可以生成出一棵树，这棵树即为 DFS生成树，它的性质有如下几点：
深度优先遍历的第一个点 ...
【模板】图的存储与遍历
图的存储与遍历
直接存边法
做法
建立三个数组 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）
最近公共祖先（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_ ...
【题解】CF1931D Divisible Pairs
解题思路
先看到第一个条件 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 ...
【题解】CF1931C Make Equal Again
题目大意
给定一个数组 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 ...
【题解】CF1918B Minimize Inversions
题目大意
给定两个长度均为 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 序列由 ...
【题解】CF1921C Sending Messages
解题思路
很显然的贪心题，只需要判断每一个路程耗电量的大小进行选择即可，但是这道题同样可以用 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. ...
【题解】CF1921B Arranging Cats
题目大意
给定一个长度为 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 ...