邯郸做网站价格,什么网站专门做境外当地游,xp配置网站服务器,哈尔滨今天重大新闻枚举 前言 hello#xff0c;大家好#xff0c;前面一段时间已经是把acwing Linux基础课讲完了#xff0c;其实那些内容完全可以带领小白入门Linux我说过如果有人留言要Linux和Windows server 配置DNS Web ftp 的内容我就做一期#xff0c;但是没人留言我也就先不自作多情了… 枚举 前言 hello大家好前面一段时间已经是把acwing Linux基础课讲完了其实那些内容完全可以带领小白入门Linux我说过如果有人留言要Linux和Windows server 配置DNS Web ftp 的内容我就做一期但是没人留言我也就先不自作多情了不过后面有人留言的话我还是会继续做的按照计划我开始讲蓝桥杯备赛系列了。 因为蓝桥杯是分为研究生组、A组B组C组四个赛道的他的要求是B组必须掌握B组以及C组的内容,A组掌握B组以及C组的内容所以先给大家列一下提纲我逐个知识点开始讲解然后不光是讲知识点还有我们的计划就是在Linux基础课最后一节我写过了哈哈哈哈在这再讲一下1.讲知识点acwing版的、例题、模板2.讲蓝桥杯这个知识点对应的历年题目3.讲紫皮书里面对知识点有用的知识4.讲官网上的备战思路和双周赛的题目。争取实现看过的同学并且跟着一块学习的同学能起码混个省奖也不枉费300大洋的报名费用。不多bb上内容 一、大学C组 1、枚举 2、排序入门 3、搜索 4、贪心 5、模拟 6、二分 7、基础动态规划 8、高精度 9、数据结构 10、数学 二、大学B组 11、排序进阶 12、搜索 13、进阶动态规划 14、字符串 15、图论 16、数学 17、数据结构 18、计算几何 模板 要问枚举有什么模板没 我的答案是 暴力枚举相信大家对暴力枚举都不陌生也经常能在各大oj平台上看到诸如这个题暴力能不能解之类的讨论许多题其实都可以暴力枚举只是大部分题目都可能会超时但是超时是超出了oj平台对改题目设置的限定时间蓝桥杯的填空题可没有超时这个说法只需要填写答案而且许多编程 题暴力枚举也能拿不少分那么我们为什么不选择更容易想到的暴力枚举呢 大家都知道枚举简单不就是把所有情况都列举出来吗但是在实际写的时候很多人并没有使用或者第一时间选择枚举难道是害怕超时吗经过了解几个小伙伴的想法后才知道原来大家不是不想用枚举也不是不了解枚举而是不知道该如何进行有效的枚举。 2.枚举模板 我个人对可以枚举题目的理解结合oj平台上一些大佬的经验总结出一个基本思想和一个大白话的模板 一个基本思想 怎么简单怎么来能for就for不能for就while 一个白话模板 1.找到要进行枚举的东西 2.要枚举东西的特性 3.枚举的上下边界 4.符合条件的判断 5.能否在枚举的基础上简单优化视情况判断是否省略 我们根据一个基本思想和一个白话模板结合往年蓝桥杯真题实践实践 悄悄告诉你们我认为蓝桥杯的枚举小题填空直接用表格去做或者计算机算大题无非就是暴力能做但是能不能ac看运气基本上都要有一定的巧法才能完全ac要不然一个大题考你暴力就没啥意思了 真题练习 先上一个小开胃菜 1.马虎的算式 小明是个急性子上小学的时候经常把老师写在黑板上的题目抄错了。 有一次老师出的题目是36 x 495 ? 他却给抄成了396 x 45 ? 但结果却很戏剧性他的答案竟然是对的 因为 36 * 495 396 * 45 17820 类似这样的巧合情况可能还有很多比如27 * 594 297 * 54 假设 a b c d e 代表1~9不同的5个数字注意是各不相同的数字且不含0 能满足形如 ab * cde adb * ce 这样的算式一共有多少种呢 请你利用计算机的优势寻找所有的可能并回答不同算式的种类数。 满足乘法交换律的算式计为不同的种类所以答案肯定是个偶数。 答案直接通过浏览器提交。 注意只提交一个表示最终统计种类数的数字不要提交解答过程或其它多余的内容
#includeiostream
using namespace std;
int main(){int ans 0;for(int a 1;a 10;a){for(int b 1;b 10;b){if(ba) continue;for(int c 1;c 10;c){if(ca || cb) continue;for(int d 1;d 10;d){if(da||db||dc) continue;for(int e 1;e 10;e){if(ea||eb||ec||ed) continue;if((a*10b)*(c*100d*10e) (a*100d*10b)*(c*10e)){ans;}}}} }}cout ans;return 0;
}
是不是有点蒙蒙没关系给大家上一个纯暴力枚举的题目但是我提前声明一下这个题目用暴力只能解决一部分的数据没办法全部ac的正解需要用到前缀和或者二分双指针都可以由于知识点没讲所以我放出暴力代码和正确代码但是后面讲到知识点的时候提一下正解咋来的自行理解一下吧先。 给定三个整数数组 A[A1,A2,…AN] B[B1,B2,…BN] C[C1,C2,…CN] 请你统计有多少个三元组 (i,j,k) 满足 1≤i,j,k≤N1AiBjCk 输入格式 第一行包含一个整数 N 第二行包含 N个整数 A1,A2,…AN1 第三行包含 N 个整数 B1,B2,…BN 第四行包含 N 个整数 C1,C2,…CN 输出格式 一个整数表示答案。 数据范围 1≤N≤10000 0≤Ai,Bi,Ci≤1000000 输入样例 3
1 1 1
2 2 2
3 3 3输出样例 27 #includeiostream
using namespace std;
int main()
{int n;cinn;int ans0;int a[n],b[n],c[n];for(int i0;in;i)scanf(%d,a[i]);for(int i0;in;i)scanf(%d,b[i]);for(int i0;in;i)scanf(%d,c[i]);for(int i0;in;i){for(int j0;jn;j){for(int k0;kn;k){if(a[i]b[j]b[j]c[k])ans;}}}coutans;return 0;
}
正解
#include cstdio
#include cstring
#include iostream
#include algorithmusing 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];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]] ;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];// 求cs[]memset(cnt, 0, sizeof cnt);memset(s, 0, sizeof s);for (int i 0; i n; i ) cnt[c[i]] ;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]];// 枚举每个b[i]LL res 0;for (int i 0; i n; i ) res (LL)as[i] * cs[i];cout res endl;return 0;
}我再整个跟第一个类似的基本上蓝桥杯考这样的比较多问符合某种性质的数有多少
注意这个题目里面有一个小模版就是如何把一个n位数的每一位数给单独调出来。
先放模板 while (x){int t x % 10; // 取出x的个位x / 10; // 删掉x的个位
}
题目是这样的 小明对数位中含有 2、0、1、9 的数字很感兴趣不包括前导 0在 1 到 40中这样的数包括 1、2、9、10 至 32、39 和 40共 28 个他们的和是 574。 请问在 11 到 n中所有这样的数的和是多少 输入格式 共一行包含一个整数 n 输出格式 共一行包含一个整数表示满足条件的数的和。 数据范围 1≤n≤10000 输入样例 40输出样例 574 再放题目答案
#include iostream
#include algorithmusing 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;
} 四平方和 题目描述 四平方和定理又称为拉格朗日定理 每个正整数都可以表示为至多4个正整数的平方和。 如果把0包括进去就正好可以表示为4个数的平方和。 比如 5 0^2 0^2 1^2 2^2 7 1^2 1^2 1^2 2^2 ^符号表示乘方的意思 对于一个给定的正整数可能存在多种平方和的表示法。 要求你对4个数排序 0 a b c d 并对所有的可能表示法按 a,b,c,d 为联合主键升序排列最后输出第一个表示法 程序输入为一个正整数N (N5000000) 要求输出4个非负整数按从小到大排序中间用空格分开 例如输入 5 则程序应该输出 0 0 1 2 再例如输入 12 则程序应该输出 0 2 2 2 再例如输入 773535 则程序应该输出 1 1 267 838 分析 声明一下这个题目是思路我是跟着别人学的公式我也打不出来只能用一下图片的方式给大家放一下
#includecstdio
#includecmath
int n;
int main(){scanf(%d,n);for(int i0;i*in;i)for(int ji;i*ij*jn;j)for(int kj;i*ij*jk*kn;k){int lint(sqrt(n-i*i-j*j-k*k));if(i*ij*jk*kl*ln){printf(%d %d %d %d,i,j,k,l);return 0;}}
}
放一个独立思考的题目下期出答案毕竟自己思考出来的才是真香练习亿下 2021 是一个非常特殊的数它可以表示成两个非负整数的平方差2021 45 * 45 - 2 * 2。 2025 也是同样特殊的数它可以表示成 2025 45 * 45 - 0 * 0。 请问在 1 到 2021 中有多少个这样的数 请注意有的数有多种表示方法例如 9 3 * 3 - 0 * 0 5 * 5 - 4 * 4在算答案时只算一次。 本次压轴题给大家送上这个题暴力能做还是那句话要有巧法才能ac这个题就无非总结了蓝桥杯枚举的特点以及它未来的考法方向个人理解哈。 小明这些天一直在思考这样一个奇怪而有趣的问题 在 1∼N 的某个排列中有多少个连号区间呢 这里所说的连号区间的定义是 如果区间 [L,R] 里的所有元素即此排列的第 L个到第 R个元素递增排序后能得到一个长度为 R−L1 的“连续”数列则称这个区间连号区间。 当 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样例解释 第一个用例中有 77 个连号区间分别是[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4][1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4] 第二个用例中有 99 个连号区间分别是[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5] 代码如下优化过后的 #include cstring
#include iostream
#include algorithmusing namespace std;const int N 10010, INF 100000000;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 ;}}cout res endl;return 0;
} 最后再给大家用代数法模拟一下这个过程最后一遍帮大家理解一下循环了不会暴力的直接看这也可以理解了
题目的大致思路是如果一个区间[a,b]中max-minb-a那就说明这个区间没有不连续的数字因为一个数字占一个坑位不允许有重复的数所以只能说明没有连续的数字 代码在18行之前都是定义数字和读入数据的这里面就是那个INF是很重要的因为开头肯定要把a[j]读入所以定义minv是个无限大的数maxv反之。 好开始代数了从枚举区间左端点开始代码第18行。eg读入第一组数据 4 3 2 1 4 ,开始i0;minvINF,maxv-INF;ji0,minvmin(INF,a[j]),minva[j]a[0]3; maxvmax(maxv,a[j]),maxva[j]3; maxv-minv3-3j-i0-0;res; j; j1,i0; minvmin(minv(3),a[1]),minva[1]2, maxvmax(maxv(3),a[1]),maxv3; maxv-minv3-2j-i1-0 ;res;j; j2,i0,minv(2,a[2])minv1;maxvmax(maxv,a[2])maxv3;maxv-minv3-1j-i2-0;res; j; j3,i0; minvmin(1,a[3])minv1,maxvmax(3,a[3])maxva[3]4; maxv-minv4-1j-i3-0,res; 返回i; i1 其实到这已经开始新的循环了两轮循环也看清楚咋执行的了这个题目重要的是思路代数法就是验证的一个过程对理解思路没啥好处可以帮大家理解一下循环的过程。
我们下期见
