C++博客-默、

一维线段树组

煙雨默嘫 — Tue, 10 Jul 2012 12:44:00 GMT

树状数组是对一个数组改变某个元素和求和比较实用的数据结构。两中操作都是O(logn)。
在解题过程中，我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]。

但是不难发现，如果我们修改了任意一个A[i],S[i]、S[i+1]...S[n]都会发生变化。

可以说，每次修改A[i]后，调整前缀和S[]在最坏情况下会需要O(n)的时间。

当n非常大时，程序会运行得非常缓慢。

因此，这里我们引入“树状数组”，它的修改与求和都是O(logn)的，效率非常高。

【理论】

为了对树状数组有个形象的认识，我们先看下面这张图。

如图所示，红色矩形表示的数组C[]就是树状数组。

这里，C[i]表示A[i-2^k+1]到A[i]的和，而k则是i在二进制时末尾0的个数，

或者说是i用2的幂方和表示时的最小指数。

（当然，利用位运算，我们可以直接计算出2^k=i&(i^(i-1)) ）

同时，我们也不难发现，这个k就是该节点在树中的高度，因而这个树的高度不会超过logn。

所以,当我们修改A[i]的值时，可以从C[i]往根节点一路上溯，调整这条路上的所有C[]即可，

这个操作的复杂度在最坏情况下就是树的高度即O(logn)。

另外，对于求数列的前n项和，只需找到n以前的所有最大子树，把其根节点的C加起来即可。

不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开成2的幂方和时的项数,

因此，求和操作的复杂度也是O(logn)。

接着，我们考察这两种操作下标变化的规律：

首先看修改操作：

已知下标i，求其父节点的下标。
我们可以考虑对树从逻辑上转化：

如图，我们将子树向右对称翻折，虚拟出一些空白结点（图中白色），将原树转化成完全二叉树。

有图可知，对于节点i，其父节点的下标与翻折出的空白节点下标相同。

因而父节点下标 p=i+2^k (2^k是i用2的幂方和展开式中的最小幂，即i为根节点子树的规模)

即 p = i + i&(i^(i-1)) 。

接着对于求和操作：

因为每棵子树覆盖的范围都是2的幂，所以我们要求子树i的前一棵树，只需让i减去2的最小幂即可。

即 p = i - i&(i^(i-1)) 。

至此，我们已经比较详细的分析了树状数组的复杂度和原理。

在最后，我们将给出一些树状数组的实现代码，希望读者能够仔细体会其中的细节。

求最小幂2^k:

int Lowbit(int t)
{
return t & ( t ^ ( t - 1 ) );
}

求前n项和：

int Sum(int end)
{
    int sum = 0;
    while(end > 0)
    {
        sum += in[end];
        end -= Lowbit(end);
    }
    return sum;
}

对某个元素进行加法操作：

void plus(int pos , int num)
{
    while(pos <= n)
    {
          in[pos] += num;
          pos += Lowbit(pos);
    }
}

煙雨默嘫 2012-07-10 20:44 发表评论

哈夫曼树（转）

煙雨默嘫 — Sun, 06 May 2012 02:50:00 GMT

哈夫曼树又称最优树（二叉树），是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。

结点之间的路径长度：从一个结点到另一个结点之间的分支数目。

树的路径长度：从树的根到树中每一个结点的路径长度之和。

结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：

WPL为最小的二叉树就称作最优二叉树或哈夫曼树。

完全二叉树不一定是最优二叉树。

哈夫曼树的构造：

（1）根据给定的n个权值{w₁,w₂,...,w_n}构造n棵二叉树的集合F={T₁,T₂,...,T_n}，其中Ti中只有一个权值为w_i的根结点，左右子树为空；
（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。
（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；
（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。

例1：

例2：

结点的存储结构:

构造哈夫曼树的算法说明：

#define n /* 叶子总数 */
#define m 2*n-1 /* 结点总数 */
证：由性质3，叶子结点数 n₀=n₂+1，故哈夫曼树结点总数为 n₀+n₂=n₀+(n₀-1)=2*n₀-1

例3 在解某些判定问题时，利用哈夫曼树获得最佳判定算法。

（a)

WPL=0.05*1+0.15*2+0.4*3+0.3*4+0.1*4=3.15

（b)(c)

WPL=0.4*1+0.3*2+0.15*3+0.05*4+0.1*4=2.05 WPL=0.05*3+0.15*3+0.4*2+0.3*2+0.1*2=2.2

哈夫曼编码

从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。

例，对电文 EMCAD 编码。若等长编码，则

