蓝桥杯C++AB算法辅导

1.1 教学计划与递归

很不错的解释

92. 递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式
输入一个整数 n。

输出格式
每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围
1≤n≤15
输入样例：
3
输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

//y总
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 16;

int n;
int st[N];  // 状态，记录每个位置当前的状态：0表示初始还没判断，1表示选它，2表示不选它

void dfs(int u)
{
    if (u > n)//u从1开始, 当n个位置确定时 u == n + 1 
    {
        for (int i = 1; i <= n; i ++ )
            if (st[i] == 1)
                printf("%d ", i);
        printf("\n");
        return;
    }

    st[u] = 2;
    dfs(u + 1);     // 第一个分支：不选
    st[u] = 0;  // 恢复现场

    st[u] = 1;
    dfs(u + 1);     // 第二个分支：选
    st[u] = 0;
}

int main()
{
    cin >> n;

    dfs(1);//从1开始

    return 0;
}


#include<iostream>
using namespace std;
int n;
//用二进制状态压缩,也就是用二进制上的位来记录数有没有被用过。
// u是当前枚举到的数，state是二进制数记录哪些数被选
void dfs(int u ,int state){
    if( u == n){
        for(int i = 0; i< n; i++)
            //判断第i位是不是1，如果是1就代表被选，输出
            if(state >> i & 1) 
                //第几位就代表输出几，只不过不是从0开始，而是从1开始
                cout << i + 1 << " ";
        cout << endl;
        return;
    }
    // 不用这个数，第u位不动
    dfs(u + 1, state); 
    // 用这个数，把第u位变成1
    // 运算优先级： 左移高于位运算|
    dfs(u + 1, state | 1 << u);  


}

int main()
{

    cin >> n;
    /*
    回顾一下dfs参数的含义：
        - u是当前枚举到的数，
        -state是二进制数记录哪些数被选

    则 dfs(0, 0)表示：当前枚举到0，没有数被选

    */ 
    dfs(0, 0);

}

//详细注释版
//作者：ShizhengLee 链接：https://www.acwing.com/solution/content/41249/



/*

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n,a[N];

void dfs(int k){
    for(int i=1;i<k;++i)
        cout << a[i] << ' ';
    cout << endl;

    if(k > n)
        return;

    for(int i=a[k-1]+1;i<=n;++i){
        a[k] = i;
        dfs(k+1);
    }
}

int main()
{
    cin >> n;
    dfs(1);
    return 0;
}
*/

94. 递归实现排列型枚举

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式
一个整数 n。

输出格式
按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围
1≤n≤9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

全排列满足字典序最小，根据递归第一轮满足字典序最小之后也最小

全排列：dfs基础

#include<iostream>

using namespace std;

const int N = 10;
int path[N];
bool st[N];
int n;
void dfs(int u)//当前位u
{
    if(u == n)
    {
        for(int i = 0;i < n;i++)printf("%d ",path[i]);
        puts("");
    }
    
    for(int i = 1;i <= n;i++)
    {
        if(!st[i])
        {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            path[u] = 0;//恢复现场，但其实path因为会被覆盖，所以这步可以省略【简单理解：全排列枚举所有结果就要恢复现场】
            st[i] =false;
        }
    }
}

int main()
{
    
    cin >> n;
    
    dfs(0);
        
    return 0;
}

717. 简单斐波那契

以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。

这个数列从第 3 项开始，每一项都等于前两项之和。

输入一个整数 N，请你输出这个序列的前 N 项。

输入格式
一个整数 N。

输出格式
在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。

数据范围
0<N<46
输入样例：
5
输出样例：
0 1 1 2 3
存储Fib版

#include<iostream>
using namespace std;

const int N = 50;
int f[N];
int n;
int main()
{
    cin >> n;
    f[1] = 0 ,f[2] = 1;//下标从1开始 (也可以从0开始)
    for(int i = 3;i <= n;i++)f[i] = f[i - 1] + f[i - 2];
    
    for(int i = 1 ;i <= n;i ++)printf("%d ",f[i]);
    
    return 0;
}

不开数组版:滚动数组 - dp雏形
注意Fib当n超过46就需要开高精度了

#include<stdio.h>
typedef long long LL;
LL n,a = 0, b = 1, c;//a第一项，b第二项，下一项c = a + b ， a，b位置再往后移动
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        printf("%d ",a); //a每轮表示第i项  从1开始
        c=a+b;
        a=b,b=c;
    }
}

95. 费解的开关

你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。

数据范围
0<n≤500
输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：

3
2
-1

核心：上一行的状态能确定下一行的状态
枚举前n-1行即可确定全部状态[前n-1规定每行全变亮, 则最后只需判断最后一行是不是全亮]
(先把第一行的状态拆分二进制,则有$2^5$的分支去转移到下一行)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6;//字符串末尾'\0''

char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};//上下左右+自身

void turn(int x, int y)//相邻十字型翻转: (x, y)以及上下左右5个位置翻转
{
    for (int i = 0; i < 5; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;   // 在边界外, 直接忽略即可
        g[a][b] ^= 1;//字符类型的0与1互转【异或】: ASCLL码中0为48, 1为49 二进制仅最后一位1不同-->'0'^1 = '1'; '1'^1= 0 
    }
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        for (int i = 0; i < 5; i ++ ) scanf("%s", g[i]);//字符串读入

        int res = 10;
        for (int op = 0; op < 32; op ++ )//枚举第一行5个灯按或不按 [2^5种操作方式]
        {
            memcpy(backup, g, sizeof g);//每轮需要恢复成原始状态g, 先备份到backup
            int step = 0;
            for (int i = 0; i < 5; i ++ )//按下去就改变自身和上下左右四个格子, 即翻转5个格子
                if (op >> i & 1)//第一行有暗的就要按
                {
                    step ++ ;
                    turn(0, i);
                }

            for (int i = 0; i < 4; i ++ )//枚举确定的第1行以及234行,使得1234全亮
                for (int j = 0; j < 5; j ++ )
                    if (g[i][j] == '0')
                    {
                        step ++ ;
                        turn(i + 1, j);//中间行按法：如果这个位置是灭的，就按下一行对应的位置
                    }

            bool dark = false;//标记是否有暗的灯 
            for (int i = 0; i < 5; i ++ )//遍历最后一行判断是否全亮
                if (g[4][i] == '0')
                {
                    dark = true;//最后一行有暗的, 此轮失败
                    break;
                }

            if (!dark) res = min(res, step);//若最后一行全亮, 判断更新答案
            memcpy(g, backup, sizeof g);//判断下一轮状态, 恢复初始g
        }

        if (res > 6) res = -1;//限制5步, 超过5步返回-1

        cout << res << endl;
    }

    return 0;
}

