C++博客-混沌的云@HDU~

HDU1429胜利大逃亡（续）！终于过了，顺便学了位压缩

混沌的云 — Sat, 21 Feb 2009 11:29:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 #include 2 #include 3 ... 阅读全文

混沌的云 2009-02-21 19:29 发表评论

1166线段树版本，第一次自己写线段树，值得纪念

混沌的云 — Sat, 14 Feb 2009 08:08:00 GMT

  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~

混沌的云 2009-02-14 16:08 发表评论

STL简单讲解

混沌的云 — Tue, 10 Feb 2009 10:42:00 GMT

    //队列的使用

        #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(起始位置,长度)； //取子串

混沌的云 2009-02-10 18:42 发表评论

C++ 标准模板库（STL）编程示例 - set 拿来学习

混沌的云 — Mon, 09 Feb 2009 08:48:00 GMT

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 }

混沌的云 2009-02-09 16:48 发表评论

1026优先队列，论坛的代码，我加了批注，用于学习优先队列

混沌的云 — Sat, 07 Feb 2009 16:51:00 GMT

  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 }//第一次用优先队列，用的是论坛上的代码，加了批注

混沌的云 2009-02-08 00:51 发表评论

快排的实现

混沌的云 — Fri, 06 Feb 2009 14:44:00 GMT

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 }

混沌的云 2009-02-06 22:44 发表评论

胡大牛的sg超短运算~

混沌的云 — Fri, 06 Feb 2009 14:43:00 GMT

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 }

混沌的云 2009-02-06 22:43 发表评论

二分搜索

混沌的云 — Fri, 06 Feb 2009 14:41:00 GMT

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

混沌的云 2009-02-06 22:41 发表评论

1085Holding Bin-Laden Captive!(HDU)母函数模板，来自teddy

混沌的云 — Wed, 28 Jan 2009 14:30:00 GMT

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 //甘露大牛的母函数个人加了批注，学习中。。。

混沌的云 2009-01-28 22:30 发表评论

大明A+B（hdu）

混沌的云 — Tue, 27 Jan 2009 06:11:00 GMT

摘要: 1#include 2#include 3char *add(char s1[],char s2[]) 4{ 5 char st... 阅读全文

混沌的云 2009-01-27 14:11 发表评论