wyh123 - C++博客

HDOJ 2041(DP)

题目大意：有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

解题思路：用dp[i]表示走到第i级的方法数。
              那么走到第i级的最后一步只可能是两种，走一级或者两级，即dp[i]=dp[i-1]+dp[i-2]

              注意，开始的时候是在第一级开始的，所以要求的是dp[n-1]

              写完之后才发现它是斐波那契数列啊~~囧~！！！

代码：

#include <iostream>
2

#include <cstdio>
3

#include <cmath>
4

using namespace std;
6

long long sum[45];
8

int T,n;
9

int main()
11

{ sum[1]=1;
12

sum[2]=2;
13

for (int i=3; i<=40; i++)
14

sum[i]=sum[i-1]+sum[i-2];
15

cin >> T;
16

while (T--)
17

{ cin >> n;
18

cout << sum[n-1] << endl;
19

}
20

return 0;
21

}
22

posted @ 2011-07-31 10:58 wyh 阅读(213) | 评论 (0) | 编辑收藏

HDOJ 2067(DP)

题目大意：小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?

解题思路：很明显的DP，dp[i][j]表示走到(i,j)的路径数。
              转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1](i!=j);
                            dp[i][j]=0(i=j);
              这里面要注意的是这里的(0,0)表示的是格子，而方程里面的(i,j)表示的是下格点
              所以事实上(n,n)换成格子表示是(n+1,n+1)
              而所有的对角线上的格点也是来源于其左边和上面的格点所以ans=dp[n+1][n]+dp[n][n+1]

代码：

#include <iostream>
2

#include <cstdio>
3

#include <cstring>
4

#include <cmath>
5

using namespace std;
7

int m,n,k;
9

long long dp[40][40];
10

int main()
12

{ dp[0][0]=0;
13

for (int i=0; i<=37; i++)
14

{ dp[0][i]=1; dp[i][0]=1;
15

}
16

for(int i=1; i<=37; i++)
17

for(int j=1; j<=37; j++)
18

if(i != j)
19

dp[i][j] = dp[i-1][j] + dp[i][j-1];
20

else
22

dp[i][j] = 0;
23

k=1;
24

while(cin >> n)
25

{if (n==-1) break;
26

cout <<k <<" "<<n<< " " <<dp[n+1][n]+dp[n][n+1] << endl; k++;}
27

return 0;
29

}
30

其实勒，这道题是由于数据量比较小，所以可以使用DP+long long来解决，但是其本质上还是属于一个排列组合问题，如果数据量变大的话，需要用到大数来解决。

posted @ 2011-07-31 10:29 wyh 阅读(452) | 评论 (1) | 编辑收藏

HDOJ 1267(DP)

题目描述：给出m个H和n个D，求由这m个H和n个D组成的字符串满足“从左到右扫描该串，字符H的累计数总是不小于字符D的累计数”的方案数

解题思路：DP
              显然，这里面可以把状态划分为dp[i][j]，表示i个H和n个D含有多少成功的方案数。
              那么它的转移方程就是： dp[i][j]=dp[i-1][j]+dp[i][j-1];
              1）所有的串一定是以H或者D结尾
              3）i>j,则dp[i][j]=0;
              3）在成功的dp[i-1][j]后面中加上H，则这个是必然成立的。
              4）关键是在成功的dp[i][j-1]后面中加上D。
                   如果此时恰好是i=j-1的话，加上D就错了~~，但问题是当i=j-1的时候i<j的根本不满足2)，所以这个无须考虑的。
                   那么这里只有可能是i>j-1，所以加上了D，最坏的情况就是i=j，不会出现不满足题意的情况。
              5）有人会认为可以通过一个不成功的串可以通过向其中加上一个H使其满足题设：
                   Eg：HDD+H=HDHD
                   这里给的反例是HDH+D=HDHD
                   其实很简单，HDD和HDH所出现的概率是相等的，所以一个不成功的串其中插入H势必会找到一个相对应的成功的串后面加上D

                *写的时候也是凭感觉写出来，一做发现对了。后来才仔细的想了一下，其实转移也算是比较别扭的，不过总的来说这不是一道很难的DP题。

代码：

#include <iostream>
2

#include <cstdio>
3

#include <cstring>
4

#include <cmath>
5

using namespace std;
7

int m,n;
9

