Home
SSC Studio
Cancel

PAT 1066 Root of AVL Tree

Link AVL 模板题, 我之前也写过一篇相关的题解, 有图, 较为详细. #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <string.h> #inc...

PAT 1123 Is It a Complete AVL Tree

Link Yet another AVL 模板题 :) #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <string.h> #include <ve...

PAT 1125 Chain the Ropes

Link 越早加入绳子的段, 对折的次数就越多, 因此想让绳子最长就应该让长度较长的段对折次数尽可能少. 将所有段从小到大排序, 依次加入绳子中即可. AC 代码: #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include...

PAT 1158 Telefraud Detection

Link 并查集一定要这样: int fa1=findFather(x), fa2=findFather(y); //对大小关系无要求 if(fa1!=fa2) fa[fa1]=fa2; //对大小关系有要求 if(fa1>fa2) fa[fa1]=fa2; else fa[fa2]=fa1; //or if(fa1!=fa2){ if(fa1<fa2) swap(f...

PAT 1122 Hamiltonian Cycle

Link 这题本身很简单, 不过我对此有一些拓展的想法. 如果给出的只是一些点的集合, 要求判断这些点 (可能不是按照给出的顺序) 能不能构成 Hamiltonian Cycle, 就可以用 DFS 来解决 (开始以为是这个意思于是写的 DFS 🐭). void DFS(int u,int cur){ if(cur==num){ if(g[u][vertex[1...

PAT 1121 Damn Single

Link 不是有 CP 就可以无忧无虑了啊… ta 要是没来你也是孤身一人, just like a damn single 🐶. #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #in...

PAT 1119 Pre- and Post-order Traversals

Link 已知前序、后序, 求中序. 不唯一的原因: 最后一个子树只有两个节点 A B 时, 根据前序或后序都可以推得 A 是子树的根节点, 但是 B 是 A 的左孩子还是右孩子就不得而知了. 再就是, 只需要在前序序列中找后序序列所确定的子树根节点 (postRight-1), 或者在后序序列中找前序序列所确定的子树根节点 (preLeft+1), 而不用两个都找一遍 (虽然也不会有...

指令系统

CISC vs RISC 指令系统有两个的发展方向: 增强原有指令的功能, 设置更为复杂的新指令实现软件功能的硬化. ——复杂指令系统计算机 CISC, 典型的如采用 x86 架构 (Intel 的) 的计算机. 减少指令种类, 简化指令功能, 提高指令的执行速度. ——精简指令系统计算机 RISC, 典型的如采用 ARM、MIPS 架构的计算机. 直接跳转和间接跳转 正常...

PAT 1118 Birds in Forest

Link 这题交了两遍才过, 第一遍为了省事没写 findFather, 导致忽略了一种情况: 当时写的是: if(!indexes[id]) indexes[id]=i; else if(indexes[id]==i) continue; else{ father[i]=father[indexes[id]]; //当时让father更新为旧值是想在for(i)里直接算出tr...

PAT 1117 Eddington Number

Link 寻找 N 天中满足: 有 E 天的骑行距离大于 E 的最大的 E. 思路: 对输入数据从大到小排序, 则排序后的 a 数组表示: 前 i 天中骑行距离的最小值是 a[i]. 那么只要保证 a[i]>i 就行了. #include <iostream> #include <cstdio> #include <cstdlib> #incl...