首页 > 其他分享 >2024牛客暑期多校训练营6 K.The Great Wall 2

2024牛客暑期多校训练营6 K.The Great Wall 2

时间:2024-08-02 15:06:36浏览次数:16  
标签:Great le Wall 多校 tot 决策 cdots len 序列

题意

给定长为\(n\)的序列\(\{a_i\}\),分成恰好\(k\)个非空连续段使得这\(k\)的极差之和最小,对\(k=1,2,\cdots,n\)分别求解。\(n\le 5000\)

做法

定义:令\(f_{i,j}\)为将前\(i\)个数分成\(j\)段的最小极差之和,令\(w_{l,r}\)为\(a_l,\cdots,a_r\)的极差。

按\(j=1\sim n\)按层转移:

\[f_{i,j}=\min_{i_1=1}^{i}f_{i_1-1,j-1}+w_{i_1,i} \]

观察:对任意\(i_1<i_2\le i\),若\(f_{i_1-1,j-1}+w_{i_1,i}\le f_{i_2-1,j-1}+w_{i_2,i}\),则对任意\(i'>i\),\(f_{i_1-1,j-1}+w_{i_1,i'}\le f_{i_2-1,j-1}+w_{i_2,i'}\)。即对于\(i_1<i_2\),\(i_1\)对某一段后缀的转移比\(i_2\)优。

做法一\(O(n^2\log n)\)

考虑对于\(i=j\sim n\),动态维护一个决策序列\(j\le i_1,i_2,\cdots,i_{len}\le i\)(其中的每个点可能会成为某个\(i'\ge i\)的最优决策点),满足\(f_{i_k-1}+w_{i_k,i}>f_{i_{k+1}-1}+w_{i_{k+1},i}\)。\(i_{len}\)为\(i\)的最优决策点。

对应相邻的\(i_k,i_{k+1}\),可以二分出\(i_{k+1}\)何时会再比\(i_k\)更优,此时可以将其踢出序列。

序列用链表维护。实测与\(\text{std}\)跑得差不多快。

做法二(官方题解)\(O(n^2\alpha(n))\)

考虑对于\(i=j\sim n\),动态维护一个决策序列\(j\le i_1,i_2,\cdots,i_{len}\le i\)(其中的每个点可能会成为某个\(i'\ge i\)的最优决策点),满足\(f_{i_k-1}+w_{i_k,i}>f_{i_{k+1}-1}+w_{i_{k+1},i}\)。\(i_{len}\)为\(i\)的最优决策点。

考虑从\(i\)到\(i+1\)不同\(k\)的\(w\)增量\(\Delta_k=w_{k,i+1}-w_{k,i}\)。
增量的形式可以表示为\((l_1,r_1,\delta_1)(l_2,r_2,\delta_2)\cdots(l_{tot},r_{tot},\delta_{tot})\)(\(r_i=l_{x+1}-1\)、\(\delta_x<\delta_{x+1}\)),满足\(\forall k\in [l_x,r_x].\Delta_k=\delta_x\)

可以如此考虑维护决策序列:
从\(x=tot\sim 1\),找到\([l_x,r_x]\)中最大的决策点\(i_k\)(或者说,找到\(\le r_k\)的最大决策点),反复与其后面一个决策点进行比较,如果更优则将后面一个决策点踢掉。

观察2:可以不按\(x\)降序的顺序而是任意对于\(\{1,2,\cdots,tot\}\)的任意顺序,进行踢决策点的操作。

观察3:对于所有可能的\(r_x\),可以通过两个单调栈,分别维护后缀最小值和后缀最大值的过程得到。

对于某个位置\(pos\),如何找到\(\le pos\)的最大决策点和\(> pos\)的最小决策点,可以通过并查集得到。

标签:Great,le,Wall,多校,tot,决策,cdots,len,序列
From: https://www.cnblogs.com/Grice/p/18338566

相关文章

  • 2018多校集训 H. Hills And Valleys
    传送门题意给你一个\(n\leq10^5\)的序列,数字都是0-9,你可以任意翻转一个子区间,问翻转后最长不降子序列的最大长度。题解简略题解:我开始考虑的是\(f_i,j,k\)表示的是翻转\(i\)结尾的区间,翻转区间贡献了最长不降序列中\(j\)到\(k\)的部分,那么只要新加入的数小于\(j\)就可以翻......
  • 2024牛客暑期多校训练营6
    目录写在前面HBDAFI写在最后写在前面比赛地址:https://ac.nowcoder.com/acm/contest/81601#question以下按个人难度向排序。纯纯战犯场呃呃呃呃做题不看题小保底当成100抽一发我草太唐了开局吃五发呃呃呃呃中期口了三题出来写出来两道最后好歹没太烂呃呃置顶广告:中南大学A......
  • 2024牛客多校第5场
    很神奇的场hh,大家一起坐牢,多好啊!B找规律,这种题一般都是多模拟几个数据然后猜出来#include<bits/stdc++.h>usingnamespacestd;inlineintread(){intx=0;boolf=1;charch=getchar();for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');for(;......
  • 2024牛客暑期多校训练营6
    Abstract好难qwqA-CakeIdea全是博弈!首先来解释题目意思。phase1:给出一颗树,根节点为1,树上每一条边的权值为0或者1。初始时刻,根节点处有一只小马,小G和小O依次控制小马移动,每次只能向子节点移动,若当前节点是叶节点,phase1结束。在移动的过程中,需要记录经过的边的......
  • 2024牛客暑期多校训练营6 A Cake
    题目大意详细题目传送门\(A\)和\(B\)要从轮流走,从根到一个叶子节点位置,\(A\)先。树有边权\(0,1\),按照顺序经过的边权按字符串拼接得到一个串\(S\)。现在\(B\)可以把\(1\)拆分成任意个分数(但不能超过\(S\)的长度,且分数可以为空,)两人按照\(S\)串的顺序选取,如果\(S_......
  • 2024杭电多校2
    2024杭电多校2打的比较迷的一场,6,7,10签到,队友把11字符串写了,之后队友把字符串过来,全队就被1题鸡爪构造卡住了,队友继续取开构造我就随便开了,3题魔方玩过一段时间一眼看出结论后,变量名写反wa了一发,改过来之后没多久队友构造也过了,队友去开12,结果构造出一组hack样例,发现题比想象中难......
  • 2024牛客暑期多校训练营6 A.cake(题解)
    A.Cake题意两个人玩游戏,游戏分两阶段第一阶段在一棵有根树上轮流走,走到叶子停止,有根树边上有01标记,记录下走过的01串第二阶段分蛋糕,Oscar按自己的意愿切蛋糕,然后按照第一阶段获得的01串顺序依次拿蛋糕(1代表Grammy拿,0代表Oscar拿)两人都想让自己获得尽量多的蛋糕,......
  • 2024牛客暑期多校训练营6
    Preface警钟长鸣,经典一个变量拿来跑两次循环然后挂了看不出来,主要这种睿智错误只有像我这种把循环变量声明在开头的人才会犯当时看了半天没看出来红温了,还把队友都摇过来看,然后三个人全红温了直到最后瞎JBassert了半天才发现这个问题,然后罚时爆炸,会的题也没时间写了,直接掉大......
  • 杭电多校 2024 游记
    前言和ppip还有b6e0_组的队,team102。2024-07-19Round1自己过了2,8,12,5。2024-07-22Round2自己过了8,3,2。2024-07-26Round3自己过了8,11,12,5。2024-07-29Round4自己过了5,4,7。......
  • 2024杭电多校2&3
    能补多少是多少吧(大哭21002梦中的地牢战斗(hdu7446)本来看到66/386的战况差点打算跳过,看一眼题解似乎是dp+最短路之类,或许可以再想想?于是开始认真读题,数据范围很小,尤其是怪物数量\(k\leq10\),加之题目时限\(4s\),考虑略显暴力的状态压缩。由于角色血量\(\leq0\)时失去所有......