首页 > 其他分享 >【题解 P8476】 惊蛰

【题解 P8476】 惊蛰

时间：2023-11-13 15:13:31浏览次数：34  
标签：f1 return lc 题解 P8476 惊蛰 long rc ql

「GLR-R3」惊蛰

题目背景

  「微雨众卉新，一雷惊蛰始」

  中午，休息室，阿绫肩膀上。

  “我有一个愿望，参加全国音乐祭，获奖，和阿绫一起，摆脱这训练的苦海。”

  “为热爱而到来，为抽身而努力……吗”。

  正午的阳光渗过窗帘，抚上困倦的人儿的脸颊。天依的左手悄悄搭上阿绫怀里的吉他，

  “铮——”

  蛰虫被雷声唤醒，没人向他们保证雨的降临。

  惊蛰 「我愿把岁月磨成望镜寻遍这星空　将微光聚焦手心紧紧握住不放松」

题目描述

比赛临近，各式测试也丰富了起来，作为天依他们的专业分析师，你的工作是统计分析队员们表现情况——总之，某领导要来慰问，所以你被要求修改出一份令人赏心悦目的分析报告。

在已有的 \(n\) 次测试中，对于某位特定的选手，他在第 \(i\) 次测试的波动值是非负整数 \(a_i\)。波动值越小表示选手在测试中的心态和发挥越稳定，所以你需要“略微调整”波动值序列 \(\{a_n\}\)，得到另一个非负整数序列 \(\{b_n\}\)。不过，做人不能昧良心，但报告又必须好看，所以 \(\{b_n\}\) 有如下要求：

  • \(\{b_n\}\) 单调不递增，选手越来越厉害嘛；

  • 对于每个 \(i\)，如果 \(b_i<a_i\)，老师会不高兴，所以你需要花费 \(C\) 单位的精力说服老师（其中 \(C\) 为给定常数）；

  • 对于每个 \(i\)，如果 \(a_i\le b_i\)，选手会不高兴，而且可能很不高兴，所以你需要花费 \(b_i-a_i\) 单位的精力安慰选手。

你希望在满足条件的情况下，最小化花费的精力之和。作为成熟的信竞选手，你自然需要自己动手，求出这一最小化的结果。

形式化题意

给定非负整数序列 \(\{a_n\}\)，定义函数 \(f(x,y)\) 为

\[f(x,y)=\begin{cases} x-y,&x\ge y\\ C,&x< y \end{cases}, \]

其中 \(C\) 是给定常数。请构造一个不增非负整数序列 \(\{b_n\}\)，最小化

\[\sum_{i=1}^nf(b_i,a_i). \]

你仅需输出这一最小化的结果。

输入格式

第一行两个整数，表示序列长度 \(n\) 和给定常数 \(C\)。

接下来一行表示序列 \(\{a_n\}\) 。

输出格式

输出一行一个整数，表示最小化的结果。

样例 #1

样例输入 #1

3 3
4 5 2

样例输出 #1

1

样例 #2

样例输入 #2

10 5
12 17 20 2 0 1 13 6 10 1

样例输出 #2

26

提示

样例 #1 解释

构造 \(\{b_n\}=\{5,5,2\}\)，可见：

\[\begin{aligned} \sum_{i=1}^nf(b_i,a_i) &= f(5,4)+f(5,5)+f(2,2)\\ &= 1+0+0\\ &= 1. \end{aligned} \]

样例 #2 解释

构造 \(\{b_n\}=\{12,11,4,2,1,1,1,1,1,1\}\)，可以得到答案。

数据规模与约定

本题采用 Subtask 的计分方式。

设 \(V\) 为序列 \(\{a_n\}\) 中元素以及常数 \(C\) 的值域。

对于 \(100\%\) 的数据，\(1\le n\le10^6\)，\(V\subseteq[0,10^9]\)。

对于不同的子任务，作如下约定：

