爬塔的鸡煲

分类

题解(1)

/ 注册

全部文章（共8篇）

题解 | 区间覆盖问题的变形

时间复杂度：O(mlogm)区间覆盖问题给定n个小区间和一个范围[a, b],选择尽量少的区间，使得[a, b]能够被完全覆盖。解法：贪心如果有区间x和y，x包含了y，显然选择x这个大区间更好。因此考虑对每个区间按左端点升序排序，从第一个小区间开始选择，每次选择区间左端点在目标区间内且右端点尽可能大...

2024-02-27

0 269

题解 | #矩阵转置#

矩阵原地转置（时间换空间）思路引入参考在一维数组中进行循环位移： a[]={1,2,3,4}，要将数组循环左移1位，下标循环：与循环位移类似，以一个2x3矩阵为例，元素右下角数字为其在一维数组中的下标。直接从矩阵来看，看不出什么下标规律，但是将其展开为一维数组，就能发现一些下标循环： ...

2024-02-17

0 301

题解 | #C翻转#

观察几个旋转例子，就可以发现n*n矩阵有以下规律：逆时针旋转90度：第i行变为第n-i+1列顺时针旋转90度：第j列变为第n-j+1行若矩阵二维数组a从0开始使用，则有：逆时针旋转90度：a'[n-j-1][i]=a[i][j]顺时针旋转90度：a'[j][n-i-1]=a[i][j]对于有起始坐标...

2024-02-16

0 244

题解 | #洋灰三角#

考点：递推式计算矩阵快速幂注意点：负数的模应该先加上MOD再模设s(n)为n个格子铺满需要多少洋灰三角。根据题意，可以得出如下递推式：因此可以构造出：以此递推即可得到：因此问题就转化为求一个三阶矩阵的高次幂，与纯数的快速幂类似，只是将数的乘法改为矩阵乘法即可。(吐槽：牛客M...

C++ 数学

2024-02-10

0 274

题解 | #Sharing#

记录两种思路：按照链表的观点，找公共结点，可以利用双指针的思想实现（a+c+b=b+c+a，其中a、b分别为两个链表前缀的长度，c为公共后缀的长度）。把链表看成有向图，公共后缀结点其实就是入度为2的结点。这里提供第二种思路的代码 // // Created by Zed on 2024/2/9. /...

2024-02-09

0 229

题解 | #最短路径#

从Prim算法和Dijkstra算法两种算法异同的角度说明为何本题最小生成树中包含了所有最短路径。两种思路：最短路+高精度加乘（最容易想到的方法，该题大数可以用二进制数组表示比较方便）最小生成树+dfs这里着重记录第二种思路。首先说明一下为什么最小生成树中包含了所有最短路径。这里不得不提及一下Pri...

2024-02-08

0 214

题解 | #2的幂次方#

典型的递归问题。对于x需要将其转化为2次幂的和而其中指数同样需要按第一条处理因此递归函数就有了基本框架：从大到小，提取x的二次幂的指数x'对指数x'调用递归函数最终代码如下 // // Created by Zed on 2024/2/8. // #include <iostream> ...

2024-02-08

0 229

题解 | #剩下的树#

提供一种O(n+m)的思路。利用差分数组可以实现O(1)进行一次区间操作，而计算具体某个元素的时间复杂度为O(n)（一次性计算所有元素的值时间复杂度为O(n)）。因为本题先进行一系列区间操作，最后再询问一次所有元素的值，因此十分适合用差分数组求解。对于本题，可将原数组初值设置为0，表示树还在，而后续...

2024-01-27

0 224