首页 > 其他分享 >NOIP模拟赛 #10

NOIP模拟赛 #10

时间:2024-11-12 20:20:41浏览次数:1  
标签:10 优惠券 NOIP min mid 商品 le 模拟

A

Luogu6472

猜结论。

B

有 \(n\) 堆硬币,每堆有 \(3\) 枚,第 \(i\) 堆硬币从上到下价值分别为 \(a_i, b_i, a_i\)。取若干个硬币,要求每堆必须先取上面再取下面,求分别取 \(1, 2, 3, \dots, k\) 枚硬币时的最大价值和。

\(1\le n\le 5\times 10^6, \ 1\le k\le 3n\)

对于第 \(i\) 堆,可以转化为一个价值为 \(a_i\) 的物品,体积为 \(1\),以及一个价值为 \(a_i + b_i\) 的物品,体积为 \(2\),发现所有组合情况恰好对应这堆硬币取 \(0, 1, 2, 3\) 枚时的价值。

所以我们只需要对体积为 \(1\) 或 \(2\) 的一些物品进行背包,求出体积之和恰好为 \(1, 2, 3, \dots, k\) 时的答案。考虑钦定只取体积为 \(1\) 的物品,反悔取体积为 \(2\) 的物品即可。

C

给定一个由至多 \(10\) 种小写字母组成的字符串,多次询问,求一个一个区间内本质不同子序列数量,答案模 \(10^9 + 7\)。

\(1\le n, q\le 5\times 10^5\)

考虑猫树分治。对于一个子序列,在原串中匹配该子序列,映射到最小表示上。

对于一个分治节点 \((l, r, mid)\),对于一个询问 \([l_q, r_q]\) 满足 \(l\le l_q\le mid < r_q\le r\),若只用匹配 \([l_q, mid]\) 匹配是容易的。否则考虑枚举 \([mid + 1, r_q]\) 匹配的第一个字符 \(c\),对于 \(l\le i\le mid\) 设 \(f_{i, c}\) 表示从匹配到了第 \(i\) 位,在左半部分后续匹配且 \([\text{左半部分最后一个匹配位置} + 1, mid]\) 中没有字符 \(c\) 的方案数,对于 \(mid + 1\le i\le r\) 设 \(g_{i, c}\) 右半部分开头匹配到了位置 \(i\) 且第一个匹配的字符是 \(c\) 的方案数,那么对答案的贡献为 \(f_{l_q - 1, c}\sum_{i = mid + 1} ^ r g_{i, c}\)。

对于 \(f, g\),可以直接差分 / 前缀和优化求出,时间复杂度 \(\mathcal O(10n\log n)\)。

D

你需要依次 \(n\) 件商品,第 \(i\) 件商品需要花费 \(a_i\) 个金币。你可以使用一张优惠券代替一枚金币,买商品 \(i\) 使用的优惠券数量应不超过 \(b_i\)。初始时你有 \(m\) 张优惠券,当你买商品 \(i\) 时使用了 \(x\) 张优惠券,则购买后可以获得 \(\dfrac {a_i - x} c\) 张优惠券,\(c\) 为给定常数,求使用的最少金币总数。

\(1\le n\le 10^6, \ 0\le m, a_i, b_i\le 10^9, \ 2\le c\le 10^9\)

考虑商品 \(i\) 该如何合理使用优惠券:

  • 首先使用 \([0, a_i \bmod c]\) 张优惠券,此时不影响获得的优惠券数量,性价比最高。

  • 接着使用 \(k \cdot c\) 张优惠券,会损失 \(k\) 张优惠券的获得。

  • 最后使用 \([0, c - 1]\) 张优惠券,会损失 \(1\) 张优惠券的获得。

不难发现三种方式有着严格的优先级。先处理第一种方式,设 \(x_i\) 为商品 \(i\) 使用的优惠券数量,设 \(s_i\) 为买完商品 \(1\sim i\) 后剩下的优惠券数量,那么 \(x_i = \min(s_{i - 1}, b_i, a_i \bmod c)\)。

然后是第二种,不难发现对应的商品越靠后越好,考虑从后往前处理,则 \(x_i \gets x_i + c \cdot \min \left(\left \lfloor \dfrac {b_i - x_i} c \right \rfloor, \left \lfloor \dfrac {s_{i - 1} - x_i} c \right \rfloor, \min_{j = i + 1} ^ n \left \{ \left \lfloor \dfrac {s_{j - 1} - x_j} {c + 1} \right \rfloor \right \} \right)\),第三者可以通过维护后缀 \(\min\) 解决。

最后是第三种方式,不难发现操作的商品数量越少越好,可以优先操作可使用优惠券数量尽量多的商品。商品 \(i\) 可使用的优惠券数量为 \(\min(b_i - x_i, s_{i - 1} - x_i, \min_{j = i + 1} ^ n \{ s_{j - 1} - x_j - 1 \})\)。设 \(t_i = s_{i - 1} - x_i\),则原式为 \(\min(b_i - x_i, t_i, \min_{j = i + 1} ^ n \{ t_j - 1 \})\)。

