Maddison10

分类

NOIP模拟赛题解(1) 每日一题笔记(3) 每日一题题解(11) 比赛总结(3) 牛客周赛普及组&提高组(2) 牛客多校比赛(4) 牛客练习赛|挑战赛|小白月赛题解(5) 知识点学习笔记(3) 题解(1)

/ 注册

全部文章（共33篇）

牛客练习赛68题解

A:牛牛的mex题目要求一个区间的mex，可以离线，我们可以莫队维护。需要注意的是，因为我们要的是根号算法，不能带log，因此我们搞两个分块，一个是莫队的，一个是值域的。可以做到插入是O(1)的，单次查询是O(sqrt(n))的，就可以通过，总时间复杂度O(nsqrt(n))代码： #include...

2020-09-26

0 569

悬线法学习笔记&总结

悬线法是一类用于解决最大子矩阵的问题的算法，其大概的代码实现和dp递推差不多？大致算法是我们用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界，统计最大扩展的距离。然后我们注意的是红色的面积更大，这样的情况也可以在红色的边界被算上，所以这大概是悬线法算法的正确性。接下来举一些悬线法的例题...

2020-09-24

0 647

小V的序列题解

题目链接：https://ac.nowcoder.com/acm/problem/205370题目难度：提高+/省选-推荐理由：思路非常妙，巧妙的运用了随机生成数据的特点，一道非常好的思维题题目知识点：位运算技巧，阈值思想题意描述：我们用一种随机生成数据的方式生成一个长度为n的序列，然后有m个询问，...

2020-09-24

1 952

牛客IOI周赛18-普及组题解

A:数字计数简单题，基础模拟，我们sort一遍就可以了但是我们要用一个unique去重，不太熟悉unique的同学可以用一个桶，或者和上一次的值比较一下手动去重！然后直接输出，这个没什么好说的吧？代码： #include<bits/stdc++.h> #define LL long lo...

2020-09-12

0 577

牛客挑战赛42题解

A:小睿睿的数列我们注意到一个区间内的数字全部相同这种贡献是可以单独算的那么我们可以把它们都缩在一起然后我们发现我们每个点的gcd要使找得到，一定是下一次是这一次的约数，然后我们不断向两边扩展，由于是约数而且我们规定了它们不同，所以每次至少是上次的两倍，这样最多是log次的我们找一个起点作为gcd然...

2020-09-12

1 731

牛客小白月赛27题解

A:巨木之森首先这题的路径我们发现除了最后到达的点以外，其他每条边都要遍历两次（因为最后不回来了）然后我们会尽量贪心的走最远的点，然后有一个关于直径的性质，距离一个点最远的点一定是直径的两个端点，因此我们求出直径，然后在树上倍增lca选下距离，选出最优的最后我们sort一遍能选就选，取最多的就可以了...

2020-09-06

1 535

2020牛客暑期多校训练营（第四场）题解

部分题题解，剩余部分待补A：Ancient Distance这道题写了个根号的复杂度的，没有被卡我们只需要做到O(1)判断就好了！然后我们可以写一个有关于单调性的解法，然后我们可以类似于整除分块可能更好理解！nlogn的代码和思路以后会补，先放上根号的代码： #include<bits/std...

2020-08-25

0 629

2020牛客暑期多校训练营（第三场）题解

写一下一些作者掌握的题的题解，其他会慢慢补A: Clam and Fish这题是一道贪心，我们发现我们要最优策略就是有鱼我们就钓鱼，反之如果最后有多余的蛤蜊，我们可以花一半的时间用来更优的策略，注意要下取整算是一道基础题吧！B: Classical String Problem一道不易让我们思维定向...

2020-08-25

0 793

牛客练习赛67题解

A: 牛牛爱字符串一道简单的模拟题稍微有点细节注意不要输出多余的空格并且不能有多余的0000这样的问题，但是要注意如果是0必须输出0，这是个易错的细节这里读入用string和getline更方便，并且细节部分可以用个deque维护代码： #include<bits/stdc++.h> #...

2020-08-20

1 540

2020牛客暑期多校训练营（第二场）题解

首先由于这场比赛的代码写得有点过于仓促，主要都是考试写得代码，和大部分根据框架改的代码，所以可读性一般，因此这篇题解就不给代码了，见谅！A: All with Pairs首先这道题要求我们求一个最长前缀和后缀的关系，我们可以把所有的前缀和后缀都存在一个hash表里面，然后我们发现有些前缀和后缀会算重...

2020-08-14

0 727