狂点技能树

分类

思维题(1) 题解(17)

/ 注册

全部文章（共17篇）

题解 | #幼稚园的树#

A 本题数据范围较小，可以直接枚举每一天每一棵树的变化。坑点：求第 mmm 天中午的状态实际上是进行了 m−1m - 1m−1 次变化（生长和剪切）。时间复杂度：O(T×n×m)O(T \times n\times m)O(T×n×m)。 B 注意到 xxx 的取值不超过区间中数的个数，这说明区...

C++ 牛客小白月赛

2022-11-25

11 902

题解 | #小白月赛62#

A 本题数据范围较小，可以直接枚举每一天每一棵树的变化。坑点：求第 mmm 天中午的状态实际上是进行了 m−1m - 1m−1 次变化（生长和剪切）。时间复杂度：O(T×n×m)O(T \times n\times m)O(T×n×m)。 B 注意到 xxx 的取值不超过区间中数的个数，这说明...

C++ 牛客小白月赛

2022-11-25

1 617

题解 | #或与异或#

只需要判断目标数字是否由 “0 1”、“1 0” 和 “1 1” 这三种位置的集合组成即可。证明（图片中给出证明，此处无法读取请点击：https://blog.nowcoder.net/n/2841f568ef4a478f84d3368ace8d4bd8）：代码： #in...

思维

2022-06-19

0 429

题解 | #柠檬树#

基本思路：按题解的，分两部来做。第一步：按顺序对所有点到根的路径染上对应的颜色，这样区间查询就变成了查询颜色号 >= 左端点号的点的数量了，这里可以用 LCT （这个是静态问题，也可以用轻重链剖分来写）。第二步：减去区间所有点的 LCA 到根节点的距离（可以用欧拉序加倍增来求，也...

LCT 欧拉序倍增 C++

2022-03-18

0 517

题解 | #Honeycomb#

思路：随便选两条轴作为x、y轴，把蜂巢映射到二维平面后找规律即可。找到规律后可直接二分到某个区间然后分类讨论确定坐标求解即可。 #include <bits/stdc++.h> using namespace std; #define _for(i, a, b) for(int i =...

C++ 二分查找数学

2021-12-10

0 538

题解 | #方格取数（number）#

此题非常好！！！思路：基础取数 dp 的变式。考虑只能向下走和向右走（很简单）考虑只能向上走和向右走（很简单）区别：既可以向上走又可以向下走所以我们考虑对于每一列，既进行向下的 dp 也进行向上的 dp （具体过程见代码） #include <bits/stdc++.h>...

贪心贪心优化 dp

2021-06-03

1 820

题解 | #dd爱框框#

双指针模板题。思路：其实没什么好说的，这题都讲烂了，无非是维护两个指针 l，r 来标识前后位置，维护 sum 代表其间的和，若 sum 大于等于 x 就尝试更新答案并移动左指针，若 sum 小于 x 就移动右指针（指针都只向前移动，移动时保证 sum 为 l，r 之间的和）唯一的麻烦在于边界处...

双指针

2021-06-01

1 1289

题解 | #dd爱矩阵#

算法进阶指南例题改编。思路（来自算法进阶指南一书）：假设我们只有两行 a，b 需要被合成排序最大值显然是 a[n] + b[n] ，记录最大值次大值可能出现在 a[n - 1] + b[n] 和 a[n] + b[n - 1] 之中 ……（自己写两个数组同上分析）我们发现，对于任...

堆贪心思维题优先队列

2021-06-01

5 686

题解 | #dd爱矩阵#

思路：代数法分析对于每一种变化，我们可以用代数的方法将其表示出来第一种变化：a[i][j] --> a[n - i + 1][n - j + 1] 第二种变化：a[i][j] --> a[n - i + 1][j] 最有意思的在于我们如果尝试对翻转的再翻转或者镜像的再镜像，其...

模拟思维题

2021-06-01

2 628

题解 | #dd爱科学2.0#

思路： dp 我们枚举每一位变成每一种字符（26种）时的花费（保证此时字符串递增）。值得注意的是当我们计算花费时需要取得当前位最小值，就必须要去遍历前面状态小于自己字符的花费取最小，这个问题可以通过加一个额外的记录最小值的变量完成，不过在代码里我们做的更绝：每一位保存的都是全体最小值，其意...

贪心思维题 dp

2021-06-01

2 730