算法基础：差分
一维差分本质 前缀和的逆运算 想要更容易搞懂差分，前提是要先搞懂前缀和如何求 前缀和链接
原理 有一数组a，b，使得 ai = b1 + b2 + b3 + … + bi
例如 b1 = a1
b2 = a2 - a1；
b3 = a3-a2
bn = an-a（n-1）；
b就称为a的差分，a就称为b的前缀和
使某一区域的前缀和被同步改变，
本质上是改变边界的值，使得中间连续值得以被间接改变
用处：且比原先（n）的时间复杂度优化为O（1）
例题模板//改变a任意区间的前缀和，使该区间的前缀和+c，其他保持不变#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>#include <cstdio>using namespace std;const int N = 10001;int n, m;int a[N];int b[N];//改变两边的值，使得中间连续值得以被间接 ...
算法基础：前缀和
前缀和一维前缀和 思想：假设有原数组a1，a2，a3….an;
求前缀和si
则si = a1 + a2 + … + ai;
若要求区间[l,r]之间的前缀和，则只需将r的前缀和减去l - 1的前缀和即可
时间复杂度为O（1）；
模板#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>#include <cstdio>using namespace std;const int N = 100010;int q[N];int s[N];int main(){ int n,m; scanf("%d %d", &n,&m); for (int i = 1;i <= n;++i) scanf("%d", &q[i]);//每项前缀和的初始化 for (int i = 1;i <= n;++i) s[i] = s[i - 1] + q[i];//询问每次 while (m--) { int ...
高精度算法
1.高精度加法 思想：分别用两个数组逆存储两个整数的值，数组下标为0的值存储个位，为1存在十位，以此类推；
再通过模拟加法进位来将得到的值的每一位存储的新数组当中，得到相加数
模板 #define _CRT_SECURE_NO_WARNINGS 1#include <iostream>#include <vector>#include <string>using namespace std;const int N = 1000010;vector<int> add(vector<int> &A, vector<int> &B)//传址调用，节省占用，无需再另拷贝新数组{ vector<int> C; int t = 0; for (int i = 0;i < A.size() || i < B.size();++i) { if (i < A.size()) t += A[i]; if (i < B.size()) t += ...
c语言后期笔记
字符函数&内存函数使用0.NULL – 空指针NUL,Null – ‘\0’1.strtok函数样例
#include <stdio.h>#include <string.h>int main(){ char str[100]; scanf("%s",str); char* p = ".,"; char* ret = NULL; for(ret = strtok(str,p);ret != NULL;ret = strtok(NULL,p)) printf("%s\n",ret); return 0;}
1.1 函数的作用
将字符数组以特定字符分隔开，字符可以是任意几个特定的字符
1.2 函数参数
char* strtok(char * str,const char * sep)
1.3 如果找到特定字符，会直接将原字符数组的该位置字符改为 ‘/0’
1.4 传入的str不为空指针NULL，strtok将找到str的第一个标 ...
快速排序算法
1. 快排 确定一组数据 ，即q数组
左端点为了，右端点为r
（1）确定分界点
q[l] 或 q[ (l + r) / 2] 或 q[r] 或任意一个数 作为分界点，分界点数为x
（2）调整区间 （重点）
使 <= x的数放在左半边，使 >= x 的数放在右半边，两边的数可以乱序，暂时不用排序
（3）利用递归处理左右两端 ，进行排序
暴力法
（1）开两个额外数组a，b
（2）扫描 l 到 r 的所有数，将 <= x 的值放到a中，将 >= x的数放到b中
（3）将a，b排序后放到q数组中 a[ ] -> q[ ], b[ ]->q[ ];
（4）弊端：额外开辟空间，占用内存
简便方法（指针）
用两个指针i，j指向左端与右端的数
（1）判断指针i所指向的数是否小于x，符合条件时往右移一位，当大于等于x时指针i停下
（2）判断指针j所指向的数是否大于x，符合条件时往左移一位，当小于等于x时指针停下
（3）将i与j ...
幸运数的定义与判断
幸运数的定义与判断
前言前几天作为我校一场比赛的压轴题出场，但可以通过骗分得到可观的分数，本人所用方法虽不是骗分，但本质上也是骗过系统得分。
原题链接：牛客网幸运数
幸运数的定义： 1、对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。2、然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。3、如果这个过程 结果为 1，那么这个数就是幸运数。
e.g:
19–>1,9 1²+9²=82 82–>8,2 8²+2²=68 68–>6,8 6²+8²=100 100–>1,0,0 1²+0²+0²=1 此时和为1，无需再往下运算，可认为19为幸运数
判断思路 1.在输入相应的n值后，利用while循环以及计数器算出该数为几位数 2.利用数组a[some]存放该数的每一位 3.通过for循环将此时的各位数平方求和，同时讲该值赋给n，让n进入下一次循环（在赋给n的同时定义的求和sum也要清零） 4.
在每次循环结束前判断n是否为1，若为1 ...
