pat团体程序设计天梯赛题目精讲以及知识点总结
L2-001紧急救援
知识点一:求两点之间最短路径条数
代码思路类似于求背包问题下的最优方案数(链接:https://blog.csdn.net/wykwasd75869/article/details/144101854?fromshare=blogdetail&sharetype=blogdetail&sharerId=144101854&sharerefer=PC&sharesource=wykwasd75869&sharefrom=from_link)
#include
using namespace std;
typedef long long ll;
const int N = 100010,M=400010,mod = 100003;
int n, m;
int h[N], e[M], ne[M], idx;
int dist[N],cnt[N];
bool st[N];
queue
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
cnt[1] = 1;
q.push(1);
while (q.size()) {
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + 1) {
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
q.push(j);
}
else if (dist[j] == dist[t] + 1) {
cnt[j] = (cnt[j] + cnt[t]) % mod;
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
bfs();
for (int i = 1; i <= n; i++)cout << cnt[i]< } 知识点二:输出最优路径各个点 思路:设一个path[]数组,记录这个点的前驱节点是谁,一般是当当前的点被更新时,就更新path点 输出函数: ////s是起始节点,主函数直接调用find(最终节点)即可 void find(int t) { if (t == s) { cout << t; return ; } int k = t; find(path[t]); cout << " " << k; } 二叉搜索树(BST树)相关知识点 (1) 二叉搜索树的镜像:每个节点的左右子树转换; (2) 二叉搜索树能够进行快速的查找和删除(通过折半查找的方式,时间复杂度O(logn)) (3) 二叉搜索树左子树所有元素严格小于根节点,右子树所有元素严格大于根节点,按照中序遍历排列必定是上升序列. 问题:给一个树的先序遍历,请你判断这个树是否是二叉搜索树或者是二叉搜索树的镜像 注意:代码中有大量细节,请仔细思考 #include using namespace std; vector int pre[1005]; bool isMirror=false; void getpost(int l,int r) { if(l>r) return ;//当l等于r时,表示当前函数遍历的是一个叶子结点,所以可以等于 int i=l+1,j=r;//因为是先序遍历,所以l一定是根节点 if(!isMirror)//如果不是镜像 { while(i<=r&&pre[l]>pre[i]) i++; //找到第一个大于等于根节点的节点,这个点i一定是右子树的根节点, //根据二叉搜索树的定义,小于二叉搜索树的那颗子树不能包含根节点,大于根节点的子树可以包含根节点,所以此处的i和下面else的j等于根节点的时候合法 while(j>l&&pre[l]<=pre[j]) j--; //找到第一个小于根节点的节点,这个点j一定是左子树的先序遍历的最后一个节点 } else { while(i<=r&&pre[l]<=pre[i]) i++;//找到第一个小于根节点的节点,这个点i一定是右子树的根节点 while(j>l&&pre[l]>pre[j]) j--;//找到第一个大于或者等于根节点的节点,这个点j一定是左子树的先序遍历的最后一个节点 } if(i-j!=1) return; getpost(l+1,j); //左子树 getpost(i,r); //右子树 post.push_back(pre[l]); //存放根节点,根据后序遍历左右中,最后输出,所以先递归再存放元素 } int main() { int n; scanf("%d",&n); for(int i=0;i post.clear(); getpost(0,n-1);//先假设他不是镜像看看行不行 if(post.size()!=n) 如果不是二叉搜索树,就可能因为找不到适合的i,j而导致没有存放元素,所以元素个数可以判断是否是二叉搜索树 { isMirror=true; post.clear(); getpost(0,n-1);//再看看是不是镜像 } if(post.size()!=n) puts("NO"); else { puts("YES"); for(int i=0;i printf(i!=n-1?"%d ":"%d\n",post[i]); } return 0; } 图论问题注意事项 h数组的更新不要写到add后面否则输出0,也就是说不能写到算法函数里面,最好写到main函数的开头 . 如果不知道某个数的范围,就把数组能开多大就开多大,要不然容易段错误 . vector容器中有几个元素,大小就是多少,只有一个1e9,大小就是1