1.2 递推与递归——习题课

93. 递归实现组合型枚举

从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式
两个整数 n,m ,在同一行用空格隔开。

输出格式
按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25
输入样例：
5 3
输出样例：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
思考题：如果要求使用非递归方法，该怎么做呢？

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 30;

int n, m;
int way[N];

void dfs(int u, int start)//当前位置下标u，当前选择的数值start【为了满足字典序】
{	//可加剪枝优化但不是记忆点 (挖掘条件得出):开始start到结束n长度不足剩下要填未确定的位置m - u
    if(n - start < m - u) return;  // 剪枝优化【减少时间，不影响结果】
    if (u == m + 1)
    {
        for (int i = 1; i <= m; i ++ ) printf("%d ", way[i]);
        puts("");
        return;
    }

    for (int i = start; i <= n; i ++ )
    {
        way[u] = i;
        dfs(u + 1, i + 1);//下一位，条件：下一个值比当前位值i大,即i+1（从小到大即可满足字典序）
        way[u] = 0; // 恢复现场【可不写，因为下一次覆盖上一次的值】
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    dfs(1, 1);

    return 0;
}

1209. 带分数

100 可以表示为带分数的形式：100=3+69258714
还可以表示为：100=82+3546197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。

类似这样的带分数，100 有 11 种表示法。

输入格式
一个正整数。

输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围
1≤N<$10^6$
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6

//y总思路：全排列 + 划分枚举a、c，判断b是否成立 ，等式 n == a + b / c 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
bool st[N], backup[N];
int ans;

bool check(int a, int c)//检查b，等式是否成立
{	//可以开个全局LL
    long long b = n * (long long)c - a * c;  //n = a + b / c 鉴于int向上取整,两边同乘c避开int特性: n * (long long c) == a * c + b

    if (!a || !b || !c) return false;  //a,b,c中含有0，false

    memcpy(backup, st, sizeof st); //使用备份数组，复制原标记数组
    while (b)
    {
        int x = b % 10;     // 取个位
        b /= 10;    // 个位删掉
        if (!x || backup[x]) return false; //x不为0且x被标记过（a或c已经使用），则b不能选此数，false
        backup[x] = true;
    }

    for (int i = 1; i <= 9; i ++ )//1-9没有全部用上，false
        if (!backup[i])
            return false;

    return true;
}

void dfs_c(int u, int a, int c) //当前位u ， a的值 ， c的值
{
    if (u > 9) return;

    if (check(a, c)) ans ++ ;

    for (int i = 1; i <= 9; i ++ )
        if (!st[i])
        {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;
        }
}

void dfs_a(int u, int a)//枚举a 
{
    if (a >= n) return; //a > n 等式不成立，剪枝
    if (a) dfs_c(u, a, 0); 

    for (int i = 1; i <= 9; i ++ )
        if (!st[i])
        {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i); //判断下一组a，a加位数
            st[i] = false;
        }
}

int main()
{
    cin >> n;

    dfs_a(0, 0);

    cout << ans << endl;

    return 0;
}

next_permutation

#include <bits/stdc++.h>
using namespace std;
int num[10] = {1,2,3,4,5,6,7,8,9};  //[1-9]
int cnt;

int get(int l,int r)  //区间[l, r]组成一个数
{
  int sum = 0;
  for(int i = l; i <= r; i++)
  {
    sum = sum * 10 + num[i];
  }
  return sum;
}

int main()
{
  int n;
  cin >> n;
  while(next_permutation(num, num + 9)) //【全排列】
  {
    for(int i = 0;i < 9; i++) //枚举a的位数
    {
      int a = get(0, i);
      for(int j = i + 1; j < 9; j++) //枚举b与c的分界位数
      {
        int b = get(i + 1, j); 
        int c = get(j + 1, 8);
        if(n * c == a * c + b)
        {
          cnt ++;
        }
      }
    }
  }
  cout << cnt;
  return 0;
}

116. 飞行员兄弟

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。

但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式
输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式
第一行输出一个整数 N，表示所需的最小切换把手次数。

接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围
1≤i,j≤4
输入样例：

	-+--
	----
	----
	-+--

输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4

最优解：每个开关只用一次
此题按一次影响行列【十字型】 与费解的开关不同的是，每个灯泡会受到不同的开关的影响
最小字典序：矩阵0-15编号–>二进制枚举–>从小到大即满足
最一般情况【总结通用性公式】：难度究极版 ： 208.开关问题【可高斯消元求解】

数组写法

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
 
const int N = 5;

char g[N][N], backup[N][N];//字符存储

int get(int x, int y)//矩阵位置坐标映射成[0, 15] --> 在二进制操作中为第几位
{
    return x * 4 + y;
}

void turn_one(int x, int y)//翻转每格
{
    if (g[x][y] == '+') g[x][y] = '-';
    else g[x][y] = '+';
}

void turn_all(int x, int y)//十字型翻转
{
    for (int i = 0; i < 4; i ++ )//行列翻转
    {
        turn_one(x, i);//x行翻转
        turn_one(i, y);//y列翻转
    }

    turn_one(x, y);//交叉点被翻了两次抵消了, 需再翻一次
}

