大新网站制作,代码交易网站,手机免播看成片,可以做图接单的网站[蓝桥杯 2019 省 A] 糖果
题目描述
糖果店的老板一共有M种口味的糖果出售。为了方便描述#xff0c;我们将M 种口味编号 1∼ M。小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果#xff0c;而是K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味…[蓝桥杯 2019 省 A] 糖果
题目描述
糖果店的老板一共有M种口味的糖果出售。为了方便描述我们将M 种口味编号 1∼ M。小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果而是K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味所以小明可以在买之前就知道每包内的糖果口味。
给定 N 包糖果请你计算小明最少买几包就可以品尝到所有口味的糖果。
输入格式
第一行包含三个整数 NM 和 K。
接下来 N 行每行K这整数T1,T2,⋯,TK代表一包糖果的口味。
输出格式
一个整数表示答案。如果小明无法品尝所有口味输出−1。 代码表示
#include bits/stdc.h
using namespace std;const int N 20;
int n, m, k, dp[1 20], v[1 20]; // 状压的数组需要开2^n因为表示的是状态int main() {scanf(%d%d%d, n, m, k);memset(dp, 0x3f3f3f3f, sizeof(dp)); // 初始化dp数组为最大值for (int i 1; i n; i) {int h 0, p;for (int j 1; j k; j) {scanf(%d, p);p--;h h | (1 p); // 将糖果的口味对应的位置置为1表示这个糖果包含了该口味}dp[h] 1; // 这些口味都可以用一包糖解决v[i] h; // 记录糖的状态}for (int i 0; i (1 m); i) { // i枚举的是状态即01...11111m个1for (int j 1; j n; j) {dp[i | v[j]] min(dp[i | v[j]], dp[i] 1); // 将当前状态i与糖果j的状态进行合并并更新最小包数dp}}if (dp[(1 m) - 1] 0x3f3f3f3f)cout -1; // 搭配不出来elsecout dp[(1 m) - 1]; // 搭配出来return 0;
}
心得体会
这题是0-1背包问题 2、在这段代码中dp[1 20]和v[1 20]是用于状态压缩的数组。状态压缩是一种常用的优化技巧用于在处理具有多种状态组合的问题时减少内存和计算量。在这个问题中糖果的口味有 M 种每种口味可以选择购买或不购买。那么总共可能的状态就有 2^M 种每种口味的糖果都有两种选择购买或不购买。因为 M 的最大值为 20所以最多可能有 2^20 种状态。
为了表示这些状态可以使用一个整数来表示整数的二进制位表示每个口味是否购买。例如假设 M3那么状态 5二进制为 101表示购买了第 1 和第 3 种口味的糖果但没有购买第 2 种口味的糖果。因此为了存储这些状态可以使用大小为 2^M 的数组。在这段代码中dp和v数组的大小都是1 20即 2^20。这样就可以通过数组的索引来表示不同的状态。
这种状态压缩的技巧可以减少内存的使用并且在处理状态转移时更加高效。在该代码中dp数组用于记录每个状态下需要的最小包数v数组用于记录每个糖果包。 [蓝桥杯 2014 省 AB] 蚂蚁感冒
题目描述
长 100厘米的细长直杆子上有n 只蚂蚁。它们的头有的朝左有的朝右。每只蚂蚁都只能沿着杆子向前爬速度是1 厘米 / 秒。当两只蚂蚁碰面时它们会同时掉头往相反的方向爬行。
这些蚂蚁中有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时会把感冒传染给碰到的蚂蚁。请你计算当所有蚂蚁都爬离杆子时有多少只蚂蚁患上了感冒。
输入格式
第一行输入一个整数n(1n50) 表示蚂蚁的总数。
接着的一行是n 个用空格分开的整数 Xi(−100Xi100)Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。正值表示头朝右负值表示头朝左数据中不会出现0值也不会出现两只蚂蚁占用同一位置。其中第一个数据代表的蚂蚁感冒了。
输出格式
要求输出 1个整数表示最后感冒蚂蚁的数目。 代码表示
#include bits/stdc.h
using namespace std;int x[55];//定义蚂蚁数组int main(){int n;//定义蚂蚁数cinn;//输入蚂蚁数for(int i1; in; i) scanf(%d,x[i]);//输入每个蚂蚁的情况int l0,r0;//统计在第1只蚂蚁左侧朝右、右侧朝左的蚂蚁数。for(int i2; in; i){if(abs(x[i])abs(x[1]) x[i]0) l;//左侧朝右if(abs(x[i])abs(x[1]) x[i]0) r;//右侧朝左}int sum0;//定义感冒蚂蚁总数if(x[1]0){//第1只蚂蚁朝左if(l0) sum1;else sumlr1;}else{//第1只蚂蚁朝右if(r0) sum1;else sumlr1;}coutsum;return 0;
}
心得体会
这个题目真的就是找规律和仔细理解题目。 其中 L 表示向左R 表示向右G 表示感冒。最后第1,2,4 只蚂蚁感冒。
由表格可以发现由于碰面就掉头这些蚂蚁的相对排列顺序是保持不变的那么应该可以从开始的位置就能预测谁会被传染。
在样例 2 中第 1 只蚂蚁感冒蚂蚁朝左。
1、位于第 1只蚂蚁左侧且朝右蚂蚁有一只即第 2只蚂蚁被传染
2、由于步骤 1 第 1只蚂蚁朝右位于第 1 只蚂蚁右侧且朝左蚂蚁也有一只即第 4只蚂蚁也被传染。 最后第1,2,3,4 只蚂蚁感冒。
在这个例子中第1 只蚂蚁感冒蚂蚁朝右。
1、位于第 1 只蚂蚁右侧且朝左蚂蚁有两只即第 4 只蚂蚁和第 5 只蚂蚁它们都被传染其中第 3 只蚂蚁在与第 5 只蚂蚁碰面后朝左
2、由于步骤 1第 1只蚂蚁朝左位于第1 只蚂蚁左侧且朝右蚂蚁有一只即第 2 只蚂蚁也被传染。
总结一下 [蓝桥杯 2020 省 B1] 整数拼接
题目描述
给定一个长度为n 的数组A1,A2,⋯,An。你可以从中选出两个数Ai 和Aji≠j然后将 Ai 和 Aj 一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换Ai 和Aj 的顺序总是被视为2种拼法即便是AiAj 时。请你计算有多少种拼法满足拼出的整数是 K 的倍数。
输入格式
第一行包含 2个整数n 和K。
第二行包含n个整数A1,A2,⋯,An。
输出格式
一个整数代表答案。 代码表示
#include bits/stdc.h
using namespace std;
//动态规划
long long n,k,l,ans;
int a[12][1000005],b[1000005];void d()
{for(int i1;in;i){ansa[(int)log10(b[i])1][(k-b[i]%k)%k];//答案加方案数for(int j1,p10;j10;j){a[j][(b[i]%k*p)%k];//这个次方和次方余数方案加1pp*10%k;}}
}
int main()
{cinnk;for(int i1;in;i)cinb[i];d();reverse(b1,bn1);//翻转memset(a,0,sizeof(a));//将数组 a 清空为 0d();coutans; return 0;
}心得体会
1、从左到右存储每个数乘 10 的 1 到 10 次方模 k 的余数和1 到10 查找后面数是否相同相同就将答案加上个数然后再从右到左来一次最后输出。
2、(int)log10(b[i]) 1计算数字 b[i] 的位数。log10 函数返回以 10 为底的对数将结果转换为整数后加 1 是因为位数从 1 开始计数。
例如果 b[i] 的值是 12345则 (int)log10(b[i]) 的结果是 4因为 12345 是一个 5 位数其对数的整数部分是 4。
3、(k - b[i] % k) % k计算数字 b[i] 对 k 的余数再与 k 相减并取模运算得到需要的余数。 [蓝桥杯 2018 省 B] 递增三元组
题目描述
给定三个整数数组 A[A1,A2,⋯,AN]B[B1,B2,⋯,BN]C[C1,C2,⋯,CN]。请你统计有多少个三元组(i,j,k) 满足1、1≤i,j,k≤N2、AiBjCk
输入格式
第一行包含一个整数N。
第二行包含N 个整数A1,A2,⋯,AN。
第三行包含N 个整数B1,B2,⋯,BN。
第四行包含N 个整数C1,C2,⋯,CN。
输出格式
一个整数表示答案 代码表示
第一种 72分 会超时
#include bits/stdc.h
using namespace std;int main() {int n;cin n;int a[10001];int b[10001];int c[10001];for (int j 0; j n; j) {cin a[j];}for (int j 0; j n; j) {cin b[j];}for (int j 0; j n; j) {cin c[j];}int ann 0;for (int j 0; j n; j) {for (int i 0; i n; i) {for (int k 0; k n; k) {if (a[i]b[j] b[j] c[k]) {ann;}}}}cout ann;return 0;
}
把开始的部分换成vector也可以
vectorint A(N), B(N), C(N);for (int i 0; i N; i) {cin A[i];}for (int i 0; i N; i) {cin B[i];}for (int i 0; i N; i) {cin C[i];} 法二 利用两种函数来写解析说这是二分法震惊♀️
#include bits/stdc.h
using namespace std;typedef long long ll;
int n;
ll cnt 0;
int a[100007], b[100007], c[100007];int main()
{scanf(%d, n); // 从输入中读取 n 的值// 从输入中读取数组 a 的元素for (int i 1; i n; i)scanf(%d, a i);// 从输入中读取数组 b 的元素for (int i 1; i n; i)scanf(%d, b i);// 从输入中读取数组 c 的元素for (int i 1; i n; i)scanf(%d, c i);// 对数组 a、b、c 进行升序排序sort(a 1, a n 1);sort(b 1, b n 1);sort(c 1, c n 1);// 遍历数组 b 的每个元素for (int i 1; i n; i) {// 使用 lower_bound 函数计算在数组 a 中小于 b[i] 的元素个数//将偏移量减去 a 的起始位置得到在数组 a 中的下标ll n1 lower_bound(a 1, a n 1, b[i]) - a - 1;// 使用 upper_bound 函数计算在数组 c 中大于 b[i] 的元素个数//将偏移量减去 c 的起始位置得到在数组 c 中的下标ll n2 upper_bound(c 1, c n 1, b[i]) - c - 1;// 计算满足条件的组合数量并累加到 cnt 变量中cnt n1 * (n - n2);}cout cnt;return 0;
}心得体会
1、lower_bound(a1, an1, b[i])这是一个函数调用用于在数组 a 中查找第一个不小于 b[i] 的元素的位置并返回该位置的指针
2、upper_bound(c1, cn1, b[i])这是一个函数调用用于在数组 c 中查找第一个大于 b[i] 的元素的位置并返回该位置的指针
lower_bound 和 upper_bound 是 C 标准库中的两个函数用于在已排序的序列例如数组或容器中进行二分查找。
lower_bound 函数用于查找第一个不小于给定值的元素的位置。upper_bound 函数用于查找第一个大于给定值的元素的位置。
1)、lower_bound
templateclass ForwardIt, class T
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T value);first 和 last 是正向迭代器表示要搜索的范围。范围是左闭右开的即包括 first但不包括 last。value 是要查找的值。
lower_bound 函数返回一个指向范围中第一个不小于 value 的元素位置的迭代器。如果所有元素都小于 value则返回 last。
2)、upper_bound
templateclass ForwardIt, class T
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T value);first 和 last 是正向迭代器表示要搜索的范围。范围是左闭右开的即包括 first但不包括 last。value 是要查找的值。
upper_bound 函数返回一个指向范围中第一个大于 value 的元素位置的迭代器。如果所有元素都不大于 value则返回 last。
这两个函数的时间复杂度是对数级别的因为它们使用了二分查找算法。在使用这两个函数之前需要确保序列是按升序排序的这样才能得到正确的结果。 [蓝桥杯 2018 省 A] 倍数问题
题目描述
众所周知小葱同学擅长计算尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数希望你从这 n个数中找到三个数使得这三个数的和是K 的倍数且这个和最大。数据保证一定有解。
输入格式
从标准输入读入数据。
第一行包括 2个正整数表示n 和K。
第二行n个正整数代表给定的n个数。
输出格式
输出一行一个整数代表所求的和。 代码表示
第一种60分 超时/(ㄒoㄒ)/~~我滴暴力呀
#include bits/stdc.h
using namespace std;
#define long long int;
int main()
{int n,k;cinnk;int a[n];for(int i1;in;i){cina[i];}int ann0;for(int j1;jn;j){for(int ij1;in;i){for(int fi1;fn;f){if((a[i]a[j]a[f])%k0){annmax(a[i]a[j]a[f],ann);}}}}coutann;return 0;
}第二种 #includebits/stdc.h
using namespace std;int n, k, a[100005];
long long ans -6e8, maxx[1005][3];int main() {cin n k;// 初始化maxx数组用于存储每个余数对应的最大、次大、第三大的数的值for (int i 0; i k; i)maxx[i][0] maxx[i][1] maxx[i][2] -6e8;for (int i 1; i n; i) {cin a[i];// 计算当前数除以k的余数int mod a[i] % k;// 根据当前余数更新maxx数组中的最大、次大、第三大的数的值if (maxx[mod][0] a[i])maxx[mod][2] maxx[mod][1], maxx[mod][1] maxx[mod][0], maxx[mod][0] a[i];else if (maxx[mod][1] a[i])maxx[mod][2] maxx[mod][1], maxx[mod][1] a[i];else if (maxx[mod][2] a[i])maxx[mod][2] a[i];}//计算第三个余数xfor (int i 0; i k; i) {for (int j 0; j k; j) {for (int l 0; l 2 * k; l k) {int x l - i - j;//如果x不在合法范围内则跳过当前循环if (x 0 || x k)continue;// 更新最大和ans的值其中根据i和j的关系决定余数j要取次大值x也是同理ans max(ans, maxx[i][0] maxx[j][(i j)] maxx[x][(i x) (j x)]);}}}cout ans;return 0;
}
心得体会
for(int j1;jn;j){ for(int ij1ini){ for(int fi1fnf){
注意写这种连续循环的时候要记得画黑的部分 [蓝桥杯 2017 省 AB] 包子凑数
题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N 种蒸笼其中第 i 种蒸笼恰好能放Ai 个包子。每种蒸笼都有非常多笼可以认为是无限笼。每当有顾客想买X 个包子卖包子的大叔就会迅速选出若干笼包子来使得这若干笼中恰好一共有X 个包子。
比如一共有 3 种蒸笼分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时大叔就会选2笼3个的再加1笼5个的也可能选出1笼3个的再加2笼4个的。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼分别能放 4、5和 6个包子。而顾客想买 7 个包子时大叔就凑不出来了。小明想知道一共有多少种数目是包子大叔凑不出来的。
输入格式
第一行包含一个整数 N。(1≤N≤100)。
以下N 行每行包含一个整数Ai。(1≤Ai≤100)。
输出格式
一个整数代表答案。如果凑不出的数目有无限多个输出 INF。 代码表示
#include bits/stdc.h
using namespace std;const int maxn 1e5;
int n, x[maxn];// 辗转相除法求最大公约数
int gcd(int a, int b) {if (!b)return a;return gcd(b, a % b);
}// 判断数组中的数是否存在公因数大于1
bool pd() {int Gcd 0;for (int i 1; i n; i)Gcd gcd(Gcd, x[i]);return Gcd 1;
}// 裴蜀定理可得axby 永远能被 gcd(a, b) 整除 bitsetmaxn 1 S; // S[i]为1表示可以拼凑出数i为0表示不能int main() {cin n;S[0] 1; // 初始化S0可以拼凑出for (int i 1; i n; i)cin x[i];sort(x 1, x n 1); // 对数组x进行排序if (pd()) {cout INF;exit(0); // 如果数组中存在公因数大于1则输出INF表示无限个数无法拼凑退出程序}for (int i 1; i n; i)for (int j x[i]; j 1000; j)S | S x[i]; // 更新S将能拼凑出的数进行标记int ans 0;for (int i 1; i x[n] * 990; i)if (!S.test(i))ans; // 统计无法拼凑的数的个数cout ans; // 输出结果return 0;
}
心得体会
1、S | S x[i] 是对位集合 S 进行按位或运算的操作。
在这个表达式中S x[i] 表示将 S 中的每个位都向左移动 x[i] 位。例如如果 S 的二进制表示为 1010而 x[i] 的值为 2那么 S x[i] 的结果就是 101000。
然后 表示将位集合 S | S x[i]S 与 进行按位或运算并将结果赋值给 S x[i]S。按位或运算的规则是对应位置上的两个位只要有一个为1结果的对应位置上就为1。因此这个操作将把 S 中的某些位设为1表示能够拼凑出特定的数。
通过循环遍历数组 x 中的数每次都对 S 进行位移和按位或运算最终能够拼凑出的数会在 S 中被标记为1。
2、bitsetmaxn 1 S; 是定义了一个名为 S 的位集合bitset它的长度为 maxn 1。
bitset 是一种固定长度的二进制位集合每个位只能是0或1。在这里bitsetmaxn 1 表示创建了一个长度为 maxn 1 的位集合 。S
这个位集合 S 可以被用来表示一组布尔值其中每个位置上的位都可以表示某个状态的真或假。
在给定的代码中位集合 S 被用来表示能否拼凑出某个数。每个位置上的位可以表示对应的数是否能够被拼凑出来1 表示可以拼凑0 表示不能拼凑。
通过使用位集合 S可以高效地进行位运算操作例如左移、按位或等来更新和查询拼凑数的状态。 回溯递归问题
回溯法一般可以解决如下几种问题
组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等
注意组合是不强调元素顺序的排列是强调元素顺序。
例如{1, 2} 和 {2, 1} 在组合上就是一个集合因为不强调顺序而要是排列的话{1, 2} 和 {2, 1} 就是两个集合了。
记住组合无序排列有序就可以了所有回溯法的问题都可以抽象为树形结构
回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度都构成的树的深度。
递归就要有终止条件所以必然是一棵高度有限的树。 回溯三部曲 1、回溯函数模板返回值以及参数
在回溯算法中习惯是函数起名字为backtracking但回溯算法中函数返回值一般为void。
参数因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来所以一般是先写逻辑然后需要什么参数就填什么参数。
回溯函数伪代码如下
void backtracking(参数)2、回溯函数终止条件
达到了终止条件树中就可以看出一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。
所以回溯函数终止条件伪代码如下
if (终止条件) {存放结果;return;
}3、回溯搜索的遍历过程
在上面我们提到了回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。 回溯函数遍历过程伪代码如下
for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果
}for循环就是遍历集合区间可以理解一个节点有多少个孩子这个for循环就执行多少次。
backtracking这里自己调用自己实现递归。
从图中看出for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果。
回溯算法模板框架如下
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
} 组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。可以按 任何顺序 返回答案。 提示
1 n 201 k n
思路提示
直接的解法当然是使用for循环例如示例中k为2很容易想到 用两个for循环这样就可以输出 和示例中一样的结果。代码如下
int n 4;
for (int i 1; i n; i) {for (int j i 1; j n; j) {cout i j endl;}
}输入n 100, k 3 那么就三层for循环代码如下
int n 100;
for (int i 1; i n; i) {for (int j i 1; j n; j) {for (int u j 1; u n; n) {cout i j u endl;}}
}如果n为100k为50呢
要解决 n为100k为50的情况暴力写法需要嵌套50层for循环那么回溯法就用递归来解决嵌套层数的问题。递归来做层叠嵌套可以理解是开k层for循环每一次的递归中嵌套一个for循环那么递归就可以用于解决多层嵌套循环的问题了。
回溯法三部曲
1、递归函数的返回值以及参数
在这里要定义两个全局变量一个用来存放符合条件单一结果一个用来存放符合条件结果的集合。代码如下
vectorvectorint result; // 存放符合条件结果的集合
vectorint path; // 用来存放符合条件结果函数里一定有两个参数既然是集合n里面取k个数那么n和k是两个int型的参数。
然后还需要一个参数为int型变量startIndex这个参数用来记录本层递归的中集合从哪里开始遍历集合就是[1,...,n] 。
startIndex 就是防止出现重复的组合。
从下图中红线部分可以看出在集合[1,2,3,4]取1之后下一层递归就要在[2,3,4]中取数了那么下一层递归如何知道从[2,3,4]中取数呢靠的就是startIndex。 需要startIndex来记录下一层递归搜索的起始位置整体代码如下
vectorvectorint result; // 存放符合条件结果的集合
vectorint path; // 用来存放符合条件单一结果
void backtracking(int n, int k, int startIndex) 2、回溯函数终止条件
到达所谓的叶子节点path这个数组的大小如果达到k说明我们找到了一个子集大小为k的组合了在图中path存的就是根节点到叶子节点的路径。 用result二维数组把path保存起来并终止本层递归所以终止条件代码如下
if (path.size() k) {result.push_back(path);return;
} 3、单层搜索的过程
回溯法的搜索过程就是一个树型结构的遍历过程在如下图中可以看出for循环用来横向遍历递归的过程是纵向遍历。 如此才遍历完图中的这棵树for循环每次从startIndex开始遍历然后用path保存取到的节点 i。代码如下
for (int i startIndex; i n; i) { // 控制树的横向遍历path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归控制树的纵向遍历注意下一层搜索要从i1开始path.pop_back(); // 回溯撤销处理的节点
}可以看出backtracking递归函数通过不断调用自己一直往深处遍历总会遇到叶子节点遇到了叶子节点就要返回。backtracking的下面部分就是回溯的操作了撤销本次处理的结果。
代码表示
#include bits/stdc.h
using namespace std;vectorvectorint result; // 存放符合条件结果的集合
vectorint path; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n; i) {path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}
}
vectorvectorint combine(int n, int k) {result.clear();path.clear();backtracking(n, k, 1);return result;
}
int main() {int n, k;cin n k;vectorvectorint combinations combine(n, k);// 输出所有可能的组合for (const auto combination : combinations) {for (int num : combination) {cout num ;}cout endl;}return 0;
}
