Try Again

基础知识学习
随笔 - 4, 文章 - 0, 评论 - 0, 引用 - 0
数据加载中……

2009年3月13日

树状数组

class TreeArray
{
    
int c[1100000]; // element id must start at 1
    int size;
    
int lowbit(int x)
    {
        
return x & (-x);
    }
public:
    
void init(int s = N - 1)
    {
        size 
= s;
        memset(c,
0,size * sizeof(c[0]));
    }
    
int sum(int n) // 前n个数的和,包括n
    {
        
int s = 0;
        
while (n > 0)
        {
            s 
+= c[n];
            n 
-= lowbit(n);
        }
        
return s;
    }
    
void plus(int p,int x) // add x to the element at position p
    {
        
while (p <= size)
        {
            c[p] 
+= x;
            p 
+= lowbit(p);
        }
    }
};

posted @ 2009-03-13 11:30 NicYun 阅读(101) | 评论 (0)编辑 收藏

2009年3月8日

java 分数类

class Fraction
{
    BigInteger up, down;
    
public Fraction (Fraction f)
    {
        
this.up = f.up;
        
this.down = f.down;
    }
    
public Fraction(String s)
    {
        
this.up = new BigInteger(s);
        
this.down = new BigInteger("1");
    }
    
public Fraction(BigInteger a, BigInteger b)
    {
        
this.up = a;
        
this.down = b;
    }
    
public BigInteger getUp()
    {
        
return this.up;
    }
    
public BigInteger getDown()
    {
        
return this.down;
    }
    
public Fraction subtract(Fraction f)
    {
        BigInteger save1 
= this.up.multiply (f.down);
        BigInteger save2 
= f.up.multiply(this.down);
        Fraction tmp 
= new Fraction(save1.subtract (save2), f.down .multiply ( this.down));
        
return simplex(tmp);
    }
    
public Fraction add(Fraction f)
    {
        Fraction tmp 
= new Fraction ("0");
        tmp 
= tmp.subtract(f);
        Fraction ans 
= new Fraction (this.subtract(tmp));
        
return ans;
    }
    
public Fraction multiply(Fraction f)
    {
        Fraction tmp;
        tmp 
= new Fraction(this.up.multiply (f.up), this.down.multiply (f.down));
        
if (tmp.down.compareTo(new BigInteger("0")) == -1)
        {
            tmp.down 
= tmp.down.multiply (new BigInteger("-1"));
            tmp.up 
= tmp.up.multiply (new BigInteger("-1"));
        }
        
return simplex(tmp);
    }
    
public Fraction divide(Fraction f)
    {
        Fraction tmp 
= null;
        tmp 
= new Fraction(this.up.multiply (f.down), this.down.multiply (f.up));
        
if (tmp.down.compareTo(new BigInteger("0")) == -1)
        {
            tmp.down 
= tmp.down.multiply (new BigInteger("-1"));
            tmp.up 
= tmp.up.multiply (new BigInteger("-1"));
        }
        
return simplex(tmp);
    }
    BigInteger gcd(BigInteger a, BigInteger b)
    {
        
if (b.compareTo(new BigInteger("0")) == 0)
            
return a;
        
return gcd(b, a.remainder (b));
    }
    Fraction simplex(Fraction f)
    {
        BigInteger tmp 
= gcd(f.up.abs(), f.down.abs ());
        f.up 
= f.up.divide (tmp);
        f.down 
= f.down.divide (tmp);
        
return f;
    }
    
void print()
    {
        BigInteger a, b, c;
        a 
= this.getUp ();
        b 
= this.getDown();
        c 
= gcd(a.abs(), b.abs());
        a 
= a.divide (c);
        b 
= b.divide (c);
        
if (b.compareTo (new BigInteger("1")) == 0)
            System.out.println(a);
        
else
            System.out.println (a 
+ "/" + b);
    }
}

posted @ 2009-03-08 21:02 NicYun 阅读(353) | 评论 (0)编辑 收藏

2008年8月5日

线段树

#include <iostream>
#include 
<string>
#include 
<algorithm>
using namespace std;

const int SIZE = 10010;

