Home
SSC Studio
Cancel

PAT 1105 Spiral Matrix

Link AC 代码: #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <string.h> #include <vector> #includ...

PAT 1104 Sum of Number Segments

题解 Link 思路很简单, 就不说了, 主要是浮点数溢出和精度的问题. 两个坑点: 用 double 存储答案会溢出, 过不了测试点 2、3. 应该用 long d📧ouble 或者 long long. 如果是用 long double, 那么一定要是 ans+=a*i*(n-i+1), 而不是 ans+=i*(n-i+1)*a; 如果用 long long, 那么一定要...

PAT 1103 Integer Factorization

Link #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <string.h> #include <vector> #include <cm...

欧拉函数

前缀和&差分

前缀和 来一道二维前缀和的模板题 (简单但有点坑): AcWing 99 激光炸弹 Link 坑点 1: 不同目标可能在同一位置, 也就是说可能两次输入的是同一坐标点处的权值, 所以要 w[i][j]+=a; 坑点 2: 输入的 x,y 的范围是从 0 开始的, 而我们二维前缀和的矩阵是从 1 开始的, 所以要 w[++x][++y]; #include <iostream...

TSP 问题

输入: 4 0 30 6 4 6 5 0 20 30 0 5 10 4 10 20 0 输出: 30 #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <st...

二叉树三种遍历方式的非递归写法

前序遍历 void PreOrderTraverse(BiTree T) { BiTree p = T; stack<BiTree> s; while (p || !s.empty()) { if (p) { visit(p); s.push(p); p = p-&g...

PAT 1102 Invert a Binary Tree

Link 树的层次遍历和中序遍历. 代码中给出了中序遍历的递归和非递归写法: #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <string.h> #inc...

PAT 1101 Quick Sort

Link 思路: 能够作为 pivot 的一定在排好序后它应该在的位置. 设原序列是 b, 排好序后的序列是 a, 那么元素 b[i] 是 pivot 的必要条件就是 b[i]==a[i] (即, 只要是 pivot 就一定有 b[i]==a[i]). 那么充分条件是什么? 只有 b[i]==a[i] 还不够, 例如 9 8 7 6 5 4 3 2 1 中 5 就满足必要条件, 但是 ...

PAT 1160 Forever

Link 思路: 首先要明确的是, 个位数一定是 9, 否则 A+1 一定与 A 互质 (因为必定一个是奇数, 一个是偶数). 既然已经规定了位数必须是 K, 那么就可以枚举从低位到高位的第一个不是 9 的位是哪一位. 假设从个位开始有连续的 S 个 9, 那么就有 n=m-9*S+1. 此时如果有 gcd(n,m)>2, 那么就说明和为 m 且末尾有连续的 S 个 9 的数 ...