devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯 第 3 场算法双周赛(E-H) 解题报告 | 珂学家_蓝桥杯之深秋的苹果

作者：神奇cpp | 2024-08-16 00:04:32

赞

踩

蓝桥杯之深秋的苹果

前言

整体评价

这场题变多了，但是难度不如上周，G题是道经典的博弈题，H题是一道有趣的图论题，需要优化（过河拆桥）。

这篇主要写E-H的题解，上一篇写A-D的题解。

蓝桥杯 第 3 场算法双周赛

顺便小小的吐槽下，比赛的机器性能还行，但比赛后的评测机感觉降级了。

E. 深秋的苹果

Q: 求划分为M段后，最大美味值最小？

最大最小一般就是二分解法，不过这题上界比较大, 是 2e18

本质是对公式

 \sum_{i=l}^{r} \sum_{j=i+}^{r} A_i *A_j

 \sum_{i=l}^{r} \sum_{j=i+}^{r} A_i *A_j \Rightarrow (\sum_{i=l}^{r} A_i)^2 / 2

只要能转化为这个式子，那这题基本就稳了

在核心的check逻辑中，从左到右贪心构造满足条件的最大段，然后看段的数量是否<=k

  1. import java.io.BufferedInputStream;
  2. import java.util.Scanner;
  3. import java.util.function.Function;
  4.  
  5. public class Main {
  6.  
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(new BufferedInputStream(System.in));
  9.         int n = sc.nextInt();
  10.         int k = sc.nextInt();
  11.  
  12.         long acc = 0;
  13.         long[] arr = new long[n];
  14.         for (int i = 0; i < n; i++) {
  15.             arr[i] = sc.nextLong();
  16.             acc += arr[i];
  17.         }
  18.  
  19.         // 编写check函数和逻辑
  20.         Function<Long, Boolean> check = (m) -> {
  21.             int cnt = 0;
  22.             long acc1 = 0; // 维护\sum ai
  23.             long acc2 = 0; //  维护\sum ai^2
  24.             for (int i = 0; i < n; i++) {
  25.                 acc1 += arr[i];
  26.                 acc2 += arr[i] * arr[i];
  27.                 long x = (acc1 * acc1  - acc2) / 2;
  28.                 if (x > m) {
  29.                     cnt++;
  30.                     acc1 = arr[i];
  31.                     acc2 = arr[i] * arr[i];
  32.                 }
  33.             }
  34.             cnt++;
  35.             return cnt <= k;
  36.         };
  37.  
  38.         long l = 0, r = 2l * acc * acc;
  39.         while (l <= r) {
  40.             long m = l + (r - l) / 2;
  41.             if (check.apply(m)) {
  42.                 r = m - 1;
  43.             } else {
  44.                 l = m + 1;
  45.             }
  46.         }
  47.         System.out.println(l);
  48.     }
  49.  
  50. }

F. 鲜花之海

Q:  在一个n*n元组对中，找到第k小的元组，排序规则元组(a, b)中，a+b优先，a其次

有多种解

  • 二分
  • 解方程

对于二分的解法，a+b优先，所以采用对角线(y=x+k)作为二分的依据, 这边的长度从1~N，在从N~1，处理起来有点变扭，需要特别注意。

  1. import java.io.BufferedInputStream;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.  
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(new BufferedInputStream(System.in));
  8.         int t = sc.nextInt();
  9.         while (t-- > 0) {
  10.             int n = sc.nextInt();
  11.             long k = sc.nextLong();
  12.  
  13.             int l = 1, r = 2 * n - 1;
  14.             while (l <= r) {
  15.                 int m = l + (r - l) / 2;
  16.                 long s = 0;
  17.                 if (m <= n) {
  18.                     s = (long)(1 + m) * m / 2;
  19.                 } else {
  20.                     int e = 2 * n - 1 - m;
  21.                     s = (long)n * n - (long)(e + 1) * e / 2;
  22.                 }
  23.                 if (s < k) {
  24.                     l = m + 1;
  25.                 } else {
  26.                     r = m - 1;
  27.                 }
  28.             }
  29.             if (l <= n) {
  30.                 // 对角线
  31.                 int row = (int) (k - (long) l * (l - 1) / 2);
  32.                 int col = l + 1 - row;
  33.                 System.out.println(row + " " + col);
  34.             } else {
  35.                 int e = 2 * n - 1 - l;
  36.                 int left = (int)((long)n * n - (long)(e + 1) * e / 2 - k);
  37.                 // 存在一个截距
  38.  
  39.                 int s = l + 1 - n;
  40.                 int col = s + left;
  41.                 int row = l + 1 - col;
  42.                 System.out.println(row + " " + col);
  43.             }
  44.         }
  45.     }
  46.  
  47. }

