数学

蓝桥杯真题

1.买不到的数目

题目描述：
小明开了一家糖果店。

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

糖果不能拆包卖。

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

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

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

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

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

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

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

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

输入样例：

4 7

输出样例：

17

解题思路

结论：
如果 a,b 均是正整数且互质，那么由 ax+by,x≥0,y≥0 不能凑出的最大数是 ab−a−b。
证明可以参考这个博客：证明

代码实现+详细注释c++

#include<iostream>using namespace std;int main()
{int a,b;cin>>a>>b;cout<<a*b-a-b<<endl;
}

2.蚂蚁感冒

题目描述
长 100 厘米的细长直杆子上有 n 只蚂蚁。

它们的头有的朝左，有的朝右。

每只蚂蚁都只能沿着杆子向前爬，速度是 1 厘米/秒。

当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。

这些蚂蚁中，有 1 只蚂蚁感冒了。

并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。

请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。

输入格式
第一行输入一个整数 n, 表示蚂蚁的总数。

接着的一行是 n 个用空格分开的整数 Xi, Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。

正值表示头朝右，负值表示头朝左，数据中不会出现 0 值，也不会出现两只蚂蚁占用同一位置。

其中，第一个数据代表的蚂蚁感冒了。

输出格式
输出1个整数，表示最后感冒蚂蚁的数目。

数据范围
1<n<50,
0<|Xi|<100
输入样例1：

3
5 -2 8

输出样例1：

1

输入样例2：

5
-10 8 -20 12 25

输出样例2：

3

解题思路

如果两个蚂蚁相遇就会感冒，然后二者掉头，我们可以看成是两个蚂蚁穿过对方继续向前走，因为两只蚂蚁都是感冒的，所以可以看成是一样的，那么一直感冒的蚂蚁如果向右走，那么跟它碰面的一定是右边向左走的，如果右边存在向左走的，那么这些蚂蚁继续向左走，一定会跟第一个感冒的蚂蚁左边向右走的蚂蚁碰面

第一种情况 第一个感冒的蚂蚁向右走

那么这个蚂蚁右边向左走的一定会感染
这个蚂蚁右边向右走的一定不会被感染
这个蚂蚁左边向左走的一定不会被感染
这个蚂蚁左边向右走的
(1)如果右边有向左走的，则一定会感染，(2)如果右边没有向左走的，则不会被感染

第二种情况 第一个感冒的蚂蚁向左走

那么这个蚂蚁左边向右走的一定会感染
这个蚂蚁左边向左走的一定不会被感染
这个蚂蚁右边向右走的一定不会被感染
这个蚂蚁右边向左走的
(1)如果左边有向右走的，则一定会感染，(2)如果左边没有向右走的，则不会被感染

如果用两个变量 left和right分别表示 第一只感冒的蚂蚁左边向右走的 和 右边向左走的 因为这两个方向都决定了感冒的结果

当第一只蚂蚁a[1]>0 向右走 如果 right=\=0 则感染的数量就是 1 如果right>0 则感染的数量就是left+right+1
当第一只蚂蚁a[1]<0 向左走如果 left=\=0 则感染的数量就是 1 如果left>0 则感染的数量就是 left+right+1

代码实现+详细注释C++

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=55;
int a[N];
int n;
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int left=0,right=0;//分别表示左边向右走的，和右边向左走的for(int i=1;i<=n;i++){if(abs(a[i])<abs(a[1])&&a[i]>0) left++;//记录在第一只蚂蚁左边 且 向右走的else if(abs(a[i])>abs(a[1])&&a[i]<0) right++;//记录在第一只蚂蚁右边 且 向左走的}if(a[1]>0&&right==0||a[1]<0&&left==0) cout<<"1"<<endl;else cout<<left+right+1<<endl;return 0;
}

3.饮料换购

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

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

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

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

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

100

输出样例：

149

解题思路

只要凑够三个瓶盖既可以换一个，我们用n表示瓶盖的数量，res表示一共得到的饮料，当n>=3时，就可以换饮料了，res+=n/3，但是n不一定刚好全部被换了，剩下n%3的还是瓶盖，留到下一次换,而且这次换到的饮料数n/3其实就是增加的瓶盖数， 所以n=n/3+n%3

