Blog of a programmer who wants to open a cafe

原创 蓝桥杯比赛注意事项

三种题型：结果填空题、代码填空题、编程大题程序一定要以 return 0；结尾多组输入题中会给出——多组T，否则无须多组输入大题提交的时候要选择哪种语言c、c++、java注意时间复杂度可空间复杂度是否满足字符数组使用前要清0#include<stdio.h>#include<string.h>int main(){ char dest[25]; ...

原创 求循环节长度

【题目描述】两个整数做除法，有时会产生循环小数，其循环部分称为：循环节。比如，11/13 = 0.846153846153…其循环节为846153共有6位。【样例输入】11 13【样例输出】6【代码】#include <iostream>#include <algorithm>#include <vector>using namespace ...

原创 时间复杂度和空间复杂度

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a++; //1 }}for (int i = 0; i < n; i++) { b++; //2}while (n) { n = n / 2; //3}int a[n];int b[n][...

原创 练习题-小计算器

【资源限制】时间限制：1.0s 内存限制：256.0MB【问题描述】模拟程序型计算器，依次输入指令，可能包含的指令有数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)输出指...

原创 比赛和训练中特别容易犯的一些低级错误和治疗方法

原创 堆排序 Heap Sort

堆和优先队列 Heap and priority Queue❓什么是优先队列？普通队列：先进先出，后进后出优先队列：出队顺序和入队顺序无关，和优先级相关❓为什么使用优先队列？在1,000,000个元素中选出前100名？抽象：在N个元素中选出前M个元素排序？NlogN使用优先队列？NlongM❓优先队列主要操作？入队出队：取出优先级最高的元素❓优先队列的实现？【注】使用堆...

原创 Merge Sort和Quick Sort的衍生问题

Merge Sort和Quick Sort的衍生问题【1】Merge Sort和Quick Sort都使用了分治算法顾名思义，分而治之，就是将原问题，分割成同等结构的子问题，之后将子问题逐一解决后，原问题也就得到了解决。【2】求一个数组中逆序对的数量（衡量一个数组的有序程度）（思路1）暴力解法（思路2）使用Merge Sort的思路求逆序对的个数，算法复杂度为O(nlogn)要解决...

原创 快速排序法-Quick Sort

快速排序法-Quick Sort【算法思想】(1)在当前数组中选择一个数为基点，使它处于排好序的位置，并且这个数左边的数小于它，右边的数大于它。(2)分别对这个基点左右两边的数进行相同操作。【Partition】(1)通常选取数组最左边的数作为分界点元素，这里我们标记为l，然后我们开始遍历剩余的数组，将其分为小于v的部分和大于v的部分，这两个部分的分界点我们用j来表示。当前访问的元素...

原创 归并排序法-Merge Sort

归并排序-Merge Sort(O(nlogn))【算法思路】(1)要对如下数组进行归并排序，首先将数组分为两半分别进行排序。(2)然后再将左边数组和右边数组分别分为两半，进行排序。(3)同理，再次分半。这是每个部分只有一个元素，可以当作是有序的，这是我们要向上归并。(4)一直归并，直到归并到最后一层，这是数组就已经有序了【归并过程】(1)首先开辟一个同样大小的临时空间来...

原创 插入排序法-Insertion Sort

插入排序-Insertion Sort        其实插入排序的思想和打扑克时整理扑克牌的思想是一样的，看后面的每张牌，将它们插入到前面合适的位置，当最后一个牌进行操作之后手里的牌就是有序的了。(1)如下是我们要排序的数组。首先，第一个元素8的位置不动，默认已经排好序了(2)然后为第二个元素6找到合适的...

原创 选择排序法-Selection Sort