G. 斐波拉契跳跃

Q: 在一个数组中，必须按照斐波那契步长跳跃(比前一次更长，且目标位置数大于当前值)，谁不能行动，谁就认输？

很经典的博弈题，寻找必胜态和必败态

经典的alpha+beta剪枝解法

数组很长，但是斐波那契数组增长非常快，10^5范围内，只有24项。

如果令 dp[i][s],  i为位子，s为步长，实际只有O(24*n)的状态总量

借助记忆化搜索，可以快速求解出来。

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5. import java.util.stream.Collectors;
  6.  
  7. public class Main {
  8.  
  9.     static class Solution {
  10.         List<Integer> steps;
  11.         int n;
  12.         int[] arr;
  13.  
  14.         Map<Long, Boolean> memo = new HashMap<>();
  15.  
  16.         public void ready(int n, int[] arr, List<Integer> steps) {
  17.             this.n = n;
  18.             this.arr = arr;
  19.             this.steps = steps;
  20.         }
  21.  
  22.         public boolean dfs(int u, int s) {
  23.             long key = (long)u << 32 | s;
  24.             if (memo.containsKey(key)) {
  25.                 return memo.get(key);
  26.             }
  27.             for (int i = s; i < steps.size(); i++) {
  28.                 int jump = steps.get(i);
  29.                 if (u + jump < n && arr[u] < arr[u+ jump]) {
  30.                     if (!dfs(u + jump, i + 1)) {
  31.                         memo.put(key, true);
  32.                         return true;
  33.                     }
  34.                 }
  35.                 if (u - jump >= 0 && arr[u] < arr[u - jump]) {
  36.                     if (!dfs(u - jump, i + 1)) {
  37.                         memo.put(key, true);
  38.                         return true;
  39.                     }
  40.                 }
  41.             }
  42.             memo.put(key, false);
  43.             return false;
  44.         }
  45.     }
  46.  
  47.     public static void main(String[] args) {
  48.         AReader sc = new AReader();
  49.         int n = sc.nextInt();
  50.         int[] arr = new int[n];
  51.         for (int i = 0; i < n; i++) {
  52.             arr[i] = sc.nextInt();
  53.         }
  54.  
  55.         // 预处理
  56.         List<Integer> steps = new ArrayList<>();
  57.         int f0 = 1, f1 = 1;
  58.         while (f1 < n) {
  59.             steps.add(f1);
  60.             int t = f1 + f0;
  61.             f0 = f1;
  62.             f1 = t;
  63.         }
  64.  
  65.         List<String> result = new ArrayList<>();
  66.         Solution solution = new Solution();
  67.         solution.ready(n, arr, steps);
  68.         for (int i = 0; i < n; i++) {
  69.             boolean r = solution.dfs(i, 0);
  70.             result.add(r ? "Little Lan" : "Little Qiao");
  71.         }
  72.         System.out.println(result.stream().collect(Collectors.joining("\n")));
  73.     }
  74.  
  75.     static
  76.     class AReader {
  77.         private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  78.         private StringTokenizer tokenizer = new StringTokenizer("");
  79.         private String innerNextLine() {
  80.             try {
  81.                 return reader.readLine();
  82.             } catch (IOException ex) {
  83.                 return null;
  84.             }
  85.         }
  86.         public boolean hasNext() {
  87.             while (!tokenizer.hasMoreTokens()) {
  88.                 String nextLine = innerNextLine();
  89.                 if (nextLine == null) {
  90.                     return false;
  91.                 }
  92.                 tokenizer = new StringTokenizer(nextLine);
  93.             }
  94.             return true;
  95.         }
  96.         public String nextLine() {
  97.             tokenizer = new StringTokenizer("");
  98.             return innerNextLine();
  99.         }
  100.         public String next() {
  101.             hasNext();
  102.             return tokenizer.nextToken();
  103.         }
  104.         public int nextInt() {
  105.             return Integer.parseInt(next());
  106.         }
  107.  
  108.         public long nextLong() {
  109.             return Long.parseLong(next());
  110.         }
  111.  
  112. //        public BigInteger nextBigInt() {
  113. //            return new BigInteger(next());
  114. //        }
  115.         // 若需要nextDouble等方法，请自行调用Double.parseDouble包装
  116.     }
  117.  
  118. }

