引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 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∣ ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 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 ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 思路： 考虑到题目要求我们求的是出现相同数字的概率，所以我们可以使用 unordered_map 把每一个骰子中出现的数字的数量存下来。 然后进行循环枚举我们使用的两个骰子，注意到使用编号为 111 和 222 的骰子和使用编号为 222 和 111 的骰子的出现相同数字的概率其实是一样的，所以我们枚举使用骰子的时候可以通过让第二个骰子的编号 jjj 大于我们第一个骰子的编号 iii 来减少循环。 在枚举两个 unordered_map 中是否有相同的数时，也可以进行优化，我们可以枚举 unordered_map 中数字少的 unordered_map 中的数字，判断另外一个有没有相同的数字。 注意要开 long long。 浮点数用 double 就可以了。 代码： #include<bits/stdc++.h>using namespa ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 题意： 给定 NNN 个袋子，每个袋子里有若干石子。每次操作可以选择两个袋子，将其中一个的所有石子倒入另一个。求所有操作结束后，各袋子石子数的异或和有多少种不同的可能值。 思路： 观察发现最终异或和的值仅与分组方式有关。每次合并操作相当于将两个袋子的石子合并为一个新的袋子，最终的分组可以看作将初始的 NNN 个袋子划分成若干非空子集，每个子集的石子总和构成最终的异或和。 可以通过动态规划逐步生成所有可能的分组方式。 处理每个石子堆时，对当前所有可能的状态进行扩展： 新增分组，将当前石子堆作为独立分组。 合并到已有分组，将当前石子堆合并到任意一个已有分组中。 最后进行去重统计。 代码： #include<bits/stdc++.h>using namespace std;#define LL long long#define itn i ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 思路： 语法题。 考点：循环结构和分支结构。 将两个批改结果的和分别存下来，如果第一次的和大于等于 TTT，则输出第二次批改结果的和，否则输出第一次批改结果的和。 代码： #include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long long int T=1;int n; int a[15],b[15];int main(){ cin>>n>>T; LL sum1=0,sum2=0; for(int i=1;i<=n;i++)cin>>a[i],sum1+=a[i]; for(int i=1;i<=n;i++)cin>>b[i] ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 思路： 递归构建二叉树，并输出先序排列。 首先要知道后序排列、中序排列是怎么构成的。 后序排列是先左，然后右，最后根；中序排列是先左，然后根，最后右。 依此我们可以确定后序排列中的最后一个一定是这个树的根，我们可以将根的左右两边分为两个子树，左子树和右子树，在中序排列中在根左边的是左子树，在右边的是右子树，最后便可构建出二叉树。 例如样例： 给出了中序排列为 BADC，后序排列为 BDCA，可以看的后序排列的最后一个字母是 A，那么说明 A 是根，然后我们在中序排列中找到 A，此时 A 左边的是左子树里的，右边是右子树里的。 所以现在可以转换为： 左子树：中序排列为 B，后序排列是 B。 右子树：中序排列为 DC，后序排列是 DC。 接着我们一直递归直到不能递归就能构建出二叉树了。 样例可能有点小不好理解这里给出另一组再进行一次解释。 当中序排列为 ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 思路： 引用站外地址，不保证站点的可用性和安全性 参考了 OI Wiki 背包 DP 模版题。 首先定义一个 dpdpdp 数组，其中 dpi,jdp_{i,j}dpi,j​ 表示第 iii 个物品在背包容量为 jjj 时的最大价值。 考虑转移。 枚举每一个物品在背包容量剩余 jjj 时可以得到的最大价值。 如果现在枚举的剩余容量 jjj 小于选择这个物品需要的容量，那么 dpi,jdp_{i,j}dpi,j​ 的最大值就是 dpi−1,jdp_{i-1,j}dpi−1,j​。 否则有两种情况，选和不选。 对于选的情况，背包的剩余容量会减小这个物品需要的容量，价值会增加这个物品的价值，故此情 ...