关于BIT。。。

二叉索引树(Binary Indexed Tree 或 Fenwick Tree, BIT),俗称树状数组,是一种十分精妙的数据结构。
先上图:
无标题.png
*就是它*
至于它的含义,就是:每个点代表一段区间所包含的信息(sum, min, max, etc.),这段区间的长度取决于当前节点编号的lowbit,也就是二进制下最低的不为零的一位。因为数字再计算机中用补码存储,所以可以很方便的求出lowbit(i) : i & -i。
若要求一段区间*的信息怎么办?
由这段区间的最后一个节点开始,每次向前“跳”lowbit个位置,直到1。
更新?
由这段区间的第一个节点开始每次向后“跳”lowbit个位置,直到n。
*注:此处的区间指的是[1, x]
所谓“单点修改,区间查询”
那么“区间修改,单点查询”呢?
加上差分乱搞一番就好了
重点来了
如果我想要实现“区间修改,区间查询”怎么办?
线段树? 太难写(对于我这种蒟蒻),常数大,空间大。
所以可以糊一个公式。
首先,由一个差分的数组(序列)di
原数组中的an即为
1 (2) (1).png
然后呢,原数组的前缀和即可以表示为
1.gif
(推导过程自己看)
所以,我们只需要两个BIT,一个存,另一个存1 (1),再带入上述公式…稳了!
PS:jxc大佬(%%%)说,用BIT是无法代替线段树的。所以还是要用又长又烦的线段树辣。

NOIP2017训练总结

 

这几日成绩都不怎么样很差,至于有多差。。。反正还不至于爆零

好吧,现在就来分析一下为什么。

  1. too young,写程序太慢,最后暴力都来不及写(而且这几次仿佛数据特别水,暴力总是出奇迹)
  2. too simple,每次糊到贪心都会出偏差;
  3. sometimes naive,什么东西都想不到。

以后咋办呢?

  1. 睡觉颓,平时多打打基础;
  2. 用脑子(你可是省招生啊);
  3. 同上。

以上,有多了再补。

11.7upd:对于一些特殊情况常常忘记判断。

康托展开

之前对于“XX展开”一直都非常忌惮(想必是初一看泰勒展开的时候被吓傻啦),然后前几天讲搜索的时候提到了康托展开,我一查wiki(这个链接是中文界面维基百科的,然而我又没有找到对应的英文界面,所以要进行一波骚(fan)操(qiang)作)才发现——

就是个编码嘛!

公式如下:

{\displaystyle X=a_{n}(n-1)!+a_{n-1}(n-2)!+\cdots +a_{1}\cdot 0!}

这就是全排列进行编码,原来要10ⁿ存的数据,现在n!就可以做到!

解释一下上述公式的含义:ai表示在当前这个排列中比i这一位数字小的个数(第一个数字为第n位,以此类推)

举个栗子,

例如,3 5 7 4 1 2 9 6 8 展开为 98884。因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.

解释:

排列的第一位是3,比3小的数有两个,以这样的数开始的排列有8!个,因此第一项为2*8!

排列的第二位是5,比5小的数有1、2、3、4,由于3已经出现,因此共有3个比5小的数,这样的排列有7!个,因此第二项为3*7!

以此类推,直至0*0!

那么这样,就可以轻松的编码了。

 

继续阅读“康托展开”

Hello World

#include <bits/stdc++.h>
int main()
{
    printf("Hello World");
    return 0;
}
begin
    writeln('Hello World');
end.

e^{i\pi}+1=0

\sum_{x=a}^{b}f(x)\Delta x \sim \int_a^b f(x)