EMCAD => 000001010011100 共15位

设各字母的使用频度为 {E,M,C,A,D}={1,2,3,3,4}。用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，树枝分配代码“0”或“1”:

煙雨默嘫 2012-05-06 10:50 发表评论

zoj 3607

煙雨默嘫 — Mon, 16 Apr 2012 11:00:00 GMT

这题当时比赛的时候以为是dp,以为客人走了还会回来==！

1 #include
2 #include
3 using namespace std;
4
5 int main()
6 {
7     int pi[1001],ti[1001];
8     double temp,Maxtime,Max,Time;
9     int t,n,i,sum;
10     scanf("%d",&t);
11     while(t--)
12     {
13         scanf("%d",&n);
14         for(i=1;i<=n;i++)
15         {
16             scanf("%d",&pi[i]);
17         }
18         ti[0]=0;
19         for(i=1;i<=n;i++)
20         {
21             scanf("%d",&ti[i]);
22         }
23         sum=0;
24         Max=0;
25         Maxtime=0;
26         for(i=1;i<=n;i++)
27         {
28             sum+=pi[i];
29             temp=(double)sum/(i);//当前的平均价格
30             if(Maxtime<(ti[i]-ti[i-1]))
31             {
32                 Maxtime=ti[i]-ti[i-1];
33             }
34             if(i==n)
35             {
36                 if(temp>Max)
37                 {
38                     Max=temp;
39                     Time=Maxtime;
40                 }
41                 continue;
42             }
43             if(Maxtime<(ti[i+1]-ti[i])&&temp>Max)
44             {
45                 Max=temp;
46                 Time=Maxtime;
47             }
48         }
49         printf("%.6lf %.6lf\n",Time,Max);
50     }
51     return 0;
52 }

煙雨默嘫 2012-04-16 19:00 发表评论

zoj 3609

煙雨默嘫 — Sun, 15 Apr 2012 10:52:00 GMT

比赛的时候卡在这里，都是我没有把题目看懂，m=1的情况没考虑好，直接当不存在处理了==

下面给一种暴力法

不过时间也是很快的

#include
#include
using namespace std;

int t;
int main()
{
    int t,a,m,aa,ans,mm,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&m);
        if(m==1||a==1)
        {
            printf("1\n");
            continue;
        }
        if(a%m==0||m%a==0)
        {
            printf("Not Exist\n");
            continue;
        }
        for(i=1;i        {
            if(a*i%m==1)
            {
                break;
            }
        }
        if(i==m)
        {
            printf("Not Exist\n");
        }
        else
        {
            printf("%d\n",i);
        }
    }
    return 0;
}

下面是我比赛时想的，因为m=1考虑出错，结果很悲剧
#include<iostream>

#include
using namespace std;

int run(int a,int b)
{
    if(a    {
        a^=b;
        b^=a;
        a^=b;
    }
    if(b==0) return a;
    return run(b,a%b);
}

int t;
int main()
{
    int t,a,m,aa,ans,mm;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&m);
        if(m==1||a==1)
        {
            printf("1\n");
            continue;
        }
        if(a%m==0||m%a==0)
        {
            printf("Not Exist\n");
            continue;
        }
        if(run(a,m)==1)
        {
            if(a>m)
            {
                aa=a;
                while(aa%m!=1)
                {
                    aa+=a;
                }
                ans=aa/a;
            }
            else
            {
                mm=m;
                while((mm+1)%a!=0)
                {
                    mm+=m;
                }
                ans=(mm+1)/a;
            }
            printf("%d\n",ans);
        }
        else
        {
            printf("Not Exist\n");
        }
    }
    return 0;
}

煙雨默嘫 2012-04-15 18:52 发表评论

HDU 1536

煙雨默嘫 — Sat, 17 Mar 2012 06:46:00 GMT

S-Nim

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1782 Accepted Submission(s): 802

Problem Description

Arthur and his sister Caroll have been playing a game called Nim for some time now. Nim is played as follows:

The starting position has a number of heaps, all containing some, not necessarily equal, number of beads.

The players take turns chosing a heap and removing a positive number of beads from it.

The first player not able to make a move, loses.

Arthur and Caroll really enjoyed playing this simple game until they recently learned an easy way to always be able to find the best move:

Xor the number of beads in the heaps in the current position (i.e. if we have 2, 4 and 7 the xor-sum will be 1 as 2 xor 4 xor 7 = 1).

If the xor-sum is 0, too bad, you will lose.

Otherwise, move such that the xor-sum becomes 0. This is always possible.

It is quite easy to convince oneself that this works. Consider these facts:

