本文主要是介绍Atcoder Begginer Contest 352 A~E题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- [A - AtCoder Line ](https://atcoder.jp/contests/abc352/tasks/abc352_a)
- [B - Typing](https://atcoder.jp/contests/abc352/tasks/abc352_b)
- [C - Standing On The Shoulders](https://atcoder.jp/contests/abc352/tasks/abc352_c)
- [D - Permutation Subsequence](https://atcoder.jp/contests/abc352/tasks/abc352_d)
- [E - Clique Connect](https://atcoder.jp/contests/abc352/tasks/abc352_e)
- 模板代码：
A - AtCoder Line
题目:
铁路有N个站，从1编号到N，有两辆方向相反的动车，一个从1到N，另一个从N到1，给起始站X和终点站Y，判断能够经过站Z
思路:
判断Z是否在X和Y之间即可
static void solve() throws IOException {String[] ins = pStringArray();int n = pInt(ins[0]), x = pInt(ins[1]), y = pInt(ins[2]), z = pInt(ins[3]);if ((x <= z && z <= y) || (x >= z && z >= y)) {out.println("Yes");} else {out.println("No");}}
B - Typing
题目:
给两个小写字母组成的字符串S和T，要求从T中找出组成S的子序列，输出其下标
思路:
模拟
static void solve() throws IOException {String a = in.readLine(), b = in.readLine();int n = a.length(), m = b.length();for (int i = 0, j = 0; i < n; i ++) {while (j < m && b.charAt(j) != a.charAt(i)) j ++;out.print(j + 1 + " ");j ++;}
}
C - Standing On The Shoulders
题目:
有N个人，从1编号到N，第i个人的肩膀高度为 Ai，头到地面的高度为为 Bi；现在叠高高：另一个站在一个人的肩膀上，站完这N个人，求从地面到最高的人头的最大高度值
思路:
无论怎么组合，肩膀总高度都是相同的，只有最后一个人的头部到肩膀的高度决定了最终的高度，因此只需要维护这个最大差值，最后加上
static void solve() throws IOException {int n = pInt();int[][] h = new int[n + 1][2];long ans = 0, max = 0;for (int i = 1; i <= n; i ++) {String[] ins = pStringArray();for (int j = 0; j < 2; j ++) {h[i][j] = pInt(ins[j]);}ans += h[i][0];max = Math.max(max, h[i][1] - h[i][0]);}out.println(ans + max);
}
D - Permutation Subsequence
题目:
给一个从1到N的排列序列P，只有长度为K且严格递增的下标序列，同时调整顺序后下标对应P的值组成的序列是连续的，这种子序列才能被称为好的下标序列，求所有好下标序列中最后一个减去第一个的最小差值。
思路:
按照例子来分析
排列：2 3 1 4
下标：1 2 3 4
其中按照题目要求，下标序列对应的P值组成的序列是连续的，也就是说我们可以根据连续的P值来找到对应的下标序列：
连续的P值：1 2 3 4
对应下标： 3 1 2 4
我们得到了序列为 (3,1) 、(1,2)、(2,4)；
同时题目要求下标序列是严格递增的，这些序列都是可以通过重新调整变成严格递增的；
求的值是最后一个减去第一个，那么就是最大值减去最小值，可以通过 滑动窗口 来维护长度为2的序列，维护该序列的最大值和最小值，那么该序列的差值就能被计算了
static void solve() throws IOException {String[] ins = pStringArray();int n = pInt(ins[0]), k = pInt(ins[1]);int[] p = pIntArray(1);Integer[] idx = new Integer[n + 1];Arrays.setAll(idx, i -> i);// 按照P值来排序Arrays.sort(idx,1, n + 1, Comparator.comparingInt(a -> p[a]));int ans = Integer.MAX_VALUE;// 维护最大值和最小值的PriorityQueue<Integer> minQ = new PriorityQueue<>(Comparator.comparingInt(a -> a));PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.comparingInt(a -> -a));int l = 1, r = 0;boolean[] vis = new boolean[n + 1];while (r < k) {r++;maxQ.offer(idx[r]);minQ.offer(idx[r]);}ans = Math.min(ans, maxQ.peek() - minQ.peek());while (r < n) {vis[idx[l]] = true;while (!maxQ.isEmpty() && vis[maxQ.peek()]) maxQ.poll();while (!minQ.isEmpty() && vis[minQ.peek()]) minQ.poll();l++;r++;maxQ.offer(idx[r]);minQ.offer(idx[r]);ans = Math.min(ans, maxQ.peek() - minQ.peek());}out.println(ans);
}
E - Clique Connect
题目:
给一个有权无向图G，有N个节点，一开始该G没有边，可以执行M次操作，每次操作给一个图节点的子集S，这个子集任意一个节点对添加到G的边的权为 k；求执行M次操作后，如果G是连通图输出其最小生成树的总边权，否则输出 -1
思路:
最小生成树的Kruskal算法：排序所有边，然后从边权最小的边找，如果该边的两个节点已经连通，那么跳过，否则将这条边加入树中；
根据题目的意思，所给的子集对应的子图是一个全部边权为k的完全连通图；如果我们要将所有边都统计起来，会超时（k最大是4e5）。所给子图都是完全连通图，只需要一个点和其他点保留边，形成的就是当前子图的最小生成树；
只要连接到该最小生成树的任意一点，那么相当于连接到其他点；我们就可以从边权最小的子集开始连接即可。使用 并查集 维护图的连通性。
static class Pair {int cost;int[] nodes;Pair(int[] nodes, int cost) {this.cost = cost;this.nodes = nodes;}
}
static final int N = (int) (2e5 + 10);
static final int[] p = new int[N];
static {Arrays.setAll(p, i -> i);
}
static int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}
static void solve() throws IOException {List<Pair> lst = new ArrayList<>();String[] ins = pStringArray();int n = pInt(ins[0]), m = pInt(ins[1]);// 加入list进行排序for (int i = 0; i < m; i ++) {ins = pStringArray();int k = pInt(ins[0]), c = pInt(ins[1]);int[] es = pIntArray(0);lst.add(new Pair(es, c));}lst.sort(Comparator.comparingInt(a -> a.cost));long ans = 0;for (Pair pair : lst) {int a = pair.nodes[0];int px = find(a);for (int i = 1; i < pair.nodes.length; i ++) {int py = find(pair.nodes[i]);if (px != py) {p[py] = px;ans += pair.cost;}}}for (int i = 2; i <= n; i ++) {if (find(1) != find(i)) {out.println(-1);return;}}out.println(ans);
}
模板代码：
import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;public class Example {static void solve() throws IOException {}public static void main(String[] args) throws IOException {int t = 1;
// t = Integer.parseInt(in.readLine());while (t -- > 0) {solve();}in.close();out.flush();out.close();}private static InputStream is = System.in;static {try {is = Files.newInputStream(Paths.get("F:\\Notes\\Algorithm\\Problems\\java\\java\\src\\main\\java\\input.txt"));} catch (Exception e) {is = System.in;}}private static final BufferedReader in = new BufferedReader(new InputStreamReader(is));private static final PrintWriter out = new PrintWriter(System.out);private static int pInt(String s) {return Integer.parseInt(s);}private static int pInt() throws IOException {return Integer.parseInt(in.readLine());}private static long pLong(String s) {return Long.parseLong(s);}private static long pLong() throws IOException {return Long.parseLong(in.readLine());}private static String[] pStringArray() throws IOException {return in.readLine().split(" ");}private static int[] pIntArray(int start) throws IOException {String[] s = pStringArray();int[] arr = new int[start + s.length];for (int i = start, j = 0; i < arr.length; i++, j ++) {arr[i] = Integer.parseInt(s[j]);}return arr;}private static long[] pLongArray(int start) throws IOException {String[] s = pStringArray();long[] arr = new long[start + s.length];for (int i = start, j = 0; i < arr.length; i++, j ++) {arr[i] = Long.parseLong(s[j]);}return arr;}
}这篇关于Atcoder Begginer Contest 352 A~E题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
