标签：偏序路径拐点操作考虑杂题我们贪心

基本都抄的，窝怎么这么渺小啊

AGC007F

这种匹配可行性基本都是从后往前贪心，这样没有后效性。

而我们考虑原序列的每个字符都对应了最后序列的一个区间（如果用上）。

考虑把整个变化过程写成一个矩阵，并且将每个字符染上不同颜色。

像这样：

容易发现对于一条新的路径，我们尽可能与上一条路径贴合最优。因为 \(y\) 坐标每增加一其实是拐点（向右）增加了一。

所以答案就是整个图最大连续（左下斜线）的右拐点个数。其实也是纵坐标。

考虑一个路径的拐点，与上一条路径贴和的话，就是上一个拐点的左下的点是当前路径的拐点。

所以可以存下每个拐点的路径起始位置 \(x\)，用队列维护拐点，假设其当前已经往左下走了 \(k\) 次，那么其坐标就是 \((x-k,k)\)。

每一次添加一条新路径时，那些 \(x\) 大于对应区间左端点的拐点会全部删掉。设 \(j\) 为原序列 \(j\) 位置与结果序列区间匹配，这个区间左端点是 \(i\)，需要有 \(j\le i\)，while(h<=t&&q[h]+h-t>i)++h;

所以这条路径的拐点会由剩下的原本拐点向左下走一步更新，而新拐点就从匹配位置起始（原序列的位置，这个位置向下走一步就开始右拐，这就是最上面的那个拐点）。q[++t]=j;

不难发现更新次数与当前拐点是队列里第几个对应（在之后插入了多少个拐点）。if(j!=i)ans=max(ans,h-t+2)，这是因为自带一个拐点，要特判掉直接往下走的情况。

AGC009 D

题意就是要求构造一颗原树的点分树，要求最大深度最小，求这个最小的最大深度。

不妨模仿求直径，我们设 \(d_i\) 为最优点分树里，到 \(i\) 的最长链长度。答案就是最大的 \(d_i\)。

那么根据点分树的性质：两点 \(LCA\) 必然在点分树路径上，点分树 \(LCA\) 必然在两点原树路径上。

可以得出一个必要条件：\(\forall i,j,d_i=d_j\) 则必然存在 \(x\)，\(d_x>d_i\) 且 \(x\) 在原树两点路径上。

同时我们说明这是充分的。

考虑每次取出最大 \(d\)，以它为根，删除它，递归处理剩下的连通块，由上述性质得到每个连通块里面最大的 \(d\) 唯一且都小于这个 \(d\)。

如果某个连通块存在两个最大的 \(d\)，那么整体的最大 \(d\) 不在其路径上，矛盾。如果某个连通块的最大 \(d\) 等于这个最大 \(d\)，跟唯一性矛盾。我们说明了每个连通块有相同性质，递归构造即可。

所以这个条件充要。

那么问题就变成了我们给所有点分配点权，使得最大的点权最小，且满足任意两个相同点权，路径上必然有点点权大于它们。

不妨考虑状压 \(dp\)。

设 \(f_{u,S}\) 为子树 \(u\) 里，有集合 \(S\) 的点权都出现了，且尚未解决（也就是尚未满足有一个点权大于它们，显然这是惟一出现）。

那么对于 \(d_u\) 的取值，也就是首先不能取各个子树的 \(S\) 里面有过的元素，且必须大于两个 \(v\) 共有元素的最大值。

从这里我们可以发现，对于每个值，取能取的最小值没有后效性，且一定最优。

所以我们不妨设 \(s_u\) 为按照以上贪心策略，子树 \(u\) 出现过的且还没有解决的点权集合。

因此我们任意钦定一个根，贪心的由叶子向根构造即可（原本是叶子在点分树上一定也是叶子，因为只有一个方向）。

那么可以求出 \(t=|_{i\neq j}s_{v_i}\& s_{v_j}\)，这是容易计算的（保留 \(| v_i\) 的前缀和即可），求出 \(w=| s_{v_i}\)

则我们所求的 \(k\)，必须大于 \(t\) 的最高位，且没有在 \(w\) 中出现过，可以利用 builtin 系列函数做到 \(O(1)\)。（取出 \(t\) 的最高位 \(k\)，然后将 \(w\) 的 \([0,k]\) 全部变成 \(1\)，接着再取 \(w\) 的第一个 \(0\) 即可）

根据点分治的知识我们知道答案不超过 \(O(\log n)\) 用个 unsigned int 的数状压即可。

将最优化问题变成树上赋权问题，这很妙啊。

AGC 018C

显然先拆分贡献，假定所有点都取 \(c\) ，变换 \((a_i,b_i,c_i)\to (a_i-c_i,b_i-c_i)\)，不妨设为 \((f_i,g_i)\) 那么答案也就是选出 \(x\) 个 \(f_i\)，\(y\) 个 \(g_i\) 使得其和最大。

考虑两个 \((f_i,g_i),(f_j,g_j)\) 分别取 \(f,g\) 优于取 \(g,f\)，则有：