int main()
{
    for (int i = 0; i < 4; i ++ ) cin >> g[i];//读入字符串

    vector<PII> res;
    for (int op = 0; op < 1 << 16; op ++ )//枚举所有的操作, 每个位置按或不按(1或0) ==> 共2^16 (小于10^6)  的op 方案数   
    {
        vector<PII> temp;//临时存放每轮操作位置的坐标
        memcpy(backup, g, sizeof g);        // 备份初始状态

        // 进行操作
        for (int i = 0; i < 4; i ++ )
            for (int j = 0; j < 4; j ++ )
                if (op >> get(i, j) & 1)//映射开关的下标[0, 15]-->op的开关映射的位置&1-->算出每轮对应位状态按或不按[1或0]
                {
                    temp.push_back({i, j});//放入操作答案路径
                    turn_all(i, j);//对i, j进行十字型范围翻转操作
                }

        // 判断所有灯泡是否全亮
        bool has_closed = false;//标记
        for (int i = 0; i < 4; i ++ )
            for (int j = 0; j < 4; j ++ )
                if (g[i][j] == '+')
                    has_closed = true;//若遇到加号说明有关闭的, 没有全部打开

        if (has_closed == false)//说明全部关闭, 更新res , 属性min
        {
            if (res.empty() || res.size() > temp.size()) res = temp;//若为空说明还没有合法方案 或 有更优解更新
        }

        memcpy(g, backup, sizeof g);        // 还原成初始状态, 新一轮判断
    }

    cout << res.size() << endl;
    for (auto op : res) cout << op.x + 1 << ' ' << op.y + 1 << endl;

    return 0;
}

位运算写法-二进制优化

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> PII;
const int N = 4, INF = 100;

int change[N][N];

int get(int x, int y)
{
    return x * N + y;
}

int main()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
        {
            for (int k = 0; k < N; k ++ ) change[i][j] += (1 << get(i, k)) + (1 << get(k, j));
            change[i][j] -= 1 << get(i, j);
        }

    int state = 0;
    for (int i = 0; i < N; i ++ )
    {
        string line;
        cin >> line;
        for (int j = 0; j < N; j ++ )
            if (line[j] == '+')
                state += 1 << get(i, j);
    }

    vector<PII> path;
    for (int i = 0; i < 1 << 16; i ++ )
    {
        int now = state;
        vector<PII> temp;
        for (int j = 0; j < 16; j ++ )
            if (i >> j & 1)
            {
                int x = j / 4, y = j % 4;
                now ^= change[x][y];
                temp.push_back({x, y});
            }
        if (!now && (path.empty() || path.size() > temp.size())) path = temp;
    }

    cout << path.size() << endl;
    for (auto &p : path)
        cout << p.first + 1 << ' ' << p.second + 1 << endl;

    return 0;
}

1208. 翻硬币

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式
一个整数，表示最小操作步数

数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：

**********
o****o****

输出样例1：
5
输入样例2：

*o**o***o***
*o***o**o***

输出样例2：
1

初始状态变化到目标状态 ：常用BFS
仅限定一次翻转即为最优解

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
char start[N], aim[N]; //记录初始 -->目标状态  ，【不能用end 或 y : 库函数重名】


void turn(int i)
{
    if (start[i] == '*') start[i] = 'o';
    else start[i] = '*';
}

int main()
{
    cin >> start >> aim;//输入字符串 [一维char数组]
    n = strlen(start);//char数组长度

    int res = 0;
    for (int i = 0; i < n - 1; i ++ )//翻转到倒二个，包含倒一
        if (start[i] != aim[i])
        {
            turn(i), turn(i + 1);//依题意翻转
            res ++ ;//翻转次数
        }

    cout << res << endl;
    return 0;
}

2.1 二分与前缀和

789. 数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1

二分定位
首先判断能否使用二分：依据题目找到二分前提：升序排列区间

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);  //没有&时 ：Segmentation Fault   

    for (int i = 0; i < m; i ++ )
    {
        int x;
        scanf("%d", &x);
        // 二分x的左端点
        int l = 0, r = n - 1;   // 确定区间范围
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid; //左->右,x在找到的区间的最大值[l = 0 , x] ,找大于等于x的第一个位置
            else l = mid + 1;
        }

        if (q[r] == x) //若找到左->右的x下标
        {
            cout << r << " "; 

            // 二分x的右端点
            r = n - 1;  // 右端点一定在[左端点, n - 1] 之间   
            while (l < r)
            {
                int mid = l + r + 1 >> 1;   // 因为写的是l = mid，所以需要补上1
                if (q[mid] <= x) l = mid;//右->左 x在找到的区间的最小值[x , r = n - 1] ,找小于等于x的第一个位置
                else r = mid - 1;
            }
            cout << r << endl;
        }
        else cout << "-1 -1" << endl;
    }

    return 0;
}

790. 数的三次方根

给定一个浮点数 n，求它的三次方根。

输入格式
共一行，包含一个浮点数 n。

输出格式
共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000

浮点二分有细节,但easy

$y=x^3$ 具有有单调性可以二分,但不是只有单调性才可以二分。
[单调性为二分的充分不必要条件]
确定满足二分-->确定区间-->确定二段性（判断条件）

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    double x;
    cin >> x;
    double l = -10000, r = 10000;//区间范围
    while (r - l > 1e-8)//误差精度范围 结果所在区间[l,r] < 1e-8    
    {
        double mid = (l + r) / 2;//double类型不能位运算 >> 1
        if (mid * mid * mid >= x) r = mid; //浮点数的二分好处，都是mid
        else l = mid;
    }

    printf("%lf\n", l);//double默认6位

    return 0;
}

795. 前缀和

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式
第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式
共 m 行，每行输出一个询问的结果。

数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10

前缀和模板
注意下标用到i-1，s前缀和数组下标从1开始存放

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N];   // 表示原数组
int s[N];   // 表示前缀和数组

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ )//用到下标i-1 ,下标从1开始
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];//前缀和数组
    }

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}

796. 子矩阵的和

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式
共 q 行，每行输出一个询问的结果。

数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21

二维前缀和：容斥原理
构造二维前缀和矩阵 : $S_{x,y}=S_{x-1,y}+S_{x,y-1}-S_{x-1,y-1}+a_{x,y}$
用前缀和矩阵得到子矩阵的和 :给出(x1,y1)(x2,y2)求和: $S_{x2,y2}-S_{x1-1,y2}-S_{x2,y1-1}+S_{x-1,y-1}$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];//二维前缀和公式
        }

    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);//子矩阵求和
    }

    return 0;
}

