OI 第5页

努力向前, 永不言弃.

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

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

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

[洛谷P3865]【模板】ST表

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

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

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

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

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

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

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

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

[POJ1845]Sumdiv[约数,逆元]

cgazn阅读(692)评论(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^...

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

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

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

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

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

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

异或运算实现成对变换

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

规律:对于自然数n,若n为偶数,则n^1=n+1;若n为奇数,则n^1=n-1 因此 0与1 2与3 4与5 ……^1可构成成对变换 应用:邻接表存图,把每条边及其反向边放在从2开始的连续位置,则有 若e[i].t为边i的终点,则其反向边为...

memset()用法小结

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

void * memset ( void * ptr, int value, size_t num ); Fill block of memory Sets the first num bytes of the block of memor...