The player that takes the last bead wins.

After the winning player's last move the xor-sum will be 0.

The xor-sum will change after every move.

Which means that if you make sure that the xor-sum always is 0 when you have made your move, your opponent will never be able to win, and, thus, you will win.

Understandibly it is no fun to play a game when both players know how to play perfectly (ignorance is bliss). Fourtunately, Arthur and Caroll soon came up with a similar game, S-Nim, that seemed to solve this problem. Each player is now only allowed to remove a number of beads in some predefined set S, e.g. if we have S =(2, 5) each player is only allowed to remove 2 or 5 beads. Now it is not always possible to make the xor-sum 0 and, thus, the strategy above is useless. Or is it?

your job is to write a program that determines if a position of S-Nim is a losing or a winning position. A position is a winning position if there is at least one move to a losing position. A position is a losing position if there are no moves to a losing position. This means, as expected, that a position with no legal moves is a losing position.

Input

Input consists of a number of test cases. For each test case: The first line contains a number k (0 < k ≤ 100 describing the size of S, followed by k numbers si (0 < si ≤ 10000) describing S. The second line contains a number m (0 < m ≤ 100) describing the number of positions to evaluate. The next m lines each contain a number l (0 < l ≤ 100) describing the number of heaps and l numbers hi (0 ≤ hi ≤ 10000) describing the number of beads in the heaps. The last test case is followed by a 0 on a line of its own.

Output

For each position: If the described position is a winning position print a 'W'.If the described position is a losing position print an 'L'. Print a newline after each test case.

Sample Input

2 2 5

2 5 12

3 2 4 7

4 2 3 7 12

5 1 2 3 4 5

2 5 12

3 2 4 7

4 2 3 7 12

Sample Output

LWW

WWL

//很郁闷，因为题目看不懂，只能看别人的代码。才知道意思……

//题意：有一个集合有S个数。玩N次取石子游戏，每次只能取S集合里的数个石子。求判先手胜负。

1 //递归写的
2 #include
3 using namespace std;
4
5 int t;
6 int num[101];
7 int sg[10001];
8
9 int Get_sg(int n)
10 {
11     if(n==0) return 0;
12     int i;
13     bool mex[101]={0};
14     for(i=0;i15     {
16         if(n>=num[i])
17         {
18             int temp=n-num[i];
19             if(sg[temp]==-1)
20             {
21                 sg[temp]=Get_sg(temp);
22             }
23             mex[sg[temp]]=true;
24         }
25     }
26     for(i=0;;i++)
27     {
28         if(!mex[i])
29         {
30             return i;
31         }
32     }
33 }
34
35 int main()
36 {
37     int i,l,m,k;
38     while(scanf("%d",&t)!=EOF,t)
39     {
40         for(i=0;i41         {
42             scanf("%d",&num[i]);
43         }
44         scanf("%d",&l);
45         memset(sg,-1,sizeof(sg));
46         while(l--)
47         {
48             int temp=0;
49             scanf("%d",&k);
50             while(k--)
51             {
52                 scanf("%d",&m);
53                 if(sg[m]==-1)
54                 {
55                     sg[m]=Get_sg(m);
56                 }
57                 temp^=sg[m];
58             }
59              if(temp)
60             {
61                 printf("W");
62             }
63             else
64             {
65                 printf("L");
66             }
67         }
68         putchar('\n');
69     }
70     return 0;
71 }
72

煙雨默嘫 2012-03-17 14:46 发表评论

HDU 2074叠筐

煙雨默嘫 — Sat, 17 Mar 2012 06:38:00 GMT

叠筐

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

需要的时候，就把一个个大小差一圈的筐叠上去，使得从上往下看时，边筐花色交错。这个工作现在要让计算机来完成，得看你的了。

Input

输入是一个个的三元组，分别是，外筐尺寸n（n为满足0

Output

输出叠在一起的筐图案，中心花色与外筐花色字符从内层起交错相叠，多筐相叠时，最外筐的角总是被打磨掉。叠筐与叠筐之间应有一行间隔。

Sample Input

11 B A

5 @ W

Sample Output

AAAAAAAAA

ABBBBBBBBBA

ABAAAAAAABA

ABABBBBBABA

ABABAAABABA

ABABABABABA

ABABAAABABA

ABABBBBBABA

ABAAAAAAABA

ABBBBBBBBBA

AAAAAAAAA

@@@

@WWW@

@W@W@

@WWW@

@@@

1 #include<iostream>

2 using namespace std;
3
4 char map[85][85];
5
6 int main()
7 {
8     int n,i,j,mark;
9     char a,b,t=0;
10     while(scanf("%d %c %c",&n,&a,&b)!=EOF)
11     {
12         if(t) putchar('\n');
13         if((n-1)%4)
14         {
15             t=a;
16             a=b;
17             b=t;
18         }
19         t=a,mark=1;
20         for(i=0;i<=n/2;i++)
21         {
22             t=a;
23             mark=1;
24             for(j=0;j25             {
26                 if(n!=1&&i==0&&(j==0||j==n-1))//注意n==1的时候
27                 {
28                     putchar(' ');
29                     map[i][j]=' ';
30                     continue;
31                 }
32                 map[i][j]=t;
33                 putchar(t);
34                 if(i>j||j>=(n-1)-i)//字符变换的范围
35                 {
36                     if(mark)
37                     {
38                         t=b;
39                         mark=0;
40                     }
41                     else
42                     {
43                         t=a;
44                         mark=1;
45                     }
46                 }
47             }
48             putchar('\n');
49         }
50         for(i=n/2-1;i>=0;i--)
51         {
52             for(j=0;j53             {
54                 printf("%c",map[i][j]);
55             }
56             putchar('\n');
57         }
58     }
59     return 0;
60 }

煙雨默嘫 2012-03-17 14:38 发表评论

C++简单练习

煙雨默嘫 — Sun, 11 Mar 2012 12:23:00 GMT

其实c++不懂，刚开始看，有点稀里糊涂的，虽然不是计算机专业的，不过我觉得要自学，
所以顺便帮同学。最后没做出来，
请了我们班的高手，就做出来了，贴贴代码

定义一个用户管理类，管理用户名和密码，输入用户名时输出其密码。

提示：定义Cuser类，含有name、pwd 2个数据成员，构造函数、Getname()、Getpwd() 3个成员函数。

定义一个对象数组并对其初始化，对象数组中的每个元素存储一个用户信息。

输入用户名后，在数组中查找，找到后输出其密码，找不到时输出错误信息。*/

注意：构造函数不能调用==！

#include<iostream>
#include<string>
using namespace std;

class Cuser
{
private:
    string name;
    int pwd;
public:
    Cuser()
    {}
    string Getname()
    {
        return name;
    }
    int Getpwd()
    {
        return pwd;
    }
    void Insetdata(string str,int p)
    {
        name=str;
        pwd=p;
    }
};

int main()
{
    string str;
    Cuser Cus[3];
    int i,f;

    Cus[0].Insetdata("liny",123);
    Cus[1].Insetdata("abd",12345);
    Cus[2].Insetdata("oweu",3232);
    while(cin>>str)
    {
        f=0;
        for(i=0;i<3;i++)
        {
            if(Cus[i].Getname()==str)
            {
                cout<<"密码是："<<endl;
                cout<<Cus[i].Getpwd()<<endl;
                f=1;
            }
        }
        if(!f)
        {
            cout<<"没有信息"<<endl;
        }
    }
    return 0;
}

煙雨默嘫 2012-03-11 20:23 发表评论

【转】HDU上DP问题汇总

煙雨默嘫 — Thu, 08 Mar 2012 12:38:00 GMT

转载自 superkiki1989

最终编辑 youmingke

http://acm.hdu.edu.cn/showproblem.PHP?pid=2955
     背包[bao];第一次做的时候把概率[gai lv]当做背包[bao](放大100000倍化为整数):在此范围[fan wei]内最多能抢多少钱   最脑残的是把总的概率[gai lv]以为是抢N家银行的概率[gai lv]之和… 把状态[zhuang tai]转移方程写成了f[j]=max{f[j],f[j-q[i].v]+q[i].money}(f[j]表示在概率[gai lv]j之下能抢的大洋);

     正确的方程是:f[j]=max(f[j],f[j-q[i].money]*q[i].v)   其中,f[j]表示抢j块大洋的最大的逃脱概率[gai lv],条件[tiao jian]是f[j-q[i].money]可达,也就是之前抢劫过;
     始化为:f[0]=1,其余初始化[chu shi hua]为-1   (抢0块大洋肯定不被抓嘛)

最大报销额 http://acm.hdu.edu.cn/showproblem.php?pid=1864
     又一个背包[bao]问题[wen ti],对于每张发票,要么报销,要么不报销,0-1背包[bao],张数即为背包[bao];
     转移方程:f[j]=max(f[j],f[j-1]+v[i]);
     恶心地方:有这样的输入[shu ru]数据[shu ju] 3 A:100 A:200 A:300

最大连续[lian xu]子序列 http://acm.hdu.edu.cn/showproblem.php?pid=1231
     状态[zhuang tai]方程:sum[i]=max(sum[i-1]+a[i],a[i]);最后从头到尾扫一边
     也可以写成:
                 Max=a[0];
                 Current=0;
                 for(i=0;i                 {
                     if(Current<0)
                         Current=a[i];
                     else
                         Current+=a[i];
                     if(Current>Max)
                         Max=Current;
                 }

max sum http://acm.hdu.edu.cn/showproblem.php?pid=1003
     同上,最大连续[lian xu]子序列

Largest Rectangle http://acm.hdu.edu.cn/showproblem.php?pid=1506
     对于每一块木板,Area=height[i]*(j-k+1)   其中,j<=x<=k,height[x]>=height[i];找j,k成为关键,一般方法[fang fa]肯定超时[chao shi],利用动态[dong tai]规划,如果它左边高度大于等于它本身,那么它左边的左边界[bian jie]一定满足这个性质,再从这个边界[bian jie]的左边迭代[die dai]下去
     for(i=1;i<=n;i++)
         {
             while(a[l[i]-1]>=a[i])
                 l[i]=l[l[i]-1];

         }

     for(i=n;i>=1;i--)
         {
             while(a[r[i]+1]>=a[i])
                 r[i]=r[r[i]+1];
         }

City Game http://acm.hdu.edu.cn/showproblem.php?pid=1505
     1506的加强版,把2维转换[zhuan huan]化成以每一行底,组成的最大面积;(注意处理连续[lian xu]与间断的情况[qing kuang]);

Bone Collector http://acm.hdu.edu.cn/showproblem.php?pid=2602
     简单0-1背包[bao],状态[zhuang tai]方程:f[j]=max(f[j],f[j-v[i]]+w[i])

Super Jumping   http://acm.hdu.edu.cn/showproblem.php?pid=1087
     最大递增子段[zi duan]和,状态[zhuang tai]方程:sum[j]=max{sum[i]}+a[j]; 其中,0<=i<=j,a[i]
命运http://acm.hdu.edu.cn/showproblem.php?pid=2571
     状态[zhuang tai]方程:sum[i][j]=max{sum[i-1][j],sum[i][k]}+v[i][j];其中1<=k<=j-1,且k是j的因子

Monkey And Banana      http://acm.hdu.edu.cn/showproblem.php?pid=1069
     状态[zhuang tai]方程:f[j]=max{f[i]}+v[j];其中,0<=i<=j,w[i]
Big Event in HDU http://acm.hdu.edu.cn/showproblem.php?pid=1171
     一维背包[bao],逐个考虑每个物品带来的影响,对于第i个物品:if(f[j-v[i]]==0) f[j]=0;
     其中,j为逆序循环[xun huan],且j>=v[i]

数塔http://acm.hdu.edu.cn/showproblem.php?pid=2084
     自底向上[zi di xiang shang]:dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+v[i][j];

免费馅饼http://acm.hdu.edu.cn/showproblem.php?pid=1176
     简单数塔
     自底向上[zi di xiang shang]计算:dp[i][j]=max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+v[i][j];处理边界[bian jie]

I Need A Offer http://acm.hdu.edu.cn/showproblem.php?pid=1203
     简单0-1背包[bao],题目要求的是至少收到一份Offer的最大概率[gai lv],我们得到得不到的最小概率[gai lv]即可,状态[zhuang tai]转移方程:f[j]=min(f[j],f[j-v[i]]*w[i]);其中,w[i]表示得不到的概率[gai lv],(1-f[j])为花费j元得到Offer的最大概率[gai lv]

FATE http://acm.hdu.edu.cn/showproblem.php?pid=2159
     二维完全背包[bao],第二层跟第三层的要顺序循环[xun huan];(0-1背包[bao]逆序循环[xun huan]);状态[zhuang tai]可理解为,在背包[bao]属性[shu xing]为 {m(忍耐度), s(杀怪个数)} 里最多能得到的经验值,之前的背包[bao]牺牲体积,这个背包[bao]牺牲忍耐度跟个数
     注意: 最后扫的时候外层循环[xun huan]为忍耐度,内层循环[xun huan]为杀怪个数,因为题目要求出剩余忍耐度最大,没有约束[yue shu]杀怪个数,一旦找到经验加满的即为最优解;
     状态[zhuang tai]转移方程为: f[j][k]=max(f[j][k],f[j-v[i]][k-1]+w[i]); w[i]表示杀死第i个怪所得的经验值,v[i]表示消耗的忍耐度

How To Type http://acm.hdu.edu.cn/showproblem.php?pid=2577
     用两个a,b数组[shu zu]分别记录Caps Lock开与关时打印第i个字母的最少操作步骤;
     而对于第i个字母的大小写还要分开讨论:
     Ch[i]为小写: a[i]=min(a[i-1]+1,b[i-1]+2);不开灯直接字母,开灯则先关灯再按字母,最后保持不开灯;     b[i]=min(a[i-1]+2,b[i-1]+2);不开灯则先按字母再开灯,开灯则Shift+字母(比关灯,按字母再开灯节省步数),最后保持开灯;
     Ch[i]为大写: a[i]=min(a[i-1]+2,b[i-1]+2); b[i]=min(a[i-1]+2,b[i-1]+1)

     最后,b[len-1]++,关灯嘛O(∩_∩)O~

Coins http://acm.hdu.edu.cn/showproblem.php?pid=2844
     类似于HDU1171 Big Event In HDU,一维DP,可达可不达

Beans http://acm.hdu.edu.cn/showproblem.php?pid=2845
     横竖分别求一下不连续[lian xu]的最大子段[zi duan]和;
     状态[zhuang tai]方程: Sum[i]=max(sum[j])+a[i];其中,0<=j
Largest Submatrix http://acm.hdu.edu.cn/showproblem.php?pid=2870
     枚举[mei ju]a,b,c 最大完全子矩阵,类似于HDU1505 1506

Matrix Swapping II http://acm.hdu.edu.cn/showproblem.php?pid=2830
最大完全子矩阵,以第i行为底,可以构成的最大矩阵,因为该题可以任意移动列,所以只要大于等于height[i]的都可以移动到一起,求出height>=height[i]的个数即可,这里用hash+滚动,先求出height[i]出现的次数,然后逆序扫一遍hash[i]+=hash[i+1];

最少拦截系统[xi tong]http://acm.hdu.edu.cn/showproblem.php?pid=1257
     两种做法,一是贪心,从后往前贪;二是DP;
     if(v[i]>max{dp[j]})   (0<=j     dp[len++]=v[i];

Common Subsequence http://acm.hdu.edu.cn/showproblem.php?pid=1159
     经典DP,最长公共子序列
     Len[i][j]={len[i-1][j-1]+1,(a[i]==b[j]); max(len[i-1][j],len[i][j-1])}
     初始化[chu shi hua]的优化:
     for(i=0;i             for(j=0;j                 len[i][j]=0;
         for(i=1;i<=a;i++)
             for(j=1;j<=b;j++)
                 if(ch1[i-1]==ch2[j-1])
                     len[i][j]=len[i-1][j-1]+1;
                 else
                     len[i][j]=max(len[i-1][j],len[i][j-1]);

★ 搬寝室http://acm.hdu.edu.cn/showproblem.php?pid=1421
     状态[zhuang tai]Dp[i][j]为前i件物品选j对的最优解
     当i=j*2时,只有一种选择[xuan ze]即 Dp[i-2][j-1]+(w[i]-w[i-1])^2
     当i>j*2时,Dp[i][j] = min(Dp[i-1][j],Dp[i-2][j-1]+(w[j]-w[j-1])^2)

★ Humble Numbers http://acm.hdu.edu.cn/showproblem.php?pid=1058
     如果一个数是Humble Number,那么它的2倍,3倍,5倍,7倍仍然是Humble Number
     定义F[i]为第i个Humble Number
     F[n]=min(2*f[i],3*f[j],5*f[k],7*f[L]), i,j,k,L在被选择[xuan ze]后相互移动
     (通过此题理解到数组[shu zu]有序特性)

★ Doing Homework Again http://acm.hdu.edu.cn/showproblem.php?pid=1789
     这题为贪心,经典题;
     切题角度,对于每个任务[ren wu]要么在截至日期前完成要么被扣分;所以考虑每个人物的完成情况[qing kuang]即可;由于每天只能完成一个任务[ren wu],所以优先考虑分值较大的任务[ren wu],看看该任务[ren wu]能不能完成,只要能完成,即使提前完成,占了其他任务[ren wu]的完成日期也没关系,因为当前任务[ren wu]的分值最大嘛,而对于能完成的任务[ren wu]能拖多久就拖多久,以便腾出更多时间完成其他任务[ren wu];

How Many Ways http://acm.hdu.edu.cn/showproblem.php?pid=1978
     两种D法,一是对于当前的点,那些点可达;二是当前点可达那些点;
     明显第二种方法[fang fa]高,因为第一种方法[fang fa]有一些没必要的尝试;
     Dp[i][j]+=Dp[ii][jj]; (map[ii][jj]>=两点的曼哈顿距离)
     值得优化的地方,每两点的曼哈顿距离可能不止求一次,所以预处理一下直接读取[du qu]

珍惜现在感恩生活http://acm.hdu.edu.cn/showproblem.php?pid=2191
     每个物品最多可取n件,多重[duo zhong]背包[bao];
     利用二进制[er jin zhi]思想,把每种物品转化为几件物品,然后就成为了0-1背包[bao]

Piggy-Bank http://acm.hdu.edu.cn/showproblem.php?pid=1114
     完全背包[bao];常规背包[bao]是求最大值,这题求最小值;
     只需要修改[xiu gai]一下初始化[chu shi hua],f[0]=0,其他赋值[fu zhi]为+∞即可;
     状态[zhuang tai]转移方程:f[i][V]=max{f[i-1][V],f[i-1][V-k*v[i]]+k*w[i]},其中0<=k*v[i]<=V

★ Max Sum Plus Plus http://acm.hdu.edu.cn/showproblem.php?pid=1024
     1. 对于前n个数, 以v[n]为底取m段:
     当n==m时,Sum[m][n]=Sum[m-1][n-1]+v[n],第n个数独立[du li]成段;
当n>m时, Sum[m][n]=max{Sum[m-1][k],Sum[m][n-1]}+v[n]; 其中,m-1<=k2. 空间[kong jian]的优化:
         通过状态[zhuang tai]方程可以看出,取m段时,只与取m-1段有关,所以用滚动数组[shu zu]来节省空间[kong jian]

FatMouse’s Speed http://acm.hdu.edu.cn/showproblem.php?pid=1160
     要求:体重严格递增,速度严格递减,原始顺序不定
     按体重或者速度排序[pai xu],即顺数固定后转化为最长上升子序列问题[wen ti]
     Dp[i]表示为以第i项为底构成的最长子序列,Dp[i]=max(dp[j])+1,其中0<=jw[j]&&s[i]
Cstructing Roads http://acm.hdu.edu.cn/showproblem.php?pid=1025
     以p或者r按升序排列[pai lie]以后,问题[wen ti]转化为最长上升子序列
     题目数据[shu ju]量比较大,只能采取二分查找[cha zhao],n*log(n)的算法[suan fa]
用一个数组[shu zu]记录dp[]记录最长的子序列,len表示长度,如果a[i]>dp[len], 则接在后面,len++; 否则在dp[]中找到最大的j,满足dp[j]
FatMouse Chees http://acm.hdu.edu.cn/showproblem.php?pid=1078
     Dp思想,用记忆化搜索[sou suo];简单题,处理好边界[bian jie];

To the Max http://acm.hdu.edu.cn/showproblem.php?pid=1081
     最大子矩阵
     把多维转化为一维的最大连续[lian xu]子序列;(HDU1003)

龟兔赛跑http://acm.hdu.edu.cn/showproblem.php?pid=2059
未总结

★ Employment Planning http://acm.hdu.edu.cn/showproblem.php?pid=1158
     状态[zhuang tai]表示:     Dp[i][j]为前i个月的留j个人的最优解;Num[i]<=j<=Max{Num[i]};
                 j>Max{Num[i]}之后无意义,无谓的浪费记Max_n=Max{Num[i]};
     Dp[i-1]中的每一项都可能影响到Dp[i],即使Num[i-1]<     所以利用Dp[i-1]中的所有项去求Dp[i];
     对于Num[i]<=k<=Max_n,     当k                             当k>j时, 解雇   然后求出最小值
     Dp[i][j]=min{Dp[i-1][k…Max_n]+(招聘,解雇,工资);

Dividing http://acm.hdu.edu.cn/showproblem.php?pid=1059
     一维Dp   Sum为偶数的时候判断Dp[sum/2]可不可达

Human Gene Factions http://acm.hdu.edu.cn/showproblem.php?pid=1080
状态[zhuang tai]转移方程:
f[i][j]=Max(f[i-1][j-1]+r[a[i]][b[j]], f[i][j-1]+r[‘-‘][b[j]],f[i-1][j]+r[a[i]][‘-‘]);

★ Doing Homework http://acm.hdu.edu.cn/showproblem.php?pid=1074
     这题用到位压缩[ya suo];
     那么任务[ren wu]所有的状态[zhuang tai]有2^n-1种
     状态[zhuang tai]方程为:Dp[next]=min{Dp[k]+i的罚时} 其中,next=k+(1<>i的奇偶[qi ou]性决定状态[zhuang tai]k
具体实现为: 对每种状态[zhuang tai]遍历[bian li]n项任务[ren wu],如果第i项没有完成,则计算出Dp[next]的最优解

Free DIY Tour http://acm.hdu.edu.cn/showproblem.php?pid=1224
     简单的数塔Dp,考察的是细节的处理;
     Dp[i]=Max{Dp[j]}+v[i]   其中j->i为通路[tong lu];
     v[n+1]有没有初始化[chu shi hua],Dp数组[shu zu]有没有初始化[chu shi hua]
     这题不能用想当然的”最长路”来解决,这好像是个NP问题[wen ti] 解决不了的


重温世界杯http://acm.hdu.edu.cn/showproblem.php?pid=1422
这题的状态[zhuang tai]不难理解,状态[zhuang tai]表示为,如果上一个城市剩下的钱不为负,也就是没有被赶回杭电,则再考虑它对下一个城市的影响;如果上一个城市剩下的前加上当前城市的前大于当前城市的生活费,那么Dp[i]=Dp[i-1]+1;
值得注意的而是这题的数据[shu ju]为100000;不可能以每个城市为起点来一次Dp,时间复杂度[shi jian fu za du]为n^2;足已超时[chao shi];
我是这样处理的,在保存的数据[shu ju]后面再接上1…n的数据[shu ju],这样扫描[sao miao]一遍的复杂度为n;再加一个优化,当Dp[i]==n时,也就是能全部游完所有城市的时候,直接break;

Pearls http://acm.hdu.edu.cn/showproblem.php?pid=1300
     Dp[i]=min{Dp[j]+V},   0<=j
Zipper http://acm.hdu.edu.cn/showproblem.php?pid=1501
     Dp[i][j]=

★Fast Food http://acm.hdu.edu.cn/showproblem.php?pid=1227
     这里需要一个常识:在i到j取一点使它到区间[qu jian]每一点的距离之和最小,这一点为(i+j)/2用图形[tu xing]即可证明[zheng ming];
     Dp[i][j]=max{Dp[i-1][k]+cost[k+1][j]   其中,(i-1)<=k
Warcraft http://acm.hdu.edu.cn/showproblem.php?pid=3008
     比赛的时候这道DP卡到我网络[wang luo]中心停电!!! 卧槽~
     因为你没有回血效应,所以你挂掉的时间是一定的;
     用Dp[i][j]表示第i秒剩余j个单位[dan wei]的MP时怪物所剩的血量; 注意必须是剩余,也就是说,初始化[chu shi hua]的时候,DP[0][100]=100;   其他Dp[0]状态[zhuang tai]都不合法,因为没有开战的时候你的MP是满的
     以前的Dp都是利用前面得到的最优解来解决,而这题的麻烦点是MP在攻击过后要自动恢复x个单位[dan wei];用当前的状态[zhuang tai]的状态[zhuang tai]推下一状态[xia yi zhuang tai][zhuang tai],仔细想想也未尝不可;状态[zhuang tai]转移方程为:
     Dp[i+1][j-sk[k].mp+x]=min(Dp[i+1][j-sk[k].mp+x],Dp[i][j]+sk[k].at; 释放[shi fang]第K种技能,物理攻击可以看成是at=1,mp=0 的魔法;

Regular Words http://acm.hdu.edu.cn/showproblem.php?pid=1502
     F[a][b][c]=F[a-1][b][c]+F[a][b-1][c]+F[a][b][c-1];
     a>=b>=c;

Advanced Fruits http://acm.hdu.edu.cn/showproblem.php?pid=1503
     最长公共子序列的加强版
     posted

煙雨默嘫 2012-03-08 20:38 发表评论

STL中map用法详解

煙雨默嘫 — Thu, 08 Mar 2012 12:34:00 GMT

摘要: Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有... 阅读全文

煙雨默嘫 2012-03-08 20:34 发表评论

交换

煙雨默嘫 — Thu, 08 Mar 2012 01:07:00 GMT

//中间变量法
void swap1(int& a,int& b)
{
    int temp=a;
    a=b;
    b=temp;
}
//相互加减法
void swap2(int& a,int& b)
{
    a=a+b;//可能会溢出
    b=a-b;
    a=a-b;
}
//异或法
void swap3(int& a,int& b)
{
    a^=b;
    b^=a;
    a^=b;
}

煙雨默嘫 2012-03-08 09:07 发表评论