2.2 二分与前缀和——习题课

730. 机器人跳跃问题

机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。

编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑高度为 H(i) 个单位。

起初，机器人在编号为 0 的建筑处。

每一步，它跳到下一个（右边）建筑。

假设机器人在第 k 个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。

如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1) 的能量值。

游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式
第一行输入整数 N。

第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。

输出格式
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围
1≤N,H(i)≤105,

输入样例1：
5
3 4 3 2 4
输出样例1：
4
输入样例2：
3
4 4 4
输出样例2：
4
输入样例3：
3
1 6 4
输出样例3：
3

发现规律+单调性可二分

规律： e’ = 2 * e - h
发现随着e增大 2 * e - h也增大 --> 具有单调性 —> 二分寻找答案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int h[N];

bool check(int e)//机器人是否合法通过
{
    for (int i = 1; i <= n; i ++ )
    {
        e = e * 2 - h[i];
        if (e < 0) return false;//能量e在过程不能小于0
        if (e >= 1e5) return true;//超过必定满足,只会越来越大 , 且不断增加会导致溢出, 需提前终止 
    }
    return true;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);

    int l = 0, r = 1e5;//若e > 10^5  2 * e - h > 10^5 : 只需枚举[l,r] = [0,10^5]
    while (l < r)//O(logn)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);//也可以L

    return 0;
}

1221. 四平方和

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去，就正好可以表示为 4 个数的平方和。

比如：

5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 4 个数排序：

0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。

输入格式
输入一个正整数 N。

输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。

数据范围
0<N<$5\ast 10^6$
输入样例：
5
输出样例：
0 0 1 2

空间换时间

算法思想:
先枚举$c^2+d^2$的所有值存入数组, 令sum = n - $c^2+d^2$, 枚举$a^2+b^2$过程中判断是否出现在标记数组中
【是否C[sum](或D[sum])被标记】, 输出ans{a, b, C[sum], D[sum]};

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e6 + 10;

int n;

int C[N], D[N]; //存c与d的平方和为下标sum, c = C[sum],d = D[sum]  

int main()
{
    cin >> n;

    memset(C, -1, sizeof C);

    for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ ){
            int sum = c * c + d * d;
            if (C[sum] == -1)
                C[sum] = c, D[sum] = d; //hash表<sum,对应组成c>  , <sum,对应组成d>
        }

    for (int a = 0; a * a <= n; a ++ )
        for (int b = a; a * a + b * b <= n; b ++ ){
            int sum = n - a * a - b * b;
            if (C[sum] != -1){
                printf("%d %d %d %d\n", a, b, C[sum], D[sum]);
                return 0;
            }
        }
    return 0;
}

二分 $O(N2logN)$ 2721ms

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

struct Sum
{
    int s, c, d;
    bool operator< (const Sum &t)const
    {
        if (s != t.s) return s < t.s;
        if (c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];

int n, m;

int main()
{
    cin >> n;

    for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
            sum[m ++ ] = {c * c + d * d, c, d};//结构体按默认顺序赋值

    sort(sum, sum + m);//重载<

    for (int a = 0; a * a <= n; a ++ )
        for (int b = 0; a * a + b * b <= n; b ++ )
        {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;//范围
            while (l < r)//查找最后另一组平方和 a * a + b * b 
            {
                int mid = l + r >> 1;
                if (sum[mid].s >= t) r = mid;
                else l = mid + 1;
            }
            if (sum[l].s == t)//若存在输出答案
            {
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }

    return 0;
}

1227. 分巧克力

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。

切出的巧克力需要满足：

形状是正方形，边长是整数
大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行包含两个整数 Hi 和 Wi。

输入保证每位小朋友至少能获得一块 1×1 的巧克力。

输出格式
输出切出的正方形巧克力最大可能的边长。

数据范围
1≤N,K≤$10^5$,
1≤Hi,Wi≤$10^5$
输入样例：
2 10
6 5
5 6
输出样例：
2

单调性可二分

首先判断单调性【随着选取切除的边长越大切出的块数越少：单调递减==>可以二分】
边长x, 切出的块数res(需满足res >= k) 边长为x最多切的块数为: $\lfloor \frac{w}{x}\rfloor \ast \lfloor \frac{h}{x}\rfloor$ (向下取整)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, k;
int h[N], w[N];

bool check(int mid) //判断边长mid能否切k块 
{
    int res = 0;//边长为mid时能切的块数res
    for (int i = 0; i < n; i ++ )//共n块巧克力来切
    {
        res += (h[i] / mid) * (w[i] / mid);// (向下取整) (长 / 划分的边长mid) * (宽 / 划分的边长mid)   [小学划分easy]
        if (res >= k) return true;//能切k块
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &h[i], &w[i]);

    int l = 1, r = 1e5;//边长至少1 * 1 ,左边界L从1开始, 且右边界R不超过W或H (长宽) 
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;//边长为mid能切k块,往更大的尝试,找最大
        else r = mid - 1;//mid不满足,则在试试[1,mid - 1] 找满足的
    }

    printf("%d\n", r);

    return 0;
}

99. 激光炸弹

地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式
第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来 N 行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。

输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围
0≤R≤$10^9$
0<N≤10000,
0≤Xi,Yi≤5000
0≤Wi≤1000
输入样例：
2 1
0 0 1
1 1 1
输出样例：
1

前缀和下标从1开始
边长r ： 能炸的目标数量 (r - 1) * (r - 1) ： 价值用前缀和优化枚举[给的是坐标]

数据范围分析：

0 < x,y < 5000 , 则R最多也就取5000 $R^2=2.5\ast 10^7<10^8$ 可AC
2 * 2.5*1e7 / 1024 / 1024 = 200MB > 168MB（超过题目限制,不能开两个数组）

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010;

int n, m;
int s[N][N];

int main()
{
    int cnt, R;
    cin >> cnt >> R;
    R = min(5001, R);

    n = m = R;//枚举
    while (cnt -- )
    {
        int x, y, w;
        cin >> x >> y >> w;
        x ++, y ++ ;//编写细节最为重要, 前缀和用到i-1从1开始可以不用判断边界
        n = max(n, x), m = max(m, y);
        s[x][y] += w;
    }

    // 预处理前缀和
    for (int i = 1; i <= n; i ++ )//从1开始
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int res = 0;

    // 枚举所有边长是R的矩形，枚举(i, j)为右下角
    for (int i = R; i <= n; i ++ )
        for (int j = R; j <= m; j ++ )
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]); //即(i-R+1,j-R+1) 到 (i,j)

