首页 > 其他分享 >P9499 「RiOI-2」change 题解--zhengjun

P9499 「RiOI-2」change 题解--zhengjun

时间:2023-08-06 13:22:58浏览次数:37  
标签:P9499 cnt val -- 题解 int auto 贪心

思维妙妙题。

赛时的错误做法:

  • 找到每个点往后进位变优的位置,最多 \(O(\log)\) 个;

  • 然后从前往后能变优就变优,往后贪心进位。

hack 数据:

0
1
3
3 5 100
2 1 0
2 2

输出:100

这样子由于 \(1\) 到 \(2\) 不优,而 \(1\) 到 \(3\) 个数不够,所以导致无法进位到 \(3\)。

所以加强一下贪心策略。

用若干二元组 \(a_j=(c_j,v_j)\) 表示在当前的第 \(i\) 位,可以【最多 \(c_j\) 次】付出【前 \(i\) 位 \(v_j\) 的代价】换一个【 \(i\) 位的 \(1\)】。

注:此时已经使得 \(a_j\) 关于 \(v_j\) 升序,保证贪心顺序。

然后考虑共有那些操作:

  • 从第 \(i\) 位到第 \(i+1\) 位,第 \(i\) 位的 \(x_i\) 个 \(1\) 可以变成 \(1\) 个第 \(i+1\) 位的 \(1\),贪心的每次用前 \(x_i\) 个合并成一个即可。

  • 插入 \((c_i,v_i)\),为了保证单调性,发现如果 \((c,v)\) 满足 \(v<v_i\),那么是可以使用该操作获得 \(v_i-v\) 的收益,所以把所有 \(v<v_i\) 的合并掉,并把 \((c,v)\) 加入开头即可。

    注:此时需要把 \(c_i\leftarrow c_i+c\)。

这样的复杂度最坏可以到达 \(O(n^2)\),而且这样合并之后的 \(v\) 会非常大,然而这样的 \((c,v)\) 却没有任何作用,所以新增一个操作:把序列末位 \(v>10^9\) 的二元组弹掉。

只需用 deque 维护即可,时间复杂度:\(O(n\log n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10,INF=1e9,mod=998244353;
int T,n,a[N],b[N],c[N];
struct zj{
	ll cnt,val;
};
void get(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<n;i++)scanf("%d",&c[i]);
	deque<zj>q;
	int ans=0;
	auto merge=[&](int x){
		ll cnt=0,val=0;
		deque<zj>p;
		for(zj t:q){
			if(cnt+t.cnt<x)cnt+=t.cnt,val+=t.cnt*t.val;
			else{
				p.push_back({1,val+(x-cnt)*t.val});
				t.cnt-=x-cnt,cnt=0;
				if(t.cnt>=x)p.push_back({t.cnt/x,t.val*x});
				cnt=t.cnt%x,val=cnt*t.val;
			}
		}
		q.swap(p);
	};
	auto reduce=[&](){
		for(;!q.empty()&&q.back().val>INF;q.pop_back());
	};
	auto insert=[&](zj x){
		for(;!q.empty()&&q.front().val<x.val;q.pop_front()){
			ans=(ans+(x.val-q.front().val)*q.front().cnt)%mod;
			x.cnt+=q.front().cnt;
		}
		q.push_front(x);
	};
	for(int i=1;i<=n;i++){
		reduce();
		ans=(ans+1ll*b[i]*a[i])%mod;
		insert({b[i],a[i]});
		if(i<n&&c[i]>1)merge(c[i]);
	}
	printf("%d\n",ans);
}
int main(){
	freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	for(scanf("%*d%d",&T);T--;)get();
	return 0;
}

标签:P9499,cnt,val,--,题解,int,auto,贪心
From: https://www.cnblogs.com/A-zjzj/p/17609325.html

相关文章

  • 可与ViT一较高下,DeepMind从稀疏转向Soft混合专家模型
    前言 对于谷歌DeepMind的SoftMoE,有人表示:「即使它不是万能药,仍可以算得上一个突破」。本文转载自机器之心仅用于学术分享,若侵权请联系删除欢迎关注公众号CV技术指南,专注于计算机视觉的技术总结、最新技术跟踪、经典论文解读、CV招聘信息。CV各大方向专栏与各个部署框架最......
  • 单片机基础知识
    一、原理图和元器件1.芯片引脚Vdd和VssVdd=VoltageDrain-DrainVss=VoltageSource-Source{width:20pxheight:20px}......
  • 深信服行为管理AC配置笔记
    深信服行为管理AC配置,可以直接参考官网原文:https://support.sangfor.com.cn/productDocument/read?product_id=22&version_id=907&category_id=244007 步骤1.通过默认IP登录设备,比如通过LAN口登录设备,LAN口的默认IP是10.251.251.251/24,在电脑上配置一个此网段的IP地址,通过http......
  • MySQL数据库的常用命令
    1.创建数据库指定字符集:CREATE DATABASEdb_nameDEFAULTCHARACTERSETutf8COLLATEutf8_general_ci 2.新建用户:createuser'hive'@'localhost'identifiedby'123456';如果提示:ERROR1290(HY000):TheMySQLserverisrunningwiththe--skip-gra......
  • 如何使用 Python 运算符进行性能优化 All In One
    如何使用Python运算符进行性能优化AllInOne为什么Python运算符//比运算符/性能更好,运行速度更快呀❓WhyPythonoperator//isfasterthanoperator/demosclassSolution:defnumberOfSteps(self,num:int)->int:steps:int=0whilenum>......
  • DOM重点核心
             ......
  • zabbix触发器标签提取监控项子字符串功能实现对应告警恢复
    0实验环境zabbix6.01监控项1.1监控项设置通过zabbixagent自定义监控项,读取某文件内容模拟日志/trap告警,测试获取触发器标签中提取子字符串功能,以及相同标签的触发器自动恢复功能。1.2手工运行手动触发之后,模拟产生如下日志数据,意为集群中node-01主机离线。07:28:29......
  • axios介绍
    1. axios介绍   42axios是一个基于 promise 的 HTTP 库,可在浏览器和 node.js 中。1.1 特性:  42o 从浏览器中创建 XMLHttpRequesto 从 node.js 发出 http 请求o 支持 Promise APIo 拦截请求和响应o 转换请求和响应数据o 取消请求o 自动转换JSON数据o 客户端支持......
  • Google Review评价被删除了,怎么恢复?【附详细操作指引】
    自从2022年初,谷歌推出Googlereviews的人工智能AI评论过滤器之后,在删除大量虚假Googlereviews的同时,连同许多正常顾客的Google评价也一起删掉了,这种情况经常发生,这引起很多Googlebusiness商家强烈不满。 对此,今年Google终于发布一个关于Googlereviews的表单求助功能,帮助Google......
  • PPT| 数据治理实时数据中心解决方案 P56
    PPT共56页,由于篇幅有限,以下为部分资料.......