pta团体程序设计天梯赛-练习集l3

### PTA 团体程序设计天梯赛 L3 练习题目及解析 #### 题目概述 L3级别的题目通常涉及较为复杂的算法和数据结构应用，难度较高。这些题目不仅考察编程能力，还测试选手对于特定算法的理解程度以及解决实际问题的能力。 #### 示例题目分析 ##### 千手观音 [^1] **背景描述** 在一个二维平面上有N个点，每个点代表一个可以被机器人手臂触及的位置。给定M条线段连接某些点对之间的路径，每条路径都有一定的长度。目标是从起点出发到达终点，在这个过程中尽可能多地触碰不同的点，并返回能够触碰到的最大不同点数。 **输入格式** - 第一行两个整数 N 和 M (2 ≤ N ≤ 50; 1 ≤ M ≤ 200)，表示总共有多少个节点以及有多少条边； - 接下来 M 行，每行三个正整数 u,v,w 描述一条无向加权边(u != v)，其中 w 是这条边的权重； **输出格式** 仅有一行包含一个整数 K ，即最多能访问到的不同顶点数目（不包括起始位置）。 **解法思路** 这个问题可以通过动态规划来处理。定义 dp[i][j] 表示当前处于第 i 步并且最后一步停留在 j 这个结点上所能获得的最大分数。通过遍历所有可能的状态转移方程更新dp数组中的值直到找到最优解为止。 ```python def max_touch_points(N, edges): from collections import defaultdict graph = defaultdict(list) for edge in edges: u, v, _ = edge graph[u].append(v) graph[v].append(u) # 初始化DP表格 dp = [[0]*(N+1) for _ in range(N)] def dfs(current_node, visited_nodes): if all(visited_nodes): return sum([int(not node) for node in visited_nodes]) best_score = 0 for neighbor in graph[current_node]: new_visited = list(visited_nodes) if not new_visited[neighbor]: new_visited[neighbor] = True score_with_neighbor = dfs(neighbor, tuple(new_visited)) + int(not any(new_visited)) best_score = max(best_score, score_with_neighbor) return best_score start_state = [False] * (N + 1) result = dfs(1, tuple(start_state)) return result - 1 # 减去起始位置本身 ``` ##### 关于深度优先搜索和逆序对的问题 **背景描述** 给出一组序列，要求计算该序列中存在的全部逆序对数量。所谓“逆序对”，指的是如果存在一对索引(i,j)(i<j)，使得a[i]>a[j]，那么这对元素就构成了一个逆序对。 **输入格式** 单组测试样例的第一行为一个整数n(n≤10^5)，表示待测序列的长度；第二行为n个由空格分隔开来的整数ai(ai∈[-1e9,+1e9])，它们共同构成了一串完整的待检测序列。 **输出格式** 输出文件应只含有一行，内有一个整数m，它代表着所求得的结果——也就是整个序列里存在的逆序对总数。 **解法思路** 利用归并排序的思想可以在O(nlogn)时间内解决问题。当我们将左半部分与右半部分合并时，只要左边某个元素大于右边任意一个小于它的元素，则说明这两个之间形成了若干个新的逆序对。因此我们只需要统计这样的情况即可得到最终答案。 ```cpp #include <iostream> using namespace std; long long merge(int* A, int l, int m, int r){ int n1=m-l+1; int n2=r-m; int L[n1], R[n2]; for(int i=0;i<n1;++i)L[i]=A[l+i]; for(int j=0;j<n2;++j)R[j]=A[m+j+1]; int i=0,j=0,k=l,inversions=0; while(i<n1 && j<n2){ if(L[i]<=R[j]){ A[k++]=L[i++]; }else{ inversions+=n1-i; A[k++]=R[j++]; } } while(i<n1){A[k++]=L[i++];} while(j<n2){A[k++]=R[j++];} return inversions; } long long countInversions(int*A,int l,int r){ if(l>=r)return 0; int mid=(l+r)/2; long long cnt=countInversions(A,l,mid)+countInversions(A,mid+1,r); cnt+=merge(A,l,mid,r); return cnt; } int main(){ int n,*arr; cin>>n; arr=new int[n]; for(int i=0;i<n;++i)cin>>arr[i]; cout<<countInversions(arr,0,n-1)<<endl; delete[] arr; return 0; } ```