代码实现+详细注释C++

#include<iostream>
using namespace std;
int n;
int main()
{cin>>n;int res=n;//初始就能喝到n瓶while(n/3){res+=n/3;//每三个换一瓶饮料n=n/3+n%3;//每次瓶盖换完，剩下没换的加上这次换到的，就是此刻的瓶盖数量}cout<<res<<endl;
}

简单DP

例题

1.01背包问题

什么是01背包以及代码模板

有 N件物品和一个容量为 V 的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。

「0-1 背包」是较为简单的动态规划问题，也是其余背包问题的基础。

动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第 i个物品的做出决策，「0-1」正好代表不选与选两种决定。

二维

（1）状态f[i][j]定义：前 i个物品，背包容量 j下的最优解（最大价值）：

当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 N件物品，则需要 N次决 策，每一次对第 i 件物品的决策，状态f[i][j]不断由之前的状态更新而来。
（2）当前背包容量不够（j < v[i]），没得选，因此前 i 个物品最优解即为前 i−1个物品最优解：
对应代码：f[i][j] = f[i - 1][j]。
（3）当前背包容量够，可以选，因此需要决策选与不选第 i个物品：
选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
不选：f[i][j] = f[i - 1][j] 。
我们的决策是如何取到最大价值，因此以上两种情况取 max()

代码

for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){//  当前背包容量装不进第i个物品，则价值等于前i-1个物品if(j < v[i]) f[i][j] = f[i - 1][j];// 能装，需进行决策是否选择第i个物品else    f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);}  

一维

（1）状态f[j]定义：N 件物品，背包容量j下的最优解。

（2）注意枚举背包容量j必须从m开始。

（3）为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。(正序的话每一轮都会从体积较小的开始更新，那么f[j-v[i]]用到的就是更新过的，而不是上一轮的)

代码

//实际上，只有当枚举的背包容量 >= v[i] 时才会更新状态，因此我们可以修改循环终止条件进一步优化。
for(int i = 1; i <= n; i++)
{for(int j = m; j >= v[i]; j--)  f[j] = max(f[j], f[j - v[i]] + w[i]);
} 

题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

解题思路

这题就是一个01背包问题，直接用模板就行，可以选择一维也可以选择用二维的。

代码实现+详细注释C++
二维

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=1010;
int f[N][N],v[N],w[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=1;j<=m;j++){if(j<v[i]) f[i][j]=f[i-1][j];//如果当前背包的容量不足，则不选第i件物品else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);//否则，就判断选与不选第i件哪个价值更大}}int res=0;for(int i=1;i<=m;i++) res=max(res,f[n][i]);cout<<res<<endl;
}

一维

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N],v[N],w[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=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m]<<endl;
}

2.摘花生

题目描述

解题思路

因为只能像南或者向东走，所以对于每一个可以到达的点(i,j)，要么是从它的北面到达它的f[i-1][j],要么是从它的西面到达它的f[i][j-1]
状态表示：f[i][j]
集合：从(1,1)走到(i,j)可以摘到的花生数
属性：最大值
状态计算：
左边最大值：f[i][j-1]
上边最大值：f[i-1][j]
以上两种情况取max

代码实现+详细注释C++

#include<iostream>
#include<algorithm>
using namespace std;
int t,r,c;
const int N=110;
int f[N][N];//f[i][j]=max(f[i-1][j],f[i][j-1])+f[i][j]; int main()
{cin>>t;while(t--){cin>>r>>c;for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)cin>>f[i][j];for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){f[i][j]=max(f[i-1][j],f[i][j-1])+f[i][j];//看从那个方向走到它摘到的花生最多}}cout<<f[r][c]<<endl;}return 0;
}

3.最长上升子序列

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

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

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

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

数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

解题思路

状态表示:f[i]
集合：表示以第 i 个数结尾的最长上升子序列
属性：最大值
状态计算：f[i]=max(f[j]+1)(j=0,1,2,…i-1)
因为以i结尾的子序列，一定是由前i-1个数结尾的子序列长度加一取max
比如一个子序列a[j]a[i] ,那么当a[j]<a[i],以i结尾的子序列长度就是f[j]+1,但是a[j]可以是a[i]前面的任意一个数,也就是从0到i-1

