-符拉迪沃斯托克-

题解

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

/ 注册

全部文章 / 题解（共26篇）

二分

题意是求裁判最多说对了几次。对于每次猜数，如果猜的数是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

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

[JLOI2015]装备购买

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

线性基高斯消元

2021-08-20

0 496

无效位置

如果没有修改，这个题就是个线性基板子题对吧。再看加上修改之后怎么整。我们发现，对于任意一种已经确定数字的情况，只要线性基建好了，答案可以搞出来。那么问题就是怎么动态维护线性基。啥？动态维护？？不存在的！我才不告诉你我不会写那玩意因为只有删除操作，所以顺序颠倒就是一个一个加入数字。也就是离...

并查集线性基

2021-08-20

0 425

[CQOI2013]新NIM游戏

先看原来的游戏先手必胜条件：所有值的异或和不为零。带回到本体，也就是两个回合之后，所有值的异或和不为零。那么我们就不能让对方从我方已经取完的情况下还能把情况变成异或和为零。怎么做？等会儿，这不就是一线性基么？只要线性基插满了，或者有个值插不下就行（进不去，怎么想都进不去。。。）先把线性基...

线性基贪心

2021-08-20

0 448