首页 > 其他分享 >20240914 模拟赛

20240914 模拟赛

时间:2024-11-08 15:19:09浏览次数:1  
标签:tot 插入 20240914 数组 排序 mex 模拟

20240914 模拟赛

A 开挂(openhook)

可以发现结果序列是能确定的,而且我们并不关心具体对哪个数进行操作,有用的信息只有操作次数,从而可以得到一个数组 \(c\) 表示对某个数操作了某个次数。设对 \(tot\) 个数进行了操作,将 \(c\) 从小到大排序,将 \(b\) 中的前 \(tot\) 小从大到小排序,于是 \(ans=\sum_{i=1}^{tot}c_ib_i\)。

要最小化这个值,注意到 \(c_i\) 的和是一定的,那么肯定是让较大的数越大越好,也就是尽可能不平均。考虑从原数组中取出一个最大的不重集合并排序,那么剩下的数要么插入集合中的两个数之间,要么放到末尾。放到末尾的部分容易处理,只需求出插入的情况。按值从小到大枚举这个集合中可插入的区间,根据分析的性质发现插入的数原本要越大越好,并且从大到小插入。二分出可插入的数,链表维护剩下的数就好,时间复杂度 \(O(n \log n)\)。

B 叁仟柒佰万(clods)

容易注意到一个性质,分开后每段的 \(mex\) 一定为全局 \(mex\),因为每个出现过的数都会使某一段的 \(mex\) 不为这个数。于是可以想到双指针维护哪些区间的 \(mex\) 为全局 \(mex\),时间复杂度 \(O(n)\)。

瞪眼可以想到一个 dp,设 \(f_{i,j}\) 表示前 \(i\) 个数分 \(j\) 段的方案数,这是 \(O(n^3)\) 的。很快发现记录段数根本没用,于是省掉第二维变成 \(O(n^2)\)。于是得到这样的式子:f[i] += f[l - 1] * check(l, i);,根据双指针的预处理可以 \(O(1)\) check。

分析得到能产生贡献的总是一段前缀,前缀和优化即可做到 \(O(n)\)。

这题卡空间,只能开 3 个 37000000 的 int 数组,把 \(f\) 省去即可。

标签:tot,插入,20240914,数组,排序,mex,模拟
From: https://www.cnblogs.com/luyuyang/p/18535160

相关文章

  • Chromium 进程降权和提权模拟示例c++
     一、背景知识概念参考微软链接:强制完整性控制-Win32应用程序|Microsoft学习授权)(模拟级别-Win32apps|MicrosoftLearnDuplicateTokenEx函数(securitybaseapi.h)-Win32apps|MicrosoftLearn本文主要演示 low,medium,high,andsystem四种权限创建......
  • C++:模拟实现STL的list
    目录一.list类1.list的创建节点2.list迭代器的运算符操作3.list的构造函数及析构4.list的迭代器5.list的插入及删除二.整体代码1.list.h2.list.cpp在上一节已经了解list在库中的用法,在这里实现list的底层逻辑一.list类1.list的创建节点template<classT>struc......
  • [赛记] NOIP2024加赛1 && 多校A层冲刺NOIP2024模拟赛18
    暴力错解大赛玩游戏82pts乱糊的错解,正确性和时间复杂度都不对,但是拿了82pts;对于正解,考虑从$k$将原序列分成两个部分,左边和右边,然后分别求一次前缀和(注意这里,可以省去很多分讨和常数),设前一个前缀和数组为$a$,后一个为$b$,那么问题就转化成有两个指针$i,j$,可以任......
  • NOIP 模拟 7
    T1图书管理(book)考虑每个数做中位数的贡献,经典trick就是小于的为\(-1\),大于的为\(1\),前缀和相减为\(0\)的就合法,不会链表。T2两棵树(tree)又是经典trick,森林的连通块数为点数减边数,证明就是算树的数量,好像之前见过这个trick。然后把贡献拆开,\(e\)代表点,\(v\)代......
  • 多校A层冲刺NOIP2024模拟赛19
    多校A层冲刺NOIP2024模拟赛19其实不太想写博客,但还是从今天开始坚持写吧。T1图书管理对于这种一边大一边小的问题,一般套路是大的设为$1$,小的设为$-1$,这道题也是,这样之后去扫一遍,两端的前缀和值一样即可。T2两棵树新学到的一个重要$trick$是:$$连通块的个数......
  • C# 队列的一些并发模拟
    usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.Threading;usingSystem.Collections.Concurrent;namespace......
  • 【记录分享】多任务黑客攻击仿真模拟器
     在电影和电视剧中,黑客攻击的场景往往充满了紧张、快速的打字声和不断滚动的命令行界面。为了让这种体验更具沉浸感,我们可以通过编程模拟出一个真实的黑客攻击过程。本篇文章将介绍如何使用Python和Tkinter库设计一个多任务黑客攻击仿真模拟程序,包含攻击模拟、网络带宽......
  • [63] (多校联训) A层冲刺NOIP2024模拟赛19
    lhx对\((\lnn)^{\lnn}\)求导求出一个形如\(\frac{1}{n\lnn\ln\lnn}\)的东西A.图书管理说一种很好玩的\(n^2\logn\)做法(因为动态中位数我只会这个)对顶堆:就是你开一个大根堆和一个小根堆,然后把它们怼在一起,钦定比中位数大的放小根堆,小的放大根堆,这样中间就是中位......
  • 11月7日 NOIP模拟(难题math、矩阵游戏matrix、括号序列seq、道路road) - 模拟赛记录
    PrefaceT1试图找规律失败,正经推反而几分钟就出来了。以后应该少想这些歪门邪道(除非实在闲的蛋疼或者没有一点头绪,且必须要打完所有能打的子任务比如暴力或特殊性质;而且必须在用常规方法思考过后,才能够用一些稍微不那么常规的方法)至于T2、T3、T4,因为知道T1浪费了太多时间,都是......
  • 多校 A 层冲刺 NOIP2024 模拟赛 19
    题解还是得写,不能偷懒啊~多校A层冲刺NOIP2024模拟赛19图书管理签到题考虑最困难的部分是确定中位数,不妨钦定中位数,然后计算其贡献,然后考虑只枚举一个边界,另一个边界可以放桶里。时间复杂度\(O(n^2)\)。两棵树概率期望考虑拆贡献,有等式\[连通块个数=点数-边数\]证明考虑......