引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路：
通过分析，可以发现：
当 nnn 和 mmm 中有一个为 111 时，只用一条线就可以，答案为 111。
当 nnn 和 mmm 中没有一个为 111 时，当 n<mn<mn<m 时，最优方案是是用 nnn 条线把每一行的所有车站连起来，再用一条线把一列连起来，就可以实现，答案为 n+1n+1n+1；同理当 n<mn<mn<m 时，答案为 m+1m+1m+1，综上 ans=min(n,m)+1ans=\min(n,m)+1ans=min(n,m)+1。
如果还是无法理解，可以看看图片。
代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigne ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路：
设第一个士兵与第 2k+12k+12k+1 个士兵配对（k≥0k \ge 0k≥0），则：
左侧：前 2k2k2k 个士兵必须形成合法分组，方式数为 CkC_kCk。
右侧：剩余 2(n−k−1)2(n-k-1)2(n−k−1) 个士兵形成合法分组，方式数为 Cn−k−1C_{n-k-1}Cn−k−1。
综上：
Cn=∑k=0n−1Ck×Cn−k−1C_n=\sum_{k=0}^{n-1} C_k \times C_{n-k-1}
Cn=k=0∑n−1Ck×Cn−k−1
可以发现其实就是卡特兰数。
代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long lo ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
题意总结：
777 个字母 W，H，Q，E，S，T，X 分别代表着 1,12,14,18,116,132,1641,\dfrac{1}{2},\dfrac{1}{4},\dfrac{1}{8},\dfrac{1}{16},\dfrac{1}{32},\dfrac{1}{64}1,21,41,81,161,321,641。
每行一个字符串，分为好几节，每节用 / 分隔，求每个字符串有几个小节字母代表的值和为 111。
思路：
我不想处理小数，可以想到去分母，同乘分母最小公倍数 646464，然后处理每个字符串，计算每小节的字母表示的数的和，如果这小节所有字母表示的数的和等于 646464 就让答案加一。
注意：多测不清空，爆零两行泪。
代码：
用 map 存字符表示值：
#include<bits/stdc++.h>usi ...
![题解：AT_arc033_2 [ARC033B] メタ構文変数](https://fastly.jsdelivr.net/npm/xyx404blogphoto@1.2.57/ATarc0332.jpg)
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路：
题目要求求两个集合中相同的元素个数除以两个集合合并在一起并去重后的元素个数。
考虑使用 set。
定义两个 set，第一个 set 存第一个集合中的元素，第二个 set 存两个集合的元素。
定义一个变量做两个集合中相同元素的计数器。
在输入时，把两个集合中的元素都放进第二个 set 里。
在输入第二个集合时，顺便判断这个元素是否在第一个集合中出现过，出现过让计数器加一。
最后输出两个集合中相同的元素个数除以两个集合合并在一起并去重后的元素个数就行了。
set 会自动去重。
代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longset<string>a,a ...
![题解：AT_abc397_c [ABC397C] Variety Split Easy](https://fastly.jsdelivr.net/npm/xyx404blogphoto@1.2.56/abc397c.jpg)
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
题意：
将数组分割成两个非空连续子数组，使得两个子数组中不同元素的数量之和最大。
思路：
定义数组 preprepre，其中 preipre_iprei 表示前 iii 个元素中不同元素的数量。
定义数组 sufsufsuf，其中 sufisuf_isufi 表示从位置 iii 到末尾的不同元素数量。
将两个数字预处理完成后，对于所有满足 1≤i<n1 \le i < n1≤i<n 的 prei+sufi+1pre_i+suf_{i+1}prei+sufi+1 中取最大值就是答案。
代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longconst ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
题意：
将数组分割成三个非空连续子数组，使得三个子数组中不同元素的数量之和最大。
思路：
线段树。
可以先把线段树的加法模版做了在来看。
定义数组 preprepre，其中 preipre_iprei 表示前 iii 个元素中不同元素的数量。
定义数组 sufsufsuf，其中 sufisuf_isufi 表示从位置 iii 到末尾的不同元素数量。
这样就可以差不多可以把这道题的弱化版，本场的 C 题写出来。
接下来继续考虑本题。
定义 mid(i,j)mid(i,j)mid(i,j) 是对于 AAA 数组中的所有满足下标 i≤k≤ji \le k \le ji≤k≤j 的 AkA_kAk 的不同元素个数。
用数学方式可以表示为 mid(i,j)=∣{Ak∣i≤k≤j}∣mid(i, j)= \left| \{ A_k \mid i \leq k ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
题意：
给定一个有向图，我们从顶点 111 出发，想要到达顶点 NNN。
有两种操作：
沿着有向边移动到下一个顶点，花费为 111。
反转所有边的方向，花费为 XXX。
我们的目标是找到到达 NNN 的最小总花费。
思路：
最短路，迪杰斯特拉。
只需要改建图就行了。
建图：
每个顶点 uuu 在原图和反转图中被分别表示为两个节点 2×u2 \times u2×u 为状态 000 原图和 2×u+12 \times u+12×u+1 为状态 111 反转图。
原图边：对于原边 uuu 到 vvv，在状态 000 中添加边 2×u2 \times u2×u 到 2×v2 \times v2×v 代价为 111。
反转边：对于原边 uuu 到 vvv，在状态 111 中添加边 2×v+12 \times v+12×v+1 到 2×u+12 \times ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
翻译：
高桥君有 2×N2 \times N2×N 个牙齿，NNN 个上排的牙齿和 NNN 个下排的牙齿。
注：以下为了方便“上牙”指的是上排的牙齿，“下牙”指的是下排的牙齿。
第 iii 个上牙的长度为 UiU_iUi，第 iii 个下牙的长度为 DiD_iDi。
有个操作，需要花费一元，选择一个长度大于 000 的牙齿，将其长度减少 111。
求使牙齿“咬合良好”的最小总费用。
牙齿“咬合良好”需要满足以下两个条件：
存在一个整数 HHH，使得对于所有 1≤i≤N1 \le i \le N1≤i≤N，满足 Ui+DiU_i + D_iUi+Di 等于 HHH。
对于所有 1≤i<N1 \le i < N1≤i<N，满足 ∣Ui−Ui+1∣≤X\left |U_i - U_{i+1} \right | \le X∣ ...
![题解：AT_abc392_c [ABC392C] Bib](https://fastly.jsdelivr.net/npm/xyx404blogphoto@1.2.54/abc392c.jpg)
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路：
对于第 iii 个人他看着的人是 PiP_iPi，而 PiP_iPi 头上戴着的帽子编号是 QPiQ_{P_i}QPi。
定义一个 ansansans 数组，其中 ansians_iansi 表示头上戴着的帽子编号为 iii 的人他看着的人头上戴着的帽子的编号。
第 iii 个人戴着的帽子编号是 QiQ_iQi，而我们又知道 PiP_iPi 头上戴着的帽子编号是 QPiQ_{P_i}QPi，所以 ansQians_{Q_i}ansQi 会等于 QPiQ_{P_i}QPi。
代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longLL N;LL ...
![题解：AT_abc392_d [ABC392D] Doubles](https://fastly.jsdelivr.net/npm/xyx404blogphoto@1.2.54/abc392d.jpg)
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路：
考虑到题目要求我们求的是出现相同数字的概率，所以我们可以使用 unordered_map 把每一个骰子中出现的数字的数量存下来。
然后进行循环枚举我们使用的两个骰子，注意到使用编号为 111 和 222 的骰子和使用编号为 222 和 111 的骰子的出现相同数字的概率其实是一样的，所以我们枚举使用骰子的时候可以通过让第二个骰子的编号 jjj 大于我们第一个骰子的编号 iii 来减少循环。
在枚举两个 unordered_map 中是否有相同的数时，也可以进行优化，我们可以枚举 unordered_map 中数字少的 unordered_map 中的数字，判断另外一个有没有相同的数字。
注意要开 long long。
浮点数用 double 就可以了。
代码：
#include<bits/stdc++.h>using namespa ...
