1：枚举
按照题目要求进行遍历即可，要注意数据范围。
2：进位制
一：10进制转X进制，除以X，把余数保存起来翻转即X进制下对应的数。 二：X进制转10进制，第一位数乘以X的n-1次方，以此递推，求和即 10进制下对应的数。 三：X进制转Y进制，还没学，只能X转10进制，再把10进制转Y进制，只能骗分。
3：双指针算法
能把O(n^2)压缩为O(nlogn)。用i对一个单调递增的序列遍历，用j从i开始遍历，使得该序列所有情况都能计算。
**4：二分 **
只能靠模板。
int l = 0 ,r = n;
while(l<r)
{
int mid = (l+r)/2;
if(check())r=mid;
else l = mid+1;
}
//第二种 这种情况二分的结果偏小
while(l<r)
{
int mid = (l+r+1)/2;
if(check())l=mid;
else l = mid-1;
}
cout<<l+1<<endl;
5:前缀和
一维前缀和和二维前缀和，也不是遇见矩形一定要二维前缀和，可以对列进行前缀和。
6：背包问题
有限空间下的价值最大值。
01背包
for(int i=1;i<=n;i++)
{
for(int j=0;j<=V;j++)
{
if(v[i]<=j)//放的下第i件物品
{
dp[i][j]=max(dp[i-1][j] , dp[i-1][j-v[i]] + w[i]);
}
else //放不下第i件物品
dp[i][j] = dp[i-1][j];//放不下的话 前i件物品在容量j条件下的最大价值 就等于 前i-1件物品最大价值
}
}
完全背包
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);//01背包问题后面是dp[i]即用更新过的数据继续向后更新
//所以一个物品可以被无限更新(添加)
//01背包 dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]]+v[i]);
else
dp[i][j] = dp[i-1][j];
}
}
多重背包
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
for(int k=1;k<=s[i] && k*v[i]<=j;k++)//这里加了循环来判断加入k件物品是否会是dp的值更大
{
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);//相当于把k件物品捆绑 不过和01背包没有什么差别
}
}
}
多重背包的二进制优化
//二进制优化 1 2 4 8 16 ........
//二进制优化nb的在于 能表示出来所有情况 就比如7=1+2+4
/*
题目的意思是某物品最多有s件，我们需要从所有的物品中选择若干件，
使这个背包的价值最大。题目并没有说某物品一定需要选多少件出来，也没有说一共要选多少件出来。
只是选择若干件，至于选几件，无所谓，但要保证价值最大。按照优化的策略某物品有s件，
我们给其打包分成了好几个大的物品。
第一个大物品是包含原来该物品的1件，第二个大物品是包含原来该物品的2件，
第三个大物品是包含原来该物品的4件，第四个大物品是包含原来该物品的8件,.....依次类推。
此时我们就把所有的物品都重新进行了一个分类。
原先每个物品最多s件，我们就把这个件数条件给消去了。
取而代之的是，按照一定原先件数组合出来的新若干大物品。
我们又已知按照我们划分成大物品进行搭配组合，一定能转化为原先的若干件小物品出来。
并且选择某物品的最多件数，是不会超过原先该物品的s件。
所以就转化为从下面这些若干件大物品中，选择能使背包容积最大大的情况下，价值最高。
这个就是一个01问题。
*/
int t = 1;
while(t<=s)
{
k++;
v[k] = x * t;
w[k] = y * t;
s-=t;
t *= 2;
}
if(s>0)
{
k++;
v[k] = x * s;
w[k] = y * s;
}
}
for(int i=1;i<=k;i++)
{
for(int j=m;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
分组背包
//k循环在j前面是01背包
//k循环在j后面是分组背包
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=s[i];k++ )//k的循环 和 j的循环 不能换位置 否则意义就变了
// 现在表示的是在j的空间下 第i组元素的最大取值
// 先进行k循环 和01背包没有区别 体现不出分组的概念
if(j>=v[i][k])
dp[j] = max(dp[j],dp[j-v[i][k]]+w[i][k]);
}
}
7:BFS,DfS
一：记忆化搜索+剪枝 DfS 详见 链接
二：DFS模板
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
三：BfS模板
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
8:异或
如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
9：差分
和前缀和相似，有一维差分和二维差分，看适用条件。
10：并查集
模板
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
11：KMP
模板
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
12:字符串哈希
思想是吧字符串转化为一个数，怎么才能确保数不一样呢，那就是采用进制。
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
13：最大公约数 辗转相除法。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
至此，最大公约数为1
京公网安备 11010502036488号