25 关于区间内的子区间查询问题的探究

陈小白     2022.10.25     算法相关     抢沙发     61人打酱油
这是一类什么问题,在一个区间内要想求得某个区间,你需要什么样的复杂度? n*(n-1)/2?你需要暴力出所有的情况。 能否找到一个方法使得我们所得到的满足子区间是最优的且一定使我们想要的? 这里存在两种方法:尺取法(两个指针)和二分。 那么先来说说尺取和二分,尺取是固定一边去寻找另一...

15 Codeforces Round #827 (Div. 4) A-G

陈小白     2022.10.15     算法相关     抢沙发     130人打酱油
比赛链接:https://codeforces.ml/contest/1742 A题:水题 B题:水题 C题:思维+审题。大意是给出一个8*8的矩阵,每次操作可以画一行红色或者是一列蓝色,每次绘制可以覆盖之前的颜色。求出最后画的是哪一笔?题目保证给出一个正确解。 这...

18 C. Schedule Management

陈小白     2022.09.18     算法相关     抢沙发     50人打酱油
题目链接:https://codeforc.es/contest/1701/problem/C 一个青名题。二分类型 大意是,给出n个人编号1-n,然后给出m个任务,每个任务a[i]对应一个值,这个值在1-n内,含义是a[i]这个人做这个任务时擅长的。 如果一个人去做他擅长的任...

26 P1258 小车问题 (二分逼近)

陈小白     2022.07.26     算法相关     抢沙发     97人打酱油
题目链接:https://www.luogu.com.cn/problem/P1258 大意是给出两个城市的距离,给出人行走速度和车辆行驶速度,有两个人需要同时从一个城市到达另一个城市。车上除了司机之外只能做一个人,问最快两人多长时间能够同时达到目的地。 这个题可以用公式法推导...

26 cf C. Doremy's IQ

陈小白     2022.07.26     算法相关     抢沙发     90人打酱油
题目链接:https://codeforc.es/contest/1708/problem/C 一道比较标准的蓝题难度,用到了二分 大意是:给出n个任务的难度,智商为q。如果任务难度>q,那么q会减少1,如果不做这个任务,智商不变,求最多能做出的任务的状态。 也就是做这个...

15 P1024 [NOIP2001 提高组] 一元三次方程求解

陈小白     2022.07.15     算法相关     抢沙发     75人打酱油
题目链接:https://www.luogu.com.cn/problem/P1024 大意就是给出一个一元三次方程abcd,保证有三个解且解在-100-100之间 然后求出这三个解 这是一个二分的题,不过涉及到一些数学问题。 ,,,如果将x代入后的两个方程表达式异...

23 cf E. Binary Deque

陈小白     2022.06.23     算法相关     抢沙发     90人打酱油
题目链接:https://codeforces.com/problemset/problem/1692/E 前缀和+二分或双向队列双指针 大意:输入n个数,只包含0和1,输入一个数s。sum为数列的和,每次操作可以删除第一个数或最后一个数,最后求最少通过几次这样的操作可以使得s...

05 最大子段和 三种解法 :分治、贪心、dp

陈小白     2022.04.05     算法相关     抢沙发     143人打酱油
题目链接:https://www.luogu.com.cn/problem/P1115 如题,先分析复杂度。n的范围是2*10^5,对应之前总结的复杂度问题,nlogn可以解决10^5,这个题能解决一半 从而这个题只能考虑n线性计算的复杂度,这里贪心算法和一维dp可以解决,两个...