Chrety

算法

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 详尽的思路(1) 题解(1)

/ 注册

全部文章 / 算法（共13篇）

P3028 汽水机(差分)

题目 P3028 [USACO10OCT]汽水机Soda Machine 解析差分，看到\(a[i]\leq 1e9\)，离散化一下，在\(l\)处\(+1\)，\(r+1\)处\(-1\)，这样就只有\(2n\)个点了，再按位置排一下序，扫一遍记录答案就可以了。需要注意的是，如果在某个位...

差分离散化

2019-10-28

0 619

poj3045 Cow Acrobats (思维，贪心)

题目： poj3045 Cow Acrobats 解析：贪心题，类似于国王游戏考虑两个相邻的牛\(i\),\(j\) 设他们上面的牛的重量一共为\(sum\) 把\(i\)放在上面，危险值分别为\(x_1=sum-s_i\),$ x_2=sum+w_i-s_j$ 把\(j\)放在上面，危险...

贪心

2019-10-11

0 595

loj#10012\poj2018 Best Cow Fences(二分)

题目 #10012 「一本通 1.2 例 2」Best Cow Fences 解析有序列\(\{a_i\}\)，设\([l,r]\)上的平均值为\(\bar{x}\)，有\(\sum_{i=l}^r(a_i-\bar{x})=0\) 这样我们就可以通过二分平均值，先同减二分到的平均值，若存...

二分

2019-07-23

0 613

loj#10013 曲线(三分)

题目 #10013. 「一本通 1.2 例 3」曲线解析首先这个题保证了所有的二次函数都是下凸的， \(F(x)=max\{s_i(x)\}i=1...n\)在每一个x上对应的最大的y，我们最后得到的还是一个凸函数这个题比较特殊的一点是函数可能退化为一次，但退化为一次后的函数还是凸函数...

三分

2019-07-23

0 523

bzoj2654: tree(最小生成树+二分)

题目 bzoj2654: tree 解析 kruscal在做最小生成树时先按权值排序，权值小的先被选到，我们可以通过控制白色边的边权来控制白色边的数量。我们可以通过二分答案来给白边加某一个值同时注意两点不要忘记减去给白边加的值排序时白边优先代码 #include ...

kruscal 最小生成树二分

2019-07-21

0 681

P1462 通往奥格瑞玛的道路 (二分+最短路)

题目 P1462 通往奥格瑞玛的道路给定\(n\)个点\(m\)条边，每个点上都有点权\(f[i]\)，每条边上有边权，找一条道路，使边权和小于给定的数\(b\)，并使最大点权最小。解析二分一下钱，然后跑最短路，判断一下如果只有这么多钱的话能不能到终点（最短路边权和是不是不超过\(b\)...

二分最短路算法

2019-04-27

0 751

P3709 大爷的字符串题 (莫队)

题目 P3709 大爷的字符串题题意：求\([l,r]\)中众数的个数。解析维护两个数组： \(cnt[x]\)，数\(x\)出现的次数。 \(sum[x]\)，出现次数为\(x\)的数的个数。考虑往里添加元素时，直接取\(max\)；删除元素时，如果这个数是众数(...

莫队算法

2019-04-16

0 451

P4137 Rmq Problem / mex (莫队)

题目 P4137 Rmq Problem / mex 解析莫队算法维护mex，往里添加数的时候，若添加的数等于\(mex\)，\(mex\)就不能等于这个值了，就从这个数开始枚举找\(mex\)；若不等于\(mex\)，没有影响，因为它之前的所有数都出现过了，又出现一次不会怎样，放...

莫队算法

2019-04-16

0 545

HDU 1757 A Simple Math Problem (矩阵快速幂)

题目 A Simple Math Problem 解析矩阵快速幂模板题构造矩阵 \[\begin{bmatrix}a_0&a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9\\ 1&0&am...

数学矩阵矩阵快速幂算法

2019-04-13

0 639

P1494 [国家集训队]小Z的袜子

题目 P1494 [国家集训队]小Z的袜子解析在区间\([l,r]\)内，任选两只袜子，有 \[r-l+1\choose2\] \[=\frac{(r-l+1)!}{2!(r-l-1)!}\] \[=\frac{(r-l+1)(r-l)}{2}\] 种选择。对于一种颜***r...

莫队算法

2019-03-27

0 530