C++博客-yes you do

单链表反转程序

chenweiwei — Thu, 20 Aug 2009 14:21:00 GMT

1
2 struct Node
3 {
4     int data;
5     struct Node *next;
6 };
7
8 int InitLink(Node *h)
9 {
10     int i;
11     Node *p, *q;
12     p = new Node;
13     p = h;
14     for (i = 1; i <= 10; ++i)
15     {
16         q = new Node;
17         q ->data = i;
18         p ->next = q;
19         p = q;
20     }
21     p ->next = NULL;
22     return 0;
23 };
24
25 int ReverseLink(Node *head)
26 {
27     Node *p, *q, *cur;
28
29     p = head ->next;
30     cur = q = p;
31     cur = cur ->next;
32     p = p ->next->next;
33     q->next = NULL;
34
35     while (p != NULL)
36     {
37         cur ->next = q;
38         q = cur;
39         cur = p;
40         p = p->next;
41     }
42     cur ->next = q;
43     head ->next = cur;
44     return 0;
45 }
46
47 int main()
48 {
49     Node *head;
50     head = new Node;
51     InitLink(head);
52     ReverseLink(head);
53     return 0;
54 }

chenweiwei 2009-08-20 22:21 发表评论

PKU1988Cube Stacking 并查

chenweiwei — Sat, 30 May 2009 07:35:00 GMT

Cube Stacking

Cube StackingFarmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.

Write a program that can verify the results of the game.

-------------------
仍然是并查，仍然是想了很久，仍然是参考了别人的代码才明白，学了这么久，真的会怀疑自己的智商了。

PKU1988仍然是并查的题目，没有特意说要找并查的题目来做，只是偶尔到了某一页发现某一道题目可以用并查来做，于是载下去了。
题意：
其实题意比较好理解，两个命令:如果是c命令则算出输出的cube X下面有多少个立方体，如果是M命令，则把cube Y所在的集合中的全部立方体放入cube X 所在的立方集合下。
初始化：
定义一个结构体，保存一个cube的根cube存于parent中，保存cube上面的立方数于up中，保存cube的下面的立方数于down中。

struct node
{
    int parent;
    int up;
    int down;
}Node[SIZE];

void Init(int nt)
{
    for (int i=0; i <= nt;i++)
    {
        Node[i].parent=i;  //根为自己
        Node[i].down=1;    //初始化设为1只是为了计算的方便，到后面会减1
        Node[i].up=0;      //初始化高上面没有立方体。
    }
}

合并操作：
合并的时候找两个cube的根结点，并且对要结点的up及dow变量进行操作。具体看代码注释

int UnionSet(int i,int j)
{
    i=FindSet(i);
    j=FindSet(j);
    Node[j].up=Node[i].down;    //i下面的cube都变成了j上面的cube，归入Node[j].up
    Node[i].down+=Node[j].down; //能够想像，j下面的所有cube同时也都归入i中
    Node[j].parent=i;           //两个集合合并成一个集合 i为根
    return 0;
}

查询操作：
查询的时候找结点父亲，并且找父亲结点的上面cube数归入结点上面cube数中，如果父亲结点有根结点，则继续查找（哇，很难表达啊）。

int FindSet(int i)
{
    int m;
    if (Node[i].parent!=i)
    {
        m=Node[i].parent;
        Node[i].parent=FindSet(Node[i].parent); //找父亲结点的父亲结点
        Node[i].up+=Node[m].up;                 //将父亲结点的up归入结点的up中
    }
    return Node[i].parent;
}

主函数：

int main(int argc, char* argv[])
{
//    freopen("in.txt","r",stdin);
    int p;
    scanf("%d",&p);
    char op;
    Init(SIZE);
    while(p--)
    {
        getchar();
        op=getchar();
        if(op=='M')
        {
            int x,y;
            scanf("%d %d",&x,&y);
            UnionSet(x,y);
        }
        else if(op=='C')
        {
            int x,y;
            scanf("%d",&x);
            y=FindSet(x);
            printf("%d\n",Node[y].down-Node[x].up-1); //这里需要减1
        }
    }
    return 0;
}

chenweiwei 2009-05-30 15:35 发表评论

PKU3468线段树入门

