rk_no

题解

/ 注册

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

Running Median(离散+权值线段树)

题目：往一个空序列加个数。当序列中数的个数为奇数个时，记录此时序列排序后的中位数。输出所有中位数。做法：看到中位数，第一时间想到权值线段树。所以我们先将所有数读进来离线处理。先将所有数离散化，便与用线段树维护。然后一个一个数加到序列中，线段树该数字出现的次数+1。奇数个数时，线段树上查询第小...

2020-04-09

1 809

牛客算法周周练1（ABCDE题解）

A.Maximize The Beautiful Value（贪心，前缀和）题目：一个单调不减的序列，进行一次操作后使值最大。操作：选一个往前挪至少位。做法：不难发现每个有合法操作，而且多往前挪几位不会使答案更优。所以贪心枚举计算往前挪位的值，取即可。算用前缀和优化。具体看代码。代码...

2020-04-07

1 948

数码（整除分块）

题目：给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。做法：可以拆分成2个区间处理。。问题变成了：统计区间中每个数的因子的最高位数码的出现次数。例...

2020-04-07

0 954

黑白树（树形DP）

题目：一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i...

2020-04-07

3 1225

Shortest Path(树形DP)

题目：一棵偶数结点的树，边带权。请将结点分成n/2对点，使每对点路径求和最小。做法：代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(...

2020-04-02

0 727

月月查华华的手机（转移预处理）

题目：月月和华华一起去吃饭了。期间华华有事出去了一会儿，没有带手机。月月出于人类最单纯的好奇心，打开了华华的手机。哇，她看到了一片的QQ推荐好友，似乎华华还没有浏览过。月月顿时醋意大发，出于对好朋友的关心，为了避免华华浪费太多时间和其他网友聊天，她要删掉一些推荐好友。但是为了不让华华发现，产生猜疑...

2020-04-01

0 725

Rinne Loves Edges（树型DP）

题目 Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 w_i 现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 ...

2020-03-31

0 650

城市网络（倍增）

题目：有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。在每次行程开始时，你手上有价...

2020-03-30

10 1283

滑动窗口（单调队列）

题目：给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位。你的任务是找出窗体在各个位置时的最大值和最小值。做法：单调队列的经典例题。最大值最小值分开处理。处理最大值时，从左到右遍历维护一个数值从大到小的单调队列。具体操作就是每加入一个...

2020-03-29

0 848

数学考试(前缀和，RMQ)

题目题意：在长为n的序列a[]中选2段不连续长度为k的区间使区间和最大。n ≤ 2e5 做法代码 #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug...

2020-03-26

0 776