比赛地址：https://ac.nowcoder.com/acm/contest/9982 出题人题解：https://ac.nowcoder.com/discuss/593874 智乃姐姐的题解超级详细啊，认真看完之后嘴巴立马就会了。 A-牛牛与牛妹的RMQ 知识点：单调栈、树状数组 给定个下标，最多有种，分别为个下标点和个区间。 使用单调栈求出每个极值的作用范围。 使用树状数组求出每个极值左右作用范围内可选的下标个数，即可求出该极值对答案的贡献。 注：下面代码可，取就会超时，原因在于求区间极值时用的循环，没想到过了(QAQ)。 #include <bits/stdc++.h&gt...

萌新们请学习一下对拍 今天题自己赛中写傻了，赛后学弟傻了。 先写一份产生随机数据的代码，数据生成是否可靠很重要！！！ 然后用AC的代码、WA的代码和数据代码的文件跑脚本。 下面脚本的意思是先把数据放进，然后两份代码从中读入，运行结果分别输出到和中，比较两个文件是否有不同，没有就继续上述操作否则停止。 生成的数据和结果会保存在和文件中。 #include <bits/stdc++.h> using namespace std; #define LL long long int main() { srand(time(NULL)); LL n = (ran...

比赛地址：https://ac.nowcoder.com/acm/contest/9981 出题人题解：https://ac.nowcoder.com/discuss/593200 A-串 知识点： 第一种：定义状态表示前个字符是否包含字母和。 表示前个字符没有，也没有。 表示前个字符没有，但是有。 表示前个字符有，但后面没有。 表示前个字符有，且后面有。 则有状态转移方程： 前个字符没有和，第个位置有24个字母(除了)可选。 前个字符没有和，第个位置只能选；前个字符有，第个位置有25个字母(除了)可选。 前个字符没有和，第个位置只能选；前个字符有，第个位置也可以选；前个字符有，第个位置...

比赛地址：https://ac.nowcoder.com/acm/contest/9667 出题人题解：https://ac.nowcoder.com/discuss/575975 A-黑白边 知识点：并查集 优先选择黑边然后再选白边，选择条边可使图连通。 #include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <...

比赛地址：https://ac.nowcoder.com/acm/contest/8564 出题人题解：https://ac.nowcoder.com/discuss/564880 A-进攻 知识点：前缀最大值 战机按破坏力从小到大排序、基地按防御值从小到大排序并维护价值的前缀最大值。 #include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset&gt...

个人博客：http://www.kindkidll.com/index.php/archives/157/ A-牛牛和牛可乐的赌约 知识点：概率计算 求其对立事件的概率。 #include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include...

个人博客：http://www.kindkidll.com/index.php/archives/156 A-巨木之森 知识点：树的直径 求出从每个点出发遍历完块区域的最短路程，排序后贪心选择最短路程小的点。 从一个点出发遍历完个点并返回起点，要经过每条边两次，现在不返回起点则最短路的终点应该是距离起点最远的点，最短路程等于所有边长度之和的两倍减去起点到其最远点的距离。 树上距离一个点最远的点一定是树的直径的端点之一，详见博客树的直径。 通过两遍搜索可以得到直径两端点到其余点的距离，即可求出从每个点出发遍历完块区域的最短路程。 #include <bits/stdc++.h> ...

个人博客：http://www.kindkidll.com/index.php/archives/153 A-牛牛爱学习 知识点：二分 答案具有单调性，二分所需要的天数，将书按知识力降序排列求和进行判断。 #include <bits/stdc++.h> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi...

个人博客：http://www.kindkidll.com/index.php/archives/152 A-AOE还是单体？ 知识点：贪心 显然使用技能蛮牛践踏的条件是能对不少于个怪造成伤害，将所有的怪按血量升序排序，存在一个最大操作次数，当使用次蛮牛践踏技能后再使用此技能的收益不如使用蛮牛冲撞。 #include <bits/stdc++.h> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite...

前排弱弱地说：如果对你有帮助的话，下方求赞QAQ顺便悄悄的贴一下自己新搭的小破站http://www.kindkidll.com/ A-最短路 数学几何题，不会，卒。 B-组队 题意：个数里选若干个数，任意两个数的差值小于等于。 基本思路：滑动窗口--由暴力优化而来。 很容易想到的一种方法是先从小到大排序，然后枚举右端点，由0往右找最小的满足，这样做的时间复杂度是的。 考虑一下当已经找到满足要求的时，还需要从0开始找吗？显然是不需要的，因为，则，所以只需要从开始即可。滑动窗口每次右端点滑动一位，左端点要滑动若干位来满足条件限制（此题的限制是差值不能超过）。每个点最多被访问两次，时间复杂度。 ...

离散化+权值线段树 离散化：排序去重 权值线段树：区间维护的是有多少个数大于等于且小于等于。 #include <bits/stdc++.h> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const int mod = 1e9 + 7; const double eps =...

基本思路 由于每个点只能往上更新，所以dfs一遍从叶子结点开始往根结点做选择。 但需要注意如下图所示的情况：当我们dfs回溯到红色的结点时，发现已经选过的结点都无法更新到该结点，那么是直接选择该结点继续往上更新吗？ 答案是否定的，因为很明显我们选择权值为10的结点更优，也就是说当某个结点无法被已选择的结点更新时，可能在其子树中存在更优解。 若，则结点比结点更优，其中表示结点的权值，表示到的路径长度，是的孩子。 可以先dfs一遍获得每个结点的最优解，再dfs一遍求需要操作的最小次数，但显然两次dfs可以合并成一次。 代码 #include <bits/stdc++.h> usin...

dp做法 时间复杂度。 在树中选择任意一个叶子结点作为起点，沿着边一个点接一个点的涂色。定义为前个点使用了种颜色的方案数，状态转移方程： 若第个点选用未使用的颜色，则。 若第个点选用已经使用过的颜色，则必须和的颜色相同，若和更前面的结点颜色相同则在路径中会经过不符合题意，则。 #include <bits/stdc++.h> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfc...

暴力写法：枚举因子，计算有多少个数含有该因子并求和，时间复杂度。 int gethead(int x) { while(x >= 10) x /= 10; return x; } LL solve(int r, int x) { LL ret; for(int i = 1; i <= r; i++) { if(gethead(i) != x) continue; ret += r / i; } return ret; } int main() { int l, r; scanf("%d...