    cout << res << endl;

    return 0;
}

1230. K倍区间

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式
输出一个整数，代表 K 倍区间的数目。

数据范围
1≤N,K≤100000,
1≤Ai≤100000
输入样例：
5 2
1
2
3
4
5
输出样例：
6

暴力双重枚举区间,看是不是k的倍数:【TLE】

前缀和优化 + 区间差值==k倍数(常用等效法) + 余数组合:

思路：
①以i为右端点的区间, (s[i] - s[i - 1] ~ s[i] - s[0] ) 有多少个区间值 % k == 0
②转化成s[i] - s[j] % k == 0 <==> s[j] % k == s[i] % k 余数是否相等【相等说明这一段的数的和是k的倍数】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;//从n个数中找区间为k的倍数
LL s[N], cnt[N];// s[N]最大10^10    cnt数组：cnt[x]:余数为x的数有多少

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ )//构造前缀和
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    LL res = 0;
    cnt[0] = 1;//一个都不选,则余数为0,初始有1个 
    for (int i = 1; i <= n; i ++ )//枚举右端点
    {   //res一开始是表示的相减满足题目的条件，因为一旦再出现%k和res数组里面有相当的情况，就全加一遍（和前面全部组合一遍）
        res += cnt[s[i] % k];//加上新增的组合[2个相同就有1个k倍区间]
        cnt[s[i] % k] ++ ;//统计 前缀和 % k 余数个数
    }

    printf("%lld\n", res);

    return 0;
}

3.1 数学与简单DP

1205. 买不到的数目

小明开了一家糖果店。

他别出心裁：把水果糖包成4颗一包和7颗一包的两种。

糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。

当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。

大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式
两个正整数 n,m，表示每种包装中糖的颗数。

输出格式
一个正整数，表示最大不能买到的糖数。

数据范围
2≤n,m≤1000，
保证数据一定有解。

输入样例：
4 7
输出样例：
17

数论公式
小学数二结论题(证明略)：若两个整数p、q互质 ，则p,q不能凑出的最小整数为 (p - 1)*(q - 1) - 1

#include <iostream>

using namespace std;

int n,m;

int main()
{
    cin >> n >> m;
    cout << (n - 1) * (m - 1) - 1 << endl;
    return 0;
}

1211. 蚂蚁感冒

转换思路：掉头等价于穿过
a[0] > 0感冒的左边：向左不会碰（先走出去），向右不会碰（感冒先走出去） , 感冒的右边：向左会碰,向右不会碰（先走出去）
再结合相遇掉头：感冒右边的向左会碰与向右不会碰还要分类【如果左边有则会掉头，则右边会被感染】
a[0] < 0感冒的左边：向左不会碰（先走出去），向右会碰 , 感冒的右边：向左不会碰（感冒先走出去）,向右不会碰（先走出去）
再结合相遇掉头：感冒左边的向右会碰与向右不会碰还要分类【如果右边有则会掉头，则左边会被感染】

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int left = 0, right = 0;    // 分别表示左边向右走的蚂蚁数量，和右边向左走的蚂蚁数量
    for (int i = 1; i < n; i ++ )
        if (abs(a[i]) < abs(a[0]) && a[i] > 0) left ++ ;
        else if (abs(a[i]) > abs(a[0]) && a[i] < 0) right ++ ;

    if (a[0] > 0 && right == 0 || a[0] < 0 && left == 0) cout << 1 << endl;//这种情况仅自己，不会碰到别的蚂蚁
    else cout << left + right + 1 << endl;//左边有则回头时右边也会碰，再加上自己

    return 0;
}

1216. 饮料换购

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料，凭3个瓶盖可以再换一瓶C型饮料，并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n 瓶饮料，最后他一共能喝到多少瓶饮料。

输入格式
输入一个整数 n,表示初始买入的饮料数量。

输出格式
输出一个整数，表示一共能够喝到的饮料数量。

数据范围
0<n<10000
输入样例：
100
输出样例：
149

简单模拟

#include<iostream>

using namespace std;

int n,res;

int main()
{
    cin >> n;
    res += n;
    while(n / 3)//y总 : n >= 3
    {
        res += n / 3;
        n = n / 3 + n % 3; 
    }

    cout << res << endl;

    return 0;
}

2. 01背包【详细版】

从1开始存放
朴素：

#include <iostream>
using namespace std; 
#include<algorithm>
const int N = 1010;
int v[N],w[N];//体积，价值
int dp[N];
int f[N][N]; //爆栈会直接导致无法编译 , 各种问题 
int n,m;

int main()
{
	cin >> n >> m ;
	
	for(int i = 1;i <= n;i++) cin >>  v[i] >> w[i]; 
	
	for(int i = 1;i <= n;i++)
		for(int j = v[i];j <= m;j++) //0~v[i]之前放不下，没有意义
		{
			f[i][j] = f[i-1][j]; //左边状态			
			if(j >= v[i]) f[i][j] = max(f[i][j] , f[i-1][j - v[i]] + w[i]);	 //右边状态 
		}//【j-1中选出的最大值+选了i后+w[i]即】	
	cout << f[n][m] << endl; 
	
	return 0;
}

一维优化：

#include <iostream>
using namespace std; 
#include<algorithm>
const int N = 1010;
int n,m; //种类n ， 体积m
int v[N],w[N];//体积，价值
int dp[N];


