首页 > Minimizing maximizer
开通博客写题解
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-29 20:07:10
Minimizing maximizer 题目大意 有一条长度为的线段，然后会按照顺序给你条线段（固定起点终点）问，你按照顺序使用这条线段，最少要多少条才能把整条线段覆盖完但是题目有一个条件，大概就是这条线段至少与之前的覆盖的线段有一个交点 分析 那么这样的话，就可以设计动态转移方程表示从开始覆盖到 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-29 20:30:51
吐槽 看这道题的时候，由于英语太菜读题读了好久都没读懂依据暂时的理解打了一个程序之后发现一直WA最后在玄学注释（去掉排序）程序的时候，居然A了。。。之后在机房英语巨佬シンドリー的帮助下才懂得了题意。。。 分析 不太懂题意的，可以看看这位巨佬的Blog一眼题？（以前在Atcoder上边好像做过类似的题 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 林思艺
发表于 2020-09-29 20:42:27
写在前面的话 蒟蒻流下了不学无术的眼泪，英语不好是真的硬伤，蒟蒻在巨佬的提示下才勉强明白了题意 题意 你有条按顺序（很重要！）给出的线段，要求你使用最少的线段覆盖。另外在你选择一条线段时你必须保证你的前置线段已全部被覆盖。 思路 我们可以定义为前个排序器将第个数提到所需要的最少的排序器的数量，那么当 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 __故人__
发表于 2020-09-29 21:04:33
分析 对于这类问题，我们先观察是否有什么性质。由于我们要求 的所有数最后都可以到达 。而 在行动时候会经过 的所有节点。那么我们的问题就随之转换为， 到 最少要经过几个区间。那么我们可以先考虑 。令 为考虑到前 个机器，当前点为 的最小步数。那么我们就有两个转移 和 。那么这 展开全文
去ta的博客 赞 (4) 回复(3) 收起
头像 Kur1su
发表于 2020-10-01 11:59:48
Description The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input repre 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 熠丶
发表于 2020-10-01 00:37:30
做法：线段树优化dp 思路： dp[i]表示覆盖[1,i]需要的最少区间数。然后用线段树更新取最小值。dp[t]=min(dp[t],min(dp[s]~dp[t])+1) 代码 #include <iostream> #include <cstdio> #include & 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 呱呱咕
发表于 2020-10-05 22:48:53
题意：N个排序器，每个可以把第l个数到第r个数这个区间里面的数从小到大排序，这些排序器按顺序运行，最后一个排序器运行完第n个数为第n小（最大数）。这些排序器去掉若干个也可以完成任务，问最少要留下几个，才能使留下的排序器依次运行使得对于任何输入最后一个排序器输出的最后一个数字为最大数。（题意看的一个犇 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 rk_no
发表于 2020-10-07 10:21:04
题目： 给一个长为的，落在上的区间序列，问最短的子序列，相邻区间有交集，连续覆盖上所有点。。 做法： 线段树上每个叶子表示上的一个点，维护当前延伸到需要的最短区间序列长度。一开始设结点1为0，其他点为。每次读入一个区间，左端点，即用已有的区间延伸到所需的最短区间序列长度，设为。然后用，线段树上区间 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-10-01 15:38:47
题意 给你个区间 选出最少长度的序列,满足按序列顺序操作,每次对 的元素进行排序 最后在位置的数需要是最大的数(你必须保证对于任意的元素顺序,都满足这点) 分析 非常经典的题 很容易想到当最大的数在位置时如果都能满足条件,任意情况都能满足条件 于是定义表示当前覆盖了的最小区间个数 转移从里找最小值就 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”