摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 #include<iostream> 2 #include<cstdio> 3 ...
閱讀全文
posted @
2009-02-21 19:29 混沌的云 閱讀(451) |
評論 (2) |
編輯 收藏
1 #include<stdio.h>
2 #include<string.h>
3 int value[200005];
4 struct NODE{
5 NODE *lchild,*rchild;
6 int left,right;
7 int sum;
8 }mem[100001];
9 int mempos=0;
10 NODE *makenode()
11 {
12 NODE *p=&mem[mempos++];
13 memset(p,0,sizeof(p));
14 return p;
15 }
16 void update(NODE *root,int id)
17 {
18 if(root->right-root->left==1&&(id==root->right||id==root->left))
19 {
20 root->sum=value[root->right]+value[root->left];
21 }else
22 {
23 int mid=(root->left+root->right)/2;
24 if(id>=mid)
25 update(root->rchild,id);
26 if(id<=mid)
27 update(root->lchild,id);
28 root->sum=root->rchild->sum+root->lchild->sum-value[mid];
29 }
30 }
31 NODE *build(int beg,int end)
32 {
33 NODE * root=makenode();
34 root->left=beg;
35 root->right=end;
36 if(end-beg==1)
37 {
38 root->sum=value[beg]+value[end];
39 }else
40 {
41 int mid=(beg+end)/2;
42 root->lchild=build(beg,mid);
43 root->rchild=build(mid,end);
44 root->sum=root->rchild->sum+root->lchild->sum-value[mid];
45 }
46 return root;
47 }
48 int get(NODE *root,int beg,int end)
49 {
50 if(root->left==beg&&root->right==end)
51 {
52 return root->sum;
53 }
54 int mid=(root->left+root->right)/2;
55 if(beg>=mid)
56 {
57 return get(root->rchild,beg,end);
58 }else if(end<=mid)
59 {
60 return get(root->lchild,beg,end);
61 }else
62 {
63 int l=get(root->lchild,beg,mid);
64 int r=get(root->rchild,mid,end);
65 return l+r-value[mid];
66 }
67 }
68
69 int main()
70 {
71 int t,n,i,j,k,ss;
72 int a,b;
73 int co;
74 char qus[20];
75 scanf("%d",&t);
76 for(co=1;co<=t;co++)
77 {
78 printf("Case %d:\n",co);
79 scanf("%d",&n);
80 for(i=1;i<=n;i++)
81 {
82 scanf("%d",&value[i]);
83 }
84 getchar();
85 mempos=0;
86 NODE *root=build(1,n);
87 while(scanf("%s",qus))
88 {
89 if(strcmp(qus,"End")==0)
90 {
91 break;
92 }
93 if(strcmp(qus,"Add")==0)
94 {
95 scanf("%d%d",&a,&b);
96 value[a]+=b;
97 update(root,a);
98 }
99 if(strcmp(qus,"Sub")==0)
100 {
101 scanf("%d%d",&a,&b);
102 value[a]-=b;
103 update(root,a);
104 }
105 if(strcmp(qus,"Query")==0)
106 {
107 scanf("%d%d",&a,&b);
108 ss=get(root,a,b);
109 printf("%d\n",ss);
110 }
111 }
112 }
113
114 }
115 //寫了一下午，終于用線段樹寫出了1166~
posted @
2009-02-14 16:08 混沌的云 閱讀(222) |
評論 (0) |
編輯 收藏
//隊列的使用
#include<queue>
//在BFS中會使用到隊列
//優先隊列
priority_queue<元素類型> Q;
Q.push(); // 壓入元素
Q.pop； // 彈出
Q.front(); // 取頂元素
Q.empty(); // 判斷是否為空
// 優先隊列中默認的是大的先出
// 若要使小的先出，則可在元素類型struct中重載 “<”
struct node{
friend bool operator < (node n1, node n2)
{
return n1.Step > n2.Step;
// 小的先出
}
int Step;
};
// 優先隊列 取頂時應使用 Q.top();
//鏈表的使用
#include<list>
list<int> lis;
list<int>::iterator iter; // 跌代器 (指針)
list.push_back(); // 在鏈表尾插入元素
//操作表中的每個元素時，必須要使用指針
// *iter 即為 iter 所指的元素的值
for(iter = lis.begin(); iter != lis.end(); iter ++)
{
iter = lis.erase(iter);
// 刪除表中一位置的元素
// 若刪除指定位置，第 i 個，可用 i 記數
}
// lis.insert() 插入在當前指針所指的元素之前
//容器 vector 的使用
#include<vector>
vector<int> v;
v.push_back(); // 在尾部插入元素
v.size(); // 返回容器的大小
v.clear(); // 清除容器的元素
v.resize(); //分配表的大小
//若使用vector 來表示二維，則可
vector<vector<int> > v(n);
//或者
vector<vector<int> > v;
v.resize(n);
// 可以表示有 n 行的二維數組
// 對于每一維 ， v[i] 的操作與 v 一致
// 傳 vector 的使用
void pp(vector<vector<int> > &vv)
{
// 傳vector 的函數使用
int i ,j;
for(i = 0 ; i < vv.size(); i ++)
{
for(j = 0 ; j < vv[i].size(); j ++)
printf("%d ",vv[i][j]);
printf("\n");
}
}
void main()
{
int i,j;
vector<vector<int > > a(10);
for(i = 0 ; i < 10 ; i++)
for(j = 0 ; j < i;j ++)
a[i].push_back(j);
pp(a);
// 調用函數
}
// C++ 自帶的排序 sort
#include<algorithm>
//頭文件
bool cmp(int a, int b){
return a > b;
} // 使得降序排列
//默認為升序 sort(a,a + n);
sort(A, A+n,cmp);
//也可對結構體排序，比較函數自己實現
// 要對容器中的元素排序
// 可使用跌代器
// 把容器中起始與結束的指針傳給 sort
// example
vector<int> v;
vector<int> ::iterator it1;
vector<int> ::iterator it2;
it1 = v.begin();
it2 = v.end();
sort(it1, it2 ,cmp);
// string
// 使用起來相對比較多 ， 主要在處理字符串的時候
#include<string>
string s1 , s2 , s3;
// string 類的賦值
// 即可以 相互之間，也可以把字符串直接賦給 string 類
// example
char ss[] = “abcd”;
s1 = “”; // string 類初始為空
s1 = ss ; // 把字符串直接賦給string
s2 = s1; // sgring 之間賦值
// string 類可以直接使用 + 來進行字符串的拼接
s1 = “ab”;
s2 = “cd”;
s3 = s1 + s2;
// 操作的結果 s3 == “abcd”;
// 常用的函數
s1.size(); // 字符串的大小，既長度
// 對于已經賦值的字符串，可以直接對下表進行操作
// 可以使用查找函數
s1.find(s2) ; // 在s1 中查找 s2 ，如果存在，返回起始下表，否則返回 -1
s1.substr(起始位置,長度)； //取子串
posted @
2009-02-10 18:42 混沌的云 閱讀(547) |
評論 (2) |
編輯 收藏
1 #include <iostream>
2 #include <assert.h>
3 #include <set>
4 #include <string>
5 using namespace std;
6
7 struct employee
8 {
9 //Member Function
10 public:
11 employee() {} //默認構造函數
12 employee(long eID, string e_Name, float e_Salary);
13
14 //Attribute
15 public:
16 long ID; //Employee ID
17 string name; //Employee Name
18 float salary; //Employee Salary
19 };
20
21 //員工類構造函數
22 employee::employee(long eID, string e_Name, float e_Salary)
23 : ID(eID), name(e_Name), salary(e_Salary) {}
24
25 //用于對Set容器排序的函數對象
26 class KeyComp
27 {
28 public:
29 bool operator() (const employee& A, const employee& B)
30 {
31 return (A.salary < B.salary);
32 }
33 };
34
35
36 //定義一個元素類型為employee、按KeyComp排序的Set容器類型
37 typedef set<employee, KeyComp> EMPLOYEE_SET;
38 //定義MultiSet容器的隨機訪問迭代器類型
39 typedef set<employee, KeyComp>::iterator EMPLOYEE_IT;
40 //定義MultiSet容器的反向迭代器類型
41 typedef set<employee, KeyComp>::reverse_iterator EMPLOYEE_RIT;
42
43 //函數功能：正向輸出Set容器對象的所有元素
44 //參數：一個Set容器對象
45 //返回值：無
46 void output_set(EMPLOYEE_SET e)
47 {
48 assert(!e.empty());
49 EMPLOYEE_IT it;
50 for (it = e.begin(); it != e.end(); it++)
51 {
52 cout << (*it).ID << '\t' << (*it).name << '\t' << (*it).salary << endl;
53 }
54 }
55
56 //函數功能：逆向輸出Set容器對象的所有元素
57 //參數：一個Set容器對象
58 //返回值：無
59 void reverse_output_set(EMPLOYEE_SET e)
60 {
61 assert(!e.empty());
62 EMPLOYEE_RIT rit;
63 for (rit = e.rbegin(); rit != e.rend(); rit++)
64 {
65 cout << (*rit).ID << '\t' << (*rit).name << '\t' << (*rit).salary << endl;
66 }
67 }
68
69 int main(int argc, char* argv[])
70 {
71 EMPLOYEE_SET employees; //聲明一個容器對象
72
73 //下面的三條語句分別構造三個employee對象，然后插入MultiSet容器對象employees
74 employees.insert(EMPLOYEE_SET::value_type(100, "huahua", 20000));
75 employees.insert(EMPLOYEE_SET::value_type(101, "jiafeng", 8000));
76 employees.insert(EMPLOYEE_SET::value_type(102, "guangli", 10000));
77
78 //注意下面的兩條語句，因為是Set，不允許有重復的值，所以兩個employee對象只會有一條加入到Set容器
79 employees.insert(EMPLOYEE_SET::value_type(103, "jiahui", 12000));
80 employees.insert(EMPLOYEE_SET::value_type(103, "jiahui", 12000));
81
82 //正向和逆向輸出Set容器對象的所有元素
83 assert(!employees.empty());
84 cout << "From Head To Tail:" << endl;
85 output_set(employees);
86
87 cout << "From Tail To Head:" << endl;
88 reverse_output_set(employees);
89
90
91 cout << "Set容器對象employees是否為空？ " << (employees.empty() ? "TRUE" : "FALSE") << endl;
92 cout << "Set容器對象employees共有" << employees.size() << "個employee對象!" << endl;
93
94 return 0;
95 }
posted @
2009-02-09 16:48 混沌的云 閱讀(687) |
評論 (0) |
編輯 收藏
1 //由于本題要輸出最短時間，所以要用優先隊列，喲西
2 #include<iostream>
3 #include<stdio.h>
4 #include<functional>
5 using namespace std;
6 #include<queue>
7 struct Node
8 {
9 friend bool operator<(Node n1,Node n2)
10 {
11 return n1.t > n2.t;//這個東西是優先隊列的優先級判斷功能
12 }
13 int x;
14 int y;
15 int t;
16 struct Node *prev;//指向前綴
17 };
18 Node N[10003],P;
19 bool success;
20 int w;
21 int dir[][2]={{1,0},{0,1},{-1,0},{0,-1}};
22 char map[101][101];
23 int mark[101][101],n,m;//hash函數和地圖大小
24 int _x[1001],_y[1001];//用來保存路徑
25 int main()
26 {
27 void bfs();
28 while(scanf("%d%d",&n,&m)!=EOF)
29 {
30 int i;
31 for(i=0;i<n;i++)
32 cin>>map[i];
33 success=false;
34 bfs();//廣搜部分
35 if(success)
36 {
37 printf("It takes %d seconds to reach the target position, let me show you the way.\n",N[w].t);
38 int len=N[w].t;
39 _x[len]=N[w].x;_y[len]=N[w].y;
40 Node *p;
41 p=&N[w];
42 int b=len;
43 while(1)
44 {
45 p=p->prev;
46 if(p==NULL)
47 break;
48 b--;
49 _x[b]=(*p).x;
50
51 _y[b]=(*p).y;
52
53 }
54 int o=1;
55
56 for(i=b;i<=len-1;i++)
57 {
58
59 if(map[_x[b+1]][_y[b+1]]=='.')
60 {
61 printf("%ds:(%d,%d)->(%d,%d)\n",o,_x[b],_y[b],_x[b+1],_y[b+1]);
62 b++;
63 o++;
64 }
65 else if(map[_x[b+1]][_y[b+1]]!='.')
66 {
67 printf("%ds:(%d,%d)->(%d,%d)\n",o,_x[b],_y[b],_x[b+1],_y[b+1]);
68 int v=o;
69 for( o=o+1; o<v+1+map[_x[b+1]][_y[b+1]]-'0';o++)
70 {
71 printf("%ds:FIGHT AT (%d,%d)\n",o,_x[b+1],_y[b+1]);
72 }
73 b++;
74 }
75
76 }
77
78 }
79 else
80 printf("God please help our poor hero.\n");
81 printf("FINISH\n");
82 }
83 }
84
85 void bfs()
86 {
87 memset(mark,0,sizeof(mark));
88 priority_queue<Node>Q;//這個是優先隊列定義
89 N[1].t=0;N[1].x=0;N[1].y=0;N[1].prev=NULL;
90 mark[0][0]=1;
91 Q.push(N[1]);
92 w=2;
93 while(!Q.empty())
94 {
95
96 N[w]=Q.top();//這個是一個很大的區別，如果普通隊列是front而優先則是輸出最優先的
97 Q.pop();
98 if(N[w].x==n-1&&N[w].y==m-1)
99 {
100 success=1;
101 break;//由于是優先隊列，所以第一次找到就成功了
102 }
103 for(int i=0;i<4;i++)
104 {
105 int tx=N[w].x+dir[i][0];
106 int ty=N[w].y+dir[i][1];
107 if(tx>=0 && tx<n && ty>=0 && ty<m && !mark[tx][ty])
108 {
109 if(map[tx][ty]!='X')
110 {
111 P.x=tx;P.y=ty;P.prev=&N[w];
112 mark[tx][ty]=1;
113 if(map[tx][ty]=='.')
114 {
115 P.t=N[w].t+1;
116 Q.push(P);
117 }
118 if(map[tx][ty]!='.')
119 {
120 P.t=N[w].t+1+map[tx][ty]-'0';
121 Q.push(P);
122 }
123 }
124 }
125 }
126 w++;
127 }
128
129 }//第一次用優先隊列，用的是論壇上的代碼，加了批注
posted @
2009-02-08 00:51 混沌的云 閱讀(332) |
評論 (0) |
編輯 收藏
1 int Partition (Type a[], int p, int r)
2 {
3 int i = p, j = r + 1;
4 Type x=a[p];
5 // 將< x的元素交換到左邊區域
6 // 將> x的元素交換到右邊區域
7 while (true) {
8 while (a[++i] <x);
9 while (a[- -j] >x);
10 if (i >= j) break;
11 Swap(a[i], a[j]);
12 }
13 a[p] = a[j];
14 a[j] = x;
15 return j;
16 }
17 void QuickSort (Type a[], int p, int r)
18 {
19 if (p<r) {
20 int q=Partition(a,p,r);
21 QuickSort (a,p,q-1); //對左半段排序
22 QuickSort (a,q+1,r); //對右半段排序
23 }
24 }
posted @
2009-02-06 22:44 混沌的云 閱讀(358) |
評論 (0) |
編輯 收藏 1 #include<stdio.h>
2 void main()
3 {
4 int sg[1001],num[1001],fib[16]={1,2},n,m,p,j,i;
5 for(i=2;i<16;i++)
6 fib[i]=fib[i-1]+fib[i-2];//求出斐波那契數列
7 sg[0]=0;//0的sg值為0
8 for(i=1;i<1001;i++)
9 {
10 for(j=0;fib[j]<=i;j++)
11 num[sg[i-fib[j]]]=i;//把i的后繼的sg值都標注一下，表示出現過了，后面找sg的時候用
12 for(j=0;j<=i;j++)
13 if(num[j]!=i)
14 {sg[i]=j;break;}//找到最小的整數j，成為i的sg值
15 }
16 while(scanf("%d%d%d",&n,&m,&p)==3&&(m!=0||n!=0||p!=0))
17 puts(sg[m]^sg[n]^sg[p]?"Fibo":"Nacci");//異或判斷博弈結果，輸出結果
18 }
posted @
2009-02-06 22:43 混沌的云 閱讀(175) |
評論 (0) |
編輯 收藏 1
2
3 int erf(__int64 r[],int n,__int64 k)
4
5 {
6
7 int low=0,high=n-1,mid;
8
9 while (low<=high)
10 {
11 mid=(low+high)/2;
12 if (r[mid]==k)
13 return mid;
14 if (r[mid]>k)
15 high=mid-1;
16 else
17 low=mid+1;
18 }
19 return 0;
20 }
21
posted @
2009-02-06 22:41 混沌的云 閱讀(131) |
評論 (0) |
編輯 收藏
1 #include <iostream>
2 using namespace std;
3 int c1[10001],c2[10001];
4 int main()
5 {
6 int num1,num2,num5,i,j,k,u,o;
7 while (cin>>num1>>num2>>num5 && (num1|| num2 || num5))
8 {
9 for (i=0;i<=10001;i++)
10 {c1[i]=1;c2[i]=0;}//初始化
11
12 for (j=0,o=0;o<=num1;j++,o++)//o為1分數量限制，j為1分組成的價格
13 {
14 for (k=0,u=0;u<=num2;k+=2,u++)//k為2分的價格，u為2分個數限制
15 {
16 c2[j+k]+=c1[j];
17 }
18 }//窮舉出所有2分和1分的總和
19 for (int w=0;w<=10001;w++)
20 {c1[w]=c2[w];c2[w]=0;}
21 int t=j+k-3;
22 for (j=0,o=0;o<=t;j++,o++)
23 {
24 for (k=0,u=0;u<=num5;k+=5,u++)//同上，處理5分的情況，母函數真神奇
25 {
26 c2[j+k]+=c1[j];
27 }
28 }
29 for (int w=0;w<=10001;w++)
30 {c1[w]=c2[w];c2[w]=0;}//c2 復制到c1
31 int p;
32 for (p=1;p<=10001;p++)
33 {if (c1[p]==0)
34 {break;}}//找出最小的不能表示的價值
35 cout<<p<<endl;
36 }
37 return 0;
38 }
39 //甘露大牛的母函數 個人加了批注，學習中。。。
posted @
2009-01-28 22:30 混沌的云 閱讀(346) |
評論 (0) |
編輯 收藏
摘要: 1#include<stdio.h> 2#include<string.h> 3char *add(char s1[],char s2[]) 4{ 5 char st...
閱讀全文
posted @
2009-01-27 14:11 混沌的云 閱讀(499) |
評論 (0) |
編輯 收藏