[蓝桥杯]校内培训交流会总结

[蓝桥杯]校内培训交流会总结

//【蓝桥杯培训交流会 整理]//破解编程题目/* 破解编程题目 编程题是如何评测的？ 黑箱测试： 程序-> 编译->运行->比对 运行： 1. 将stdin重定向data.in 2. 将stdout重定向到user.out 比对： 比对data.out和user.out是否相同 出题人如何准备数据？ 出题人会预先设定一组数据： data0.in - data0.out data1.in - data1.out data2.in - data2.out 出题人目的： 测试程序正确性和效率 随机数据 边界数据 特殊数据(某些算法会退化) 规模最大的数据 较小规模数据(给部分分) 我们如何应对？ 根据数据规模和时间限制估计复杂度 (现在主流电脑1秒 = 10^8复杂度量级) 放弃满分，争取部分分 一些常见的数据规模和出题人期望的复杂度 N <= 12 O(N!) N <= 20 O(2N) N <= 100 O(N3) N <= 1000 ~ 10000 O(N2) N <= 100000 ~ 1000000 O(NlogN) N <= 1000000+ O(N) 有些题目会说明有部分分的数据范围 有些题目没有说明，需要自行判断 自测：对拍 1. sample只是用来举例说明格式和题意， 实际系统测试使用的数据比sample复杂得多。 2. 把自己当出题人，字母测出来选手程序的BUG低效 3. 出题人的目的：测试程序正确性和效率 用程序生成随机数据生成 举例：随机生成N个0~M的整数 用程序生成特殊大数据 [例] #include #include using namespace std ; int n,m,seed ; int main() { cin >> n >> m >> seed ; srand(seed) for(int i = 0; i < n; i++) { int x = rand() % m ; cout << x << endl ; } return 0 ; } “对拍” 很多时候一道题目都有很简单的朴素算法，但是效率很低 我们要拿满分不得不实现一个更复杂的高效算法 为了避免程序有BUG，我们可以再写一个朴素算法”对拍” 举例：朴素匹配 VS KMP 朴素算法很容易实现： if (s.find(p)) … 写一个脚本/程序，不断执行以下步骤 生成一个随机小数据 运行朴素匹配程序，得到结果文件1 运行KMP程序，得到结果文件2 比较文件1和文件2 大数据朴素程序太慢，小数据也能测正确性 对拍过程中，我们可以做别的题目 需要一些Windows命令行和脚本的知识 【大赛题型】 结果填空题： 1.已知测试数据，实现超长(~4小时)的编程大题。 2.难度相对简单，告诉你怎么做 3.程序已经有大致框架，可以测试 4.“送分题”，丢分很可惜 5.但是也有相当一部分没有满分 程序填空题 从main函数开始，自顶向下 1.理解变量的作用 2.推测每一条语句在做什么 3.特别是每一个循环在做什么 4.如果有递归，推测一个函数整体在做什么 5.如果所填内容不影响程序流程， 不妨先随便填一个然后运行程序，了解流程 如何答好程序填空题 1.多读别人的程序 2.出题人的程序相对比较精炼 3.同样的逻辑，不同人可能有不同的写法 4.见多识广，精益求精 5.蓝桥杯历届题目在网上都能搜到别人公开的程序 6.NOIP中有很多完善程序的题目，他山之石 编程大题 基础难度： 基础：枚举、搜索、模拟 考察基本功、基本的代码能力 学习编程的第一道门槛： “我不会高大上的算法和数据结构，程序可能超时，但是不会出错” 编程基础最重要 蓝桥杯中数列最多的题目类别 【枚举】枚举的要点：如果我一个算法根据数据范围、时限我知道要超时，我们怎么减少复杂度？方法不外乎就是1减少枚举的变量，原来我要枚举4个变量，能不能只枚举3个？ 2就是缩小枚举范围，我能不能通过改变枚举的变量，减少范围？ 确定需要的枚举变量 确定枚举的范围（不重不漏）1是二分，二分查找、二分搜索非常有效，一般是复杂度从O(N)降到O(logN)，使用范围也很广。2是用Hash，空间换时间。3此外还有一些常用的套路：比如双指针，Leetcode上对应的分类是two pointer，直译过来就是双指针，大概的思想就是滑动窗口。4还比如前缀后缀和，也是空间换时间的思路。【常见的枚举题类型】： 枚举答案： 答案难以计算，易于验证 按某个顺序(从小到大)枚举每个可能的答案，验证。 例题：哪天返回、猴子分香蕉、以及一些逻辑推理题 枚举日期： 例题：某年某月某日星期几 关键：判断某个日期是不是合法 int days[-1,31,28,31,30,31,30,31,31,30,31,30,31] ; is_leap_year(int year) 枚举数位：(枚举有规律的数列) 例题:等腰三角形 12345678910111213…. 第N个数位是几 1,2,2,3,3,3,4,4,4,4,…… 关键： 分离各位数字,设计状态变量 枚举位置、方向 例题：字母阵列、回形填数 关键： int dx = {-1, 1, 0, 0}; int dy = {0, 0, -1, 1} 方向数组描述上下左右,设计状态变量 基础的枚举类型： 选择枚举变量：优化思想 例题：第几个幸运数 二分、哈希、双指针、前缀、后缀和STL-set用法：set跟vector差不多，它跟vector的唯一区别就是，set里面的元素是有序的且唯一的，只要你往set里添加元素，它就会自动排序，而且，如果你添加的元素set里面本来就存在，那么这次添加操作就不执行。/*———————————————————————————————————————————————————————————题目：平方十位数问题描述： 由0~9这10个数字不重复、不遗漏，可以组成很多10位数字。这其中也有很多恰好是平方数（是某个数的平方）。比如：1026753849，就是其中最小的一个平方数。请你找出其中最大的一个平方数是多少？　　————————————————————————————————————————————————————————————*//*思路1：枚举答案X [9876543210, 1026753849]判断是不是恰好0-9十个数字判断是不是完全平方数令Y = int(sqrt(X))判断Y * Y == X？*/ /*思路2：枚举Y [100000, 30000]计算X = Y * Y判断X是不是恰好0-9十个数字 *///常见问题：分离整数X的个位数字if(X == 0) { //特判}while(X) { int d = X % 10; //处理d X /= 10;}bool valid(int x) { //恰好包含0-9 if(x == 0) return false; set s; while(x) { int d = x % 10; s.insert(d); x /= 10; } return s.size() == 10;}/*————————————————————————————————————————————————————————————*/#include #include using namespace std;//判断是不是包含0~9的代码bool contains0_9(long long x){ if(x==0)return false;//这里没什么用，算法的严谨性 set s; //分离x的各位数字，每次把x的末尾数字分离出去 while(x) { int d=x%10;//d是x末位数字 s.insert(d);//把d插入s中 x/=10;//更新x } return s.size()==10;}int main(int argc, char *argv[]) { //c语言中基本整型int占据两个字节， //取值范围-2^15--2^15-1(-32768--32767)肯定不够 //用 long long for (long long i=100000; i--; i>30000) {//找最大，倒着来 long long x=i*i; if(contains0_9(x)) { cout << x << endl; return 0; } } return 0;}//输出：结果为：9814072356。 /*———————————————————————————————————————————————————————————题目：四平方和问题描述：四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去，就正好可以表示为4个数的平方和。比如：5 = 0^2 + 0^2 + 1^2 + 2^27 = 1^2 + 1^2 + 1^2 + 2^2（^符号表示乘方的意思）对于一个给定的正整数，可能存在多种平方和的表示法。要求你对4个数排序：0 <= a <= b <= c <= d并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法程序输入为一个正整数N (N<5000000) //思路1：枚举abcd，判断a^2+b^2+c^2+d^2是否等于N分析规模：a：0 ~ sqrt(5000000 / 4)b：0 ~ sqrt(5000000 / 3)c：0 ~ sqrt(5000000 / 2)d : 0 ~ sqrt(5000000)abcd枚举的范围大约都是1000~2000总枚举量 10^12 还记得我们的经验吗？ 1秒 = 10^8　优化套路一：减少枚举变量，以计算代枚举思路2：枚举abc，判断N-a^2-b^2-c^2是不是完全平方数分析规模：a：0 ~ sqrt(5000000 / 4)b：0 ~ sqrt(5000000 / 3)c：0 ~ sqrt(5000000 / 2)总枚举量 10^9 还是会超时！问题：能不能只枚举ab？分析：只枚举ab，那么余下R=N-a^2-b^2能否快速求出c^2+d^2=R的解？（或者快速判断出无解)例如：N = 5, 当前枚举a=b=0。c^2+d^2 = 5，能不能快速求出解c=1, d=2。优化套路二：用哈希预处理出的可行解思路2：先预处理出c^2+d^2=R的可行解，保存在哈希表里。枚举ab，通过查表判断无解或者有解。————————————————————————————————————————————————————————————*//*空间换时间的利器：哈希查找一个东西存不存在是我们经常遇到的一个基本问题哈希(hash)：把将来需要查找的值预先保存起来，减少查找时间。基本问题：给一个数组[1, 3, 13, 4, 5, 27 … ]询问某个值V是否在数组里(在数组哪个位置)遍历数组、枚举：O(N)哈希：O(N)预处理，O(1)查询实现方法：数组(int my_hash[值域])、set(TreeSet)、map(TreeMap)、unordered_set(HashSet)、unordered_map(HashMap)unordered_set可以把它想象成一个集合，它提供了几个函数让我们可以增删查：unordered_set::insertunordered_set::findunordered_set::erase由于它内部是用哈希表实现的，所以上面这三个函数的平均时间复杂度都是O(1)。我们可以看一个简单的例子。#include#includeusing namespace std ;int main(){ unordered_set myset ; myset.insert(3) ; myset.insert(5) ; myset.insert(3) ; cout << myset.size() << endl ; myset.erase(3) ; if(myset.find(3) == myset.end()) cout << "3 not found" endl ; return 0 ;}#include头文件。然后有两点需要注意：一是这个容器是个集合，所以重复插入相同的值是没有效果的。二是find的返回值是一个迭代器(iterator)，如果找到了会返回指向目标元素的迭代器，没找到会返回end() *///#includeint n;unordered_map f;int main(){ cin >> n; for(int c = 0; c * c <= n / 2; c++) { for(int d = c; c * c + d * d <= n; d++) { if(f.find(c * c + d * d) == f.end()) { f[c * c + d * d] = c; } } } for(int a = 0; a * a * 4 <= n; a++) { for(int b = a; a * a + b * b <= n / 2; b++) { if(f.find(n - a * a - b * b) != f.end()) { int c = f[n - a * a - b * b]; int d = int(sqrt(n - a * a - b * b - c * c) + 1e-3); cout << a << ' ' << b << ' ' << c << ' ' << d << endl; return 0; } } } return 0;}//思路2int n;unordered_map f;int main(){ cin >> n; for(int c = 0; c * c <= n / 2; c++) { for(int d = c; c * c + d * d <= n; d++) { if(f.find(c * c + d * d) == f.end()) { f[c * c + d * d] = c; } } } for(int a = 0; a * a * 4 <= n; a++) { for(int b = a; a * a + b * b <= n / 2; b++) { if(f.find(n - a * a - b * b) != f.end()) { int c = f[n - a * a - b * b]; int d = int(sqrt(n - a * a - b * b - c * c) + 1e-3); cout << a << ' ' << b << ' ' << c << ' ' << d << endl; return 0; } } } return 0;}/*———————————————————————————————————————————————————————————题目：2018年倍数问题问题描述： 众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。数据规模与约定 对于 30% 的数据，n <= 100。对于 60% 的数据，n <= 1000。对于另外 20% 的数据，K <= 10。对于 100% 的数据，1 <= n <= 10^5, 1 <= K <= 10^3，给定的 n 个数均不超过 10^8。————————————————————————————————————————————————————————————*///思路：//在n个数中找出3个数的和是k的倍数并且要最大，三重循环肯定是不可取的，所以用dfs。#include#include#include#include#include#include#include#include#include#include

Talk is cheap. Show me the code

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。