CGaZn的博客CGaZn的博客

置顶

  • 置顶  世界,您好!
  • 置顶  AFO
  • 最新发布 第7页

    OI

    [POJ3784]Running Median[堆]

    cgazn阅读(367)评论(0)赞(1)

    题面 题目要求动态维护中位数, 每当序列长为奇数时输出(也就是输出第i/2+1小的数). 设当前序列长为i, 我们把整个序列按升序分为第1~i/2小, 第i/2+1小两部分. 资瓷动态插入并维持有序的数据结构容易想到堆. 对左半边和右半边分...

    OI

    [POJ2018][洛谷P1404]平均数/Best Cow Fences[二分答案]

    cgazn阅读(720)评论(0)赞(0)

    题面 题目求平均数最大的子段, 有长度下限m. 转化为答案判定, 就是对于给定的平均数aver, 能否找到一个长度不小于m的满足平均数不小于aver的子段. 把整个数组减去aver, 就变成了判断有没有和为非负的子段. 若有非负子段, 则a...

    OI

    [洛谷P3865]【模板】ST表

    cgazn阅读(352)评论(0)赞(0)

    复习板子. 远古代码概不负责. ST表基于二进制划分思想, 用于求静态RMQ, $latex O(N\log N)$预处理, $latex O(1)$查询. 设$latex max[i][j]$表示区间$latex [i,i+2^j-1]$...

    OI

    [洛谷P3384]【模板】树链剖分

    cgazn阅读(326)评论(0)赞(0)

    复习板子. 树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等. 树剖的思路其实不难, 主要是代码长… 考虑如何把一棵树通过编号处理成...

    OI

    [洛谷P1462]通往奥格瑞玛的道路[二分答案]

    cgazn阅读(477)评论(0)赞(0)

    这道题要求最大收费点的最小值,明显是二分答案 二分check(maxf)函数目标:判断能否在 最大收费点小于maxf 的条件下,走到终点 能则缩小maxf, 否则只能是更大的maxf 具体实现: dijkstra松弛的时候加个判断 点权小于...

    OI

    [POJ1845]Sumdiv[约数,逆元]

    cgazn阅读(528)评论(0)赞(0)

    题面 算数基本定理的推论: 正整数N被唯一分解为$latex p_1^{c_1}*p_2^{c_2}*…*p_m^{c_m}$的所有约数的和为$latex \prod_{i=1}^{m}(\sum_{j=0}^{c_i}p_i^...

    奇技淫巧

    2019.6救活被ban的IP

    cgazn阅读(1025)评论(1)赞(0)

    连开一二十台服务器全都被ban了ip, 找到一个用websocket+tls+nginx+cdn救活ip的办法, 尝试一下. 垃圾vultr取消了3.5$的服务器, 现在只能用5$的了 原理: 通过位于国外的cdn节点转发fq流量, 共经过...

    OI

    [洛谷P1262]间谍网络[tarjan缩点]

    cgazn阅读(632)评论(0)赞(0)

    题面 tarjan缩点模板题 tj的思路: 强连通分量可以相互到达, 必定在一个环上, 一次dfs找出所有尽量大的环即可. sta里面是表示当前所有可能能构成强连通分量的点, 追溯值low[x]表示点x及其子孙节点连的所有点中dfn的最小值...

    OI

    [POJ2299]Ultra-QuickSort[逆序对,归并排序]

    cgazn阅读(1127)评论(0)赞(0)

    题面 题目求冒泡排序的最小交换次数.冒泡排序交换一次即减少一个逆序对,所以总交换次数就是逆序对数.用归并排序求出即可. 求逆序对通常用归并排序(树状数组也可以), 统计在两区间合并的过程中产生的逆序对就可以算上所有的逆序对, 因为归并排序实...