3 NoobPlayer_llke

尚未进行身份认证

我要认证

除了编程啥都会点

等级
TA的排名 7w+

PAT链表题汇总 1032 1074 1097 1133

PAT 1032 Sharing在储存单词时,我们可以使用链表逐个字母进行储存。为了节约空间,如果两个单词拥有共同的后缀,那么可以让它们共享一个相同的子链表。例如,loading和being可以如下图所示储存:你需要找到共同后缀的起始位置。(对于上图,即为ii的位置)#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)#define INF 0x3f3f3f3f#defi...

2020-05-23 08:50:15

PAT1058 A+B in Hogwarts (水)

如果你是哈利波特的粉丝,你就会知道魔术世界有其自己的货币体系。正如海格对哈利解释的那样:“17个银镰刀(Sickle)可以换1个帆船(Galleon),29个克努特(Knut)可以换11个银镰刀。”你的工作是编写一个计算A+B的程序,其中A和B以Galleon.Sickle.Knut的标准形式给出(Galleon是一个范围在[0,107]的整数,Sickle是一个范围在[0,17) 的整数,Knut是一个范围在[0,29)的整数)。思路:其实就是把进制变成...

2020-05-21 11:56:08

PAT1136 A Delayed Palindrome && 1024 Palindromic Number 回文数(字符串模拟)

两题相似度99%,回文过程其实就是翻转字符串,改下输入输出即可PAT1136 A Delayed Palindrome首先将该数字逆转,再将逆转数与该数相加,如果和还不是一个回文数,就重复这个逆转再相加的操作,直到一个回文数出现。如果一个非回文数可以变出回文数,就称这个数为延迟的回文数。给定任意一个正整数,本题要求你找到其变出的那个回文数。#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i+..

2020-05-21 11:52:16

PAT1023 Have Fun with Numbers趣味数字(字符串模拟)

请注意,数字123456789是一个9位数字,完全由1到9组成,没有重复。将其加倍,我们将获得246913578,它恰好是另一个9位数字,恰好由1到9组成,只是排列不同。现在,给定你一个k位的数字,请你判断将其加倍以后得到的数字是否可以由原数字的各数位重新排列得到。思路:本题可以直接用int处理,个人习惯用字符串String .首先将数字扔到一个vector容器1中,处理出加倍后的字符串扔到vector容器2中两个容器都排下序,再比对一下最...

2020-05-21 11:44:13

PAT1009 Product of Polynomials && 1002 A+B for Polynomials 多项式乘积/加法(模拟)

给定两个多项式AA和BB,计算A×B的结果。共两行,每行包含一个多项式的信息,格式如下:KN1aN1N2aN2…NKaNK其中,K表示多项式中非零项的数量,Ni和aNi分别表示其中一个非零项的指数和系数。结果中的各项的系数均保留一位小数。思路:数据很小,指数位最多只有1000+1000. 考虑暴力出奇迹#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)us...

2020-05-21 11:29:01

PAT1112 Stucked Keyboard (字符串模拟)

在一个损坏的键盘上,某些键总是被卡住。因此,当你用该键盘输入一些句子时,与这些键相对应的字符将在屏幕上重复出现kk次。现在,给定k以及最终屏幕显示的结果字符串,请你找出所有可能坏掉的按键,并给出原始字符串。注意,有些字符可能被重复键入。每当卡住的按键被按下时,其对应的字符将固定被输出k次。例如,当k=3时,从字符串thiiis iiisss a teeeeeest,我们可以推断出i和e可能被卡住了,但是s并没有被卡住,尽管它也重复出现过。所以,原始字符串可能...

2020-05-20 11:06:23

PAT1118 Birds in Forest (求连通块数量-并查集)

一些科学家为森林中成千上万的鸟类拍照。假设所有出现在同一张照片中的鸟都属于同一棵树。请你帮助科学家计算森林中树木的最大数量,对于任何一对鸟类,请判断它们是否在同一棵树上。思路:与1013几乎一样,在输入上做了一点改变,转化为求点的数量和连通块的数量,并询问两点是否在同一连通块。考虑并查集来解决这种求连通块问题。#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)#define INF 0x3f

2020-05-17 17:39:40

PAT 1013 Battle Over Cities (删点求连通块问题---并查集/爆搜)

在战争中,所有城市都必须通过高速公路连接起来,这一点至关重要。如果一个城市被敌人占领,则从该城市/往该城市的所有高速公路都将关闭。此时,我们必须立即判断是否需要维修其他高速公路以保持其余城市的连通性。给定城市与道路分布地图以及一个重点关注城市列表,请你判断,当列表中的某个城市被攻陷时,至少要维修多少条高速公路才能保持其余城市的连通性。例如,共有33座城市,由22条高速公路将它们连通,一条连接城市1和城市2,一条连接城市1和城市3。当城市1被敌人占领时,我们需要在城市...

2020-05-17 16:57:56

PAT1149 Dangerous Goods Packaging 危险品集装箱 (STL)

传送门给定一张不相容物品的清单,需要你检查每一张集装箱货品清单,判断它们是否能装在同一只箱子里。思路1:对每一组询问,遍历不相容的清单,看在集合中是否同时存在#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)#define INF 0x3f3f3f;#define x first#define y secondusing namespace std;const int N=1e4+233;

2020-05-12 18:18:54

