题目传送门 这道题是一个构造题，只要是一个构造题就不用管样例的输入输出，样例的输入输出仅用于理解题意对于一般的构造题来说，并不需要那么多花里胡哨的方法。 题目中说明四舍五入保留到整数，但是为什么题目说什么你就做什么呢？当然可以不用四舍五入，而且代码也非常的简洁，但是完成代码前的推导是需要一点时间的。 题目中说明 $A$ 的最大值为 $400$，$B…

1 线段树 1.1 什么是线段树？ 线段树在算法竞赛中常用于区间操作。时间复杂度$O(\log n)$。 1.2 线段树的应用 1.2.1 线段树的基本应用 顾名思义，区间修改，区间查询。 1.2.2 线段树最大字段和问题上的运用 问题描述： 操作一：进行单点修改。 操作二：给定 $l$ 和 $r$，问 $[l, r]$ 中的最大的子段和是多少？ …

0 序 为了强化笔者对LCA的理解，故作此文。 1 DFS序求LCA 1.1 算法介绍 考虑树上的两个节点 $u$, $v$ 和其祖先 $d$，我们之所以使用欧拉序求解 LCA 是因为在欧拉序中 $d$ 一定在 $u,v$ 之间出现。但对于 DFS 序来说，$d$ 一定在 $u,v$ 之前出现。 令 $u$ 的 DFN 小于 $v$，且 $u\ne…

前置知识 图论相关概念 割点和桥 强连通分量 点双连通分量 在一个无向图中，若删除图中的任意一个点，这个图还能连通，则称这个图为点双连通 例题：P8435 【模板】点双连通分量 在书写代码的时候有需要注意的地方会在程序中标注。 #include <bits/stdc++.h> using namespace std; const int…

题目描述 有三个野人三个道士，他们在何的右岸，现有一艘只能容纳两个人的小船，因为野人比较野蛮，如果河一侧野人的数量大于道士的数量，野人就会攻击道士，问如何安全的过河。输出任意一种方案。 问题分析 这道题目可以通过搜索来实现，广搜和深搜均可，在这里为了锻炼使用广搜的代码能力，笔者决定用广搜来解答这道题目。 为了进行广搜我们需要创建一个三元组$(x, …

按照重要性递减 注意事项 *适用于四川 考试时要在 D 盘 csp 目录下作答，不能建立子文件夹。 代码中记得加freopen，考试结束前记得删注释。 检查“地球”的路径和准考证号是否正确。 注意数据范围选择合适的变量类型，若无法判断变量类型则一律开long long。 防止乱开 long long 出现的 MLE，TLE等问题。 若一个测试点中有…

割点 什么是割点 在无向图中所有能够互通的点构成了连通分量，其中有一些关键的点，如果删除它，如果这个联通分量被分成了两个或者更多，则称这个点为割点。 通俗的讲，现在有很多个主机连在一起构成网络，但是如果有一个主机烂掉了,你就无法访问洛谷，则称则称这个主机是一个割点。 求割点 在通过 DFS 遍历个图的时候，很容易发现如果一个点是割点，则它的儿子们都…

祖孙询问 此问题可以用 LCA 来解决，但是 LCA 的码量大，而且可能容易写挂，尤其是像我这种蒟蒻 如果卡时间的话有可能倍增/重链剖分 LCA 都要挂掉，这时候就是 DFS 序发挥作用的时候了。 拿一个计数器。在遍历到每一个节点的时候，我们在进入它的时候记录一下，在离开它的时候也记录一下，在记录完成后就得到了一个树的 DFS 序 代码如下： /*…

sort 算法竞赛中的每一毫秒都是珍贵的 而 sort 的不恰当使用会浪费很多额外的时间，尤其是在数据量较大的时候。 平时阅读题解的时候发现很多大佬都会这样子写 sort : sort(a + 1, a + 1 + n, [](const int& x, const int& y) { return x > y; }); 或者…

题目传送门 在编写代码的时候多写写注释！！ 多写十秒钟注释少调试十分钟程序！！ 记忆化搜索 /* problem:[USACO17JAN] Hoof, Paper, Scissor G URL:https://www.luogu.com.cn/problem/P3609 time:2023-10-03 记忆化搜索 */ #include <i…