倍增算法：（只往上和）
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;
}
标签：nowsum,int,max,dfs,集训,清北,now,CSP,nownum
From： https://www.cnblogs.com/wan169961/p/17545642.html