|
|
2009年8月20日
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 }
2009年5月30日
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;
}
2009年5月26日
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 ≤ Ai ≤ 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;
}
2009年5月22日
|