horz

题解

/ 注册

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

毒瘤xor

题意有一个长度为的数组，每次询问一个区间，找一个，使得最大。分析我们考虑每一位，假设我们区间的长度为，有个数在这位上是，三个数是，那么的这一位选的贡献会更大，因为异或之后这一位就会有个，个。所以我们可以根据区间的每一位的的个数来决定的这一位的取值。具体一点就是：多放，多放，一样多放。 #...

2020-07-02

1 573

珂朵莉的数列

题意珂朵莉给了你一个长度为的序列，有个子区间，求所有区间逆序对的个数和。分析比如说我们选择有一对逆序对，，那么以为结尾的逆序对，所产生的贡献是，区间左边有个选择，区间右边也有个选择。现在我们统计假设区间是，那么以为结尾的逆序对，所产生的贡献是。所以我们可以发现就是统计前面比它大的数的下标...

2020-07-01

0 766

借教室

题意有一个长度为的区间，有次操作，每次使得区间的值减去。分析我们每次只需要做两种操作：询问区间最小值。使得区间减去。线段树模板。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a...

2020-07-01

0 500

牛客算法周周练13

这应该是最简单的一场周周练了吧。最小生成树每个点都连节点值最小的那个点，类似于的思想。病毒感染题目说图的类型保证没有大小大于等于3的环，那不就是告诉你是一颗树了吗。树的重心。 Shopping 贪心，假设凳子一共有个，那么一共有个东西可以半价，一下求和。铺地毯题目只有一个询问，倒过来模...

2020-07-01

0 490

Growth

题意有两个属性和，每一天他可以通过努力，让涨点或涨点。有种奖励，当大于等于，大于等于时，每天可以获得的奖励。问天可以获得的最大奖励是多少？分析首先我们将和分别离散化。然后我们可以定义表示第天可以获得的总奖励。表示第天当天可以获得的总奖励。转移方程可以通过二维前缀和求解出来。 #...

2020-06-30

0 813

Shortest Path

题意给定一颗树，分成个点对，使得他们的距离和最小。分析显然不同点对之间不共用边的情况是最优的，如果有共用边，明显可以重新分配，使得距离和更小。接下来考虑，显然如果子树大小是偶数的话，可以子树内部消化，如果是奇数，就要加上边权。 #include <bits/stdc++.h> u...

2020-06-26

0 525

月月查华华的手机

题意有一个字符串，有一些匹配串，问匹配串是否是字符串的子序列。（子串是连续的，子序列是递增非连续的）分析显然我们可以贪心的去匹配，尽量匹配前面出现的字符。然后我们可以定义一个数组，代表下一个字母出现的位置。然后我们不停的跳就可以了。 #include <bits/stdc++.h&g...

2020-06-26

0 478

Rinne Loves Edges

题意有一颗树，可以删去一些边，代价是边权。现在要使得叶子节点和根节点不连通，求删边的最小代价。分析 M=N−1，这也太坑了吧。举个栗子我们可以选择删去这条边，或者删去和这条边，显然选代价小的。我们可以通过求出所需的代价。 #include <bits/stdc++.h> u...

2020-06-26

0 509

城市网络

题意在一颗树上面，求节点到节点的最大值的变化次数。分析先看一波题解首先我们发现一定是节点的祖先，所以我们可以利用倍增的思想（类似于求），首先我们先定义一个节点的父亲是在该路径上第一个大于当前节点的值的节点。然后我们可以利用倍增的思想，求出第个购入节点。然后就像求一样去往根节点跳就好了。...

2020-06-26

0 577

滑动窗口

题意求长度为的窗口的最大值和最小值。分析单调队列入门题，也是很好的入门题。用单调队列来解决问题，一般都是需要得到当前的某个范围内的最小值或最大值。假设我们要求最小值，我现在有一个队列，我让他里面的值升序排列，类似于，现在我又新加进来一个，那么他会把排在他前面的比他大的数踢掉，就变成了。我...

2020-06-26

1 634