矩阵原地转置（时间换空间） 思路引入 参考在一维数组中进行循环位移： a[]={1,2,3,4}，要将数组循环左移1位，下标循环：  与循环位移类似，以一个2x3矩阵为例，元素右下角数字为其在一维数组中的下标。  直接从矩阵来看，看不出什么下标规律，但是将其展开为一维数组，就能发现一些下标循环：    (重复) (重复) (重复)   因此，考虑用循环数组的思路来处理矩阵转置。 详细思路 后继下标计算 对于N*M原矩阵中(i,j)元素，其在转置矩阵中索引为(j,i)，前者在一维数组下标为i*M+j，后者为j*N+i。 找循环 从下标0开始遍历一维数组，根据后继下标的计算方法，循环进行移动，直到...

观察几个旋转例子，就可以发现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]对于有起始坐标偏移的旋转，再分别加上x、y偏移即可。 // // Created by Zed on 2024/2/15. // #include <iostream> using namespace std; const int MAXN = 15; const int INF = 1e7; int...

考点：递推式计算 矩阵快速幂   注意点：负数的模应该先加上MOD再模   设s(n)为n个格子铺满需要多少洋灰三角。根据题意，可以得出如下递推式：  因此可以构造出：  以此递推即可得到：  因此问题就转化为求一个三阶矩阵的高次幂，与纯数的快速幂类似，只是将数的乘法改为矩阵乘法即可。(吐槽：牛客MD编辑器真难用，基本的Latex公式都表示不出来)  // // Created by Zed on 2024/2/10. // /* * 链接：https://ac.nowcoder.com/acm/problem/17510 来源：牛客网 题目描述 洋灰是一种建筑材料，常用来筑桥搭建高层建筑，又...

记录两种思路：按照链表的观点，找公共结点，可以利用双指针的思想实现（a+c+b=b+c+a，其中a、b分别为两个链表前缀的长度，c为公共后缀的长度）。把链表看成有向图，公共后缀结点其实就是入度为2的结点。这里提供第二种思路的代码 // // Created by Zed on 2024/2/9. // #include <iostream> #include <cstdio> using namespace std; const int MAXN = 1e6 + 100; int in[MAXN];//统计结点的入度 int main() { int s1, s2, n...

从Prim算法和Dijkstra算法两种算法异同的角度说明为何本题最小生成树中包含了所有最短路径。两种思路：最短路+高精度加乘（最容易想到的方法，该题大数可以用二进制数组表示比较方便）最小生成树+dfs这里着重记录第二种思路。首先说明一下为什么最小生成树中包含了所有最短路径。这里不得不提及一下Prim算法和Dijkstra算法，这两种算法有极高的相似度，这两个算法在添加新结点时，都是选择“距离最短”的结点加入集合，但是Prim算法中，“距离最短”是指未访问的结点到已经访问的所有结点距离最小，即将已经访问的结点视为一个整体，将距离最小的结点加入到已访问的集合中；而在Dijkstra算法中，“距离...

典型的递归问题。对于x需要将其转化为2次幂的和而其中指数同样需要按第一条处理因此递归函数就有了基本框架：从大到小，提取x的二次幂的指数x'对指数x'调用递归函数最终代码如下 // // Created by Zed on 2024/2/8. // #include <iostream> using namespace std; void reverse(int x) { if (x == 0) {//递归封口 cout << 0; return; } bool first = false;//为了输出加号准备，在第一个加数出现后，需在后续每个加数后加上一个加号 for ...

提供一种O(n+m)的思路。利用差分数组可以实现O(1)进行一次区间操作，而计算具体某个元素的时间复杂度为O(n)（一次性计算所有元素的值时间复杂度为O(n)）。因为本题先进行一系列区间操作，最后再询问一次所有元素的值，因此十分适合用差分数组求解。对于本题，可将原数组初值设置为0，表示树还在，而后续砍树操作看做区间减1操作，最后再计算修改后的数组的值，当值小于0，说明被砍了，反之还在，统计结果即可。差分数组定义diff[i]=a[i]-a[i-1],i>=1（a为原数组，diff为差分数组）diff[0]=a[0]显然，a[i]=diff[0]+...+diff[i]区间操作对[l,r]...