\(f_i+g_j>f_j+g_i\implies f_i-g_i>f_j-g_j\) 所以按照 \(f-g\) 排序后必然存在分割点 \(k\)，\([1,k]\) 里选出 \(x\) 个 \(f\)，\([k+1,n]\) 里选出 \(y\) 个 \(g\)，利用堆/权值树做个前后缀贡献即可。

P5659

可以注意到，删边是假的，可以看作每条边只能够操作一次。

注意到交换后这个编号将永困子树中

但是可以注意到不妨以节点 1 为根，最差我们可以让第一个数字是1，这就要求了一个数字1到节点1操作的一个篇序关系

能否更进一步呢？

可以看出，我们最终的目的是保证i-1所对应节点的编号最小的情况下让i最小

俄

一个暴力就出来了，暴力枚举i，枚举其对应节点，建立偏序关系，判断是否成环

O(n^3)

这一定是核心做法——枚举对应节点判断是否合法

考虑下部分分

菊花图的情况

考虑一个点的所有出边的操作顺序？

由于菊花，所以我们可以完全可以把下次操作的边调整到当前操作边的旁边，会产生一个

会发现除了花心之外，我们可以适当调整剩下的顺序

可以等价为将花心移动到第一次操作的那个位置，并将最后一次操作的那个点变成花心，剩下的依次旋转

这相当于是一个置换，不妨设权值为i的点编号是p[i]，那么相当于对 p 作置换

满足置换环是一个大环即可

目的是让p最终字典序最小，那么p[1]与最小的连边，然后删去p[1]，继续决策即可

链的情况偏序关系

我们只需要关心相邻两个边的操作

那么首先我们让 \(p[1]\) 变成 \(1\)，枚举一个权值我们跑过去，并且标记这个方向上的边早于另外一个

矛盾即非法，这已经足够了

最后可以还原方案

一般的情况

这启发我们考虑一个点相邻边操作的偏序关系，而且如果没有公用顶点的边的偏序关系是不重要的

不妨维护这个偏序关系，肯定用链表维护局部吧

那么指定移动相当于给了新的偏序关系，这要求中间点的这两边必须相邻操作，同时起点边必须第一次操作，同时最终边也有较多限制

默然边指 \((u,v)\)

对起边的限制
1. 这条边的不能够已经两用了，也不能够向反方向移动，也就是这个方向没有数字占用
2. 这条边所在偏序关系链不能够不完整
  也就是指如果当前点 \(u\) 已经指定有数字将会换进来，这个必然是最后操作，同时也就提供了这个偏序关系（也就是我们已经最后一次操作（换进来数字），也即将指定第一次操作（当前换出去)）如果仍然有边没有参与那么一定非法
对中间边的限制
1. 这条边这个方向被使用过非法
2. 偏序关系成环非法
3. 当前点的边如果已经知晓始末并且这条边加入后还有游离边非法
对终边的限制
1. 这个方向被使用过非法
2. 偏序关系链如果已经确定头尾且不完整非法

实现较为复杂，我们将一条边的状态记作 \(0/1/2/3\)，表示两个方向都用完了/往上没用/往下没用/都没用，并统计每个点的后三类边个数，同时记录每条边当前所在偏序关系链的头尾。

作一次 dfs，将当前所需点设为根判断合法，然后取最小的出来往上跳更新信息

CF335F

~~335e已经够恶心了~~

题意其实是给定序列 \(a\)，然后要求将其分为两个部分 \(S,T\)，使得：

\(|S|\ge |T|\)
将 \(x\in S,y\in T,a_x>a_y\) 连边，存在完备匹配
\(\sum_{x\in S} a_x\) 最小

假定没有重复元素，可以想到将饼子按照 \(a\) 从大到小进行排序，设 \(f_{i,j}\) 表示前 \(i\) 个饼子中，还有 \(j\) 个饼子没有附赠品的最小代价

\(f_{i,j}=\min(f_{i-1,j-1}+a_i,f_{i-1,j+1})\)

可以 \(O(n^2)\) 而且感觉这东西有凸性。

如果有重复元素怎么办呢？

那就不妨设 \(f_{i,j}\) 为前 \(i\) 类饼子，还有 \(j\) 个饼子没有附赠品的最小代价

那么有：

\[f_{i,j}=\min_{k\in [0,c_i]}f_{i-1,j+c_i-2c}+(c_i-c)\times a_i \]

仍然可以 \(O(n^2)\) 做。

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    sort(a+1,a+n+1,[](int a,int b){return a>b;});
    int m=0;
    for(int i=1;i<=n;++i){
        if(a[i]!=a[i-1]){
            ++m;a[m]=a[i];
        }
        ++c[m];
    }
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(int i=0,s=0;i<m;++i){
        s+=a[i];
        for(int j=0;j<=s;++j)for(int k=0;k<=c[i+1];++k){
            if(j>=c[i+1]-k)f[i+1][j-c[i+1]+k*2]=min(f[i+1][j-c[i+1]+k*2],f[i][j]+k*a[i+1]);
        }
    }int res=0x3f3f3f3f3f3f3f3fll;
    for(int j=0;j<=n;++j)res=min(res,f[m][j]);
    cout<<res<<"\n";
}