一种暴力的方法是从大到小枚举单个商品使用优惠券数为 \(w\),然后检查每个商品是否可以操作。注意到 \(\min(t_i, \min_{j = i + 1} ^ n \{ t_j - 1 \})\) 随着 \(i\) 变大而变大,只需要注意 \(b_i - x_i\) 即可。

考虑所有商品按照 \(b_i - x_i\) 从大到小依次加入,设当前商品和下一个商品的 \(b_i - x_i\) 分别为 \(p, q\),可以处理掉 \(w \in [q + 1, p]\)。维护一个堆维护合法的位置 \(i\) 的集合,每次取出最大的合法位置,检查是否满足条件,查询可以使用线段树维护 \(t\) 的区间最小值,以及支持区间加。

  • 启示:贪心,分层,分逻辑。

标签:10,优惠券,NOIP,min,mid,商品,le,模拟
From: https://www.cnblogs.com/Sktn0089/p/18542579

相关文章

  • 一觉睡醒,全世界计算机水平下降100倍,而我却精通C语言——变量
    大家好啊,我是小象٩(๑òωó๑)۶我的博客:XiaoFeiXiangζั͡ޓއއ很高兴见到大家,希望能够和大家一起交流学习,共同进步。*这一节我们来学习变量相关的知识,学习变量的创建和分类,学习并熟悉算术操作符,赋值操作符,单双目操作符的使用,并了解强制类型转换文章目录......
  • [考试记录] 2024.11.12 noip模拟赛11
    T1使用\(bfs\)记录走到\(tx,ty\)的路径的横边和竖边的数量,然后取\(\max\)。这里取\(\max\)的原因是,找到的路径必须是最短路,当\(k\)取的小的时候竖边就会变多,所以这条路径就不一定是最短路了。#include<bits/stdc++.h>usingnamespacestd;#defineppair<int,int>i......
  • 20241112 模拟赛总结
    期望得分:100+100+0+10=210实际得分:100+80+0+10=190好困。。T1被硬控了很久。看着就像诈骗题,观察大样例发,答案就是\(a_1-a_2\),特判\(n=1\)的情况。证明的话,感觉就是后面的数,贡献成正数和负数应该是数量相同的,所以就抵消了,第一个数只能贡献成正数,第二个数只能贡献成负的。T......
  • Linux(10)——监控和管理Linux进程
    目录一、进程:1、定义:2、环境:3、状态:4、查看进程状态:二、控制作业:1、jobs命令:2、在后台运行作业:三、中断进程:1、signals:2、kill命令:3、pkill命令:4、管理员注销用户:四、平均负载值:1、uptime:2、lscpu:一、进程:1、定义:        进程是已启动的可......
  • 在通讯领域,特别是在自由空间光通信(Free Space Optics, FSO)通道模拟中,选择合适的模型需
    在通讯领域,特别是在自由空间光通信(FreeSpaceOptics,FSO)通道模拟中,选择合适的模型需要考虑模型对动态变化的光信号传播环境的适应性和预测能力。根据搜索结果,以下是一些可能适合通讯领域FSO通道模拟的模型:TACTiS-2:这是一个灵活的多变量概率时间序列预测模型,它简化了attenti......
  • 20241103
    待看1.https://blog.csdn.net/m0_62825058/article/details/137987431针对图形推理:三级判断模式+大量题库两者缺一不可。三级判断模式:1、专题类型,每一种类型的已有考法,已经可以覆盖大部分。(背后的思想是出题人出题形式的惯性)2、点,线、图、面、角,最小的元素,传统的那张图......
  • 麒麟V10系统安装jdk
    1.在/usr目录下建立java安装目录#cdusr#mkdirjava 2.将jdk-8文件包文件上传,并放给到该目录下scp/Users/xxx/[email protected]:/usr/java 3.在当前目录解压jdk-8文件包tar-zxvfbellsoft-jdk8u412+9-linux-aarch64.tar......
  • 2024.11.12 NOIP模拟 - 模拟赛记录
    Preface一套烂题。T1一眼搬的CF(赛后十秒就找到原题了),只搬idea就算了,根本不设置部分分,大样例给的更是一坨(数据范围给的\(10^{15}\),121072121算什么大样例?),甚至最后的题解都是直接复制的洛谷。T2稍好,除了实数运算稍微恶心一点,其它都没什么。T3又是一大坨,不给SPJ都......
  • 20241112【NOIP】模拟
    如果上一场是本来都会做,但是因为题没读清楚和智障错误导致挂分后排名低,那么这一场就是纯纯脑瘫,以为题会很难,一点都没有深入思考过,结果暴力一分没挂,但是别人T1T2T3都切了,最后成了小丑......
  • CF1006
    前言失而复得最开心力!!!这场AK力(可能是因为第一条)题目难度:红黄黄绿绿蓝正文A偶数-1,奇数不变B直接排个序,取前K大的就行C直接用双指针扫一遍即可D发现上下对面四个是绑定的,所以只需让上下左右四个有两对一样的即可E发现(由树剖得)一颗子树的dfn序是连续的于是就记一下d......