子任务编号 \(n\) \(V\) 特殊性质 子任务分值
\(1\) \(\le10^3\) \(\subseteq[0,10^9]\) 无 \(25\)
\(2\) \(\le10^5\) \(\subseteq[0,10^2]\) 无 \(15\)
\(3\) \(\le10^6\) \(\subseteq[0,10^9]\) A \(5\)
\(4\) \(\le10^6\) \(\subseteq[0,10^9]\) B \(15\)
\(5\) \(\le10^5\) \(\subseteq[0,10^9]\) 无 \(20\)
\(6\) \(\le10^6\) \(\subseteq[0,10^9]\) 无 \(20\)
  • 特殊性质 A：对于常数 \(C\) ，满足 \(C = 0\)。
  • 特殊性质 B：对于序列 \(\{a_n\}\) ，满足元素单调递增。

解题思路

先考虑拿部分分。
看到这种题我们就可以考虑 \(DP\) ，设 \(f_{i,j}\) 为做到第 \(i\) 次测试的 \(b_i\) 为 \(j\) ，那么有

\[f_{i,j} = \min_{k>j} f_{i-1,k} +d_{i,j} \]

\[d_{i,j}= \begin{cases} C ,j<a_i \\ j-a_i,j \ge a_i \end{cases} \]

很明显，关于 \(a_i\) 我们是可以离散化的，所以 \(d\) 变成

\[d_{i,j}= \begin{cases} C ,j<a_i \\ t_j-t_{a_i},j \ge a_i \end{cases} \]

\(t_i\) 即使变化后每一位对应的原权值。
这样只能过 Subtask 1 ，考虑优化。
首先，每一个 \(f_{i,j}\) 只跟前一个 \(f_{i-1,j}\) 有关，所以我们可以做成维护后缀 \(min\) 后再加上 \(d_{i,j}\) 。
由于有后缀 \(min\) ，所以 \(f\) 再未加上 \(d\) 是必定单调不递减，那 \(d\) 有什么单调性规律呢？
容易发现，对于 \(j<a_i\) 的部分，\(f\) 加上后必定是单调的，而 \(j \ge a_i\) 的部分，\(f\) 加上后此部分也是单调的。
所以，整个 \(f\) 在加上 \(d\) 后会分成两段单增不递减的区间，每次我们都需要对 \(f\) 做后缀 \(min\) ,给一个区间加上一个数，给一个区间加上一个递增序列，最后求最小值。
我们就可以把这个 \(DP\) 做到线段树上了，每次区间推平或区间加上一个数或区间加上一个递增序列，同时线段树二分找需推平的位置，同时维护区间最小。
时间复杂度 \(O(nlogn)\)