struct node // the node of line tree
{
    
int i,j; // 区间范围
    node * lson;
    node 
* rson;
    
int count; // 线段覆盖条数
    int m; // 测度
    int line; // 连续段数
    int lbd,rbd; // 用来计算连续段数
    node(int l,int r)
    {
        i 
= l,j = r;
        count 
= m = line = lbd = rbd = 0;
        lson 
= rson = NULL;
    }
};
class LineTree
{
    node 
* head;
    
/* 以下函数内部使用,可不用考虑 */
    
void init(node * pnode = NULL)
    {
        head 
= pnode;
    }
    
void updateM()
    {
        
if (head->count > 0// 被覆盖满
            head->= head->- head->i;
        
else if (head->- head->== 1// 该节点为叶节点
            head->= 0;
        
else    // 其他内部节点的情况
            head->= (head->lson)->+ (head->rson)->m;
    }
    
void updateLine()
    {
        
if (head->count > 0)
            head
->lbd = head->rbd = head->line = 1;
        
else if (head->- head->== 1)
            head
->lbd = head->rbd = head->line = 0;
        
else
        {
            head
->lbd = (head->lson)->lbd;
            head
->rbd = (head->rson)->rbd;
            head
->line = (head->lson)->line + (head->rson)->line - (head->lson)->rbd * (head->rson)->lbd;
        }
    }
public:
    LineTree();
    
void clear(); // 清空线段数;
    void build(int l,int r); // 建立线段树,区间[l,r];
    void insert(int l,int r); // 插入一条线段;
    void del(int l,int r); // 删除一条线段;
    int GetM(); // 测度;
    int GetLine(); // 连续段数;
    int GetCov(); // 覆盖线段数;
    ~LineTree();
};
LineTree::LineTree()
{
    head 
= NULL;
}
void LineTree::clear() // 清空线段数
{
    
if (head == NULL)
        
return;
    LineTree temp;
    temp.init(head
->lson);
    temp.clear();
    temp.init(head
->rson);
    temp.clear();
    delete head;
    head 
= NULL;
}
void LineTree::build(int l,int r) // 建立线段树,区间[l,r]
{
    head 
= new node(l,r);
    
if (r - l > 1)
    {
        
int k = (l + r) / 2;
        LineTree temp;
        temp.build(l,k);
        head
->lson = temp.head;
        temp.init();
        temp.build(k,r);
        head
->rson = temp.head;
    }
}
void LineTree::insert(int l,int r) // 插入一条线段
{
    
if (l <= head->&& r >= head->j)
        (head
->count)++;
    
else
    {
        LineTree temp;
        
if (l < (head->i+head->j)/2)
        {
            temp.init(head
->lson);
            temp.insert(l,r);
        }
        
if (r > (head->i+head->j)/2)
        {
            temp.init(head
->rson);
            temp.insert(l,r);
        }
    }
    updateM();
    updateLine();
}
void LineTree::del(int l,int r) // 删除一条线段
{
    
if (l <= head->&& head-><= r)
        (head
->count)--;
    
else
    {
        LineTree temp;
        
if (l < (head->i+head->j)/2)
        {
            temp.init(head
->lson);
            temp.del(l,r);
        }
        
if (r > (head->i+head->j)/2)
        {
            temp.init(head
->rson);
            temp.del(l,r);
        }
    }
    updateM();
    updateLine();
}
int LineTree::GetM() // 测度
{
    
return head->m;
}
int LineTree::GetLine() // 连续段数
{
    
return head->line;
}
int LineTree::GetCov() // 覆盖线段数
{
    
return head->count;
}
LineTree::
~LineTree()
{
    
this->clear();
}

posted @ 2008-08-05 09:24 NicYun 阅读(3649) | 评论 (0)编辑 收藏

2008年8月4日

最小堆和最大堆

#include <iostream>
#include 
<string>
#include 
<stdio.h>
using namespace std;

#define SIZE  500000

void swap(int &a,int &b)
{
    
int temp = a;
    a 
= b;
    b 
= temp;
}

class Heap
{
    
int size;
    
int heap[SIZE];
public:
    
virtual bool cmp(int a,int b) = 0;
private:
    inline 
int fathter(int p)
    {
        
return p / 2;
    }
    inline 
int LeftSon(int p)
    {
        
int son = 2 * p;
        
if (son > size)
            
return 0;
        
return son;
    }
    inline 
int RightSon(int p)
    {
        
int son = 2 * p + 1;
        
if (son > size)
            
return 0;
        
return son;
    }
    
int ShiftUp(int p)
    {
        
if (p == 1)
            
return p;
        
if (cmp(heap[p],heap[fathter(p)]))
        {
            swap(heap[p],heap[fathter(p)]);
            
return fathter(p);
        }
        
return p;
    }
    
int ShiftDown(int p)
    {
        
int lagest = p;

        
if ((LeftSon(p)) && (cmp(heap[LeftSon(p)],heap[lagest])))
            lagest 
= LeftSon(p);
        
if ((RightSon(p)) && (cmp(heap[RightSon(p)],heap[lagest])))
            lagest 
= RightSon(p);
        
if (lagest != p)
            swap(heap[lagest],heap[p]);
        
return lagest;
    }
public:
    Heap() { size 
= 0; }
    
int insert(int n);
    
void del(int p);
    
void DelHead();
    
int head();
    
void init();
    
bool IsEempty();
};
int Heap::insert(int n)
{
    size
++;
    heap[size] 
= n;
    
int where = size;
    
int p;
    
while (((p = ShiftUp(where)) != where))
    {
        where 
= p;
        
continue;
    }
    
return where;
}
void Heap::del(int p)
{
    heap[p] 
= heap[size];
    size
--;
    
int where;
    
while (((where = ShiftDown(p)) != p))
    {
        p 
= where;
        
continue;
    }
}
void Heap::DelHead()
{
    del(
1);
}
int Heap::head()
{
    
if (size == 0)
        
return -1;
    
return heap[1];
}
void Heap::init()
{
    size 
= 0;
}
bool Heap::IsEempty()
{
    
if (size == 0)
        
return 1;
    
else
        
return 0;
}

class MaxHeap : public Heap
{
    
bool cmp(int a,int b)
    {
        
return a > b;
    }
};

class MinHeap : public Heap
{
    
bool cmp(int a,int b)
    {
        
return a < b;
    }
};

int main()
{
    
return 0;
}

posted @ 2008-08-04 10:29 NicYun 阅读(1536) | 评论 (0)编辑 收藏