//【由去掉一维，发现状态==i-1，不对，则j从m开始到v[i]，j-v[i]还没有更新，等效i-1的，可降成一维】
//【可优化原因】：分两种讨论用的j和j-v[i] <= j且i的用f(i-1)状态，滚动
//转化成一维： - 滚动数组 
int main() 
{
	cin >> n >> m ;
	
	for(int i = 1;i <= n;i++) cin >>  v[i] >> w[i];
	
	for(int i = 1;i <= n;i++)
		for(int j = m;j >= v[i];j--)   //若正的取变成 f[i][j - v[i]] + w[i]  而不是i-1
			dp[j] = max(dp[j] , dp[j - v[i]] +w[i]);
			
	cout << dp[m] << endl;  //体积取m时，最大价值dp[m]
		
	return 0;
}

边输出边处理：

#include <iostream>
using namespace std; 
#include<algorithm>
const int N = 1010;
int n,m; //种类n ， 体积m
int v[N],w[N];//体积，价值
int dp[N];


//【由去掉一维，发现状态==i-1，不对，则j从m开始到v[i]，j-v[i]还没有更新，等效i-1的，可降成一维】
//【可优化原因】：分两种讨论用的j和j-v[i] <= j且i的用f(i-1)状态，滚动
//转化成一维： - 滚动数组 
int main() 
{
	cin >> n >> m ;
	
	for(int i = 1;i <= n;i++) cin >>  v[i] >> w[i];
	
	for(int i = 1;i <= n;i++)
		for(int j = m;j >= v[i];j--)   //若正的取变成 f[i][j - v[i]] + w[i]  而不是i-1
			dp[j] = max(dp[j] , dp[j - v[i]] +w[i]);
			
	cout << dp[m] << endl;  //体积取m时，最大价值dp[m]
		
	return 0;
}

1015. 摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

输入格式
第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

数据范围
1≤T≤100,
1≤R,C≤100,
0≤M≤1000
输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16

#include<cstdio>
#include<algorithm>

using  namespace std;

const int N = 110;

int w[N][N];
int f[N][N];

int main()
{
    int T;
    scanf("%d", &T);
    int n, m;
    while(T --)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) //用到f[i-1][j]   f[i][j-1]
            for(int j = 1; j <= m; j++)
                scanf("%d", &w[i][j]);

        for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];

        printf("%d\n", f[n][m]);
    }
    return 0;
}

895. 最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
经典DP：最长上升子序列
f[i]表示从第一个数字开始算，以a[i]结尾的最大的上升序列

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];

int main()
{
    cin >> n ;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);

        res = max(res, f[i]);
    }

    cout << res << endl;

    return 0;
}

3.2 数学与简单DP——习题课

1212. 地宫取宝

X 国王有一个地宫宝库，是 n×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。

输入格式
第一行 3 个整数，n,m,k，含义见题目描述。

接下来 n 行，每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。

输出格式
输出一个整数，表示正好取 k 个宝贝的行动方案数。

该数字可能很大，输出它对 1000000007 取模的结果。

数据范围
1≤n,m≤50,
1≤k≤12,
0≤Ci≤12
输入样例1：
2 2 2
1 2
2 1
输出样例1：
2
输入样例2：
2 3 2
1 2 3
2 1 5
输出样例2：
14

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55, MOD = 1000000007;

int n, m, k;
int w[N][N];
int f[N][N][13][14];

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            cin >> w[i][j];
            w[i][j] ++ ;
        }

    f[1][1][1][w[1][1]] = 1;
    f[1][1][0][0] = 1;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (i == 1 && j == 1) continue;
            for (int u = 0; u <= k; u ++ )
                for (int v = 0; v <= 13; v ++ )
                {
                    int &val = f[i][j][u][v];
                    val = (val + f[i - 1][j][u][v]) % MOD;
                    val = (val + f[i][j - 1][u][v]) % MOD;
                    if (u > 0 && v == w[i][j])
                    {
                        for (int c = 0; c < v; c ++ )
                        {
                            val = (val + f[i - 1][j][u - 1][c]) % MOD;
                            val = (val + f[i][j - 1][u - 1][c]) % MOD;
                        }
                    }
                }
        }

    int res = 0;
    for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % MOD;

    cout << res << endl;

    return 0;
}

1214. 波动数列

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。

栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？

输入格式
共一行，包含四个整数 n,s,a,b，含义如前面所述。

输出格式
共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以 100000007 的余数。

数据范围
1≤n≤1000,
$-10^9$≤s≤$10^9$,
1≤a,b≤$10^6$
输入样例：
4 10 2 3
输出样例：
2
样例解释
两个满足条件的数列分别是2 4 1 3和7 4 1 -2。

4.1 枚举、模拟与排序

九字型从中间枚举i与j均[-1,1]

1210. 连号区间数

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。

当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式
第一行是一个正整数 N，表示排列的规模。

第二行是 N 个不同的数字 Pi，表示这 N 个数字的某一排列。

输出格式
输出一个整数，表示不同连号区间的数目。

数据范围
1≤N≤10000,
1≤Pi≤N
输入样例1：
4
3 2 4 1
输出样例1：
7
输入样例2：
5
3 4 2 5 1
输出样例2：
9
样例解释
第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

暴力做法 for i for j 再sort for k to j - i + 1 判断

1-N排列隐藏性质：没有重复的数
得出区间[a,b]最大值与最小值等于排序好的最大值最小值 :
if(maxv - minv == b - a)说明全部填满，则[a,b]为连号区间
即满足上述性质为连号区间,初始 max = -INF ， min = INF保证更新
每次加入新的数比较大小（优化成两重循环）

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, INF = 1e8;//取大于边界范围就行

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int res = 0;
    for (int i = 0; i < n; i ++ )   // 枚举区间左端点
    {
        int minv = INF, maxv = -INF;
        for (int j = i; j < n; j ++ )   // 枚举区间右端点
        {
            minv = min(minv, a[j]);
            maxv = max(maxv, a[j]);
            if (maxv - minv == j - i) res ++ ;//说明sort(a[i~j]) -->minv = a[i] maxv = a[j] 
        }
    }

    cout << res << endl;

    return 0;
}

