十一月 2009

半学期小结

十一 28th

由shǎ崽发表在F.M.L.

英语课:旷课一次,请假两次
体育课:旷课一次,请假一次
物理课:上过两次
数据结构:上课一次,上机一次
离散数学:上过一次
C#:上过一次
毛邓三:上过一次
形式与政策:一次都没上- -

英语昨天期中考试了,我晚上放下正在想的划分树,去打了两个小时酱油,就算出意外我也及格不了,上了大学后除了看题之外就没好好看英语…
完蛋了,再不去上课的话估计期末要挂掉一片…
昨天lcy和我说学习不能丢,上课一下其实可以当作AC之余的放松的，毕竟强度没有训练这么大..
下个星期起要去教室上课了…每个学期开始都这么说,希望这次能够实现这个承诺= =(但求期末不挂科..)

Popularity: 1% [?]

- -, 上课, 挂科, 旷课

前几天学线段树,这个经典的K-th number一直没有做,关键是听别人说复杂度是log(n)^3,我对这个需要两次二分+一次查找的算法非常的不爽,于是一直拖着没搞
今天正准备着手这题的时候,发现PKU的Disscuss有人提到log(n)的算法,而且编程复杂度比log(n)^3的还小,于是对这种算法充满了憧憬,那个log(n)^3的写到一半也放弃了(其实log(n)^3的归并树算法化简了之后就是求n个有序数列的第k大数)
YY了很久之后,得到下边这个代码..关键部分已经很明白的加了的注释
完全看明白之后会发现一个非常有趣的现象,划分树逆着做就变成了归并树
(其实我也不知道这是不是hyerty大神所说的划分树,乱YY的)
画了一颗划分树对数列[1 5 2 3 6 4 7 3 0 0]进行划分,下图有助于理解(红色表示该数被分到左儿子)

划分树

更多 >

Popularity: 26% [?]

K-th, log(n), 划分树, 归并树, 线段树

线段树专辑

十一 23rd

由shǎ崽发表在Special Topic

100个评论

这几天陆陆续续更新了下边几道我所能找到得具有一些代表性的线段树题目
从最最简单的区间求和到对区间的各种操作都包涵在这些题目里了
相信对一些准备学习线段树的人有一定得帮助
突然发现自己对数据结构的题目非常有感觉,所以在刷下边的题的同时也生出灵感出了好几道线段树题目
等比赛结束后也会陆续加进里边
更多 >

Popularity: 100% [?]

code, Seg_Tree, Template, 专辑, 线段树

test

十一 23rd

由shǎ崽发表在ACM

2个评论

测试一下贴代码

顺便把我的模版贴上来,我每段代码基本上都会用到这50行预定义..所以大家看到一道水题我要写几千B的时候不要误会了XD
所以以后我贴出来的代码会少很多头文件很多代码大家看不懂,和这段合起来看就OK啦~~

这也是从TopCoder上的大牛们那学来的,即可加快了代码速度,也可减少了编码的低级错误..

^?View Code CPP

//by NotOnlySuccess
 
#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "iomanip"
#include "bitset"
#include "list"
#include "strstream"
#include "ctime"
using namespace std;
 
typedef long long LL;
typedef unsigned long long ULL;
#define CC(m,what)		memset(m,what,sizeof(m))
#define FOR(i,a,b)		for( int i = (a) ; i < (b) ; i ++ )
#define FF(i,a)			for( int i = 0 ; i < (a) ; i ++ )
#define FFD(i,a)		for( int i = (a)-1 ; i >= 0 ; i --)
#define SS(a)			scanf("%d",&a)
#define LL(a)			((a)<<1)
#define RR(a)			(((a)<<1)+1)
#define SZ(a)			((int)a.size())
#define PP(n,m,a)		puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
const double eps = 1e-11;
const double Pi = acos(-1.0);
 
#define read			freopen("in.txt","r",stdin)
#define write			freopen("out.txt","w",stdout)
 
#define two(x)			((LL)1<<(x))
#define include(a,b)		(((a)&(b))==(b))
template<class T> inline T countbit(T n)	{return n?1+countbit(n&(n-1)):0;}
template<class T> inline T sqr(T a)	{return a*a;}
template<class T> inline void checkmin(T &a,T b)	{if(a == -1 || a > b)a = b;}
template<class T> inline void checkmax(T &a,T b)	{if(a < b)	a = b;}
 
int dx[] = {-1,0,1,0};//up Right down Left
int dy[] = {0,1,0,-1};