Code

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],b[1000005],m,f[4000005],d1[4000005],d2[4000005],d3[4000005],f1[4000005];
set<long long> l; 
map<long long,long long> p;
void galaxy1(long long x,long long l,long long r,long long v)
{
	if(v==-1)return;
	f[x]=f1[x]=v;
	d1[x]=v;
	d2[x]=d3[x]=0;
	return; 
}
void galaxy2(long long x,long long l,long long r,long long v)
{
	f[x]+=v;
	f1[x]+=v;
	d2[x]+=v;
	return;
}
void galaxy3(long long x,long long l,long long r,long long v)
{
	f[x]+=b[l]*v;
	f1[x]+=b[r]*v;
	d3[x]+=v;
	return;
}
void pushdown(long long x,long long l,long long r)
{
	long long lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
	if(d1[x]!=-1)galaxy1(lc,l,mid,d1[x]),galaxy1(rc,mid+1,r,d1[x]),d1[x]=-1;
	if(d2[x]!=0)galaxy2(lc,l,mid,d2[x]),galaxy2(rc,mid+1,r,d2[x]),d2[x]=0;
	if(d3[x]!=0)galaxy3(lc,l,mid,d3[x]),galaxy3(rc,mid+1,r,d3[x]),d3[x]=0;
	return;
} 
void dijah1(long long x,long long l,long long r,long long ql,long long qr,long long v)
{
	if(ql<=l&&r<=qr)
	{
		galaxy1(x,l,r,v);
		return;
	}
	pushdown(x,l,r);
	long long lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
	if(ql<=mid)dijah1(lc,l,mid,ql,qr,v);
	if(qr>mid)dijah1(rc,mid+1,r,ql,qr,v);
	f[x]=min(f[lc],f[rc]);
	f1[x]=max(f1[lc],f1[rc]); 
	return;
}
void dijah2(long long x,long long l,long long r,long long ql,long long qr,long long v)
{
	if(ql<=l&&r<=qr)
	{
		galaxy2(x,l,r,v);
		return; 
	}
	pushdown(x,l,r);
	long long lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
	if(ql<=mid)dijah2(lc,l,mid,ql,qr,v);
	if(qr>mid)dijah2(rc,mid+1,r,ql,qr,v);
	f[x]=min(f[lc],f[rc]);
	f1[x]=max(f1[lc],f1[rc]); 
	return;
}
void dijah3(long long x,long long l,long long r,long long ql,long long qr,long long v)
{
	if(ql<=l&&r<=qr)
	{
		galaxy3(x,l,r,v);
		return; 
	}
	pushdown(x,l,r);
	long long lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
	if(ql<=mid)dijah3(lc,l,mid,ql,qr,v);
	if(qr>mid)dijah3(rc,mid+1,r,ql,qr,v);
	f[x]=min(f[lc],f[rc]);
	f1[x]=max(f1[lc],f1[rc]); 
	return;
}
long long gaia1(long long x,long long l,long long r,long long ql,long long qr)
{
	if(ql<=l&&r<=qr)return f[x];
	pushdown(x,l,r);
	long long lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1,h=1e15+5;
	if(ql<=mid)h=gaia1(lc,l,mid,ql,qr);
	if(qr>mid)h=min(h,gaia1(rc,mid+1,r,ql,qr));
	return h; 
}
long long gaia2(long long x,long long l,long long r,long long ql,long long qr,long long v)
{
	if(f[x]>=v)return l;
	if(l==r)return -1;
	long long lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1,h;
	pushdown(x,l,r);
	if(qr<=mid)return gaia2(lc,l,mid,ql,qr,v);
	if(ql>mid)return gaia2(rc,mid+1,r,ql,qr,v);
	if(f[rc]<v)return gaia2(rc,mid+1,r,ql,qr,v);
	h=gaia2(lc,l,mid,ql,qr,v);
	if(h==-1)return gaia2(rc,mid+1,r,ql,qr,v);
	return h;
}
int main()
{
	long long x,y;
	memset(d1,-1,sizeof(d1));
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),l.insert(a[i]);
	long long g=0;
	set<long long>::iterator q=l.begin();
	for(;q!=l.end();q++)
	{
		p[*q]=++g;
		b[g]=*q;
	}
	for(int i=1;i<=n;i++)a[i]=p[a[i]];
	if(a[1]!=1)dijah1(1,1,g,1,a[1]-1,m);
	dijah3(1,1,g,a[1],g,1);
	dijah2(1,1,g,a[1],g,-b[a[1]]);
	for(int i=2;i<=n;i++)
	{
		y=gaia1(1,1,g,a[i-1],a[i-1]);
		if(a[i-1]!=1)
		{
			x=gaia2(1,1,g,1,a[i-1]-1,y);
			if(x!=-1)dijah1(1,1,g,x,a[i-1]-1,y);
		}
		if(a[i]!=1)dijah2(1,1,g,1,a[i]-1,m);
		dijah3(1,1,g,a[i],g,1);
		dijah2(1,1,g,a[i],g,-b[a[i]]);
	}
	printf("%lld",gaia1(1,1,g,1,g));
	








  return 0;
}

标签：f1,return,lc,题解,P8476,惊蛰,long,rc,ql
From： https://www.cnblogs.com/dijah/p/17829190.html