代码实现+详细注释C++

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N],a[N];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){f[i]=1;//当j=0，以i结尾的子序列只有a[i]，长度为1for(int j=1;j<i;j++){if(a[j]<a[i])//只要a[j]<a[i]，就可以让以a[i]结尾的子序列前一个是a[j]f[i]=max(f[i],f[j]+1);}}int res=0;for(int i=1;i<=n;i++) res=max(res,f[i]);cout<<res<<endl;return 0;
}

蓝桥杯真题

1.地宫取宝

题目描述

解题思路

状态表示：f[i][j][k][c]
集合：表示所有从起点走到(i,j)，且取了k件宝贝，且最后一件物品价值是c的方案数
属性：count
状态计算：从上面走到(i,j)：
1.不取 f[i][j][k][c]=f[i-1][j][k][c]
2.取 因为只有最后一件物品价值小于c才能取第i件，最后一件物品可以是第i件之前的任意一个(类比最长上升子序列)
f[i][j][k][c]=f[i-1][j][k-1][c1] 需要满足c1<c 故c1可以从0取到c-1
从左面走到(i,j)：
1.不取 f[i][j][k][c]=f[i][j-1][k][c]
2.取 因为只有最后一件物品价值小于c才能取第i件，最后一件物品可以是第i件之前的任意一个(类比最长上升子序列)
f[i][j][k][c]=f[i][j-1][k-1][c1] 需要满足c1<c 故c1可以从0取到c-1
最后的答案是取所有从起点走到(n,m)，且取了k件，价值为i的方案数的和

代码实现+详细注释C++

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=55;
int n,m,k;
int f[N][N][13][14];
int a[N][N];
const int mod=1000000007;
int main()
{cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];a[i][j]++;//因为ci的范围是从0到12，第一件其实一定是能取的，但如果第一件价值是0//跟(0,1)或者(1,0)比较之后就变成不能取的了 而且状态转移方程初始化并不能将（1,0）初始化为价值-1，因为下标不能是负的//因为取得宝贝价值应该是严格单调递增的，为了不特判，将宝贝的价值的取值范围变为1到13}}//初始化f[1][1][1][a[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++){//取u件for(int v=0;v<=13;v++){//最后一件价值是vint &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&&a[i][j]==v){//当满足最后的价值为c的时候就取for(int c=0;c<v;c++){//枚举上一次取的最后一件，只要小于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;
}

2.波动数列

题目描述

解题思路

这道题就转化成了，在n个a和b的所有组合中，有多少种组合可以满足这些项的和模n等于s模n

状态表示：f[i][j]
集合：表示只考虑前i项，且当前总和除以n的余数是j的方案数的总和
属性：count
状态计算：当第i项相比前一项加a f[i][j]=f[i-1][(j-ai)%n]
当第i项相比前一项减b f[i][j]=f[i-1][j+bi)%n]

代码实现+详细注释C++

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010,mod=100000007;
int f[N][N];
int n,s,a,b;
int get_mod(int a,int b){//求a除以b的正余数return (a%b+b)%b;
}
int main()
{cin>>n>>s>>a>>b;f[0][0]=1;for(int i=1;i<n;i++){for(int j=0;j<n;j++){f[i][j]=(f[i-1][get_mod(j-a*i,n)]+f[i-1][get_mod(j+b*i,n)])%mod;//第i项 有i-1项+a，或者由i-1项-b得到}}cout<<f[n-1][get_mod(s,n)]<<endl;//最后输出前n项，和s%n的余数相同的方案数
}

总结

数论的知识还有很多，质素，素质，高斯消元，组合计数等等，y老师说要多积累，多刷点，以免不知道公式失分
01背包，线性dp，每个题都可以先找出来问题是什么，然后看看能用几维将问题表示出来，表示出来就可以将状态划分，来状态计算的方程了

学习网站：AcWing
关于背包的更多讲解：背包九讲专题
今日学习任务完成啦，欢迎交流讨论，如果有什么不理解的，欢迎提出，有错误也欢迎指出，非常感谢！