# yes you do

yes i do
posts - 4, comments - 2, trackbacks - 0, articles - 0
1
2 struct Node
3 {
4     int data;
5     struct Node *next;
6 };
7
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
26 {
27     Node *p, *q, *cur;
28
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;
44     return 0;
45 }
46
47 int main()
48 {
53     return 0;
54 }

posted @ 2009-08-20 22:21 chenweiwei 阅读(263) | 评论 (0)编辑 收藏

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仍然是并查的题目，没有特意说要找并查的题目来做，只是偶尔到了某一页发现某一道题目可以用并查来做，于是载下去了。

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;      //初始化高上面没有立方体。
}

}

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

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

posted @ 2009-05-30 15:35 chenweiwei 阅读(274) | 评论 (0)编辑 收藏

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.
...............

struct node
{

int l; //左子树
int r; //右子树
__int64 value; //区间的初始量
__int64 tsum;  //对区间的整体改变量
}
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;
}

}

int Modify(int a,int b,int s)
{
Node[s].tsum
+=(b-a+1)*mValue;

if(Node[s].l==&& Node[s].r==b)

{
+=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==&& Node[s].r==b)

{
cost
+= Node[s].value + Node[s].tsum;
}

else

{
cost

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

posted @ 2009-05-26 12:24 chenweiwei 阅读(1493) | 评论 (2)编辑 收藏

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

posted @ 2009-05-22 17:19 chenweiwei 阅读(290) | 评论 (0)编辑 收藏