单位网站建设申请,网站建设与维护 前台,西宁网站设计建设,七牛图床 wordpress前言 忘名可以再记#xff0c;回忆永不再来 整体评价
好像有一段时间没写周赛题解了#xff0c;_.
感觉今天手感特别好#xff0c;下午的几场比赛#xff0c;包括传智杯都能打出超神战绩。
T3这题属于前后缀拆解#xff0c;然后单调栈上二分(可以引入哨兵机制)#xf…
前言 忘名可以再记回忆永不再来 整体评价
好像有一段时间没写周赛题解了_.
感觉今天手感特别好下午的几场比赛包括传智杯都能打出超神战绩。
T3这题属于前后缀拆解然后单调栈上二分(可以引入哨兵机制)感觉单调栈不太严谨写起来有点变扭。
T4难道是传说中Dsu On Tree? 感觉有些像。 T1. 统计移除递增子数组的数目 I
和T3一起讲 T2. 找到最大周长的多边形
思路贪心
猜了一个结论 ∑ j 0 j i a r r [ j ] a r r [ i 1 ] 满足此条件的最大 i \sum_{j0}^{ji} arr[j] arr[i1] 满足此条件的最大i j0∑jiarr[j]arr[i1]满足此条件的最大i
先对 a r r arr arr排序逆序找到第一个 i i i即可
class Solution {public long largestPerimeter(int[] nums) {// 思维题long sum 0;Arrays.sort(nums);for (int i 0; i nums.length; i) {sum nums[i];}// 逆序for (int i nums.length - 1; i 2; i--) {sum - nums[i];if (sum nums[i]) {return sum nums[i];}}return -1;}}T3. 统计移除递增子数组的数目 II
思路 前后缀拆解 单调栈上二分
因为题目要求最左侧和最右侧都严格递增所以需要预处理前后缀保证严格递增
从左往右枚举每个点v
check后缀是递增的寻找前缀构建的单调栈且结尾小于v的点累加数量如果当前值前缀是递增的则加入单调栈
class Solution {public long incremovableSubarrayCount(int[] nums) {int n nums.length;boolean[] pre new boolean[n];boolean[] suf new boolean[n];pre[0] suf[n - 1] true;for (int i 1; i n; i) {pre[i] pre[i - 1] nums[i] nums[i - 1];}for (int i n - 2; i 0; i--) {suf[i] suf[i 1] nums[i] nums[i 1];}long res 0;// java可以用treemap来偷鸡单调栈monostackTreeMapInteger, Integer range new TreeMap();range.put(-1, 1); // 哨兵for (int i 0; i n; i) {int v nums[i];if (suf[i]) {var ent range.lowerEntry(v);if (ent ! null) {// 删除的子数组必要有1个元素所以要分类讨论if (ent.getValue() 1 i 2) {res ent.getValue() - 1;} else {res ent.getValue();}}}if (pre[i]) {// 为啥要2, 主要是为了统计方便range.put(v, i 2);}}// 处理尾巴{var ent range.lowerEntry(Integer.MAX_VALUE);if (ent ! null) {if (ent.getValue() 1 n 2) {res ent.getValue() - 1;} else {res ent.getValue();}}}return res;}}T4. 树中每个节点放置的金币数目
思路: 启发式合并
有一个结论 如果一个序列 a r r , a r r [ 0 ] , a r r [ 1 ] , . . . , , a r r [ n − 2 ] , a r r [ n − 1 ] , 抽取其中 3 个数使其乘积最大 如果一个序列arr, arr[0], arr[1], ..., , arr[n - 2], arr[n - 1], 抽取其中3个数使其乘积最大 如果一个序列arr,arr[0],arr[1],...,,arr[n−2],arr[n−1],抽取其中3个数使其乘积最大 取 a r r 的最小 3 个数 a 1 , a 2 , a 3 ( a 1 ≤ a 2 ≤ a 3 ) 取arr的最小3个数 a_1, a_2, a_3 (a_1 \le a_2 \le a_3) 取arr的最小3个数a1,a2,a3(a1≤a2≤a3) 最大的 3 个数 , b 1 , b 2 , b 3 ( b 1 ≤ b 2 ≤ b 3 ) 最大的3个数, b_1, b_2, b_3 (b_1 \le b_2 \le b_3) 最大的3个数,b1,b2,b3(b1≤b2≤b3) 乘积最大 m a x ( a 1 ∗ a 2 ∗ a 3 , a 1 ∗ a 2 ∗ b 3 , a 1 ∗ b 2 ∗ b 3 , b 1 ∗ b 2 ∗ b 3 ) 乘积最大 max(a_1 * a_2 * a_3, a_1 * a_2 * b_3, a_1 * b_2 * b_3, b_1 * b_2 * b_3) 乘积最大max(a1∗a2∗a3,a1∗a2∗b3,a1∗b2∗b3,b1∗b2∗b3)
有了这个结论后剩下的就好办了
每个子节点再往上传的时候只需要保留3个最小数3个最大数即可。
而这点就扣合本题的思路 启发式合并 启发式合并 启发式合并
class Solution {int n;ListInteger[]g;int[] cost;long[] res;ListInteger []mins;ListInteger []maxs;void dfs(int u, int fa) {ListInteger tmpMin new ArrayList();ListInteger tmpMax new ArrayList();tmpMin.add(cost[u]);tmpMax.add(cost[u]);for (int v: g[u]) {if (v fa) continue;dfs(v, u);for (int tv: mins[v]) {tmpMin.add(tv);}for (int tv: maxs[v]) {tmpMax.add(tv);}}if (tmpMin.size() 3) {res[u] 1;} else {Collections.sort(tmpMin);Collections.sort(tmpMax);// 核心逻辑long ans Long.MIN_VALUE / 10;long a1 tmpMin.get(0), a2 tmpMin.get(1), a3 tmpMin.get(2);int nz tmpMax.size();long a4 tmpMax.get(nz - 3), a5 tmpMax.get(nz - 2), a6 tmpMax.get(nz - 1);ans Math.max(ans, a1 * a2 * a3);ans Math.max(ans, a1 * a2 * a6);ans Math.max(ans, a1 * a5 * a6);ans Math.max(ans, a4 * a5 * a6);if (ans 0) {res[u] 0;} else {res[u] ans;}}// 保留3位往上传for (int i 0; i 3 i tmpMin.size(); i) {mins[u].add(tmpMin.get(i));}for (int i tmpMax.size() - 1; i 0 tmpMax.size() - i 3; i--) {maxs[u].add(tmpMax.get(i));}}public long[] placedCoins(int[][] edges, int[] cost) {n cost.length;g new List[n];this.cost cost;Arrays.setAll(g, x-new ArrayList());for (int[] e: edges) {g[e[0]].add(e[1]);g[e[1]].add(e[0]);}mins new List[n];Arrays.setAll(mins, x-new ArrayList());maxs new List[n];Arrays.setAll(maxs, x-new ArrayList());res new long[n];dfs(0, -1);return res;}}写在最后
即使是希望、即使是梦想都是需要被守护的。
