-符拉迪沃斯托克-

分类

算法(1) 赛后补题(4) 题解(26)

/ 注册

全部文章（共31篇）

二分

题意是求裁判最多说对了几次。对于每次猜数，如果猜的数是aaa，那么根据题目有三种情况：数大了：说对的范围是(−inf⁡,a](-\inf,a](−inf,a] 数小了：说对的范围是[a,+inf⁡)[a,+\inf)[a,+inf) 数相等：说对的范围是[a,a+1)[a,a+1)[...

离散化差分

2022-07-15

2 414

货仓选址

如果是个明眼人，可以看出来选中位数一定是最优解，此时答案一定是后一半的和减去前一半的和，即∑i=1n/2(vn−i+1−vi)\sum_{i=1}^{{n}/{2}}(v_{n-i+1}-v_i)∑i=1n/2(vn−i+1−vi)。但是像我这样的大制杖就只能硬证。。。我们求的是： min...

排序

2022-07-15

2 464

[CQOI2009]中位数图

一个朴素的想法是把大于bbb的数规约成111，小于bbb的数规约成−1-1−1，那么中位数为bbb就是区间的所有1,−1,01,-1,01,−1,0的和为000。而给出的数列是一个排列，那么bbb只有唯一的位置，从这个位置向两边求和，就可以找出题目要求的区间。于是整个区间的和就变成了suml+0...

前缀和

2022-07-15

0 327

Codeforces 718C - Sasha and Array

题意维护一个数列，支持区间加，以及区间斐波那契数列数列求和，即∑i=lrf(ai)\sum_{i=l}^rf(a_i)∑i=lrf(ai)。解法首先把f(ai)f(a_i)f(ai)拆成矩阵的幂次形式： f(ai)=[f(0),f(1)]×[0111](ai−1)f(a_i)=[f(0)...

线段树矩阵快速幂

2022-07-11

0 310

洛谷P4592 [TJOI2018] 异或

树上路径与子树最大异或和问题。。。想都不想一个树链剖分上去，变成序列问题。区间最大异或和。。。这不板子么？又是一个可持久化TrieTrieTrie丢上去。这个题就搞完了。复杂度O(32×n2(n))O(32\times n\log_2(n))O(32×nlog2(n))，稳的不行。（按...

树链剖分可持久化Trie树

2022-02-25

0 360

2022 BUAA Winter Training 1赛后补题

2022 BUAA Winter Training 1 A − Interesting Subarray\Large{A\ -\ Interesting\ Subarray}A − Interesting Subarray [ C...

2022-01-18

0 297

CodeForces 1626C - Monsters And Spells

题意有nnn个怪物，每只怪物的出现时间是kik_iki，血量是hih_ihi。魔法师可以从111点伤害开始施加魔法，每次伤害之后可以增加一点伤害，但如果不施法，下一次施法伤害会重新从111点伤害开始累计。问最少需要的魔法值总和。解法水题一发。把每只怪物当成线段，需要开始从111开始施法累...

动态规划线段覆盖

2022-01-17

0 604

洛谷P7577 「PMOI-3」简单模拟题

看到题目中一个求和我人就蒙了。。。这啥啊这是？？裸的暴力O(qn2)O(qn^2)O(qn2)，铁定TLETLETLE。。。得，照惯例先把里面的玩意拽出来搞事。首先要解决的是怎么在线计算F(l,r)F(l,r)F(l,r)，显然这个题我们不能用莫队了对吧。。。于是拿出主席树来维护。对于每...

二分查找主席树单调性

2021-10-10

0 507

线性基学习笔记

首先看一道题：洛谷 P3812 【模板】线性基题目名称已经说明了算法是什么，毕竟是一道模板题对吧。。。线性基是什么？哈？学过线性代数或者高斯消元的都应该知道吧。。。不知道的左转出门自行百度。。。或者参考这两篇博客： P3812 【【模板】线性基】线性基学习笔记在竞赛中，提到线性基...

算法线性基

2021-08-23

0 575

[JLOI2015]装备购买

真真正正的线性基。。。上过大一线代的都应该知道，没上过的学过高斯消元或者异或线性基也应该知道。。。第一反应高斯消元，消到最后就是秩。但是那个最优解有点难搞。于是从小到大排个序，依次加入线性基中，还没插满并且插不进去的就是选中的答案。所以为什么我的代码要开才能过啊。。。算了，过了就行附代...

线性基高斯消元

2021-08-20

0 496