相关文章

  • NOJ题解
    NOJ题解30-40素数埃氏筛，欧拉筛都可可变参数累加/平均用给出的库函数即可基思数根据题意模拟#include<stdio.h>#definelllonglongllnum[102];inlineboolIsKeith(lln){inttot=0,t=0;lls=n;while(s){num[++tot]=s%10......
  • 问题解答：SAP OData V2 和 V4 里针对日期类型的字段进行过滤操作(filter)的正确语法试
    我的知识星球里有朋友咨询一个问题：我测试了一个S/4HANAcloud的purchaseorder的API,这个是ODATAV4格式的。在对CreationDate做filter后运行有报错Invalidparametertypeusedwithfunction'eq'.对datetime字段做filter，一直搞不清楚格式。请帮忙看一下。本文就安排这......
  • [题解] P6569 [NOI Online #3 提高组] 魔法值
    P6569[NOIOnline#3提高组]魔法值不放简要题意了，题面写的很简要。看到数据范围自然可以想到矩阵快速幂优化。但乘法对异或没有分配律。所以直接拆位，把异或变成加法对二取模就有分配律了。还有一个优化就是提前预处理出矩阵的2的幂次方，然后询问时直接二进制分解乘起来就行......
  • ARC119F 题解
    前言ARC119F好厉害，是没见过的自动机DP。正文[1]分析主要分析一下为什么这么写。[2]状态设计[3]自动机状态转移感觉状态设计中最难的就是如何处理带\(O\)的。见参考资料。[4]代码还没写。写ing这是自动机的初始化（有点麻烦）。intto[Kind][2][2]={{{2,0},{8,0......
  • ABC328F题解
    原题链接洛谷题面提交记录闲话赛场就做了这道和A，喜提\(625\)大分。带权并查集练手题，有点像银河英雄传说。题目大意存在一个长度为\(N\)的数列\(X\)，给定\(Q\)个三元组\((a_i,b_i,d_i)\)，定义一个好集合为集合\(S\subseteq\{1,2,\dots,Q\}\)，使得所有\(x\inS\)满......
  • 题解：[春季测试 2023] 幂次
    题解：[春季测试2023]幂次给定\(n,k\)，求有多少个整数\(i\in[1,n]\),满足\(i=a^b(a,b\inN^+,b\geqk)\)算法一\(k\ge3:\)发现只需要筛到1e6就没有贡献了，加上\(set\)暴力判重即可。\(k=2:\)发现有\(\sqrt{n}\)个完全平方数，考虑如何避免算重它们。考虑完全平......
  • Tenzing and Random Operations CF1842G 题解
    设\(m\)次选的位置分别为\(b_{1\simm}\)。于是答案为\(\mathbbE(\prod\limits_{i=1}^{n}(a_i+\sum\limits_{j=1}^{m}[b_j\lei]\cdotv))=\frac{S}{n^m}\)。首先考虑期望很难做，希望将期望转化为概率形式，发现这样有点困难。再考虑因为所有方案等概率，将求期望转化......
  • P2687 [USACO4.3] 逢低吸纳 题解
    双倍经验分析这是一道求最长下降子序列的题目，且要统计方案，但是会有重复情况，例如以下的的数据，44223我们可以选择\(1,2\),\(1,2\),\(1,4\)这几天来购买，但是\(1,2\)和\(1,3\)本质上是一样的，所以只算一种。根据上面的说明，我们可以得出：当\(dp_j+1=dp_i\)......
  • [题解] P9838 挑战 NPC IV
    P9838挑战NPCIV定义\(f(x)=1+\log_2\operatorname{lowbit}(x)\)。定义一个\(1\simn\)的排列\(p\)的权值是\(\sum_{l=1}^n\sum_{r=l}^n\sum_{i\in[l,r]}f(p_i)。\)求所有\(1\simn\)的排列中权值第\(k\)小的排列的权值，对\(998244353\)取模。......
  • 【2023 #84】 锦城ACM周测 (大二个人赛) 题解
    题目难度\(B<D<E=C<A\)A:提高+/省选-B:普及-C:普及/提高-D:普及/提高-E:普及/提高-CandywarQuestion有\(N\)个盒子摆成环形，第\(i\)和盒子里面有\(a_i\)个糖果，他们开始在\(1\)好盒子，然后每个人取一次，可以取\(1\)，或者小于当前盒子内糖果数的一个质数\(p\),......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99