首页 > 其他分享 >【题解】P4331 [BalticOI 2004]Sequence 数字序列

【题解】P4331 [BalticOI 2004]Sequence 数字序列

时间:2023-05-11 19:48:21浏览次数:51  
标签:rt seq Sequence int 题解 rs len 2004 dis

以各种方式出现被玩烂的题目,算是小 trick 题?

cp editor 意外地好用

思路

可并堆。

平行时空同位体:CF13C P4331 P4597 CF713C P2893

已知做法:

  • \(O(n ^ 2)\) dp:令 \(f[i][j]\) 为前 \(i\) 个数不超过 \(j\) 的最小代价

  • 优化:使用堆维护 dp 产生的折线(P4597 题解区)

  • \(O(n \log n)\):可并堆

结论:\(b\) 序列中的数均为 \(a\) 序列中的数

关于可并堆做法,先考虑 \(b\) 单调不降而非严格递增的弱化版。

注意到两个比较直接的结论:

  • 当 \(a\) 单调不降时,\(b = a\).

  • 当 \(a\) 单调不增时,\(b\) 均为 \(a\) 的中位数。

又因为 \(a\) 可以分成若干段单调不增的区间,所以可以考虑将这些区间设置为其中位数,然后再调整不满足严格递增的位置。

调整其实就是把两个区间合并成一个区间,然后再用这个区间的中位数填充。

这个过程可以考虑维护增量,动态合并区间 + 求区间最值可以考虑用可并堆实现。

至于单调不降变严格递增是一个小 trick:给每个位置加上 / 减去下标就可以转化限制了。

时间复杂度 \(O(n \log n)\)。

代码

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;

typedef long long ll;

const int maxn = 1e6 + 5;

struct item
{
    int rt, l, r, sz, val;
} seq[maxn];

int n;
int a[maxn];
int ls[maxn], rs[maxn], dis[maxn];

int merge(int x, int y)
{
    if ((!x) || (!y)) return x | y;
    if (a[x] < a[y]) swap(x, y);
    rs[x] = merge(rs[x], y);
    if (dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]] + 1;
    return x;
}

int del(int x) { return merge(ls[x], rs[x]); }

int main()
{
    scanf("%d", &n);
    dis[0] = -1;
    int len = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]), a[i] -= i;
        seq[++len] = (item){i, i, i, 1, a[i]};
        while ((len > 1) && (seq[len - 1].val > seq[len].val))
        {
            len--;
            seq[len].rt = merge(seq[len].rt, seq[len + 1].rt);
            seq[len].sz += seq[len + 1].sz, seq[len].r = seq[len + 1].r;
            while (seq[len].sz > (seq[len].r - seq[len].l + 2) / 2) seq[len].sz--, seq[len].rt = del(seq[len].rt);
            seq[len].val = a[seq[len].rt];
        }
    }
    int cur = 1; ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (seq[cur].r < i) cur++;
        ans += abs(seq[cur].val - a[i]);
    }
    printf("%lld\n", ans);
    cur = 1;
    for (int i = 1; i <= n; i++)
    {
        if (seq[cur].r < i) cur++;
        printf("%d ", seq[cur].val + i);
    }
    return 0;
}

标签:rt,seq,Sequence,int,题解,rs,len,2004,dis
From: https://www.cnblogs.com/lingspace/p/p4597.html

相关文章

  • [NOIP2004 提高组] 津津的储蓄计划
    [NOIP2004提高组]津津的储蓄计划题目描述津津的零花钱一直都是自己管理。每个月的月初妈妈给津津\(300\)元钱,津津会预算这个月的花销,并且总能做到实际花销和预算的相同。为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了年末她会加上\(20\%\)还给津......
  • AtCoder Beginner Contest 298 题解
    题面:https://atcoder.jp/contests/abc298/tasks_printA-JobInterview直接模拟即可。#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/hash_policy.hpp>usingnamespace......
  • # Codeforces Round 872 (Div. 2) 题解
    CodeforcesRound872(Div.2)题解A.LuoTianyiandthePalindromeString略B.LuoTianyiandtheTable略C.LuoTianyiandtheShow略D1.LuoTianyiandtheFloatingIslands(EasyVersion)题意在树上随机撒\(k(k\leq3)\)个关键点,规定一个点是好的当且仅当这个......
  • springboot跨域问题解决方案
    以下内容仅供自己学习使用,侵权私聊必删。在进行前后端交互的时候,往往会遇到以下的跨域问题。那么解决这种跨域的话,可以使用以下这种方法:(引自于程序员青戈)创建config配置目录新建CorsConfig类然后把下面的内容复制进去根据自己需要修改以下就可以解决跨域问题啦importo......
  • P1676 [USACO05FEB] Aggressive cows G 题解
    题目传送门解题思路最大值最小化问题,考虑二分答案。首先要排序,保证序列单调不降,然后求出两个隔间之间的距离。sort(a+1,a+1+n);for(rii=1;i<=n;i++) dis[i]=a[i+1]-a[i];二分出一个\(mid\),判断它是否合法:每次累加距离,如果距离和比\(mid\)大,说明当前可以分配牛,记录数量......
  • Codeforces Round 683 (Div. 1, by Meet IT) ABCDF题解
    F和D都在ABC上做过类似的,但是没打好,道心破碎。。。。A.Knapsack若物品质量在[(w+1)/2,w]之间做完了否则一直贪心加voidsolve(){intn;llw;cin>>n>>w;intc=n;for(inti=1;i<=n;i++){cin>>a[i];if(a[i]>w)c--;}if(!c){......
  • Linux环境下,输入文件的编码格式和系统格式导致的问题解决办法
    1.用vim111.txt进入查看状态 2系统格式的查看和修改查看指令:setfileformat修改指令:setfileformat=unix3编码格式的查看和修改 查看指令 :setfileencoding 修改指令 在Vim中直接实行转换文件编码,比如将一个文件转换成u......
  • linux静态库的制作及问题解决
       首先介绍下分文件,在学习或者开发中,实现一个项目需要实现很多的功能,那么这些功能不可能在一个".c"文件下实现,需要多个".c"文件来共同实现,但是程序的入口只有一个,就体现了分文件编程的重要性,在主函数中调用其余的功能函数。分文件编程的优点及意义就是:分模块编程思......
  • CF1825D1 题解
    一、题目描述:给定$n$和$k$,表示有$n$个点,其中有$k$个点是关键点,这$k$个点随机分布。给出$n$个点的连接方式,保证构成一棵树,求有期望多少个点使得这个点到$k$个关键点的距离之和最小,答案对$1e9+7$取模。数据范围:$1\leqn\leq2e5,1\leqk\leqmin(n,3)......
  • Personalized Top-N Sequential Recommendation via Convolutional Sequence Embeddin
    目录概符号说明Caser代码TangJ.andWangK.Personalizedtop-nsequentialrecommendationviaconvolutionalsequenceembedding.WSDM,2018.概序列推荐的经典之作,将卷积用在序列推荐之上.符号说明\(\mathcal{U}=\{u_1,u_2,\cdots,u_{|\mathcal{U}|}\}\),us......