最短路径问题的几种算法
Floyd算法使用条件可以求出多源最短路，可以处理负权边的情况，但是不能出现负环。
时间复杂度O（n3）
讲解Floyed算法使用的是动态规划的方法。
只需要使用最简单粗暴的做法，将出发点、结束点、中转点都枚举一遍就可以了。
状态转移方程：
1d[i][j]=min(d[i][k]+d[k][j],d[i][j])
这样，再写出Floyd算法的核心代码就很容易了。
另外需要注意的是：Floyd算法不能解决带有负权回路（或者叫负权环）的图，因为带有负权回路的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->->1->2->3这样路径中，每绕一次1->-2>3这样的环，最短路就会减少1，永远找不到最短路。其实如果一个图中带有负权回路那么这个图则没有最短路。
核心代码1234for(k=1;k<=n;k++) //枚举中转点 for(i=1;i<=n;i++) //枚举起点 for(j=1;j<=n;j+ ...
数据离散化
题目问题描述离散化就是把无限空间（或非常大的空间）中有限的个体映射到有限的空间（较小空间）中去，以此提高算法的时空效率。通俗的说，离散化就是在不改变数据相对大小的条件下，对数据进行相应的缩小。
####栗子
原始数据：
18 999 91 100000 0000 15 999 91
离散化后：
11 3 4 2 3
离散化有什么用处呢？有时候我们需要根据数值的大小开一个数组，由于数值很多，没办法开那么大的数组（大了会超内存限制的），但是数据的个数有限。
如：有500000个数字，他们的范围是0-2000000000，这样就满足离散化的条件。我们可以把这些数离散化，最小的缩小为1，大小相邻的依次增加1，这样所有的数的范围一定能缩小到1到500000之间，同时不改变相对大小关系。
####任务
给你n个整数序列a[1],a[2],..,a[n]。请你在不改变相对大小关系的前提下进行离散化。
####要求
1.离散化后，最小的数值为1。2.原序列中相同的数，离散后还应相同。3.大小相邻的两个数离散后相差为1。4.离散后序列相对位置不变。
###输入
第一行n 原始数据的个数 。第二行n ...
莫比乌斯反演
##莫比乌斯反演相关
###莫比乌斯函数
$$\mu(n)=\left{\begin{array}{ll}1 & \text { 若 } n=1 \(-1)^{k} & \text { 若 } n \text { 无平方数因数，且 } n=p_{1} p_{2} \ldots \ldots p_{k} \0 & \text { 若 } n \text { 有大于 } 1 \text { 的平方数因数。 }\end{array}\right.$$
设f(n)、g(n)是两个数论函数，它们的狄利克雷乘积也是一个数论函数，其定义为：
$$\begin{aligned}h(n)=& \sum_{d \mid n} f(d) g\left(\frac{n}{d}\right) \& d>0\end{aligned}$$若函数满足：$$f(n)=\sum_{d \mid n} g(d)=\sum_{d \mid n} g\left(\frac{n}{d}\right)$$则有$$g(n)=\sum_{d \mid n} \mu(d) f\left(\f ...
2020年3月8日NOIP课程知识整理
一、高精度计算
这一次课程主要讲了高精度加、减、乘。
首先，定义一个高精度的结构体，储存这个数字的长度、和这个数字本身。
123456789101112131415161718192021222324252627struct gaojing{ int n,z[2333]; gaojing() { n=1; memset(z,0,sizeof(z)); } void init() { scanf("%s",s+1); int l=strlen(s+1); reverse(s+1,s+l+1); n = l; for (int a=1;a<=n;a++) z[a] = s[a]-'0'; } void print() { for (int a=n;a>=1;a--) ...
递推;矩阵加速
这个题其实很简单，简单分析一下规律，发现发f[i]=f[i-1]+f[i-2]。
如下图：
12345678910111213 1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 int n,i,j,a[101]; 6 cin>>n; 7 a[1]=1;a[2]=2; 8 for (i=3;i<=n;i++) 9 {10 a[i]=a[i-1]+a[i-2];11 }12 cout<<a[n];13 }
用这个代码，解决这个题的确很轻松。
可是只要稍微更改一下数据范围，就完全不一样了：
这样子，难度就完全不是一个等级了。
首先是不能开一个10^18^的数组，那样肯定会爆内存。
我们可以用滚动的数组：
12345678910111213141516171819202122232425262728293031323334#include< ...
洛谷P1217USACO1.5回文质数PrimePalindromes
P1217 [USACO1.5]回文质数 Prime Palindromes题目描述因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。
写一个程序来找出范围 [a,b](5≤a<b≤100,000,000)( 一亿)间的所有回文质数。
输入格式第 1 行: 二个整数 a和 b .
输出格式输出一个回文质数的列表，一行一个。
输入输出样例15 500
1234567891011125711101131151181191313353373383
说明/提示Hint 1: Generate the palindromes and see if they are prime.
提示 1: 找出所有的回文数再判断它们是不是质数（素数）.
Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.
提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。
题目翻译来自 ...
P1553数字反转（升级版)
题目描述给定一个数，请将该数各个位上数字反转得到一个新数。
这次与NOIP2011普及组第一题不同的是：这个数可以是小数，分数，百分数，整数。整数反转是将所有数位对调；小数反转是把整数部分的数反转，再将小数部分的数反转，不交换整数部分与小数部分；分数反转是把分母的数反转，再把分子的数反转，不交换分子与分母；百分数的分子一定是整数，百分数只改变数字部分。整数新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零；小数新数的末尾不为0（除非小数部分除了0没有别的数，那么只保留1个0）；分数不约分，分子和分母都不是小数（约分滴童鞋抱歉了，不能过哦。输入数据保证分母不为0），本次没有负数。
输入格式一个数s
输出格式一个数，即s的反转数
输入输出样例15087462
12647805
1600.084
16.48
1700/27
17/72
18670%
1768%
说明/提示所有数据：
25%s是整数，不大于20位
25%s是小数，整数部分和小数部分均不大于10位
25%s是分数，分子和分母均不大于10位
25%s是百分 ...
关于递归与递推
又在洛谷上刷题。
又是一题，
P1028 数的计算来，咱读题：
题目描述我们要求找出具有下列性质数的个数(包含输入的自然数nn):
先输入一个自然数nn(n \le 1000n≤1000),然后对此自然数按照如下方法进行处理:
不作任何处理;
在它的左边加上一个自然数,但该自然数不能超过原数的一半;
加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入格式11个自然数nn(n \le 1000n≤1000)
输出格式11个整数，表示具有该性质数的个数。
输入输出样例输入 #1
16
输出 #1
126
说明/提示满足条件的数为
6，16，26，126，36，136
看完题，这题不很简单吗？一个递归不就解决？
满怀信心地写程序：
12345678910111213141516171819#include<bits/stdc++.h>using namespace std;int s=0;int js(int a){ a/=2; for(int i=1;i<=a;i++) { s++; j ...
总结一下当前阶段我认为比较常用的字符串操作
首先是string：
定义：
1string str；
读取：
1getline(cin,str);//读取一行
获取长度：
1len=str.size;
粘贴：
1str1=str.substr(2,len-1)//把str的第三位到最后一位粘贴到str1
计算：
1str1+=str//在str1后面接上str
然后是字符数组：
定义：
1char a[100];
读取：
1gets(a);
获取长度：
1len=strlen(a);
注意：
字符串有时也可以当做字符数组，使用str[n]这样的写法，只不过它们大部分操作都不一样。
关于C++读入数字按位取出与进制转换问题
这一片博客我就不写具体的一个题了，只是总结一种典型问题读入数字按位取出。
就拿数字12345举例吧。
是首先，我们要取出个位。这样取出：
12312345/1=1234512345%10=5. //为了好发现规律
这样我们就有了它的个位。十位是这样：
12312345/10=12341234%10=4.
同理，百位：
12312345/100=123123%10=3.
于是可以发现，取出哪一位，就是要先将原数除以这一位的位名，再模10.
程序：
123456789101112131415#include<iostream>#include<cmath>using namespace std;int main(){ int a[100]; int wei = 0; int num; cin >> num; while ((num / (int)pow(10, wei)) != 0) //循环终止条件是这个数的位数小于这一次要除以的数的位数 { ...