1236. 递增三元组

给定三个整数数组

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k) 满足：

1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式
一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai,Bi,Ci≤105
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27

2023-简版STL二分
$\sum ($a[]中第一个大等于b[i]的位置 $\times$ c[]中第一个小于b的位置$)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];

int main() 
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	for(int i = 0; i < n; i++) scanf("%d", &b[i]);
	for(int i = 0; i < n; i++) scanf("%d", &c[i]);
	sort(a, a + n), sort(b, b + n), sort(c, c + n);
	LL cnt = 0;
	for(int i = 0; i < n; i++)  //b比a大 且 比c小 - 【枚举b[]  乘积 
	{
		LL A = lower_bound(a, a + n, b[i]) - a; //a[]中第一个大等于b[i]的位置 (从0开始刚好 个数 == 下标) 
		LL C = n - (upper_bound(c, c + n, b[i]) - c); //c[]中第一个小于b的位置 (剩下均大于b[i]) 
		cnt += A * C;
	}
	printf("%lld", cnt);
	return 0;
}

三指针

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];

int main() 
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	for(int i = 0; i < n; i++) scanf("%d", &b[i]);
	for(int i = 0; i < n; i++) scanf("%d", &c[i]);
	sort(a, a + n), sort(b, b + n), sort(c, c + n);
	LL sum = 0,s1 = 0,s2 = 0;
    for(int i=0;i<n;i++){
        while(s1 < n && a[s1] < b[i]) s1++;
            while(s2 < n && c[s2] <= b[i]) s2++;
        sum += s1 * (n - s2);
    }
	printf("%lld", sum);
	return 0;
}

before

暴力：for三重 if(a[i] < b[i] && b[i] < c[i])res++;

通过时间复杂度需限制再O(nlogn) 则只能枚举一个数组 ，应枚举B[i],因为A[i]与C[i]只需被B[i]限制
再把A、C中满足的个数相乘 [等效满足的A<B<C的组合]

实现：O(n)法①：前缀和 O(nlogn)法②：sort(A) + 二分法(B[j])找到A中小于B[j]的下标res ：答案个数就为 res + 1
前缀和映射hash有减1操作,但有数值0的，所以每位加1，取值映射变为[1,1e5 + 1]，(相对大小不变)
把数值映射为hash值 , 前缀和数组存储值小于当前下标的个数，同理c就存储大于当前下标的个数【类似桶排序】

佬滴总结：

既然要排序实现快速的查找A中小于B[i]的数的个数，可以将数组A中所有元素出现的次数存入一个哈希表中，因为数组中元素的范围只有$n^5$, 可以开一个大的数组cnt作为哈希表。
在枚举B中元素时，我们需要快速查找找小于B[i]的所有元素的总数，只需要在枚举之前先将求出表中各数的前缀和即可。

前缀和实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N], b[N], c[N];
int as[N];  // as[i]表示在A[]中有多少个数小于b[i]
int cs[N];  // cs[i]表示在C[]中有多少个数大于b[i]
int cnt[N], s[N];//cnt[]存a的值的数量

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]), a[i] ++ ;
    for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]), b[i] ++ ;
    for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]), c[i] ++ ;

    // 求as[]
    for (int i = 0; i < n; i ++ ) cnt[a[i]] ++ ;//将数组a中所有元素出现的次数存入一个哈希表中
    for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];   // 求cnt[]的前缀和
    for (int i = 0; i < n; i ++ ) as[i] = s[b[i] - 1];//a[]中小于b[i]的元素个数前缀和 ：前缀和s可表示为不超过下标值的元素个数(所以减1)

    // 求cs[]
    memset(cnt, 0, sizeof cnt);
    memset(s, 0, sizeof s);
    for (int i = 0; i < n; i ++ ) cnt[c[i]] ++ ;//将数组c中所有元素出现的次数存入一个哈希表中
    for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
    for (int i = 0; i < n; i ++ ) cs[i] = s[N - 1] - s[b[i]]; //s[N-1] - s[b[i]]表示：c[]所有元素中大于b[i]的个数

    // 枚举每个b[i]
    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += (LL)as[i] * cs[i];//1e5*1e5 会爆int 开LL

    cout << res << endl;

    return 0;
}

1245. 特别数的和

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入格式
共一行，包含一个整数 n。

输出格式
共一行，包含一个整数，表示满足条件的数的和。

数据范围
1≤n≤10000
输入样例：
40
输出样例：
574

简单模拟

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int res;

bool check(int i)
{
    while(i)
    {
        int t = i % 10;//t取个位的值
        i /= 10;//删除个位
        if(t == 1 || t == 2 || t == 9 || t == 0 ) return true;
        
    }
    return false;
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        if(check(i)) res += i;
    }
    
    cout << res << endl;
    
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int x = i;
        while (x)
        {
            int t = x % 10; // 取出x的个位
            x /= 10;    // 删掉x的个位
            if (t == 2 || t == 0 || t == 1 || t == 9)
            {
                res += i;
                break;
            }
        }
    }

    cout << res << endl;

    return 0;
}

扩：数据如果很大，要用到数位dp

1204. 错误票据

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的ID号。

全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。

因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。

你的任务是通过编程，找出断号的ID和重号的ID。

假设断号不可能发生在最大和最小号。

输入格式
第一行包含整数 N，表示后面共有 N 行数据。

接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。

输出格式
要求程序输出1行，含两个整数 m,n，用空格分隔。

其中，m表示断号ID，n表示重号ID。

数据范围
1≤N≤100
输入样例：
2
5 6 8 11 9
10 12 9
输出样例：
7 9

sstream 用法(严格读取每行，不熟做题就不用hh) 【都是自己试试就知道默认规则，然后记住】

知识点：getline() 读取回车，占空位
scanf读到文件结束符时会返回-1，而不是0。

stringstream ssin版

#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int a[N];

