- 博客(144)
- 收藏
- 关注
RSS订阅原创 【阶乘计算】 PAT 7-7 阶乘的非零尾数 求n的阶乘最后一位非零数字
显然，输入n的范围最大为10的7次方，阶乘是一个超级超级巨大巨大的天文数字，千万级别的阶乘应该有上亿位数字，存在文件里估计都得有几百MB。测试得到最后一组样例为n=5001875，k=9，该样例通过程序计算得到输出为511705344（最后k位非零数字） 1250466（末尾0的个数），但是和下面链接的网站给出的计算结果正好在倒数第9位非零尾数有区别。上面链接中给出的代码只能求出非零部分的最后一位，而对于本问题，需要求非零部分的最后K位，在求解方法上需要有所变化。本文主要记录解题过程中遇到的问题。
2023-04-06 22:50:08
623
1
原创 2022.3.5 PAT甲级 2022年春季考试 89分
2022.3.5 PAT甲级 2022年春季考试 89分7-1 Simple Lie Detection (20 分)简单字符串问题，注意连续相同子段和连续上升子段的细节。#include <iostream>#include <cstdio>#include <string>using namespace std;int main(){ int n,t,k; string s; cin>>n>>t>>k; wh
2022-03-06 13:36:31
2390
9
原创 【double浮点数精度 四舍五入问题】 算法笔记 Codeup 1918 简单计算器
【浮点数精度问题】 算法笔记 Codeup 1918 简单计算器题目本身难度不大，但是发现了一个非常关键的问题，就是浮点数在四舍五入的时候出现的问题。题目本身并不是本文要讨论的重点，这里就不放题干啦。众所周知，对于表达式计算的题目，其实如果采用Python当中的eval函数，一行就能搞定啦：while(True): temp=input() if(temp=="0"): break print(format(eval(temp),'.2f'))当然，这道题的正解显然是栈的
2022-01-29 01:16:52
1652
原创 【编译原理】 基于LR分析表编写语法分析器
【编译原理】 基于LR分析表编写语法分析器【问题描述】已知文法G[E]：E→E+T|TT→(E)|id|id[E]设计LR分析表，并用c++或JAVA语言编写语法分析器。其中：id为变量名，本次实验合法的变量名为a1, a2, …, a9。【输入形式】一个句子【输出形式】句子语法结构正确，输出“Syntax analysis is right”反之输出“Error on syntax analysis”【样例输入】a1+a2【样例输出】Syntax analysis is r
2021-12-20 17:22:27
1379
2
原创 【编译原理】 基于LL(1)分析表编写语法分析器
【编译原理】 基于LL(1)分析表编写语法分析器【问题描述】给定以下文法G[E]：E → TE′E′→ +TE′|εT → FT′T′→ *FT′|εF → a|(E)构建LL（1）预测分析表，并用C++或Java编程实现LL（1）语法分析器【输入形式】一个句子【输出形式】若句子语法正确，输出"Syntax analysis is right"若语法语法错误，输出"Error on syntax analysis"注：输出不包括引号【样例输入】a+a*a【样例输出】S
2021-12-09 00:59:22
1308
2
原创 【编译原理】 基于递归下降法实现语法分析器
【编译原理】 基于递归下降法实现语法分析器【问题描述】给定以下文法G[E]：E → TE′E′→ +TE′|εT → FT′T′→ *FT′|εF → a|(E)用C++或Java编程实现【递归下降法】语法分析器【输入形式】一个句子【输出形式】若句子语法正确，输出"Syntax analysis is right"若语法语法错误，输出"Error on syntax analysis"注：输出不包括引号【样例输入】a+a*a【样例输出】Syntax analysis
2021-12-09 00:57:19
1064
2
原创 【编译原理】 词法分析实验 手工构造词法分析器
【编译原理】 词法分析实验 手工构造词法分析器【问题描述】通过设计c语言常见单词的正规文法或正规式，而后得到NFA，再确定化得到DFA，根据DFA的转换矩阵或转换图，用c++语言实现词法分析器。【输入形式】输入一段完整的c语言程序【输出形式】各类单词的token字【样例输入】int main(){ int a = 10; double b = -20.9; if(a<=b) a+=b; else a = 0; return
2021-11-19 17:22:42
1379
2
原创 【编译原理】 词法分析实验 基于Flex构造词法分析器
【编译原理】 词法分析实验 基于Flex构造词法分析器【问题描述】设计c语言常见单词的正规式，编制lex源文件，利用flex编译得到词法分析的.c文件，继而对该文件编译得到词法分析器。【输入形式】输入一段c语言程序【输出形式】各类单词的token字，或者给出程序中的单词错误。【样例输入】int main(){ int a = 10; double b = 20.9; if(a <= b) a+=b; else a = 0; ret
2021-11-19 17:16:22
1515
2
原创 2021 ICPC网络赛1 I Neiborhood Search
2021 ICPC网络赛1I Neiborhood Search【解题思路】签到题。由于输入当中没有给定输入数字的个数，我们需要使用stringstream来读取一整行，然后依次存放每个数。【AC代码】#include <iostream>#include <cstdio>#include <sstream>#include <algorithm>using namespace std;int n=0,a[100005];int mai
2021-09-21 02:19:22
686
2
原创 2021 ICPC网络赛1 H Mesh Analysis
2021 ICPC网络赛1H Mesh Analysis【解题思路】输入当中上面的坐标是没用的。我们分别记录每个点的neighboring points，以及它属于哪些elements即可。注意去重和排序，这里使用了vector，使用set也可以。注意，查询当中 q的范围是-109到109，即有可能不存在这个编号的点，输出的时候要特判一下，代码中给了注释，比赛的时候就是差这一点没有AC。【AC代码】#include <iostream>#include <cstdio>
2021-09-21 02:15:59
498
4
原创 2021 ICPC网络赛1 F Land Overseer
2021 ICPC网络赛1F Land Overseer【解题思路】签到题，简单平面几何。注意，如果b<=R时，直接从(0,0)走到(2a-R,0)即可。【AC代码】#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;int main(){ ios::sync_with_stdio(0),cin.t
2021-09-21 02:08:58
419
2
原创 洛谷 P3378 【模板】堆
洛谷 P3378 【模板】堆【题目描述】给定一个数列，初始为空，请支持下面三种操作：给定一个整数 xx，请将 xx 加入到数列中。输出数列中最小的数。删除数列中最小的数（如果有多个数最小，只删除 11 个）。【输入格式】第一行是一个整数，表示操作的次数 nn。接下来 nn 行，每行表示一次操作。每行首先有一个整数 opop 表示操作类型。若 op = 1op=1，则后面有一个整数 xx，表示要将 xx 加入数列。若 op = 2op=2，则表示要求输出数列中的最小数。若 op = 3o
2021-09-17 15:22:43
665
2
原创 PAT（甲级）2021年秋季考试 满分题解
PAT（甲级）2021年秋季考试 满分题解7-1 Arrays and Linked Lists (20 分)【解题思路】按照题意模拟即可。我们开一个结构体数组，add表示数字对应的地址，num表示对应数组的编号。查询的同时，记录使用过的数组编号，最终使用过的数组数量，我们取其中的最大值即可。需要注意的是，A0数组是一开始默认就存在的，所以最终使用过的数组数量最小是1，而不能是0，有两个测试点一共3分是这种情况，否则不能AC。【满分代码】#include <iostream>#
2021-09-13 19:59:46
719
2
原创 2021.9.11 PAT甲级考试满分代码
2021.9.11 PAT甲级考试满分代码第1题 数组模拟#include <iostream>#include <cstdio>using namespace std;int n,m,q,start,length,tl=0,tr=0,ans=1;int flag[10005];struct node{ int add,num;}p[1300000];int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.ti
2021-09-11 22:23:48
436
5
原创 2021.9.11 PAT甲级考试满分心得
2021.9.11 PAT甲级考试满分心得前一天晚上有点兴奋睡不着，就又刷了一些题，还特意做了二叉树的题目。一觉睡到中午，洗澡吃饭就准备PAT考试了。在家线上考试，要拍照通过审核啥的，还要开手机和电脑双摄像头。开考前半个小时是不能做任何事情的，只能在那里等，于是就想一些开心的事情，给自己积极的心理暗示，这个时候就算还有没掌握的东西，那也来不及了，听天由命吧。考试开始，因为题目都是全英文的，先要看懂题目，一上来看第一题和做的以往的题就不太一样，有点紧张起来，然后一开始脑子还是不太清醒，于是大致读了题就看
2021-09-11 18:36:23
627
3
原创 PAT（甲级）2017年春季考试
PAT（甲级）2017年春季考试PAT 1124 Raffle for Weibo Followers (20 分)【解题思路】微博抽奖，输入给定第一个中奖用户编号，以及后面每隔多少个用户给一个奖。用一个循环输入，记录当前是第几条记录，判断当前用户是否中奖，输出即可。需要注意的是，已经中奖的用户不再重复中奖，我们使用一个set，将中奖用户加入，如果后面遇到相同的字符串则跳过。【满分代码】#include <iostream>#include <cstdio>#inc
2021-09-11 00:51:31
212
4
原创 PAT（甲级）2017年春季考试 PAT 1127 ZigZagging on a Tree (30 分) 二叉树
PAT（甲级）2017年春季考试PAT 1127 ZigZagging on a Tree (30 分) 二叉树【题目描述】Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a sim
2021-09-11 00:44:23
209
2
原创 PAT 1020 Tree Traversals (25 分) 二叉树
PAT 1020 Tree Traversals (25 分) 二叉树【题目描述】Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding bi
2021-09-11 00:20:30
263
2
原创 PAT（甲级）2021年春季考试
PAT（甲级）2021年春季考试7-1 Arithmetic Progression of Primes (20 分) 暴力搜索【解题思路】输入n的范围最大只有10，我们可以暴力搜索。首先打表生成2到MAXP的所有素数。最大的公差可能值为（MAXP-2）/（n-1），我们从大往小搜索，判断是否符合条件，如果符合则记录答案，结束循环。特判，如果n=1，或者不存在符合条件的等差数列，直接输出小于MAXP的最大的素数。注意，这里我们将素数存在数组当中。如果使用vector，样例4会段错误，不知道原因
2021-09-10 20:24:01
380
2
原创 PAT（甲级）2017年春季考试 PAT 1126 Eulerian Path (25 分) 欧拉路
PAT（甲级）2017年春季考试PAT 1126 Eulerian Path (25 分) 欧拉路【题目描述】In graph theory, an Eulerian path is a path in a graph which visits every edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. They were fi
2021-09-10 20:18:45
184
2
原创 PAT（甲级）2017年春季考试 PAT 1125 Chain the Ropes (25 分)
PAT（甲级）2017年春季考试B Chain the Ropes (25 分)【题目描述】Given some segments of rope, you are supposed to chain them into one rope. Each time you may only fold two segments into loops and chain them into one piece, as shown by the figure. The resulting chain will
2021-09-09 18:38:38
195
2
原创 PAT（甲级）2017年春季考试 PAT 1124 Raffle for Weibo Followers (20 分)
PAT（甲级）2017年春季考试A Raffle for Weibo Followers (20 分)【题目描述】John got a full mark on PAT. He was so happy that he decided to hold a raffle（抽奖） for his followers on Weibo – that is, he would select winners from every N followers who forwarded his post, and g
2021-09-09 18:31:41
207
2
原创 PAT（乙级）2021年春季考试
PAT（乙级）2021年春季考试7-1 打印三角形拼图 (15 分)#include <iostream>#include <cstdio>using namespace std;int main(){ int n; char a,b,c; cin>>n>>a>>b>>c; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i==j)
2021-09-09 18:26:50
564
2
原创 PAT（甲级）2021年春季考试 7-4 Recycling of Shared Bicycles (30 分) Floyd+DFS
PAT（甲级）2021年春季考试7-4 Recycling of Shared Bicycles (30 分) Floyd+DFS【题目描述】There are many spots for parking the shared bicycles in Hangzhou. When some of the bicycles are broken, the management center will receive a message for sending a truck to collect th
2021-09-09 11:08:32
297
2
原创 PAT（甲级）2021年春季考试 7-2 Lab Access Scheduling (25 分) 区间贪心
PAT（甲级）2021年春季考试7-2 Lab Access Scheduling (25 分) 区间贪心【题目描述】Nowadays, we have to keep a safe social distance to stop the spread of virus due to the COVID-19 outbreak. Consequently, the access to a national lab is highly restricted. Everyone has to submit
2021-09-07 16:45:53
217
2
原创 PAT（甲级）2021年春季考试 7-1 Arithmetic Progression of Primes (20 分)
PAT（甲级）2021年春季考试7-1 Arithmetic Progression of Primes (20 分)【题目描述】In mathematics, an arithmetic progression (AP，等差数列) is a sequence of numbers such that the difference between the consecutive terms is constant. In 2004, Terence Tao (陶哲轩) and Ben Green pr
2021-09-07 16:42:26
282
2
原创 PAT（甲级）2021年春季考试 7-3 Structure of Max-Heap (25 分) 最大堆
PAT（甲级）2021年春季考试7-3 Structure of Max-Heap (25 分) 最大堆【题目描述】In computer science, a max-heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is greater than or equal to
2021-09-07 14:51:03
436
2
原创 图论模板 连通分量数 DFS or 并查集
图论模板 连通分量数 DFS or 并查集C Battle Over Cities (25 分)（DFS）#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int num=2000005;//注意：链式前向星，无向图，开两倍（最大边数1000*1000的两倍）！！！ int n,m,k,a,b,c,ans=0;//ans为连通分量数量 struct
2021-09-04 23:42:29
234
6
原创 图论模板 最短路+最小生成树
图论模板 最短路+最小生成树5.21 最小生成树 Prime#include <iostream>#include <cstdio>#include <queue>using namespace std;const int INF=0x3f3f3f3f;//无穷大 int n,ans=0,g[105][105],dis[105],vis[105];struct edge{ int u,v,d;//边的起点、终点、权值 bool operator &
2021-09-04 22:43:46
468
4
原创 PAT（甲级）2011年秋仿真卷
PAT（甲级）2011年秋仿真卷发现PAT练习的网站上可以购买往年的真题试卷进行练习，购买时光机以后还可以看到考试的实时榜单，和当时现场考试的考生同场竞技。最近开始为准备9月的PAT考试复习刷题，争取能够取得理想的成绩！A World Cup Betting (20 分)【解题思路】算是签到题，没什么技术含量。【满分代码】#include <iostream>#include <cstdio>using namespace std;int main(){ do
2021-08-26 18:57:21
291
2
原创 洛谷 P1130 红牌 动态规划 DP
洛谷 P1130 红牌 动态规划 DP【题目描述】某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ，一共包括NN个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程，每一步政府都派了M个工作人员来检查材料。不幸的是，并不是每一个工作人员效率都很高。尽管如此，为了体现“公开政府”的政策，政府部门把每一个工作人员的处理一个申请所花天数都对外界公开。为了防止所有申请人都到效率高的工作人员去申请。这M×N个工作人员被分成M个小组。每一组在每一步都有一
2021-08-22 12:58:01
300
3
原创 PAT甲级 1015 Reversible Primes (20 分) 素数判断 进制转换 理解题意
1015 Reversible Primes (20 分) 素数 进制转换 理解题意【解题思路】首先要理解题目意思。设需要判断的两个数分别为n1和n2。n1即是输入的n，而n2是将n转换为d进制，将该d进制数翻转后，重新转换为十进制得到的数。当n1和n2都为素数时，输出Yes，否则输出No。注意细节，0和1不是素数，如果isprime函数中没有特判，测试点2不能通过。【满分代码】#include <iostream>#include <cstdio>#include &
2021-08-13 02:54:37
291
2
原创 PAT甲级 1012 The Best Rank (25 分) 排序 细节
PAT甲级 1012 The Best Rank (25 分) 排序 细节【题目描述】To evaluate the performance of our first year CS majored students, we consider their grades of three courses only: C - C Programming Language, M - Mathematics (Calculus or Linear Algrbra), and E - English. At th
2021-08-13 02:06:25
523
2
原创 洛谷 P1352 没有上司的舞会 树形DP
洛谷 P1352 没有上司的舞会 树形DP【题目描述】某大学有 n 个职员，编号为 1…n。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ri ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。【输入格式】输入的第一行是一个整数 n。第 2 到第 (n+1) 行，每行一个整数，第
2021-08-11 06:45:38
285
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人