long long dp[50][50];
10

int main()
12

{ for(int i=1; i<=20; i++)
13

dp[i][1] = i;
14

for(int i=2; i<=20; i++)
15

for(int j=2; j<=20; j++)
16

if(i >= j)
17

dp[i][j] = dp[i][j-1] + dp[i-1][j];
18

else
19

dp[i][j] = 0;
20

while(cin >> m >> n)
21

cout << dp[m][n] << endl;
22

return 0;
24

}
25

posted @ 2011-07-31 00:15 wyh 阅读(177) | 评论 (0) | 编辑收藏

HDOJ 1131(Catanlan数)

题目大意：给你n个不同的节点，求可以构成多少种二叉树。

解题思路：1）n个节点构成多少种二叉树的问题显然是卡特兰数问题。
              递推式：Cn=Cn-1*[(4n-2)/(n+1)]
              通项式：Cn=1/(n-1)*C(n-2,2n-4)
              2）注意，是n个不同的点，所以点变换顺序形成的二叉树不同故：SUM=Cn*n！

修改了1130的代码...

#include <iostream>
2

#include <cstdio>
3

#include <algorithm>
4

#include <cstring>
5

using namespace std;
7

#define MAX 105
8

#define BASE 10000
9

typedef int myType[MAX+10];
10

void multiply ( int a[], int Max, int b ) //大数乘小数
11

{ int i,array=0;
12

for (i=Max-1; i>=0; i--)
13

{
14

array+=b*a[i];
15

a[i] = array%BASE;
16

array /= BASE;
17

}
18

}
19

void divide ( int a[], int Max, int b ) //大数除小数
20

{
21

int i,div=0;
22

for (i=0;i<Max; i++)
23

{
24

div = div*BASE + a[i];
25

a[i] = div / b;
26

div %= b;
27

}
28

}
29

void outPut ( myType ctl[MAX] ,int N )
30

{
31

int i = 0;
32

while ( i < MAX && ctl[N][i] == 0 )
33

{
34

i ++ ; //去前导0
35

}
36

cout << ctl[N][i++];
37

while ( i < MAX )
38

{
39

printf ( "%04d", ctl[N][i++] );
41

}
42

cout << endl;
43

}
44

void setNum ( myType ctl[MAX] )
45

{
46

memset ( ctl[1], 0, MAX * sizeof ( int ) );
47

ctl[1][MAX-1] = 1;
48

for ( int i = 2; i < 101; i ++ )
49

{
50

memcpy ( ctl[i], ctl[i-1], MAX * sizeof ( int ) );
51

multiply ( ctl[i], MAX, 4 * i - 2 );
52

divide ( ctl[i], MAX, i + 1 );
53

}
54

}
55

myType ctl[MAX];
56

int main()
57

{
58

setNum ( ctl );
59

int N;
60

while ( cin >> N ) { if (N==0) break;
61

else
62

{for (int p=1; p<=N; p++) multiply ( ctl[N], MAX, p );
63

outPut ( ctl, N ); }
64

}
65

return 0;
66

}
67

posted @ 2011-07-30 11:18 wyh 阅读(212) | 评论 (0) | 编辑收藏

HDOJ 1130(Catanlan数)

题目大意：给出一棵n节点的二叉树，求其组成的总数。

解题思路：典型的卡特兰数裸的题目，详见：http://baike.baidu.com/view/2499752.htm
              公式：Cn=1/(n-1)*C(n-2,2n-4);

              由于是大数的卡特兰数，涉及到一个计算问题，比较麻烦。

              不过由于以前在其他地方应用过，有MiYu的大数版卡特兰数模版，就直接套用了。
              我找不到原来的地址了，不过有别人转载的文章：http://blog.csdn.net/geniusluzh/article/details/5860975

   这里的代码的MiYu的代码，仅供参考。

#include <iostream>
2

#include <cstdio>
3

#include <algorithm>
4

#include <cstring>
5

using namespace std;
7

#define MAX 105
8

#define BASE 10000
9

typedef int myType[MAX+10];
10

void multiply ( int a[], int Max, int b ) //大数乘小数
11

{ int i,array=0;
12

for (i=Max-1; i>=0; i--)
13

{
14

array+=b*a[i];
15

a[i] = array%BASE;
16

array /= BASE;
17

}
18

}
19