一、O(n2)的排序算法(1)基础(2)编码简单，易于实现，是一些简单情景的首选(3)在一些特殊情况下，简单的排序算法更有效(4)简单的排序算法思想衍生出复杂的排序算法(5)作为子过程，改进更复杂的排序算法二、选择排序-Selection Sort(1)对下面数组从小到大排序(2)找到数组中最小的元素1和第一个位置8进行交换，此时1这个元素就已经在最终数组排好序的位置了(3...

原创 2019蓝桥杯省赛C++A组真题解析

试题A: 平方和本题总分：5 分【问题描述】小明对数位中含有2、0、1、9 的数字很感兴趣，在1 到40 中这样的数包括1、2、9、10 至32、39 和40，共28 个，他们的和是574，平方和是14362。注意，平方和是指将每个数分别平方后求和。请问，在1 到2019 中，所有这样的数的平方和是多少？【解题思路】暴力法枚举1～2019即可，注意保存平方和使用long long【...

原创 蓝桥杯2013A——颠倒的价牌

标题: 颠倒的价牌小李的店里专卖其它店中下架的样品电视机，可称为：样品电视专卖店。其标价都是4位数字（即千元不等）。小李为了标价清晰、方便，使用了预制的类似数码管的标价签，只要用颜色笔涂数字就可以了。 这种价牌有个特点，对一些数字，倒过来看也是合理的数字。如：1 2 5 6 8 9 0 都可以。这样一来，如果牌子挂倒了，有可能完全变成了另一个价格，比如：1958 倒着挂就是：8561，差了几千元...

转载 2013蓝桥杯A组——振兴中华

标题: 振兴中华小明参加了学校的趣味运动会，其中的一个项目是：跳格子。地上画着一些格子，每个格子里写一个字，如下所示：比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。要求跳过的路线刚好构成“从我做起振兴中华”这句话。请你帮助小明算一算他一共有多少种可能的跳跃路线呢？方法一：递归，组合计数#inclu...

原创 2013蓝桥杯省赛A组C/C++——B题

题目标题: 排它平方数小明正看着 203879 这个数字发呆。原来，203879 * 203879 = 41566646641这有什么神奇呢？仔细观察，203879 是个6位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。具有这样特点的6位数还有一个，请你找出它！再归纳一下筛选要求：1. 6位正整数2. 每个数位上的数字不同3. 其...

原创 三角形面积&外接圆&内切圆

三角形面积4 * area = sqrt((a + b + c) * (a + b - c) * (a + c - b) * (b + c - a))ORs = (a +b + c) / 2.0area = sqrt(s * (s - a) * (s - b) * (s - c))外接圆半径R = (a * b * c) / sqrt(4 * b * b - (b * b + c * ...

原创 Java学习之网络编程

###26.01_网络编程(网络编程概述)(了解)A:计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统。B:网络编程就是用来实现网络互连的不同计算机上运行的程序间可以进行数据交换。###26.02_网络编程(网络编程三要素之IP概述)(掌握...

原创 Java学习之线程(二)

###25.01_多线程(单例设计模式)(掌握)单例设计模式：保证类在内存中只有一个对象。如何保证类在内存中只有一个对象呢？(1)控制类的创建，不让其他类来创建本类的对象。private(2)在本类中定义一个本类的对象。Singleton s;(3)提供公共的访问方式。 public static Singleton getInstance(){return s}单例...

原创 Java学习之IO流(三)

###22.01_IO流(序列流)(了解)1.什么是序列流序列流可以把多个字节输入流整合成一个, 从序列流中读取数据时, 将从被整合的第一个流开始读, 读完一个之后继续读第二个, 以此类推.2.使用方式整合两个: SequenceInputStream(InputStream, InputStream) FileInputStream fis1 = new FileInpu...

原创 Java学习之IO流(二)

###21.01_IO流(字符流FileReader)1.字符流是什么字符流是可以直接读写字符的IO流字符流读取字符, 就要先读取到字节数据, 然后转为字符。 如果要写出字符, 需要把字符转为字节再写出.2.FileReaderFileReader类的read()方法可以按照字符大小读取 FileReader fr = new FileReader("aaa.txt"...

原创 Java学习之线程(一)

###24.01_多线程(多线程的引入)(了解)1.什么是线程线程是程序执行的一条路径, 一个进程中可以包含多条线程多线程并发执行可以提高程序的效率, 可以同时完成多项工作2.多线程的应用场景红蜘蛛同时共享屏幕给多个电脑迅雷开启多条线程一起下载QQ同时和多个人一起视频服务器同时处理多个客户端请求###24.02_多线程(多线程并行和并发的区别)(了解)并行就是...

原创 Java学习之IO流(一)

###20.01_IO流(IO流概述及其分类)1.概念IO流用来处理设备之间的数据传输Java对数据的操作是通过流的方式Java用于操作流的类都在IO包中流按流向分为两种：输入流，输出流。流按操作类型分为两种：字节流 : 字节流可以操作任何数据,因为在计算机中任何数据都是以字节的形式存储的字符流 : 字符流只能操作纯字符数据，比较方便。2.IO流常用父类字节流的...

原创 Java学习之File类

###19.13_File类(File类的概述和构造方法)A:File类的概述File更应该叫做一个路径文件路径或者文件夹路径路径分为绝对路径和相对路径绝对路径是一个固定的路径,从盘符开始 D:aaa/bbb/ccc相对路径相对于某个位置,在eclipse下是指当前项目下,在dos下查看API指的是当前路径文件和目录路径名的抽象表示形式B:构造方法File(S...

原创 Java学习之异常

###19.01_异常(异常的概述和分类)A:异常的概述异常就是Java程序在运行过程中出现的错误。B:异常的分类通过API查看ThrowableError服务器宕机,数据库崩溃等ExceptionC:异常的继承体系ThrowableErrorExceptionRuntimeException###19.02_异常(JVM默认是如何处理异...

原创 Java学习之集合(四)

###18.01_集合框架(Map集合概述和特点)A:Map接口概述查看API可以知道：1* 将键映射到值的对象2* 一个映射不能包含重复的键 K3* 每个键最多只能映射到一个值 VB:Map接口和Collection接口的不同1* Map是双列的,Collection是单列的2* Map的键唯一,Collection的子体系Set是唯一的3* Map集合的数据结构值针...

原创 Java学习之集合(三)

###17.01_集合框架(HashSet存储字符串并遍历)(掌握)A:Set集合的特点(无序、不重复)*与之相对的List是可以重复的(查看API即可)B:案例演示HashSet存储字符串并遍历 HashSet&lt;String&gt; hs = new HashSet&lt;&gt;(); //创建HashSet对象 boolean b1 = hs....

原创 Java学习之集合(二)

###16.01_集合框架(去除ArrayList中重复字符串元素方式)(掌握)A:案例演示需求：ArrayList去除集合中字符串的重复值(字符串的内容相同)思路：创建新集合方式 /** * A:案例演示 * 需求：ArrayList去除集合中字符串的重复值(字符串的内容相同) * 思路：创建新集合方式 */ public static void...

原创 Java学习之集合(一)

###15.01_集合框架(对象数组的概述和使用)A:案例演示需求：我有5个学生，请把这个5个学生的信息存储到数组中，并遍历数组，获取得到 每一个学生信息。 Student[] arr = new Student[5]; //存储学生对象 arr[0] = new Student(&amp;amp;amp;amp;quot;张三&amp;amp;amp;amp;quot;, 23); arr[1] = new Stu

原创 最大公约数(辗转相除法)与最小公倍数

#include &lt;stdio.h&gt;int main(){ int a,b,c,m,t; printf("请输入两个数:\n"); scanf("%d%d",&amp;a,&amp;b); if(a&lt;b) { t=a; a=b; b=t; } m=a*b; //辗转...

原创 字母三角形

输出格式按照题目描述，输出字母三角形。样例输如12样例输出1    A  BBB 样例输入23样例输出2    A  BBBCCCCC#include&lt;iostream&gt;#include&lt;String&gt;using namespace std;int main(){ int n; cin &gt;&gt; n;...

原创 2016蓝桥杯省赛B组第一题

一堆煤球，堆成三角棱锥形。具体：第一层放1个，第二层3个(排列成三角形)，第三层6个(排列成三角形)，第四层10个(排列成三角形)，.......如果一共有100层，共有多少个煤球？#include&lt;stdio.h&gt;int main(){ int tmp=0,sum=0;//分别代表每层的煤球数和n层煤球数总和 for(int i=1;...

原创 字符串的复制

下面代码实现把一个串p复制到新的位置q。请填写空缺语句。char* p = "abcde";char* q = (char*)malloc(strlen(p)+1);for(int i=0;___________;i++) q[i] = p[i];q[i] = 0;答案:p[i]或*(p+i)字符串是以'\0'结尾的，而'\0'的ASCII码等于0，所以当p[i]读到字...

原创 求循环节的长度

两个整数做除法，有时会产生循环小数，其循环部分称为：循环节比如，11/13 = 0.846153846153...其循环节为846153共六位。 #include &lt;iostream&gt;#include &lt;algorithm&gt;#include &lt;vector&gt;using namespace std;int f(int n, int m) { ...

原创 贪心算法总结

贪心算法(贪婪算法) 定义：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 *局部最优解     到      整体最优解...

翻译 dfs——炸弹人最多杀敌

#include&amp;lt;stdio.h&amp;gt;char a[20][21];int book[20][20],max,mx,my,n,m;int getnum(int i,int j){ int sum,x,y; sum=0; x=i; y=j; while(a[x][y] != '#') { if(a[x][y] == 'G') sum++; x--; ...

原创 杨辉三角(c++队列模板实现)

#includeusing namespace std;template class LinkQueue{struct LinkQueueNode{T data;LinkQueueNode link;LinkQueueNode(T &amp;amp; theData, LinkQueueNode * n=NULL):data(theData),link(n){}};LinkQueue...