H. 星石传送阵

Q: 给了一个序列数组，但是按照规则可以构建边(双向边)形成一个稠密图，求A点到B点的最小距离。

这题难点在于

稠密图

拿最简单的BFS求路径来说，其时间复杂度为\sum v_i * e_i， V是顶点数，E是点V的均摊边数，这题容易TLE，本质的原因就在这里。假设E=V, 那就是O(V^2)

那如何求解这题呢？

这边有个概念，叫做组（同一类）

可以按组去存放这些点集列表，因为BFS的特性

里面的点集必然，最多相差1

如果从一个点出发，已经通过这个组(点集)遍历了其他节点。那么其他点(同属组)，在遍历这个组，就没必要了，因为没有增益优化的空间了。可以细细评味这个。

所以把这个技巧，称之为

过河拆桥

至于质因子拆解，这边就不展开讲了。

这题题意还是有点绕，比赛的时候，看了很久，都懵圈了。

  1. import java.io.BufferedInputStream;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     static List<Integer> primes = new ArrayList<>();
  7.  
  8.     static {
  9.         int mz = 10000;
  10.         boolean[] vis = new boolean[mz + 1];
  11.         for (int i = 2; i <= mz; i++) {
  12.             if (!vis[i]) {
  13.                 primes.add(i);
  14.                 for (int j = i * i; j <= mz; j+=i) {
  15.                     vis[j] = true;
  16.                 }
  17.             }
  18.         }
  19.     }
  20.  
  21.     static int solve(int v) {
  22.         int res = 0;
  23.         for (int i = 0; i < primes.size(); i++) {
  24.             int t = primes.get(i);
  25.             if (v < t) break;
  26.             if (v % t == 0) {
  27.                 while (v % t == 0) {
  28.                     res += t;
  29.                     v /= t;
  30.                 }
  31.             }
  32.         }
  33.         if (v > 1) {
  34.             res += v;
  35.         }
  36.         return res;
  37.     }
  38.  
  39.     public static void main(String[] args) {
  40.  
  41.         Scanner sc = new Scanner(new BufferedInputStream(System.in));
  42.  
  43.         int n = sc.nextInt();
  44.         int a = sc.nextInt(), b = sc.nextInt();
  45.  
  46.         List<Integer> []g = new List[n + 1];
  47.         Arrays.setAll(g, x -> new ArrayList<>());
  48.  
  49.         int[] values = new int[n + 1];
  50.         int[] arr = new int[n + 1];
  51.         Map<Integer, List<Integer>> hash = new HashMap<>();
  52.         for (int i = 1; i <= n; i++) {
  53.             arr[i] = sc.nextInt();
  54.             values[i] = solve(arr[i]) % n + 1;
  55.             hash.computeIfAbsent(values[i], x -> new ArrayList<>()).add(i);
  56.  
  57.             if (values[i] >= 1 && values[i] <= n && values[i] != i) {
  58.                 g[i].add(values[i]);
  59.                 g[values[i]].add(i);
  60.             }
  61.         }
  62.  
  63.         int inf = Integer.MAX_VALUE / 10;
  64.         int[] res = new int[n + 1];
  65.         Arrays.fill(res, inf);
  66.  
  67.         Deque<Integer> deq = new ArrayDeque<>();
  68.         deq.offer(a);
  69.         res[a] = 0;
  70.  
  71.         while (!deq.isEmpty()) {
  72.             int u = deq.poll();
  73.             int w = values[u];
  74.  
  75.             List<Integer> edges = hash.getOrDefault(w, Collections.EMPTY_LIST);
  76.             for (int v : edges) {
  77.                 if (v == u) continue;
  78.                 if (res[v] > res[u] + 1) {
  79.                     res[v] = res[u] + 1;
  80.                     deq.offer(v);
  81.                 }
  82.             }
  83.             hash.remove(w);
  84.  
  85.             for (int v: g[u]) {
  86.                 if (v == u) continue;
  87.                 if (res[v] > res[u] + 1) {
  88.                     res[v] = res[u] + 1;
  89.                     deq.offer(v);
  90.                 }
  91.             }
  92.         }
  93.         System.out.println(res[b] == inf ? -1 : res[b]);
  94.  
  95.     }
  96.  
  97. }

写在最后

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/985735
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号