void divide ( int a[], int Max, int b ) //大数除小数
20

{
21

int i,div=0;
22

for (i=0;i<Max; i++)
23

{
24

div = div*BASE + a[i];
25

a[i] = div / b;
26

div %= b;
27

}
28

}
29

void outPut ( myType ctl[MAX] ,int N )
30

{
31

int i = 0;
32

while ( i < MAX && ctl[N][i] == 0 )
33

{
34

i ++ ; //去前导0
35

}
36

cout << ctl[N][i++];
37

while ( i < MAX )
38

{
39

printf ( "%04d", ctl[N][i++] );
41

}
42

cout << endl;
43

}
44

void setNum ( myType ctl[MAX] )
45

{
46

memset ( ctl[1], 0, MAX * sizeof ( int ) );
47

ctl[1][MAX-1] = 1;
48

for ( int i = 2; i < 101; i ++ )
49

{
50

memcpy ( ctl[i], ctl[i-1], MAX * sizeof ( int ) );
51

multiply ( ctl[i], MAX, 4 * i - 2 );
52

divide ( ctl[i], MAX, i + 1 );
53

}
54

}
55

myType ctl[MAX];
56

int main()
57

{
58

setNum ( ctl );
59

int N;
60

while ( cin >> N ) // 这里根据各题要求需要做相应变化
61

{ outPut ( ctl, N ); }
62

return 0;
63

}
64

posted @ 2011-07-29 23:36 wyh 阅读(330) | 评论 (0) | 编辑收藏

2011/7/29

        今天，去HDOJ上的ACM steps上切题了，切的好辛苦.....
        大部分的题目并不难，这凸显了自己的代码能力很不过关，需要写多点题，努力提高代码的稳定性。
        明天，后天是SCAU暑假培训的最后两场个人赛了，....，在保的前提下要力争把排位冲前点，主要是
心态，一定要放平稳要调整好。
        希望八月份的组队赛能够有更好的进步，我们希望我们能够完成自己的目标。


                                                                                               By SCAU_3_idiots' wyh

posted @ 2011-07-29 20:54 wyh 阅读(87) | 评论 (0) | 编辑收藏

HDOJ 1018(log()+Stirling公式)

题目大意：给出一个n，叫你求n!的位数。

解题思路：1）快速求n！的位数方法：digits=lg(n!)+1=lg(n)+lg(n-1)+.......+lg(1)+1;
在我的意料之外的是，居然化成这样后，一个for扫过去它就过了

但在记忆里貌似有一道公式可以直接求n!阶层...最后在师兄的提醒下找到啦！！！！！
2）利用Stirling公式化简为：

                    lg(n!)=lg(sqrt(2*pi*n))+n*lg(n/e)

               结果是0ms...今天的收获还可以，又知道了斯特林公式这种东西

#include <cstdio>
2

#include <cmath>
3

#include <iostream>
4

using namespace std;
6

const double PI=3.14159265357,e=2.7182818284;
8

int t,n;
9

int main()
11

{ scanf("%d",&t);
12

while(t--)
13

{
14

scanf("%d",&n);
15

printf("%d\n",(int)(log10(sqrt(2*PI*n))+n*log10(n/e))+1);
16

}
17

return 0;
18

}
19

posted @ 2011-07-29 20:37 wyh 阅读(250) | 评论 (0) | 编辑收藏

HDOJ 2674（N！）

题目大意：求n！ MOD 2009的答案

解题方法：1）n!%2009=(n%2009)*[(n-1)%2009]*........*(1%2009)
              2) 2009=41*7*7
              3）当n>=41的时候均为0，剩下的直接算。

    太high了，做了一天，终于碰到一道可以瞬秒的题目了，o(∩_∩)o

#include <iostream>
2

#include <cstdio>
3

#include <cmath>
4

using namespace std;
6

int s,n;
8

int main()
10

{ while (~scanf("%d",&n))
11

{ s=1;
12

if (n<=41)
13

for (int i=1; i<=n; i++)
14

{s=s*i;
15

s=s%2009;
16

}
17

else s=0;
18

cout << s << endl;
19

}
20

return 0;
21

}
22

posted @ 2011-07-29 19:46 wyh 阅读(163) | 评论 (0) | 编辑收藏

HDOJ 3625（第一类Stirling数）

