倍增算法：（只往上和）
f[i][j] : 从ai 开始的2的j次方个数的最大值
= max(ai + ai+1 + ......+ ai+2^j-1)
f[i][0] = ai
//切一刀：f[i][j] = max(f[i][j - 1] , f[i + 2^(j-1)][j - 1])
Q：一个区间内的最大值 n <= 100000
思路:
l = 2, r = 5 f[2][2];
如果恰好是2的次方 抄答案
else
l = 2 r = 8 -> 4 <= 7 <= 8 -> max(f[2][2], f[5][2])
int n,a[10000][10000]; int x[100000];x//代表长度为i的区间 用两个长度为2^x[i] 的区间能够覆盖 f[100010][20];//j完全可以村吸收存下 int main(){ cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; x[1] = 0; for(int i = 2; i <= n; i++) x[i] = x[i >> 1] + 1; //x[111] = x[55] + 1 for(int i = 1; i <= n; i++) f[i][0] = a[i]; for(int j = 1;(1<<j) <= n; j++) for(int i = 1; i + (1<<j) - 1 <= n; i++) f[i][j] =max(f[i][j- 1], f[i + (1<<(j - 1))][j - 1]) x[1] = 0; for(int i = 2; i <= n; i++) x[i] = x[i >> 1] + 1; //x[111] = x[55] + 1 cin >> m; for(int i = 1; i <= m; i++){ int l,r; cin >> l >> r; int len = r - l + 1; cout << max(f[l][x[len]], f[r - (1 << j) + 1][j] << '\n' ; } }
二分查找算法：（只往下砍）
Q：给出序列a1 ~ an(单调不减)
m次访问， 给出x 求有没有出现x
思路： 从中间砍一刀 ， 左区间最大值为am， 如果x > am ,x在右半部分
如果小于am， 那么x一定出现在左区间，再砍一刀，继续比较……直到只剩一个数的时候停下来（x）
int main(){ cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); cin >> m; for(int i = 1; i <= m; i++){ int x; cin >> x; int l = 0, r = n; //当前x 可能出现的范围 注意：l = 0 while(l + 1 != r){ int m = (l + r) >> 1; if(x <= a[m]) r = m;//当前区间 从l + 1 ~ r变成 l + 1 ~ m else l = m;//当前答案在右边 } if(a[r] == x) cout << "Yes" << endl; //return true; else cout << "No" << endl; // return false; } }
注意：能够二分的问题数据需要具有单调性
习题：
Q：https://ac.nowcoder.com/acm/problem/24866
思路：
什么时候t[i] 小于当前 b[i] ,当前放的就是 b[i] 首歌
前缀和：(单调递增)int main(){ cin >> n; for(int i = 1; i <= n; i++) cin >> b[i]; for(int i = 1; i <= n; i++) a[i] = a[i - 1] + b[i]; sort(a + 1, a + n + 1); cin >> m; for(int i = 1; i <= m; i++){ int x; cin >> x; //找一个最小的aj 使得aj >= x 即可 int l = 0, r = n; while(l + 1 != r){ int m = (l + r) >> 1; if(x <= a[m]) r = m; else l = m; } cout << r << endl; } } /*基本二分答案(写给自己看的，没题目链接)： 找到一个最小的可实现的答案。*/ Code: bool check(int t){// 检查能否在t分钟把所有衣服弄干 int sum = 0; for(int i = 1; i <= n; i++) if(a[i] > t) sum += (a[i] - t - 1) / k + 1;//关键 if(sum <= t) return true; else return false; } int main(){ cin >> n; for(int i = 1;i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); int l = 0, r = 1919810; while(l + 1 != r) { int m = (l + r) >> 1; if(check(m)) r = m; else l = m; } cout << r << endl; }
快速幂：
计算x的y次方（数论）， 将幂次分成几次小运算 int ksm(int x,int y,int p){//x^y%p if(y == 0) return 1; int z = ksm(x,y / 2,p);//z = x ^ (y / 2) % p; z = 1ll * z * z % p;// 1ll 为long long 类型的1 强制类型转化 if(y & 1) z = 1ll = z * x & p; return z; }
矩阵（二维数组）：
用处：
1.加法：矩阵 + 矩阵 = 矩阵们的对应位置相加 ！ 行和列都一样才可以进行
2.减法：矩阵 + 矩阵 = 矩阵们的对应位置相减 ！ 行和列都一样才可以进行
3.乘法：A * B = C
|| || ||
n*m m*k n*m
i 行 j 列 = 去除第一个矩阵的第i行 乘 第二个矩阵的第j列 乘出的数相加
举例；
用处：
1.可以用来做部分动态规划的加速
2. 线性递推
斐波那契数列递推式： f[i] = f[i - 1] + f[i - 2]; struct matrix{//矩阵 int n,m; int a[5][5]; matrix(){ n = m = 0; memset(a,0,sizeof(a)); } }; matrix operator*(const matrix &m1, const matrix &m2){//m1 * m2 注意取地址， 避免重复拷贝值（当我们在使用函数的时候， 参数会拷贝一份） const :乘完了之后，不能改变m1 和 m2的值 matrix m3; m3.n = m1.n; m3.m = m2.m; for(int i = 1; i <= m3.n; i++) for(int j = 1; j <= m3.m; j++) for(int k =1; k <= m1.m; k++)//对应位置相乘 m3.a[i][j] += m1.a[i][k] * m2.a[k][j];//时间复杂度：n^3 所以极限为500或200 更大就一定不是用矩阵乘法完成 return m3; } //由于用了 operator 可以用 m3 = m1 * m2 实现(优雅) matrix ksm(int x,int y){//矩阵快速幂 if(y == 0) { matrix z; z.n = z.m = x.n; for(int i = 1; i <= n; i++) z.a[i][i] = 1; return z; } matrix z = ksm(x, y / 2, z); z = z * z; if(y & 1) z = z * x; return z; }
第一个的列数等于第二行的行数
矩阵乘法的性质：
1.结合律 a * b * c = a * (b * c)
2.没有交换律一说 a * b != b * a
3.分配率 a(b + c) = ab + ac
(a + b)c = ac + bc贪心：
Q：N个数， 求最大的前M个数
思路：
从大到小排序， 求前M个数的和即可
贪心题核心：排序
Q：P1080
恰逢 H 国国庆，国王邀请 nn 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数
，国王自己也在左、右手上各写一个整数。然后，让这 nn 位大臣排成一排，国王站在队伍的最前面。排好队后，
所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的
数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大
臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
思路：
一个人左手很大，他就不应该排在前面；一个人的右手很小，他就不应排在后面
先来比较一下两位大臣时的情况 总共两种情况
struct ren{ int l , r; }a[maxn]; bool cmp(ren x, ren y){//x是否应该站在前面 int v1 = max(a[0].l / x.r, a[0].l * x.l / y.r);// 国王 x y int v2 = max(a[0].l / y.r, a[0].l * y.l / x.r);// 国王 y x if(v1 < v2) return true; else return false; } cin >> n; for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r; //if(n == 2){ //if(cmp(a[1],a[2])); //else swap(a[1], a[2]); //}两个人时候的情况 sort(a + 1, a + n + 1, cmp);//只要保证两个大臣， 这道题就做完了（其实还没有，万恶的高精请自己完成） /*但是我们并不需要两个人的数据， 那我们怎么搞呢？注意，这道贪心题的第一步是判断 但是我们这段代码可以在cmp改进一下： 比较两个max，只取决于四个数的max是谁 等价于我们要在这四个数中找最大值 由于 a[0].l / x.r < a[0].l * y.l / x.r 所以可以删掉 由于 a[0].l / y.r < a[0].l * x.l / y.r 剩下两个数， 我们经过约分， 可得 max(x.l * x.r, y.l * y.r)*/ bool cmp(ren x, ren y){//x是否应该站在前面 int v1 = x.l * x.r;// 国王 x y int v2 = y.l * y.r;// 国王 y x if(v1 < v2) return true; else return false; }
1.假设只有两个数据的时候，得出式子
2.把写出来的式子进行排序
t2:
山洞体积为V
搬运物品过程中要占据b[i]使用的体积的
第i个物品要占据a[i] 的体积 能否把物品全部放下
思路 ：
当然是贪心！(学的就是贪心)
要决定搬物品的顺序 使用的体积的最小
当共有两件物品的时候：
先搬1：V = max(a1, a2 + a1, b1, b2 + a1)
先搬2：V = max(b1, b2, a2 + b1, a1 + a2)
bool cmp(ren x, ren y){//x是否应该站在前面 int v1 = max(a1, a2 + a1, b1, b2 + a1)//完整代码请自行补充 int v2 = max(b1, b2, a2 + b1, a1 + a2) if(v1 < v2) return true; else return false; }
搜索：
基本形式：DFS、BFS
Q:dfs 查找 前m个最大的数的和 (沿着一条路走到黑)void dfs(int now, int nownum, int nowsum){//当前要看第now个元素选不选 已经选了nownum 以精选的书和是nowsum if(now > n){ if(nownum == m) ans = max(ans, nowsum); return ; } dfs(now + 1, nownum, nowsum)//不选 dfs(now + 1, nownum + 1, nowsum + a[now]);//选 } int main(){ cin >> n >> m; for(int i = 1; i <= 1; i++)cin >> a[i]; dfs(1, 0 , 0); cout << ans << endl; return 0; }
bfs查找 一个网格里面有若干障碍物，求如何到终点
把起点表为零 把他周围的点标记为1 再往外走标记为2步 以此类推 如果到达终点就停止拓展 即答案 并且要保证每个状态只被走一次
#include<bits/stdc++.h> using namespace std; int n,m,a[1005][1005]; int sx,sy;//起点 int tx,ty;//终点 int step[1005][1005]; //step[i][j]代表从起点走到(i,j)需要走多少步 int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; signed main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];//a[i][j]==1代表有障碍物 cin>>sx>>sy>>tx>>ty; memset(step,-1,sizeof(-1)); step[sx][sy]=0; /* struct pair{ int first; int second; }; */ queue<pair<int,int> > q;//用来存能够向外进行拓展step的点 q.push(make_pair(sx,sy)); while(q.size()){ int x=q.front().first; int y=q.front().second; q.pop();//当前的点为(x,y) for(int i=0;i<4;i++){//枚举上下左右四个方向 int xx=x+dx[i]; int yy=y+dy[i];//从(x,y)走到了(xx,yy) if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]!=1&&step[xx][yy]==-1){ step[xx][yy]=step[x][y]+1; q.push(make_pair(xx,yy)); } } } }
搜索问题分类：
1.最优解问题 有多个可行解求最优解
2.可行解问题 找到一组符合条件的解
3.解数量问题 有多少组解
什么样的问题用BFS：
1.保证该问题是最优解问题
2.一定求的是最小步数(每操作一次的代价只有一)
什么样的问题用DFS： 剩余的所有情况都用DFS
优化搜索的技巧：
1.剪枝 少走一些无用状态 */
Q1：void dfs(int now, int nownum, int nowsum){//当前要看第now个元素选不选 已经选了nownum 以精选的书和是nowsum //if(nownum > n) return;优化 可行性剪枝 大于范围 一定不合法 //if(nownum + n - now + 1 < m) return; 全加上都到不了范围 一定不合法 //if(nowsum + sum[n] - sum[now] - 1 <= ans) return;都选上之后 还是没有能够超过ans的选择方案 所以break : 最优性剪枝 if(now > n){ if(nownum == m) ans = max(ans, nowsum); return ; } dfs(now + 1, nownum, nowsum)//不选 dfs(now + 1, nownum + 1, nowsum + a[now]);//选 } int main(){ cin >> n >> m; for(int i = 1; i <= 1; i++)cin >> a[i]; dfs(1, 0 , 0); cout << ans << endl; return 0; }
应试优化技巧：卡时 由于搜索很容易超时 然而我们不会优化代码 所以我们卡个计时器 到最后一刻的时候停下搜索将当前最优解输出 因为超时一定是0分 但是我们用我们的ans可以 >= 0 分 好多了呀
#include <ctime> #include <cstdlib> void dfs(int now, int nownum, int nowsum){//当前要看第now个元素选不选 已经选了nownum 以精选的书和是nowsum clock();//代表程序运行了多久 单位在win上是毫秒 在vin、洛谷 等是纳秒 if(1000 * clock() > 950 / CLOCKS_PER_SEC){ cout << ans << endl; exit(0);//卡时 } if(now > n){ if(nownum == m) ans = max(ans, nowsum); return ; } dfs(now + 1, nownum, nowsum)//不选 dfs(now + 1, nownum + 1, nowsum + a[now]);//选 } int main(){ cin >> n >> m; for(int i = 1; i <= 1; i++)cin >> a[i]; dfs(1, 0 , 0); cout << ans << endl; return 0; }
应试技巧：改变搜索顺序
自拟顺序
void dfs(int now, int nownum, int nowsum){//当前要看第now个元素选不选 已经选了nownum 以精选的书和是nowsum if(now > n){ if(nownum == m) ans = max(ans, nowsum); return ; } dfs(now + 1, nownum, nowsum)//不选 dfs(now + 1, nownum + 1, nowsum + a[now]);//选 } int main(){ cin >> n >> m; for(int i = 1; i <= 1; i++)cin >> a[i]; random_shuffle(a + 1, a + n + 1); dfs(1, 0 , 0); cout << ans << endl; return 0; }