bzoj3437: 小P的牧场

in 代码 read (52)

题目大意:一行有 $n$ 个牧场,每个牧场建造控制站要 $a_i$ 的代价,若没有建控制站,则需要 $b_i\times 往右到最近的控制站的距离$ 的代价,问最小总代价。解题思路:我们设两个 $b_i$ 前缀和,方便计算一段牧场到某一控制站的代价:$$S_i = \sum...

继续阅读

切比雪夫距离

in 代码 read (58)

在此之前我们已经懂得了两种距离的定义。欧几里得距离:$$dist(A,B)= \sqrt(A.x-B.x)^2+(A.y-B.y)^2$$曼哈顿距离:$$dist(A,B)=|A.x-B.x|+|A.y-B.y|$$现在我们定义一个切比雪夫距离:$$dist(A,B)=ma...

继续阅读

NOIP2015普及组解题报告

in 代码 read (68)

1.金币1.1 100分算法对于$100\%$的数据,有:$K \le 10000$,直接模拟即可。复杂度:$O(K)$1.2 总结签到题,主要考察选手是否会编写程序。2.扫雷游戏2.1 100分算法对于$100\%$的数据,有:$n\le100,m\le100$,直...

继续阅读

HDU 1540 - Tunnel Warfare

in 代码 read (43)

题目大意:给定一个长为n的01序列,我们用0表示不可走,1表示可走,实现三种操作:第一种:$(Q, x)$询问从某个点开始,向其左右最多可以扩展多宽,即询问包含这一位置的最长的全1序列是多长;第二种:$(D, x)$将某一个点的状态改成0;第三种:$(R)$将最近一次被修改...

继续阅读

HDU 3911 - Black And White

in 代码 read (65)

题目大意:给你一个长为n的01序列,实现两种操作:$(0,l,r)$,询问区间$[l,r]$中连续的全1序列的最长长度;$(1,l,r)$,将区间$[l,r]$中每个数取反,即异或1。$(n,m\le10^5)$解题思路:实际上,这就是一道线段树的区间合并问题,每个节点维护...

继续阅读

核糖核酸

再见,OI,我爱你,OI