- 博客(33)
- 收藏
- 关注
RSS订阅原创 栈队_A1056 Mice and Rice (25 point(s))
题意：m个数，n个一组，要求每组选出最大的数字晋级到下一轮，其余数字排名相同，直到决出最后一名。代码#include<cstdio>#include<algorithm>#include<iostream>#include<queue>using namespace std;const int maxn = 1010;struc...
2019-08-12 21:20:27
127
原创 简易计算器_中缀表达式转后缀表达式 (STL应用)&&(包含英文括号，有错误请打我)
//样例输入//30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92//0//样例输出//12178.21#include<cstdio>#include<string>#include<map>#include<queue>#include&l...
2019-08-03 12:18:46
179
原创 PAT A1022 ( STL相关&&输入相关）这题很重要
题意：输入每本书的id、书名、作者、关键词（不超过5个）、印刷厂、年份，给出n个读者查询列表，每条查询的种类（书名/作者/关键词等等）给出满足查询条件的id。Sample Input:31111111The Testing BookYue Chentest code debug sort keywordsZUCS Print20113333333Another T...
2019-08-02 16:50:14
145
原创 PAT A1100 Mars Numbers (20 point(s)) 【map&&输入相关】
题意：火星文是13进制的字符数组，要求你完成火星文–int 和 int–火星文的对照。注意：intTostr 可以用stringstrToint 可以用map因为此题范围较小，故可以直接使用打表，也就是把所有数据先init()好。注意输入的时候不能直接用cin>>，因为是一行一行的捕捉，其中可能会包含空格，所以数据数目的输入用 scanf(%d*%c,&...
2019-07-07 17:03:07
114
原创 PAT1063 Set Similarity (25 point(s))
题目大意：给出几组数字，求出其中2组的相似度（same/total)，distinct.注意：不重复用set，可以把比较过程+输出过程封装函数。代码：#include<algorithm>#include<iostream>#include<cmath>#include<set>using namespace std;...
2019-06-27 23:06:16
87
原创 PAT A1039&&A1047 vector
题目大意：给出c个课程代号，和每个课程对应的选课学生名字（4位char)。然后再给出k个学生名字，要求按照顺序输出每个学生的选课数和已选课程代号，课程代号升序表示。注意点学生名字对应选课代号可以用map<string,vector< Int> >,但本题数据量很大，不能用map，只能把学生名字转化成id，用hash存储。(对于本题来说，vector和ma...
2019-06-27 17:29:59
144
原创 质因子分解 PAT A1059 Prime Factors (25 point(s))
题目要求如下：Sample Input:97532468Sample Output97532468=2^211171011291注意点：findprime和isprime函数要熟练注意特例：num==1的情况注意存在质因子>sqrt的情况，就是num本身了#include<cstdio>#include<iostream&g...
2019-06-20 23:03:09
101
原创 算法：进制转换
10进制转D进制 do { arr[t++] = N % D; N /= D; }while(N != 0);D进制转10进制for(int i = 0; i < t; i++) { N = N * D + arr[i]; }...
2019-06-19 17:15:32
149
原创 数学问题
1. 求素数第一种：枚举判断 O(n*√n)// 列举100以内的素数#include<iostream>#include<algorithm>#include<cmath>using namespace std;const int maxn = 110;int num[maxn] = {0}, numP = 0;bool isPrim...
2019-06-16 16:05:46
102
原创 A1104 Sum of Number Segments (20 point(s))
找规律#include<cstdio>#include<algorithm>#include<iostream>using namespace std;int main(){ int n; double ans = 0.0; cin >> n; for(int i = 1; i <= n; i+...
2019-06-03 22:26:12
72
原创 STL相关
String #include<string>stoi：string转int- int a = stoi(a) - stoi(b） #string转intinsert- insert（0,2,'*'） #在0到2位置上插入*to_string-int a=5; string s = to_string(a); #string转int...
2019-06-03 18:05:55
106
原创 A1069 The Black Hole of Numbers (20 point(s))
题目大意：给出一个4位数字，如6767，实现以下过程：7766 - 6677 = 10899810 - 0189 = 96219621 - 1269 = 83528532 - 2358 = 61747641 - 1467 = 6174… …注意：善用STLSTL代码：//7766 - 6677 = 1089//9810 - 0189 = 9621//9621 - ...
2019-06-03 17:53:00
133
原创 PAT A1101 Quicksort
题目大意：给出一串不重复的数字，其中主元是满足这样条件的数字：其左边所有数字都小于它，右边所有数字都大于它。让你求出这串数字中的主元个数并列出。注意点：确定一个数字是否是主元的方法：对当前序列进行sort排序，如果当前数字次序不变，且大于其左边所有数字中的最大值，则是主元。根据格式要求，如果主元个数为0，则需要第二行为空行。代码：//5//1 3 2 4 5#include...
2019-05-25 10:30:59
64
原创 算法相关_快排递归+随机数
题目要求给出一个无序数组，要求把数组分成数组A1和数组A2，并满足两个数组元素个数差最小，元素和sum差最大思想随机排序思想：以n/2为基准，用快速排序划分数组。代码：#include<cstdio>#include<cstdlib>#include<ctime>#include<iostream>#include<a...
2019-05-12 11:53:19
277
原创 PAT A1029 Median (25 point(s)) __two pointers
题目大意：给出两个有序数组，要求输出两个数组合并之后的中位数。思路：正常思路是按照merge的思想，mid=(m+n-1)/2 (数组从0开始），边merge边判断当前count是否==mid但本题内存限制比较严格，上面思路会有一个测试点超内存。所以可以采用双指针法，只输入第一个数组，边输入第二个数组边与第一个数组比较，时刻注意count的取值。代码1（有一个测试点内存超载）：...
2019-05-09 15:43:49
188
原创 PAT A1089 Insert or Merge (25 point(s))
题目大意：题目给出两个数组a1和a2，a1是初始数组，a2是经过若干次插入排序或者归并排序后得到的数组。让你判断a2是经过哪种排序得到的，并且输出下一趟排序后的结果。注意：如果对插入排序和归并排序掌握得不好，这题就要GG。插入排序的特点是:第n趟排序结束后，前 i 个元素有序，后 n-i 个元素保持不变。归并排序（2路）的特点是：第i次排序结束后，每n/(2^i)个子列内部是有序的...
2019-05-07 21:46:46
135
原创 算法——归并排序
递归#include<cstdio>#include<algorithm>#include<iostream>using namespace std;const int maxn = 100;int a[maxn]= {0};void merge1(int a[],int l1,int r1,int l2,int r2){ //两...
2019-05-06 17:41:15
176
原创 1044 Shopping in Mars (25 point(s))__二分（需要回看）
题目大意：题目给出一串正整数num[1-n]，和一个既定和M，让你输出数组中连续的、和等于M 的部分数字。如果没有部分和恰好等于M的连续数字，则输出和大于M且与M最接近的数字。如果答案不唯一，则按照左端升序输出。注意：双层枚举会超时，用二分。因为求的是部分和，所以直接存储sum比较方便。如：num[i]到num[j]的部分和可以写成 sum[j]-sum[i-1].用二分返回的...
2019-05-05 11:40:48
122
转载 PAT_1010 1010 Radix (25 point(s))__二分法（需要回看)
题目大意：给定2个数字num1和num2，和num1的进制，要求求出在num1==num2的条件下num2的进制，如果无法满足，返回impossible.注意：思想- 将num1转化为10进制。- num2的进制有一个区间，low是num2的每个数位+1，high是num1+1- 用二分法寻找num2的进制。进制涉及到溢出问题，所有数据类型设置为long long （超出范围视...
2019-05-04 18:17:31
274
原创 A 1085 Perfect Sequence (25 point(s)) __二分法&&two_pointers
题目要求：给定p和数组 num [n]，寻找数组中的一个子集，使该子集中的最小值m*p >= 子集中的最大值M，要求寻找子集的最大长度思路：先排序，然后从小到大枚举每一个元素，寻找符合题目条件的子集，并记录子集的最大值。这种查找用二分法比较方便，可以自己写，当然也可以用upper_bound，时间复杂度在O(logn)//10 8//2 3 20 4 5 1 6 7 8 ...
2019-05-03 11:52:26
137
原创 A 1038 Recover the Smallest Number (30 point(s)) ——string
题目考察：string用得熟练就成原题：Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers suc...
2019-05-02 16:38:45
97
原创 PAT A1067_贪心
题目要求：给出【0，N-1】范围内的乱序数组，要求在只能交换0和其他数字的情况下，完成数组的排序。注意:因为是swap，所以直接记录位序比较方便刚开始有两个测试点超时，改了一下代码，设置一个变量，记录目前尚未排序的最小数字的位序。#include<cstdio>#include<algorithm>using namespace std;cons...
2019-05-02 15:12:17
241
原创 PAT A1048 Find Coins （25 分) __hash || 二分 || two pointers
简单题，思路错了。（以下会列出我的代码和满分代码）题目要求：给出 正整数m和n个正整数（num1,num2,…,num n），让你求出( num i + num j ==m)的方案，若方案不唯一，要求输出num i 最小的方案。菜鸡如我直接就想到枚举 i,j，双层循环去了。。。结果有两个测试点运行超时TAT。其实用hash表，30行代码就解决了还不容易错 o(TヘTo)另外，这道题还可以...
2019-04-19 10:47:24
108
原创 PAT B1005 继续(3n+1)猜想 （25 分)__hash
简单题，但为啥我算错了，各种格式错+运行超时，debug没de出来，最后对着答案检查才发现都是小错误，比如把t写成了n，t%2 写成了t/2…我发现，对于我这种脑残选手，写代码的时候千万不要仗着脑子暂时还好使就不动笔，就算再思路明细的题，也一定要把框架搭起来，不然绕着绕着就晕了TAT思路待补------------/*输入样例：63 5 6 7 8 11输出样例：7 6*/#inc...
2019-04-17 22:39:13
118
原创 PAT__A1041 Be Unique （20 分)__hash
简单题，我也不知道怎么就错了，可能是上午写太多了有点上头 TAT题目大意：给出一组数字，让你找出 最先出现的、在整个数组里是唯一的那个数字。思路：用到 hashTable，先统计每个数字出现的次数。再遍历初始输入数组，如果hashTable[num[i]]==1,则输出。以下是我的代码：#include<cstdio>#include<cstring>...
2019-04-17 11:59:31
84
原创 PAT A1084 Broken Keyboard （20 分) +B1033（hash&&PAT中不能用gets()的解决办法）
题目大意：给出两行字符，要求找出 第一行有的 && 第二行没有 的字符，每个字符按照大写输出，只输出一遍，空格也算。注意点：用到hashTable，数组下标可用ASCII对应，一般情况下设置数组大小为128gets函数在PAT里不能通过编译（因为OJ把gets禁用了），可以用fgets替代,用法：fgets( str1,100,stdin)str1:字符串...
2019-04-16 11:02:44
304
原创 PAT_A1095 Cars on Campus （30 分)__排序&map
题目要求：（和A1016有相似的地方）给出某一天内学校车辆通行（进出）记录，让你求出某个时间点在学校停留的车辆数当天在学校停留时间最长的车牌号和时间注意：思路：进行两次排序：第一次按照车牌号排序，并把有效记录存储到另一个结构数组中；第二次把有效记录按照时间轴排序，方便查询输出。需要用到map来存储车牌号和停留时间。涉及到24小时制的时间，为了方便计算，应先把每...
2019-04-15 12:44:13
100
原创 PAT_1080 Graduate Admission （30 分) ___排序
题目要求：给出一组学校的拟招生人数，并给出n个学生的k个志愿学校和成绩，让你根据成绩得出每个学校的录取名单（学生的id用学生信息的初始输入次序表示）。注意：1.排名规则：成绩总和 > 第一门成绩，如果都相等，则排名相同。2. 录取规则：假设学生S 1）如果S的排名<当前志愿的剩余名额，则直接录取 2）如果志愿学校没有名额了，但S的排名与学校的最...
2019-04-14 21:56:56
114
原创 PAT_1075 PAT Judge ——排序
题目大意：排序题，给出m组n个同学的pat提交记录，要求根据总分排序并输出。需注意的点（花式bug）：1.如果某人 “全场未通过编译”或者“全场未提交过任何记录” ——则不输出他的信息（利用flag区别） 如果某人在输出范围内，但“本道题未通过编译（分数为-1）” ——则在输出中本道题分数为0； （这个bug怎么都过不了，其实多审几遍题就能发现。2.如...
2019-04-13 12:04:55
94
原创 PAT_ A1055 The World's Richest——排序
简单题，题目意思是给一堆人的信息，让你找出符合某个年龄段的排序结果。虽然这道题简单，但架不住我脑残，废了九牛二虎写了一堆佶屈聱牙的代码，只为了实现一个小小的功能。为了把我的脑残经历记录下来，决定开始写这个博客，路过的大神请轻拍！满分代码我也有摘录，在我代码的下面。Forbes magazine publishes every year its list of billiona...
2019-04-12 22:20:58
143
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人