- 博客(130)
- 收藏
- 关注
RSS订阅原创 查找整数对
【题目】一个长度为n的整型数组a，给定整数x，设计一个复杂度不超过O（nlog2n）的算法，查找出这个数组中所有两两和为x的整数对并输出。【思路】先对该数组进行排序，可以考虑快速排序或归并排序，然后分别从数组的小端i=0和大端j=n-1开始，将两数相加，若和大于x，则大端前移j–，若小于x则小端后移i++，相等则输出两个数，直至i>=j。#include <iostream>#include <algorithm>#define MAX 100using name
2022-03-21 20:54:42
610
原创 蓝桥杯——十六进制转八进制、十进制和十六进制相互转化
#include <iostream>#include <string.h> using namespace std;int main(){ int i,j,n,r; char str[100005],e[400005],b[400005]; //str、e、b分别保存十六、二、八进制数 cin>>n; while(n--) //连续输入 { cin>>str; int len=0; //保存二进制数的长度 for(i=s
2022-03-14 15:22:32
444
原创 动态规划——最小找钱问题
题目：这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如，给定了7种钱币面值为6 2 5 10 20 50 100，用来凑299元，可以用几种方案。我们的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。思路：1、对于这个硬币问题，我们每次都是取硬币，或者不取硬币。因此我们可以将这个硬币问题切割成若干个子问题（取不取这种硬币），而且每次决策都会用到这个子问题。而且所有的子问题中必定存在最优解。2、每次取硬币，都仅仅是做出决策
2021-10-25 17:05:49
1215
原创 洛谷1007——独木桥
思路：士兵相遇时，虽然改变方向，但从远处看，可以认为他们穿过了对方，继续按原来方向前进，所以只需要考虑每个人撤离的最短和最长时间，即当前位置据桥头和桥尾的距离，然后取最后一个士兵完成撤离的最大和最小时间，即求士兵撤离完成最短和最长时间的最大值。图解可参考蚂蚁过桥。#include <bits/stdc++.h>using namespace std; //士兵相遇情形可看作穿过后继续各自走int main(){ int n,m,a[5005],i,j; int tmin=0,t..
2021-10-17 23:48:42
195
原创 洛谷1004——方格取数
思路：由于需要取2条路径最大值之和，且取完该位置数为0，因此两条路径相互影响，需要将两次路径看作两个人同时取数，使用四维dp数组，f[i][j][k][l]表示第一个人走到（i，j），第二个人走到（k，l）时最大取数之和 。代码：#include <bits/stdc++.h>using namespace std;//f[i][j][k][l]表示第一个人走到（i，j），第二个人走到（k，l）时最大取数之和 int main(){ int n,i,j,k,l,x,y,m;..
2021-10-15 23:48:31
371
原创 洛谷1799——数列
题目描述虽然 msh 长大了，但她还是很喜欢找点游戏自娱自乐。有一天，她在纸上写了一串数字：1, 1, 2, 5, 4。接着她擦掉了一个 1，结果发现剩下 1, 2, 4 都在自己所在的位置上，即 1 在第 1 位，2 在第 2 位，4 在第 4 位。她希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个游戏很好玩，于是开始乐此不疲地玩起来……不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！输入格式第一行为一个数 n，表示数列的长度。接下来一行为 n个用空格隔
2021-10-15 23:39:37
1208
原创 洛谷1002——过河卒
题目描述棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，AA 点 (0, 0)(0,0)、BB 点 (n, m)(n,m)，同样马的位置坐标是需要给出的。现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。输入格式一行四个正整数，分别表示 BB 点坐标和马的坐标。输
2021-10-13 18:08:27
314
转载 航电oj——I NEED A OFFER!
Problem DescriptionSpeakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大
2021-10-12 17:55:39
183
原创 洛谷P1003——铺地毯
题目描述为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。输入格式输入共 n+2 行。第一行，一个整数 n，表示总共有 n 张地毯。接下来的 n 行中，第 i+1 行表示编号 ii 的
2021-10-12 17:19:47
83
原创 分治法——归并排序
题目：使用归并排序算法对10个数实现升序排列，输出排序结果。分治步骤如下：1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；2）设定两个指针，最初位置分别为两个已经排序序列的起始位置；3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复3直到某一序列结束，将另一序列剩下的所有元素直接复制到合并序列尾。#include <bits/stdc++.h> using namespace std;#define COUNT 10
2021-09-23 10:15:19
484
原创 分治法——整数因子分解
大于1的正整数n可以分解为：n=x1×x2×…×xm。例如，当n=18时，共有8种不同的分解式。对于给定的正整数n，计算n共有多少种不同的分解式。//////////////////////////////////////////////////////////////////////*/#include <bits/stdc++.h>using namespace std;////////////////////////////////////////////////////////
2021-09-21 11:34:41
3253
原创 回文判断—栈
回文判断：假设称正读和反读都相同的字符序列为“回文”，例如，'abba’和’abcba’是回文，‘abcde’和’ababab’则不是回文。试写一个程序判别读入的一个以’#'为结束符的字符序列是否是“回文”。#include <iostream>#include <cstdio>#include <string>#include <stack>using namespace std;int main(){ stack<char>
2021-04-19 21:44:08
1810
1
原创 硬币问题—贪心算法
分析：代码：#include <iostream>using namespace std;const int a[6]={1,5,10,50,100,500};int main(){ int s[6],i,t,count=0,total; cout<<"分别输入1，5，10，50，100，500硬币的个数："<<endl; for(i=0;i<6;i++) cin>>s[i]; cout<<"输入支付钱数："&l.
2021-04-10 11:26:20
395
原创 让气球升起
问题描述比赛时间又来了！看到气球四处飘荡是多么激动啊。但要告诉你一个秘密，评委们最喜欢的时间是猜测最流行的问题。比赛结束后，他们将计算各种颜色的气球并找到结果。今年，他们决定把这份可爱的工作留给你。输入输入包含多个测试案例。每个测试案例以数字 N （0 < N <= 1000） 开头 - 分布的气球总数。下一个 N 行各包含一种颜色。气球的颜色是多达15个小写字母的字符串。带有 N = 0 的测试案例终止了输入，此测试案例无法处理。输出对于每个案例，在单行上打印气球的颜色，以解决最流
2021-04-10 10:31:20
765
原创 拆分字符串—链表
单链表的分拆：一个单链表，data域为字符型，试将单链表拆分成3个链表，分别包含数字、字母和其它字符。#include <iostream>#include <cstdlib>#include <string.h>#include <iomanip> using namespace std;///////////////////////////////////////////////////////////////////数据结构定义 type
2021-04-06 12:38:42
326
原创 循环链表及应用（删除结点、猴子选大王）
////////////////////////////////////////////////////////////////// #include <iostream>#include <cstdlib>#include <time.h>#include <iomanip> #include <string.h>using namespace std;#define NUMBER 10/////////////////////
2021-04-06 11:11:59
192
原创 两个任意长度整数相加—链表
#include <iostream>#include <cstdlib>#include <time.h>#include <iomanip> #include <string.h>using namespace std;/////////////////////////////////////////////////////////////////#define NUMBER 10////////////////////////
2021-04-06 11:01:12
214
原创 第几天？
Problem Description给定一个日期，输出这个日期是该年的第几天。Input输入数据有多组，每组占一行，数据格式为YYYY/MM/DD组成，具体参见sample input ,另外，可以向你确保所有的输入数据是合法的。Output对于每组输入数据，输出一行，表示该日期是该年的第几天。Sample Input1985/1/202006/3/12Sample Output2071思路：先按月份计算天数，当遇到2月时，判断闰年还是平年，对应29天和28天，最后加上日期数。#
2021-03-31 16:30:08
160
原创 两个多项式的相加—链表
#include <iostream>#include <cstdlib>#include <time.h>#include <iomanip> using namespace std;/////////////////////////////////////////////////////////////////#define NUMBER 10//////////////////////////////////////////////////
2021-03-30 23:34:58
108
原创 平方和与立方和
Problem Description给定一段连续的整数，求出他们中所有偶数的平方和以及所有奇数的立方和。Input输入数据包含多组测试实例，每组测试实例包含一行，由两个整数m和n组成。Output对于每组输入数据，输出一行，应包括两个整数x和y，分别表示该段连续的整数中所有偶数的平方和以及所有奇数的立方和。你可以认为32位整数足以保存结果。Sample Input1 32 5Sample Output4 2820 152#include <stdio.h>#incl
2021-03-29 23:34:47
235
原创 循环队列
循环队列Q的入队和出队的算法。为使队列空间充分利用，增设tag标志。#include <iostream>#include <cstdlib>using namespace std;#define ERROR 0#define OK 1#define Maxsize 100#define Elemtype inttypedef int Status;typedef struct{ Elemtype base[Maxsize]; int front; int
2021-03-29 22:32:10
110
原创 ASCII码排序
Problem Description输入三个字符后，按各字符的ASCII码从小到大的顺序输出这三个字符。Input输入数据有多组，每组占一行，有三个字符组成，之间无空格。Output对于每组输入数据，输出一行，字符中间用一个空格分开。Sample InputqweasdzxcSample Outpute q wa d sc x z#include <stdio.h>#include <stdlib.h>void swap(char* a,char*
2021-03-28 17:39:50
235
原创 进制转换——栈
对输入的十进制整数n，输出转换后得到的R进制数（假定R在2-36之间）。#include <iostream>#include <cstdlib>#include <string.h>using namespace std;#define ERROR 0#define OK 1#define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 typedef
2021-03-27 17:22:05
273
原创 括号匹配
假设一个算术表达式中可以包含三种括号：圆括号“(”和“)”、方括号“[”和“]”和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。其中：exp为字符串类型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式。函数返回值为布尔型，true表示正确配对，false表示不配对。注意：仅针对括号判断。#include <iostream>#include <cstdlib>
2021-03-27 16:37:05
178
原创 链表的有关操作
/*///////////////////////////////////////////////////////////////随机产生n个整数，进行单链表操作 ///////////////////////////////////////////////////////////////*/#include <iostream>#include <cstdlib>#include <time.h>#include <iomanip> using
2021-03-26 00:21:47
101
原创 顺序表操作
/*////////////////////////////////////////////////////////////////////////////顺序表的操作：初始化、建立、插入、删除、逆置、并集、交集、输出 ////////////////////////////////////////////////////////////////////////////*/ #include<iostream>#include<stdlib.h>#include <i
2021-03-26 00:20:33
108
原创 调换字符串
输入字符串个数、调换个数以及字符串，输出调换后字符串排列。输入5 2A1B2C3D4E5输出D4E5A1B2C3代码：#include <iostream>#include <cstring> using namespace std; int main(){ string a[20],b[20]; int n,k,i,j; cin>>n>>k; for(i=0;i<n;i++) cin>>a[
2021-03-20 00:18:44
148
原创 答题排名
题目：有n个学生进行答题，每题分值分别是10、20、30、50、80、40，输入字符代表学生姓名，字符串代表答题情况，若正确则为1，错误为0，输出他们的排名。输入3A 101001B 111101C 100001输出BAC#include <iostream>#include <cstring>#include <algorithm> using namespace std; int f[6]={10,20,30,50,80,40};
2021-03-19 23:18:10
179
原创 抽签
思路：由题知，需要寻找数满足a+b+c+d=m，采用二分查找法。检查是否有c和d使得c+d=m-a-b，这种情况要预先枚举出c+d所得的n*n个数字并排好序,再利用二分搜索。记所要查找的值m-a-b为x,预先把数组排好序,然后看数组中央的数字,可知如果它比x小,x只可能在它的后面半段；如果它比x大, x只可能在它的前面半段。如果再将上述方法运用在已经减半的x的存在区间上,x的存在区间就变成了初始的1/4,这样反复操作就可以不断缩小x的存在区间,最终可以确定x存在与否。代码：#inclu..
2021-03-19 12:50:13
76
原创 选数
题目描述：已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3＋7＋12=22，3＋7＋19＝29，7＋12＋19＝38，3＋12＋19＝34。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3＋7＋19＝29）。输入：n , k （1<=n<=20，k＜n）x1,x2，…,xn （1<=xi&
2021-03-18 23:29:49
253
原创 逢三出局
题目：有10个人围成一圈，顺序排号0~9，从第一个人开始报数(从1到3报数),凡是报到3的人退出圈子，剩下的继续从1开始报数，问最后留下来的人序号是多少？分析：先将所有人标记为1，报数时若报到3，标记为0，出局数加一，即此人出局，然后继续报数，直至出局数为9时，得出最后一个人的序号数。代码：#include <stdio.h>#include <stdlib.h>#define SIZE 10int main(int argc, char *argv[]) {
2021-01-17 23:24:15
249
原创 水洼的个数—深度优先搜索
#include <iostream>using namespace std;#define MAX_SIZE 100int n, m;char field[MAX_SIZE][MAX_SIZE+1];void dfs(int x, int y){ field[x][y] = '-'; //把当前位置替换成'-' for(int dx=-1; dx<=1; dx++) //循环遍历8个方向 for(int dy=-1;dy<=1;dy++
2021-01-16 18:22:29
174
原创 随机数—最大值、排序、插入数
求随机数的最大值方法一：#include <stdio.h>#include <stdlib.h>#define SIZE 20int main(int argc, char *argv[]) { int a[SIZE],i; srand(time(0)); //设置种子，time（0）得到当前时间值，负责每次运行值相同 for(i=0;i<SIZE;i++) { a[i]=rand()%100; //产生100以内的随机值 p
2021-01-15 21:41:08
485
原创 求1000以内的完数及100以内所有素数
完数：一个数恰好等于它的真因子之和分析：第一个完全数是6，1+2+3=6。第二个完全数是28，1+2+4+7+14=28。第三个完全数是496，1+2+4+8+16+31+62+124+248=496。#include <stdio.h>#include <stdlib.h>#include <math.h>int main(int argc, char *argv[]) { int n,i,sum; for(n=2;n<1000;n++) {
2021-01-15 17:04:39
411
原创 如何删数
题目：键盘输入一个高精度的正整数ｎ（<=240位），去掉任意ｓ个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的ｎ和ｓ，寻找一种方案，使得剩下的数最小。输入1785434输出13思路：高位越小则值越小，尽可能删除较大的高位数字。将相邻两位比较，若高位比低位大，则删除高位。代码：#include <iostream>#include <algorithm>#include <cstring>using namespace std
2020-12-11 23:59:29
189
原创 部分和问题
思路：代码：#include <cstdio>using namespace std;#define MAX 20int a[MAX];int n,k;bool dfs(int i,int sum){ if(i==n) return sum == k; //若遍历结束，返回sum==k是否成立，成立则返回1，否则返回0 if(dfs(i+1,sum)) //不加上a[i] return true; if(dfs(i+1,sum+a[i])) /..
2020-12-06 22:16:55
105
原创 蚂蚁掉落最短和最长时间
思路：代码：#include <stdio.h>#include <stdlib.h>#define MAX 100000int l,n,i;int x[MAX];int max(int a,int b)//最大值函数 { return a>b?a:b;} int min(int a,int b)//最小值函数 { return a>b?b:a;}int solve(){ int t1=0,t2=0; for(i=0;i<.
2020-12-06 22:07:40
155
原创 十六进制两数相加—航电oj2057
InputThe input contains several test cases, please process to the end of the file.Each case consists of two hexadecimal integers A and B in a line seperated by a blank.The length of A and B is less than 15.输入包含多个测试用例，请处理到文件的末尾。每个情况由两个十六进制整数 A 和 B 组成，在一行
2020-12-05 17:15:40
806
原创 空心三角形—航电oj2091
Problem Description把一个字符三角形掏空，就能节省材料成本，减轻重量，但关键是为了追求另一种视觉效果。在设计的过程中，需要给出各种花纹的材料和大小尺寸的三角形样板，通过电脑临时做出来，以便看看效果。Input每行包含一个字符和一个整数n(0<n<41)，不同的字符表示不同的花纹，整数n表示等腰三角形的高。显然其底边长为2n-1。如果遇到@字符，则表示所做出来的样板三角形已经够了。Output每个样板三角形之间应空上一行，三角形的中间为空。显然行末没有多余的空格。Sa
2020-12-04 16:30:41
244
转载 航电oj2093—考试排名
#include <iostream>#include <string.h>#include <algorithm> using namespace std; struct Stu{ string name; //学生姓名 int score; int num;};bool cmp(Stu a,Stu b){ return a.num!=b.num?a.num>b.num:a.score<b.score;}int mai..
2020-12-01 22:27:40
165
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人