引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
题意简述：
多组数据。
每组数据给出两个字符串（源字符串和目标字符串），输出所有通过栈操作将源单词转为目标单词的操作字符串（i 表示入栈，o 表示出栈）。
操作字符串按字典序输出。
思路：
使用 DFS 算法，暴力模拟出栈入栈操作，为了保证按字典序从小到大输出，应该优先模拟入栈操作。因为入栈用字母 i 表示，出栈用字母 o 表示，很明显 i 的字典序比 o 小。
特别注意：本题不允许行末多余空格。
代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longstring st,en;stack<char>sta;int lenen;void dfs(int s, ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
前言：
本题数据范围不大，使用 Floyd 也可通过，但本人练习迪杰斯特拉，所以写的是迪杰斯特拉建反图的题解。
题意：
有 nnn 个点，求有多少个点到 eee 点的最小花费小于等于 ttt。
有多组数据。
思路：
可以发现起点有很多个，但是终点只有一个，我们可以考虑建反图，把终点看做反图起点，然后跑迪杰斯特拉得出终点到每个点的最小花费，然后把花费小于等于 ttt 的点的个数加起来就好了。
输出格式注意。
UVA 的输出格式是谜，本题输出要求每次输出答案后换行，如果这不是最后一组数据，则需要再换一次行；但是如果是最后一组数据则只需要换一次行。
代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsi ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
题意：
输入 nnn 行，每行一个分数，格式为 p/qp / qp/q（数字与字符中间有空格），你需要将分数简化到最简形式并按格式输出。
其中 1≤p,q≤10301\le p,q \le 10^{30}1≤p,q≤1030。
思路：
我们知道，一个分数的最简形式可以通过将分子和分母同时除以它们的最大公因数来获得。
那么先不考虑数据范围，我们可以得到一个简单的代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longint n;LL p,q;int main(){ cin>>n; char k; while(n--){ cin>>p ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404
发现题解区的线段树题解都是建 262626 棵线段树的方法，来一个不建 262626 棵线段树的线段树题解。本题思路其实来源于上课老师讲了这题，并且用的是本题解的方法。
思路：
线段树。
本题除了操作三以外是模版，本题解主要讲操作三，没学过线段树出门右转线段树模版。
我们知道线段树把区间全部修改成同一个值是很简单的，但是本题操作三是要求排序，很可能是修改成不同的值，怎么办呢？我们可以想到既然是要求排序，那么排序后的值是不是连续的，既然是连续的，那是不是可以把它转换为一个普通的区间修改。
考虑把要排序的范围里的所有字母的数量求出来，然后按顺序枚举每个字母，确定排序后被排到了哪个范围，然后正常区间修改就好了。
如何确定被排序后在哪个范围内？首先设现在的起点为 ststst，有 numnumnum 个这个字母，那么修改的这个区间大小也是 numnumnum，但 ...
引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
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 ...
