品牌创意网站建设徕卡e,网络营销的基本职能有哪些,做一张网页需要多少钱,企业网站建设价格表前言 整体评价
其实T3最有意思#xff0c; T4很典#xff0c;是一道二分最短路径经典套路。
T3 如果尝试 增量差值最小 的最大梯度去贪心的话#xff0c;会失败#xff0c;需要切换思路。
珂朵莉 牛客周赛专栏
珂朵莉 牛客小白月赛专栏 A. 游游的正方形披萨
如果横竖差…
前言 整体评价
其实T3最有意思 T4很典是一道二分最短路径经典套路。
T3 如果尝试 增量差值最小 的最大梯度去贪心的话会失败需要切换思路。
珂朵莉 牛客周赛专栏
珂朵莉 牛客小白月赛专栏 A. 游游的正方形披萨
如果横竖差值最小的话
两者要么相等要么差一
令 e1 n / ((k 1)/21), e2 n / (k/2 1)
则 s e1 * e2
这样很好的兼顾了k为奇偶的情况
import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc new Scanner(new BufferedInputStream(System.in));int n sc.nextInt();int k sc.nextInt();double e1 n * 1.0 / ((k 1)/2 1);double e2 n * 1.0 / (k/2 1);double s e1 * e2;System.out.printf(%.2f\n, s);}}B. 游游的字母翻倍
这题字符串和操作次数较小然后可以暴力模拟
如果操作数很多的话可能需要借助数据结构来维护增量
因为这里面有明显的区间操作.
import java.io.BufferedInputStream;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(new BufferedInputStream(System.in));int n sc.nextInt();int q sc.nextInt();char[] str sc.next().toCharArray();for (int i 0; i q; i) {int l sc.nextInt() - 1, r sc.nextInt() - 1;int d r - l 1;char[] str2 new char[str.length d];// 头部System.arraycopy(str, 0, str2, 0,l);// 中间的doublefor (int j 0; j d; j) {str2[l j * 2] str2[l j * 2 1] str[j l];}// 尾巴System.arraycopy(str, r 1, str2, r 1 d, str.length - (r 1));str str2;}System.out.println(new String(str));}}C. 数组平均
这题很有意思先来看一个显而易见的结论
k 1, 则结果为 最大值 - 最小值k n, 则结果必然为 0
如果核心的焦点在于 k在两者之间时如何求解
一开始猜了一个从收益最大(差值减少梯度)的角度去贪心结果WA而且得分不高
一度没辙后面仔细分析了下感觉可以枚举最大的没有被选中的项
如果选中某一个项为最大值那比它小而离的越近必然被保留所以k的选择一定分布在前后缀. 所以思路是
排序枚举未被选中的最大值利用前后缀优化加速
import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc new Scanner(new BufferedInputStream(System.in));int n sc.nextInt(), k sc.nextInt();int[] arr new int[n];for (int i 0; i n; i) {arr[i] sc.nextInt();}Arrays.sort(arr);if (k 1) {System.out.println(arr[n - 1] - arr[0]);} else if (k n) {System.out.println(0);} else {double ans arr[n - 1] - arr[0];// 前后缀拆解long[] suf new long[n 1];for (int j n - 1; j 0; j--) {suf[j] suf[j 1] arr[j];}long pre 0;// 假设这个元素没被选中for (int i 0; i n; i) {if (i k) break;long acc pre suf[n i - k];double avg acc * 1.0 / k;double m1 Math.max(avg, arr[n i - k - 1]);double m2 Math.min(avg, arr[i]);ans Math.min(ans, m1 - m2);pre arr[i];}System.out.println(ans);}}}D. 游游出游
经典套路题
二分最大重量然后check逻辑中跑最短路(Dijkstra)进行验证
import java.io.*;
import java.util.*;public class Main {static long inf Long.MAX_VALUE / 10;static boolean check(int n, Listint[] []g, int limit, int h) {long[] res new long[n];Arrays.fill(res, inf);PriorityQueuelong[] pq new PriorityQueue(Comparator.comparing(x - x[1]));pq.offer(new long[] {0, 0});res[0] 0;while (!pq.isEmpty()) {long[] cur pq.poll();int u (int)cur[0];if (cur[1] res[u]) continue;for (int[] e: g[u]) {int v e[0];if (e[1] limit res[v] res[u] e[2]) {res[v] res[u] e[2];pq.offer(new long[] {v, res[v]});}}}return res[n - 1] h;}public static void main(String[] args) {Scanner sc new Scanner(new BufferedInputStream(System.in));int n sc.nextInt(), m sc.nextInt(), h sc.nextInt();// 二分Listint[][]g new List[n];Arrays.setAll(g, x - new ArrayList());int mz 0;for (int i 0; i m; i) {int u sc.nextInt() - 1, v sc.nextInt() - 1;int w sc.nextInt(), d sc.nextInt();g[u].add(new int[] {v, w, d});g[v].add(new int[] {u, w, d});mz Math.max(mz, w);}int l 0, r mz;while (l r) {int mid l (r - l) / 2;if (check(n, g, mid, h)) {l mid 1;} else {r mid - 1;}}System.out.println(r);}}写在最后