题目大意：给出n个房间，打开房间门的办法有撞击和用钥匙打开，编号1的门不能撞击。已知每个房间里有n间房间中某间房子的钥匙，问在k次撞击之内，求把房间门全部打开的概率。

解题思路：1）第一扇门必须撞开。
              2）当钥匙无法打开关闭的门的时候，必须继续采取撞开的方式
              3）编号1的门不能撞击。
              3）到这里，题目演变成了求在n间房间中形成少于k个环的概率（编号1的门不能独立成环）。
              .................然后，我就不会做了。接着上网百度了一下就n个元素划分成k个环的方法~~，.....第一次接触了所谓的第一类斯特林数。
              斯特林数学习资料：http://www.mathchina.com/usr1PvjRWKew/5/2/CBB9CCD8C1D6CAFD_1178220836.bmp
              或者：/Files/wyh123/CBB9CCD8C1D6CAFD_1178220877.doc
              继续思路：
              4）在这里我们很容易得出n把钥匙的排列数是n！，只要我们求出所有可能的方案数，则概率p=sum/n!
              5）形成少于k个环的总数有s(n,k)+s(n,k-1)+.......+s(n,1)
              6）由于编号1的房间不能独立成环，所以要计算出编号1房间独立成环的成功方案数：s(n-1,k-1)+s(n-1,k-2)+.....s(n-1,2)+s(n-1,1)
              7）总方案就为：sum=s(n,k)+s(n,k-1)+.....+s(n,1)-(s(n-1,k-1)+s(n-1,k-2)+.....s(n-1,2)+s(n-1,1))

       到这里问题解决。发现自己的数学基础还是不行啊，仍需加油，补充！！！

#include <iostream>
2

#include <cstring>
3

#include <cstdlib>
4

#include <cmath>
5

#include <cstdio>
6

#include <algorithm>
7

using namespace std;
9

long long f[30];
11

long long s[30][30];
12

int i,k,n,T;
13

double sum;
14

void init()
16

{
17

int i,j;
18

f[1]=1;
19

for(i=2;i<30;i++)
20

f[i]=i*f[i-1];
21

for(i=0;i<30;i++)
22

s[i][0]=0;
23

s[1][1]=1;
24

for(i=2;i<30;i++)
25

{
26

for(j=1;j<=i;j++)
27

s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j];
28

}
29

}
30

int main()
33

{ scanf("%d",&T);
34

init();
35

while(T--)
36

{
37

scanf("%d%d",&n,&k);
38

sum=0;
39

for(i=1;i<=k;i++)
40

sum=sum+s[n][i]-s[n-1][i-1];
41

sum=1.0*sum/f[n];
42

printf("%.4lf\n",sum);
43

}
44

return 0;
45

}
46

posted @ 2011-07-29 19:13 wyh 阅读(405) | 评论 (0) | 编辑收藏

HDOJ 1249（递推）

题目大意：给出n个三角形，求这些三角形最多能把平面划分成几个区域。

解题思路：1）画图：画出n=3的情况，20个。
              2）推规律：f(1)=2; f(2)=8=f(1)+6; f(3)=20=f(2)+12;
              3）写出递推式：f(n)=f(n-1)+6*(n-1);
              4）解出一般式：对上式进行迭代：f(n)=6*(n-1)+6*(n-2)+......+6*0+f(1)
                                                               =3*n*(n-1)+2;

我自己解释不清楚怎么找出规律的，凭一种直觉吧，画图很重要，画错了就没救了。
这里有一篇博文，对找规律有一个比较好的做法。
http://hi.baidu.com/%B7%E7%C0%D7%D1%B8%C1%D2/blog/item/8d2fcb92758f575fd0135e60.html

#include <iostream>
2

#include <cstdio>
3

using namespace std;
5

int T,n;
7

int main()
9

{ cin >> T;
10

while (T--)
11

{ cin >> n;
12

cout << 3*n*(n-1)+2<< endl;
13

}
14

return 0;
15

}
16

posted @ 2011-07-29 17:54 wyh 阅读(153) | 评论 (0) | 编辑收藏

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜

wyh123 解题思路记录和牢骚
C++博客 \| 首页 \| 发新随笔 \| 发新文章 \| 联系 \| 聚合 \| 管理	随笔：34 文章：1 评论：1 引用：0