nagisa_菜鸡

题解

/ 注册

全部文章 / 题解（共5篇）

2021牛客暑期多校训练营5（B.期望 G.暴力）

这场感觉需要记录的东西貌似不是很多，所以写个总的。 B.Boxes 根据贪心原则，其实我们可以注意到两点：1、是否要提示是开始前决定的。要么，你一开始不要提示，全部盒子都开一次。要么，先要提示，根据提示的数量开盒子。因为假若你中途再要提示，可能要到后发现盒子开多了，还不如一开始就要，花费只多不少。2...

数据结构

2021-08-01

0 773

老瞎眼 pk 小鲜肉解题报告（线段树+思维+前缀异或和）

看到题目，我想大家第一个想到的就是前缀异或和，因为这种询问一整段的异或和的一半都需要这样处理，不然复杂度太高。之后，题目要询问的就是找到在区间[L,R]中的存在的点sum[l]==sum[r],使得r-l+1最小。若是考虑直接让值对应整个[l,r]区间则会很麻烦，所以，考虑转化为单点维护。考虑单点维...

每日一题离线数据结构

2020-12-23

1 769

2020年牛客算法入门课练习赛3 解题报告(A最短路 B容斥 C线段树 D DP E 思维)

打开博客发现上次咕咕咕了写一半。。想想还是补完，顺便复习下。 A、胖胖的牛牛好像bfs也行。我这里用的是dfs，后来用了最短路解。这里主要说最短路。将每个点分成上下左右四个点，用点，其中i、j是点坐标，k为其方向：0为左，1为上，2为右，3为下，(因为当i=n,j=n时，，所以是)然后用0点作为超...

搜索 dp 数据结构

2020-07-15

1 664

2020年牛客算法入门课练习赛1 题解A(快速排序求第k小数/STL)B(STL)C(三分)D(差分+离散化)E(乱搞)

本来不想打的，结果看着看着自己就打进去了（笑哭） A.第k小数记得上课讲过。这道题卡排序（但听说有人排序过了？？） #include <iostream> #include <map> #include <ctime> #include <vector&g...

二分 dp 数据结构树状数组

2020-05-27

0 573

NC 43625717 换个角度思考解题报告（主席树/离线+树状数组/莫队（随缘更新））

wa/tle了三页才写出来。。。菜鸡果然是菜鸡主席树这个昨晚刚看的数据结构，敲的时候敲错了n多次。。在树里，把数的版本号当作数组下标，树内记录每个区间内的数的出现次数，学过之后还是比较好理解的。 #include <iostream> #include <cstdio> ...

树状数组每日一题离线数据结构主席树

2020-04-30

1 825