<ins id="pjuwb"></ins>

<blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

<noscript id="pjuwb"></noscript>

<sup id="pjuwb"><pre id="pjuwb"></pre></sup>

<dd id="pjuwb"></dd>

<abbr id="pjuwb"></abbr>

<tfoot id="44642"><delect id="44642"></delect></tfoot>

<li id="44642"></li>

<code id="44642"></code><li id="44642"><input id="44642"></input></li>

<dl id="44642"><acronym id="44642"></acronym></dl>

<li id="44642"><dl id="44642"></dl></li>

<bdo id="44642"><tbody id="44642"></tbody></bdo>

<button id="44642"><bdo id="44642"></bdo></button>

<li id="44642"></li>

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 閱讀(232) | 評論 (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 閱讀(631) | 評論 (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->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();
}

posted @ 2008-08-05 09:24 NicYun 閱讀(4268) | 評論 (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 閱讀(1792) | 評論 (0) | 編輯收藏

僅列出標題

无码国内精品久久人妻麻豆按摩| 久久强奷乱码老熟女网站| 99久久精品免费看国产一区二区三区| 欧美精品一本久久男人的天堂| 一本久道久久综合狠狠爱| 中文字幕久久波多野结衣av| 合区精品久久久中文字幕一区| 久久人人爽人人爽人人片AV麻豆| 久久久久人妻一区精品果冻| 久久99精品国产麻豆蜜芽| 久久久久国产一区二区三区| 久久久久久久免费视频| 欧美日韩精品久久久免费观看| 麻豆精品久久久久久久99蜜桃| 国产成人精品综合久久久| 久久久久久午夜成人影院| 久久精品亚洲精品国产色婷| 久久精品国产只有精品2020| 国产精品亚洲综合专区片高清久久久| 久久成人国产精品一区二区| 午夜精品久久久久| 日本欧美久久久久免费播放网| av午夜福利一片免费看久久 | 亚洲欧美国产日韩综合久久| 久久受www免费人成_看片中文| 伊人久久大香线焦AV综合影院| 99久久超碰中文字幕伊人| 久久人人爽人人爽人人片AV麻豆| 国产欧美久久久精品影院| WWW婷婷AV久久久影片| 久久久久久久亚洲精品| 亚洲精品白浆高清久久久久久| 国产69精品久久久久777| 青春久久| 91久久精品视频| 热re99久久6国产精品免费| 久久精品不卡| 久久精品国产69国产精品亚洲| 久久成人国产精品免费软件| 久久精品男人影院| 亚洲∧v久久久无码精品|

<li id="ye4u4"><dl id="ye4u4"></dl></li>

<rt id="ye4u4"><acronym id="ye4u4"></acronym></rt>