1144 The Missing Number 漏掉的数字(STL-SET)

传送给定N个整数,请你找出最小的不在给定整数列表中的正整数。思路:破水题也会超时,改用unordered_set就可#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)using namespace std;int n,a,ans;unordered_set<int>s;int main(){ cin>>n; rep(i,0,n) cin>>.

2020-05-12 17:46:51

PAT1120 Friend Numbers 找朋友(STL-SET)

如果两个整数各位数字的和是一样的,则被称为是“朋友数”,而那个公共的和就是它们的“朋友证号”。例如123和51就是朋友数,因为1+2+3=5+1=6,而6就是它们的朋友证号。给定一些整数,要求你统计一下它们中有多少个不同的朋友证号。思路:输入时用字符串加起来方便,用set可以直接去重。#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)#define INF 0x3f3f3f;u...

2020-05-12 17:16:15

PAT1063 Set Similarity 集合相似度(STL-SET)

传送门给定两个整数集合,两个集合的相似度定义为Nc/Nt×100%,其中Nc 是两个集合中都存在的不同整数的数量,Nt是两个集合中不同整数的数量。现在,请你计算给定集合的相似度。思路:Nc是两集合共有的元素数量,Nt是两集合不同的元素数量=两集合总数-Nc如何判断数是否在集合中? 利用STL中的set的count()函数#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)#define IN...

2020-05-12 16:58:05

PAT 1048 Find Coins 找硬币(模拟)

伊娃喜欢从整个宇宙中收集硬币。有一天,她去了一家宇宙购物中心购物,结账时可以使用各种硬币付款。但是,有一个特殊的付款要求:每张帐单,她只能使用恰好两个硬币来准确的支付消费金额。给定她拥有的所有硬币的面额,请你帮她确定对于给定的金额,她是否可以找到两个硬币来支付。输出一行,包含两个整数V1,V2,表示所选的两个硬币的面额,使得V1≤V2并且V1+V2=M。如果答案不唯一,则输出V1 最小的解。思路:排序,枚举每一个面额,是否存在对应的与之相加为m的另一个面额。注:同面...

2020-05-11 14:30:43

PAT 1012Invert a Binary Tree反转二叉树(反转树,层序,中序)

传送题目给定一颗二叉树,要求输出反转后二叉树的层序遍历序列和中序遍历序列关于反转操作,是一个后序遍历交换的过程,最开始我是中序交换,怎么都不对,画了N遍图才意识过来#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)#define INF 0x3f3f3f3f#define x first...

2020-05-07 17:04:16

1099 Build A Binary Search Tree构建二叉搜索树(中序+层序)

给定二叉树的具体结构以及一系列不同的整数,只有一种方法可以将这些数填充到树中,以使结果树满足 BST 的定义。一次DFS(中序)把数值放到二叉搜索树中,再BFS(层序)输出一次即可#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)#define INF 0x3f3f3f3f#define x...

2020-05-07 16:03:13

PAT dijkstra模板

常规版,大多数情况下用这个即可#include<bits/stdc++.h>#define rep(i,a,n) for(int i=a;i<n;i++)#define INF 0x3f3f3f3fusing namespace std;const int N=2333;int n,m,k;int g[N][N];int dist[N],vis[N];in...

2020-05-05 16:54:15

PAT1150 Travelling Salesman Problem旅行商问题(简单回路)

https://pintia.cn/problem-sets/994805342720868352/problems/1038430013544464384对于每个路径,在一行中输出Path X: TotalDist (Description)。其中X是路径编号(从11开始),TotalDist表示路径总距离(如果距离不存在,则输出NA),Description是下列中的一...

2020-05-05 16:22:08

PAT1146 Topological Order 拓扑排序(两种思路)

https://pintia.cn/problem-sets/994805342720868352/problems/994805343043829760辣鸡如我已经忘了拓扑序是个什么东西了。特地去百度了一下::在图中从顶点A到顶点B有一条有向路径,则顶点A一定排在顶点B之前。大致意思就是必须满足前面节点都在序列中,该节点才能进序列那么就很简单了,输入时把一个节点的父节点(不知道这样称...

2020-05-05 14:47:19

PAT 1142 Maximal Clique 最大团

传送门在一个无向图中,如果一个顶点子集满足子集内的任意两个不同顶点之间都是相连的,那么这个顶点子集就被称为一个团。如果一个团不能通过加入某个新的顶点来扩展成一个更大的团,那么该团就被称为最大团。现在,你需要判断给定顶点子集能否构成一个最大团。思路:先判断是不是个团(如果顶点子集内存在两个点没有边就不是团),再遍历子集外的点,如果存在一个点和子集内所有点都有边,那就不是最大团...

2020-05-04 19:16:09

PAT1139 First Contact (STL)

题意:当男孩A暗恋着女孩B的时候,他通常不会直接与她联系。取而代之的是,他可能会去找另一个男孩C(他的好朋友)去拜托女孩D(她是B和C的朋友)将女孩B约出来。这实在是麻烦不是吗?女孩也会做类似的事情。在给定的友谊关系网络中,请你帮助一些男孩和女孩列出所有可能会帮助他们进行第一次联系的朋友注意: 可以是同性恋(即AB性别相同);不可以无中生友(即我就是我自己的朋友,A!=...

2020-05-04 16:30:38

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。