好了现在我们给出了一个 \(O(n^2)\) 的方法，优化路径只有两条：

Slope Trick
贪心

好像有凸性，只看 \(j\equiv n\pmod 2\)

但不是很好弄阿

回到最开始的条件，我们假设不存在完备匹配，应当可以调整

例如如果有 \(x\in S,y\in T,a_x>a_y\) 那么交换 \(x,y\) 之后如果存在完备匹配，交换后不会变差，同时若不存在完备匹配，肯定是用 \(T\) 的失配值移动过去，甚至可能考虑再换一个过来

考虑反悔贪心，用一个堆来维护当前所有的赠品，遇到一个饼子的时候，如果还可以白拿就白拿，否则换一个赠品给钱白拿这个或者直接买了这个

后面这两决策谁更优秀？

换赠品给钱什么时候会优于后面的

显然不会，但是能白拿就白拿感觉是错的

当前白拿，后面给钱，代价 \(2x\)

当前给钱，后面白拿两个，代价 \(now\)

开个堆，维护当前这个白拿的换成给钱得给多少。

贪心比对决策就好了

详细地说，我们考虑维护一个小根堆，里面维护 当前所有白嫖决策的花费

当考虑新加入 \(c\) 个 \(a\) 时，我们先把可以白嫖的存下来（由于权值严格偏序，所以不能加入)

设 \(v\) 是堆顶，有如下方案：

\(v\le x\)（这是可能发生的，会有复杂的白嫖方案)

将其替换为白嫖 \(x\) 是不劣的，买了它后还能多嫖一个，所以新的白嫖方案是舍弃 \(v\)，嫖两个 \(x\)
\(v>x\)

此时考虑 \(w=2x-v\)，这是买 \(v\) 白嫖两个 \(x\) 的收益，我们当前面临选择哪个决策更好，我们可以当作白嫖了物品 \(2x-v\) （如果 \(w>0\) 的话)和物品 \(v\) 因为它后续影响是一样的（你可以看作两个方案之间转化的代价)

P6331

考虑差分，设 \(c\) 为全局差分数组，\(d\) 为下标。

发现好像很复杂，换个角度考虑。

首先我们可以调整操作二操作三的区间范围让其端点被修改。

所以我们可以统称操作二和操作三为第二类操作

发现对于 \(2k-1,2k\) 一定存在最优方案让其不可能同时进行二类操作（作为左端点)（取较小的右端点作为第一类操作）

这启发我们考虑 \(1\) 怎么消完。

\(a_1>a_2\) 首先进行 \(\min(a_1,a_2)\) 次操作一，接着 \(a_2\) 变为零，此刻要么使用二操作扩展要么就自己消自己，压力会给到 \(a_3\)，若 \(a_3\) 足够 \(a_1\) 进行第二类操作消完那就给到 \(a_3\)，否则将 \(a_1\) 先调整到 \(a_3\) 然后操作（这个调整同样可以选第二类操作，所以只会作第二类操作）

\(a_1\le a_2\) 直接做第一类操作显然是最优的。

因为每一类操作的代价是一样的，我们默然对于左端点相同的操作先进行一类。

我想我们将尽量将操作联动，考虑动态维护当前有多少一/二类可以扩展到 \(i\)（已经修正 \([1,i)\))

譬如设当前有 \(x,y\) 次 \(1/2\) 类操作可以扩展过来，有：

\(a_i\ge x+y\) 显然全部扩展过来就好了
\(a_i<x+y\)

考虑仅有第一类操作，虽然我们可以直接算出下界，但是还是回忆下它的过程，其实就是一个直接继承的过程，那么在这里我们先强制继承第一类操作是否更优？

显然是的，如果你这里继承了第二类下一次又被强行要求取第二类就违反了这个策略：相邻两个数不会同时进行第二类操作

但我们应当继承多少？全部继承么？

我们会余出 \(x+y-a\) 的操作次数随意继承，考虑延迟这个决策。

综上所述，我们维护 \(c_0,c_1,c_2\) 表示第一类，以及两种第二类的继承个数。

设当前操作的是 \((c_0,c_1)\)

分别对 \(a_{i+1}\) 取 \(\min\)
若 \(c_0+c_1>a_{i+1}\)
设 \(k=c_0+c_1-a_{i+1}\)，这是延迟操作的量，然后我们进行 \(c_0-k,c_1-k\) 次操作将 \(a_{i+1}\) 降为 \(k\)，但为了延迟决策假定现在是 \(0\)
若 \(c_0+c_1\le a_{i+1}\)
显然直接全用了最好
然后考虑增加操作：\(\min(a_i,a_{i+1})\) 需要更多的 \(c_0\)
若 \(a_i>a_{i+1}\) 还需要 \(a_i-a_{i+1}\) 次 \(c_2\)（注意这里延伸到了 \(i+2\)）
如果延迟了决策那就将 \(a_{i+1}\) 重新赋为 \(k\)。

标签：偏序,路径,拐点,操作,考虑,杂题,我们,贪心
From： https://www.cnblogs.com/spdarkle/p/18546231

跟贪心杂题爆了