宁宁也要爆wa

分类

题解(9)

/ 注册

全部文章（共9篇）

题解 | #小红数组操作#

小红数组操作题解本题的重点是找到一个数据结构能降低时间复杂度，传统的数组增删改都需要o(n)，这里我们可以用数组模拟一遍链表，用pre[x]表示当前结点的前一个结点，rear[x]表示当前结点的后一个节点，每次插入删除更新一遍这两个数组即可： ">#include<map> #incl...

C++ 链表

2024-02-04

10 330

题解 | #小红整数操作#

小红整数操作题解此题可以先求出x,y的最大公约数d,再将两数与其最大公约数相除转化为两个互质的数，同时这里用到了数论的一个结论：一个数a在区间[1,x]的倍数的个数为x/a，这里要注意拿x/d与y/d最小的数相除区间的左端点l时个数应为： l/min(x/d,l/d)+(l%min(x/d,l/d...

C++ 数学

2024-01-28

8 693

题解 | #小红的中位数#

小红的中位数题解这道题的关键在于判断删除该元素对中位数的影响，其实不难发现与删除的位置与原数组的长度有关，当为偶数时，删掉n/2以后的位置对原数组无影响，反之造成中位数后移一位。当原数组为奇数时，删掉n+1/2以后的位置造成数组前移，反之后移，注意特判原数组删中位数的情况： #include<...

C++ 贪心

2024-01-21

7 700

题解 | #玩《Minecraft》的贝贝#

玩《Minecraft》的贝贝题解链接有题目可知要想造更多的工具我们只需要选择钻石剑与钻石铲即可，再对这个列一元二次方程，即： x+2y=n,y+2x=m,其中x是我们造钻石铲的数量，y是我们造钻石剑的数量，解这个方程即可。 #include<set> #include<map...

C++ 数学

2024-01-20

14 319

题解 | #[USACO 2017 Jan S]Cow Dance Show#

#[USACO 2017 Jan S]Cow Dance Show#题解题意 K头牛上台表演，最早表演完的牛下场按照表演顺序让接下来的牛表演，让你确定最小可同时上台表演的牛的数量K，使得他们表演的总时长不超过T。做法：二分答案+优先队列首先，确定二分答案，我们可以对表演的牛的数量二分，因为要求...

C++ 二分查找堆(优先队列)

2023-12-11

0 364

题解 | #[NOIP2008]传球游戏#

上面的题解讲的很详细了，我补充几句，dp[i][j]表示第j次选第i人的方法数，根据题意，每一个人可以从他左边的人与右边的人拿到球，因此要将第一个人左边与右边的人初始化为1，不过由次要注意第一个人不可能自己传给自己，因此要特判，详情见代码； #include<iostream> #inc...

C++ 动态规划

2023-08-24

0 352

题解 | #线代高手#

看大家都用二维数组前缀和写这道题，那我就来介绍点不一样的方法，暴力枚举+一维前缀和，可以先用两层循环枚举数组的上下边界，再在循环内先预处理前缀和，再暴力枚举区间的左右边界，将x与区间和比较记录最大值； #include<iostream> #include<cstring> ...

C++ 前缀和

2023-08-16

0 342

题解 | #[NOIP2009]最优贸易#

Ciallo～(∠・ω< )⌒☆,大家好，蒟蒻斗胆写的一篇题解，有错误请多多包涵。本题可采用堆优化版本的dijstra算法，dist[i]表示1~i当前的最大价格差，sb[i]表示当前城市水晶石的价格，每次遇到更大的价格差的更新一遍，最后要注意对答案取绝对值，详情请见代码 #include&l...

C++ 最短路

2023-08-11

0 436

题解 | #第k小#

Ciallo～(∠・ω< )⌒☆,大家好，本蒻蒟的第一篇题解，不喜勿喷。首先这题可以先用设置两个优先队列，一个大根堆p，一个设置成小根堆q，先用大根堆p存储输入数据，再用小根堆q维护前K个数据，当小于等于q的堆顶元素时入队，大于时入怕，最后输出去q的堆顶元素即可。 #include<io...

C++ 堆(优先队列)

2023-07-11

3 392