chenweiwei — Tue, 26 May 2009 04:24:00 GMT

A Simple Problem with Integers

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
...............

一道简单的线段树题目，但是因为数据量大（1000000000 ≤ A_i ≤ 1000000000），按照常规的解法必然会超时，这里需要增加一些变量保存区间内的改变量.

结点定义：
这里结点有五个变量，分别是左子树，右子树，区间的初始值。对区间整体的改变值。该区间及子区间改变值

struct node
{
    int l; //左子树
    int r; //右子树
    __int64 value; //区间的初始量
    __int64 tsum;  //对区间的整体改变量
    __int64 adt;   //对区间及子区间的改变值
}Node[400040];

初始化：
建树的时候，每个结点保存这个结点跟其子树的结点值总和。

int build(int a,int b,int s)
{
    Node[s].l=a;
    Node[s].r=b;
    if(a==b)
    {
        Node[s].value=v[a];
        return 0;
    }
    else
    {
        int mid=(a+b)/2;
        build(a,mid,s*2);
        build(mid+1,b,s*2+1);
        Node[s].value=Node[s*2].value+Node[s*2+1].value;
        return 0;
    }
}

更新：
更新的时候，tsum记录整个区间的改变量。

int Modify(int a,int b,int s)
{
    Node[s].tsum+=(b-a+1)*mValue;
    if(Node[s].l==a && Node[s].r==b)
    {
        Node[s].adt+=mValue;
    }
    else
    {
        int mid=(Node[s].l+Node[s].r)>>1;
        if(b<=mid)
        {
            Modify(a,b,s*2);
        }
        else if(a>mid)
        {
            Modify(a,b,s*2+1);
        }
        else
        {
            Modify(a,mid,s*2);
            Modify(mid+1,b,s*2+1);
        }
//        Node[s].value=Node[s*2].value+Node[s*2+1].value;
    }
    return 0;
}

查询：

__int64 Query(int a,int b,int s)
{
    __int64 cost=0;

    if(Node[s].l==a && Node[s].r==b)
    {
        cost += Node[s].value + Node[s].tsum;
    }
    else
    {
        cost+=(b-a+1)*Node[s].adt;
        int mid=(Node[s].l+Node[s].r)>>1;
        if(b<=mid)
        {
            cost+=Query(a,b,s*2);
        }
        else if(a>mid)
        {
            cost+=Query(a,b,s*2+1);
        }
        else
        {
            cost+=Query(a,mid,s*2);
            cost+=Query(mid+1,b,s*2+1);
        }
    }
    return cost;
}

chenweiwei 2009-05-26 12:24 发表评论

PKU2492 A Bug's Life(并查集)

chenweiwei — Fri, 22 May 2009 09:19:00 GMT

并查集的简单变种

初始化
初始化的时候增加一个变题用来记录每只虫子的对立面。数组初始化均为-1，标志对立面未找到。

输入
查找两只虫子的对立面是否有记录，哪果有记录则将记录与输入的另一只虫子union，第二只虫子也这样操作。

判断
判断两足虫子是否为同性恋只需要判断他们的祖先是否一相同，如果相同则标记找到，如果不同按照上面的方法操作

想法
这道题最重要的是把同类合并，然后每次输入判断两只虫子是否在张图内，其中的技巧在于每次输入的两足虫子如果符合条件那们他们一定不在同一张图内，因为需要找另外一只虫子把他们加入的自己的那张图中，所以引入了opt这个数组。当然我也是参考了别人的程序，如果真的是实验比赛中恐怕很难想出这个方法。感谢提供了代码的先驱们。

void Init(int nt)//初始化
{
    for (int i=0; i <= nt;i++)
    {
        parent[i] = i;
        rank[i] = 0;
        opt[i]=-1;//表示未找到对立面
    }
}

//判断是否出现同性恋
for(i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            int finda=FindSet(a);
            int findb=FindSet(b);
            if(finda==findb)flag=1;
            else
            {
                if(opt[a]!=-1)
                {
                    UnionSet(opt[a],b);
                }
                if(opt[b]!=-1)
                {
                    UnionSet(opt[b],a);
                }
                opt[a]=b;
                opt[b]=a;
            }

chenweiwei 2009-05-22 17:19 发表评论