int main()
{
    int cnt;
    cin >> cnt;
    string line;

    getline(cin, line); // 忽略掉第一行的回车
    while (cnt -- )
    {
        getline(cin, line);
        stringstream ssin(line);//stringstream类型的ssin代替cin实现读入

        while (ssin >> a[n]) n ++ ;
    }

    sort(a, a + n);

    int res1, res2;
    for (int i = 1; i < n; i ++ )
        if (a[i] == a[i - 1]) res2 = a[i];  // 重号
        else if (a[i] >= a[i - 1] + 2) res1 = a[i] - 1; // 断号

    cout << res1 << ' ' << res2 << endl;

    return 0;
}

此题简单读法版： 读完n忽略，后面的读到空为止

#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;
const int N = 1e4 + 5;
int n, cnt;
int a[N];

int main () {
    cin >> n;
    int t;
    while (cin >> t) {
        a[cnt ++] = t;
    }
    sort (a, a + cnt);
    int res1 = 0, res2 = 0;
    for (int i = 1; i < cnt; i ++) {
        if (res1 && res2)
            break;
        if (a[i] - a[i - 1] == 2)
            res1 = a[i - 1] + 1;
        if (a[i] == a[i - 1])
            res2 = a[i - 1];
    }
    cout << res1 << ' ' << res2;

}

找到区间[min,max]读取版(类似连续区间规律)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+5, INF = 0x3f3f3f3f;

int ha[N];

int main()
{
    int n;
    cin >> n;//这个读入没什么用
    int minv = INF, maxv = -INF;
    int tp;
    while(cin >> tp)//直接读到文件尾部停止
    {
        if(tp < minv)   minv = tp;
        if(tp > maxv)   maxv = tp;
        ha[tp] ++;
    }
    int ans1 = 0, ans2 = 0;
    for(int i = minv; i <= maxv; ++ i)
    {
        if(ha[i] == 0)  ans1 = i;
        if(ha[i] == 2)  ans2 = i;
    }
    cout << ans1 << " " << ans2 << endl;
}

//作者：chaosliang  链接：https://www.acwing.com/solution/content/31989/

这份代码是多年前刚学c++写的，有些不足之处（这样写导致line是没有用的 但这题对答案是没有影响的
如果要严格按照每行读取数据可以采用getline(cin,s)的方法先读取整行
然后用sstream的这种方式来分割，再转成数字（或者遍历字符串手动分割）

下面是sstream的简易用法

//Example：可以用于分割被空格、制表符等符号分割的字符串
#include<iostream>  
#include<sstream>        //istringstream 必须包含这个头文件
#include<string>  
using namespace std;  
int main(){  
    string str="i am a boy";  
    istringstream is(str);  
    string s;  
    while(is>>s)  {  
        cout<<s<<endl;  
    }  
} 


//作者：熠丶 链接：https://www.acwing.com/solution/content/7614/

466. 回文日期

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 8 位数字表示一个日期，其中，前 4 位代表年份，接下来 2 位代表月份，最后 2 位代表日期。

显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的 8 位数字是回文的。

现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。

一个 8 位数字是回文的，当且仅当对于所有的 i(1≤i≤8) 从左向右数的第 i 个数字和第 9−i 个数字（即从右向左数的第 i 个数字）是相同的。

例如：

对于 2016 年 11 月 19 日，用 8 位数字 20161119 表示，它不是回文的。
对于 2010 年 1 月 2 日，用 8 位数字 20100102 表示，它是回文的。
对于 2010 年 10 月 2 日，用 8 位数字 20101002 表示，它不是回文的。
输入格式
输入包括两行，每行包括一个 8 位数字。

第一行表示牛牛指定的起始日期 date1，第二行表示牛牛指定的终止日期 date2。保证 date1 和 date2 都是真实存在的日期，且年份部分一定为 4 位数字，且首位数字不为 0。

保证 date1 一定不晚于 date2。

输出格式
输出共一行，包含一个整数，表示在 date1 和 date2 之间，有多少个日期是回文的。

输入样例：
20110101
20111231
输出样例：
1

(枚举,模拟) $O(10^4)$
y总：由于只有八位数，而且回文串左右对称，因此可以只枚举左半边，这样只需枚举 0∼9999总共一万个数，然后判断：
①枚举回文串
②是否在给定范围[date1,date2]内
③日期是否合法；
时间复杂度:一共枚举 $10^4$ 个数，判断每个数是否合法的计算量是常数级别的，因此总计算量是 $O(10^4)$。

【想法】
%$10^n$ : 取末尾n位
/ $10^n$ : 删除末尾n位

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int date)//检查年月日是否合法
{
    int year = date / 10000;
    int month = date % 10000 / 100;//%10000等效取后四位 ，/100删去后两位  
    int day = date % 100;

    if (!month || month >= 13 || !day) return false;

    if (month != 2 && day > months[month]) return false;//先不管二月
    if (month == 2)//特判二月
    {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;//是否闰年
        if (day > 28 + leap) return false;
    }

    return true;
}

int main()
{
    int date1, date2;
    cin >> date1 >> date2;

    int res = 0;
    for (int i = 0; i < 10000; i ++ )
    {
        int x = i, r = i;
        for (int j = 0; j < 4; j ++ ) r = r * 10 + x % 10, x /= 10;//拼接,取最后一位加上 + 原数值乘10 如：1234 --> 12344321 

        if (r >= date1 && r <= date2 && check(r)) res ++ ;//检查是否在区间[date1,date2]内
    }

    printf("%d\n", res);
    return 0;
}

787. 归并排序

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

熟能生巧

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N];
int tmp[N];

void merge_sort(int l , int r)
{
    if(l >= r)return;
    int mid = l + r >> 1;
    merge_sort(l , mid ) , merge_sort(mid + 1 , r);
    int k = 0 ,i = l  ,j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i] <= q[j])tmp[k++] = q[i++];
        else tmp[k++] = q[j++];

    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(int i = l , j  = 0;j < k; i ++ , j ++) q[i] = tmp[j];

}

int main()
{
    cin >> n;
    for(int i  = 0;i < n;i++) scanf("%d", &q[i]);
    merge_sort(0,n - 1);
    for(int i = 0;i < n;i++) printf("%d ",q[i]);

    return 0;
}