posts - 20,  comments - 6,  trackbacks - 0
     摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1 #include<iostream>  2 #include<cstdio>  3 ...  阅读全文
posted @ 2009-02-21 19:29 混沌的云 阅读(294) | 评论 (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 混沌的云 阅读(116) | 评论 (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 混沌的云 阅读(384) | 评论 (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 混沌的云 阅读(543) | 评论 (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<&& ty>=0 && ty<&& !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 混沌的云 阅读(201) | 评论 (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 混沌的云 阅读(189) | 评论 (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 混沌的云 阅读(79) | 评论 (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 混沌的云 阅读(62) | 评论 (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 混沌的云 阅读(248) | 评论 (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 混沌的云 阅读(349) | 评论 (0)编辑 收藏
仅列出标题  下一页
<2019年10月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(1)

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