C++博客-Try Again

树状数组

NicYun — Fri, 13 Mar 2009 03:30:00 GMT

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);
        }
    }
};

NicYun 2009-03-13 11:30 发表评论

java 分数类

NicYun — Sun, 08 Mar 2009 13:02:00 GMT

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);
    }
}

NicYun 2009-03-08 21:02 发表评论

线段树

NicYun — Tue, 05 Aug 2008 01:24:00 GMT

#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->m = head->j - head->i;
        else if (head->j - head->i == 1) // 该节点为叶节点
            head->m = 0;
        else    // 其他内部节点的情况
            head->m = (head->lson)->m + (head->rson)->m;
    }
    void updateLine()
    {
        if (head->count > 0)
            head->lbd = head->rbd = head->line = 1;
        else if (head->j - head->i == 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->i && 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->i && head->j <= 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();
}

NicYun 2008-08-05 09:24 发表评论

最小堆和最大堆

NicYun — Mon, 04 Aug 2008 02:29:00 GMT

#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;
}

NicYun 2008-08-04 10:29 发表评论