搜索结果
查询Tags标签： 区间，共有 281条记录-
洛谷P3502 窗口的星星
题目链接运用扫描线的方法，每一次都用一个大小固定的小矩形去框住星星，大致过程如图所示 我们要求出小矩形最多可以框住多少颗星星，也就是求出来这个区间的最大值是多少，因为小矩形的移动过程中要维护区间最大值，所以我们可以选择用线段树去维护区间最大值，我们按…
2022/4/30 23:14:07 人评论 次浏览 -
2021 ICPC 昆明站 F - Find the Maximum 题解
题面看这里题目大意 给你一个有 \(n\) 个节点的无根树，每个节点的权值为 \(b_i\)，对于树上任意一条简单路径上的点集 \(V\)，定义它的权值为 \(\displaystyle\frac {\sum_{u\in V}(-x^2+b_ux)}{|V|}\)，其中 \(x\) 可以取任意实数，问你在树上所有的长度大于 \(1\) 的点…
2022/4/23 6:14:47 人评论 次浏览 -
java中的Random类
Random类 (java.util) Random类中实现的随机算法是伪随机，也就是有规则的随机。在进行随机时，随机算法的起源数字称为种子数(seed)，在种子数的基础上进行一定的变换，从而产生需要的随机数字。 相同种子数的Random对象，相同次数生成的随机数字是完全相同的。也…
2022/4/17 17:12:42 人评论 次浏览 -
「JOISC 2022 Day4」鱼 2
考虑怎么样的鱼能取得最后的胜利，它一定是不断贪心地往两边吃，能吃就吃。 实现以上过程的一个朴素想法是，对左右两边分别维护”有效“单调栈，暴力扫一遍。 考虑用线段树维护上述过程，思考如何合并区间信息。 假设有 \(x\) 条鱼能在左子树中吃完所有的鱼，那么加入右区…
2022/4/15 23:18:00 人评论 次浏览 -
数据结构和算法 - 树状数组
树状数组 1. 问题序号 题目—— ——————————————————————————————————————————————————————307. 区域和检索 - 数组可修改493. 翻转对HDU P1166 敌兵布阵给定一个数组\(A\)，长度为\(n\)，数组的下标范围是\([0,n-1…
2022/4/5 1:19:28 人评论 次浏览 -
从有限覆盖定理到闭区间的一致连续
用类似于“有限覆盖定理的应用之一”的方法 记L(x)=supz,y∈U(x,δ(x));z≠y{|f(z)-f(y)|/|z-y|}, 由有限覆盖定理就得到δ(xi)的最小值δmin然后就用δmin 为间隔分割区间，再由局部有界得其在所有距离为2δmin 的区间都有界，则推出全局有界
2022/4/3 6:23:22 人评论 次浏览 -
贪心算法之区间问题详解
目录 1.贪心算法简介 基本思想 局限性 2.经典例题 区间问题 贪心策略 3.代码1.贪心算法简介 基本思想 1）贪婪算法（贪心算法）是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最优的算法。 2）贪婪算法所得…
2022/3/19 17:27:37 人评论 次浏览 -
dls的区间dp
区间dp ICPC Beijing 2017 J, Pangu and Stones 题目链接：http://oj.daimayuan.top/course/8/problem/327 题目大意：有n堆石子，每对有ai个，每次可以合并[L, R]堆石子，代价是这些石子的之和f[l][r][k]:表示将l,r合并成k堆的最小代价 划分方式：根据最后一顿划分的分界…
2022/3/11 23:18:47 人评论 次浏览 -
【记录】妙妙题
新坑。 arc136 e \(1\) 到 \(n\) 的数，如果两个数不互质则从小到大连有向边，点带权，求一个权最大点集使没有互相可达的点。sol 首先把 $1$ 选掉，考虑两个数 $x,y$ 互相可达的条件：\(x\equiv 0,y\equiv 0\) 一定可达。 \(x\equiv 1,y\equiv 0\) 则 \(x+minprime_x \le…
2022/3/4 23:45:22 人评论 次浏览 -
2022.3.1#差分与前缀和思想
差分： 给出n个数，再给出Q个询问，每个询问给出l，r，x，要求你在l到r上每一个值都加上x，而只给你O(n)的时间范围，怎么办？ Xenny大佬的树状数组详解 - Xenny - 博客园 (cnblogs.com)里利用一个差分值构建的树状数组，可以用来进行区间更新，单点查询。 差分的特点是区…
2022/3/1 6:23:17 人评论 次浏览 -
算法题：使得随机数出现0~X之间的概率从X变为X平方
1、先证明随机数出现0~X的概率是Xpublic static void main(String[] args) {for (int i = 1; i < 10; i++) {test(i / 10d);}}public static void test(double x) {int count = 0;int size = 10000;for (int i = 0; i < size; i++) {if (Math.random() <= x) {co…
2022/2/28 11:22:59 人评论 次浏览 -
区间选点（贪心）
说句题外话：今天2.27，立志在3.5号把基础课的贪心，dp看完，3.15号把数据结构和数学看完，然后看搜索！hhh，加油 给定 NN 个闭区间 [ai,bi][ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算…
2022/2/28 6:26:25 人评论 次浏览 -
[模板题]
一. 倍增（1）区间最值 RMQ 问题（Range Minimum/Maximum Query，区间最值问题）：给定长度为 n 的静态数列，做 m次询问，每次给定 【L,R】，查询区间[L, R]内的最值。 ST 算法两个步骤：把整个数列分为很多小区间，并提前计算出每个小区间的最值；对任意一个区间最值查询…
2022/2/28 6:25:58 人评论 次浏览 -
2022.2.25#倍增思想和ST表
倍增：将线性级转换成对数级，降低时间复杂度 只考虑二的整数幂次，缩小查询范围。 运用： 1.快速幂：算n的m次方，log(n) 递推法：int ans = 1; while (n) {if (n & 1)ans *= a;a *= a;n >>= 1; }2.RMQ问题：n个数字m次询问，每次[l,r]中最大值 运用ST表，预处…
2022/2/26 6:22:38 人评论 次浏览 -
【题解】自建题目题解
主要是可能想到一些垃圾题目，一般都放在洛谷私人题库里。 有做法的题目的题解都在下面了，没做法的题目建议您想一想做法。（ U204881 跨越做法 1 正式而卤蛋 巨佬提供！ 是区间到区间的询问。可以看作最后要求对于所有左端点有多少个右端点是合法的。把一个询问右边的区…
2022/2/24 23:29:27 人评论 次浏览
