1、UVa 10916  Factstone
Benchmark(对数函数的动–乘化加)

A –
数字三角形
题解:
设若getMax(i,j)表示点(i,j)到脚的最丰富路,
那么getMax(i,j)=max(getMax(i+1,j),getMax(i+1,j+1))+triangle[i][j];
用maxSum[i][j]存取中间结果;

  题意:给闹东,每个10年针对诺一个即电脑可支撑之字节位数,计算n!
< max(max 为目前电脑能代表的极度充分整数),求最好要命n.

  • 记忆化搜索

  思路:字节数k = (year – 1940) / 10, 
问题便转发成 n ! < 2 ^ k < (n + 1) !,
对少数止同取对数,因为log(a*b) = log(a) + log(b);所以log(n!) =
sum(log(i)), ( 1<= i <= n), 只要找到最好小的sum(log(i)) > k *
log(2) ,答案就是是i- 1.

365bet体育投注 1365bet体育投注 2

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=105;
int triangle[MAXN][MAXN];
int maxSum[MAXN][MAXN];
int n;
int getMax(int i,int j)
{
    if(i==n) return maxSum[i][j]=triangle[i][j];
    if(maxSum[i][j]!=-1) return maxSum[i][j];
    return maxSum[i][j]=max(getMax(i+1,j),getMax(i+1,j+1))+triangle[i][j];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            scanf("%d",&triangle[i][j]);
        }
    }
    memset(maxSum,-1,sizeof(maxSum));
    printf("%d\n",getMax(1,1));
}
 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int main()
 5 {
 6     int y;
 7     while (~scanf("%d", &y)&&y)
 8     {
 9         int n = (y - 1940) / 10;
10         double re = pow(2.0,1.0*n)*log(2.0);
11         double sum = 0;
12         for(int i=1;;i++)
13         {
14             sum += log(1.0*i);
15             if (sum > re)
16             {
17                 printf("%d\n", i - 1);
18                 break;
19             }
20         }
21     }
22     return 0;
23 }
  • 嵌套循环

View Code

2、zoj 1239 Hanoi Tower Troubles
Again!

#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=105;
int triangle[MAXN][MAXN];
int dp[MAXN][MAXN];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            scanf("%d",&triangle[i][j]);
        }
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        res=max(res,dp[n][i]);
    }
    printf("%d\n",res);
}

  题意:给出n个支柱,从第一个支柱开始放珠子,珠子编号从1从头,要求每个柱子上相邻两独珠子的与是平方数。

牛的故事
题意:
发生相同峰母牛,它每年开春不胜一条微微母牛。每头小母牛从第四单新春开始,每年开春啊酷一峰略母牛。请编程实现以第n年之早晚,共有多少头母牛?
题解:
设第n年母牛的数量为f(n),则第n年之牛的数相当原来的旧的母牛数量增长新出生之牛数量,旧的母牛数量等于f(n-1),因为小母牛从第四年开始才初老一峰母牛,也就是三年前之牛才发生非常多少母牛的力量,所以新来的牛的数目等三年前的牛的数码

  思路:

  • 记忆化搜索:

h(1) =
1:1独支柱时,放上1随后,2纵推广不上去了,不满足柱子上附近之球之和也平方数(1

  • 2 = 3,不是平方数);
    h(2) =
    3:2只支柱时,1及2列在1独支柱上,3足在1上面(1 + 3 = 4 = 2 ^
    2);
    h(i) = h(i – 1) + i + 1:i为奇数时,在i –
    1柱子的功底及长了一个柱子,这时候可以重放开i + 1单球;
    h(i) = h(i – 1) + i:i为偶数时,在i –
    1柱子的根基及平添了一个柱,这时候可以重新放开i个圆球。
    f(n) = f(n – 1) + (n + 1) / 2 + (n + 1)
    / 2 (n > 2)
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=60;
int sum[60];
int f(int n)
{
    if(sum[n]!=-1) return sum[n];
    if(n<5) return sum[n]=n;
    return sum[n]=f(n-1)+f(n-3);
}
int main()
{
    memset(sum,-1,sizeof(sum));
    int n;
    while(scanf("%d",&n)!=EOF,n)
    {
        printf("%d\n",f(n));
    }
}

365bet体育投注 3365bet体育投注 4

  • 嵌套循环:
 1 //h(1) = 1:1个柱子时,放上1之后,2就放不上去了,不满足柱子上相邻的球之和为平方数(1 + 2 = 3,不是平方数);
 2 //h(2) = 3:2个柱子时,1和2各放在1个柱子上,3可以放在1上面(1 + 3 = 4 = 2 ^ 2);
 3 //h(i) = h(i - 1) + i + 1:i为奇数时,在i - 1柱子的基础上增加了一个柱子,这时候可以再放i + 1个球;
 4 //h(i) = h(i - 1) + i:i为偶数时,在i - 1柱子的基础上增加了一个柱子,这时候可以再放i个球。
 5 // f(n) = f(n - 1) + (n + 1) / 2 + (n + 1) / 2    (n > 2)
 6 #include<iostream>
 7 using namespace std;
 8 int re[55];
 9 void Init()
10 {
11     re[1] = 1, re[2] = 3;
12     for (int i = 3; i <= 50; i++) re[i] = re[i - 1] + (i + 1) / 2 + (i + 1) / 2;
13 }
14 int main()
15 {
16     Init();
17     int t;
18     scanf("%d", &t);
19     while (t--)
20     {
21         int n;
22         scanf("%d", &n);
23         printf("%d\n", re[n]);
24     }
25     return 0;
26 }

View Code

#include<cstdio>
using namespace std;
const int MAXN=60;
int dp[60];
int main()
{
    for(int i=1;i<=4;i++)
    {
        dp[i]=i;
    }
    for(int i=5;i<55;i++)
    {
        dp[i]=dp[i-1]+dp[i-3];
    }
    int n;
    while(scanf("%d",&n)!=EOF,n)
    {
        printf("%d\n",dp[n]);
    }
}

3、hdu1465 不爱系列有(错排)

平面划分问题
注明出处,摘自
http://www.cnblogs.com/chaosheng/archive/2012/01/26/2329583.html
(1) n条直线最多分割平面问题
题目大致如:n条直线,最多得把平面分为小个区域。
浅析:可能你先便呈现了就题目,这最多是一律鸣初中的思考题。但一个类型的题目或者于简单的动手,才容易觉察规律。当有n-1长直线时,平面最多给分成了f(n-1)个区域。则第n漫漫直线要是切成的区域屡最好多,就亟须同各条直线相交且不可知起一样交点。这样就是见面博得n-1个交点。这些交点将第n长长的直线分为2条射线和n-2长条线断。而诸条射线和线断将因为有区域一分为二。这样虽差不多生了2+(n-2)个区域。
故:f(n)=f(n-1)+n=f(n-2)+(n-1)+n= ……=f(1)+1+2+……+n =n(n+1)/2+1
(2) 折线分割平面(hdu2050)
依据直线分平面可知,由交点决定了射线和线的条数,进而决定了新增的区域屡。当n-1漫漫折线时,区域屡也f(n-1)。为了要多的区域最多,则折线的个别限的线要和n-1久折线的尽头,即2*(n-1)条线段相交。那么新增的线段数为4*(n-1),射线数为2。但倘若小心的是,折线自相邻之星星点点线段只能多一个区域。
故f(n)=f(n-1)+4(n-1)+2-1
=f(n-1)+4(n-1)+1
=f(n-2)+4(n-2)+4(n-1)+2
……
=f(1)+4+4*2+……+4(n-1)+(n-1)
=2n^2-n+1
(3) 封闭曲线分平面问题
问题大致如在n条封闭曲线画在面及,而另外两漫长封闭曲线恰好相交于简单触及,且任何三修封闭曲线不交于同一些,问这些封闭曲线拿平面分割成的区域个数。
剖析:当n-1只圆时,区域屡也f(n-1).那么第n独全面就亟须跟眼前n-1个圆相交,则第n单到被分为2(n-1)段线段,增加了2(n-1)个区域。
故: f(n)=f(n-1)+2(n-1)=f(1)+2+4+……+2(n-1) =n^2-n+2
(4)平面分割空间问题(hdu1290)
由二维的分问题能,平面分割和线之间的交点有关,即交点决定射线和线条的条数,从而控制新增的区域屡。试想在三维中虽是否与平面的交线有关吗?当有n-1个面时,分割的空间数为f(n-1)。要起极多之空间数,则第n只面需和前方n-1独面相交,且未克生联袂之交线。即绝多起n-1
长条交线。而立n-1长交线把第n只面最多分割成g(n-1)个区域。(g(n)也(1)中之直线分平面的个数)此平面将故的上空一分为二,则太多增加g(n-1)个空中。
故:f(n)=f(n-1)+g(n-1) ps:g(n)=n(n+1)/2+1
=f(n-2)+g(n-2)+g(n-1)
……
=f(1)+g(1)+g(2)+……+g(n-1)
=2+(1*2+2*3+3*4+……+(n-1)n)/2+(n-1)
=(1+22+32+42+……+n2-1-2-3-……-n )/2+n+1
=(n^3+5n)/6+1
折线分割平面
题解:

  题意:求所起错排的错排方案往往。

#include<cstdio>
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",2*n*n-n+1);
    }
}

  思路:

平面分割球体
题解:

错排数公式:f[n] = (n – 1) * (f[n –
1] + f[n – 2]);
否得以这么想;
(1).f[1] = 0; f[2] = 1;
(2).如果确定f[n – 1] 和 f[n – 2]
的话。
f[n] 中肯定蕴含 f[n – 1] * (n –
1)种状况。
即把新入的一模一样查封同事先的任一一封交换,所取的必然是错排。

#include<cstdio>
int main()
{
    int n;
    while(~scanf("%d",&n))
    printf("%d\n",(n*n*n+5*n)/6+1);
}

365bet体育投注 5365bet体育投注 6

Working
out
题意:
有n*m个格子,
走过一个格子可以博得相应的分数.一个人数从左上角出发走及右手下角,只能望左走或者向下走;另一个口打左下角出发走及右上斗,只能为右侧走或发展走;中途两单人口只好发出相同差遇到,相遇的方格的分不到底进来,问两独人能够博得的尽酷分数;
题解:

 1 //错排数公式:f[n] = (n - 1) * (f[n - 1] + f[n - 2]);
 2 //也可以这么想;
 3 //(1).f[1] = 0; f[2] = 1;
 4 //(2).如果确定f[n - 1] 和 f[n - 2] 的话。
 5 //f[n] 中必然包含 f[n - 1] * (n - 1)种情况。 即把新加入的一封和之前的任一一封交换,所得到的必然是错排。
 6 //f[n] 中另一部分就是f[n - 2] * (n - 1) 即之前的 n - 1 封中有一封没有错排,把这封与新加入的一封交换进行错排。
 7 #include<iostream>
 8 using namespace std;
 9 long long re[25];
10 void Init()
11 {
12     re[1] = 0, re[2] = 1;
13     for (int i = 3; i <= 20; i++) re[i] = (re[i - 1] + re[i - 2])*(i - 1);
14 }
15 int main()
16 {
17     Init();
18     int n;
19     while (~scanf("%d", &n))
20     {
21         printf("%lld\n",re[n]);
22     }
23     return 0;
24 }
  • 坐个别只人不得不相遇一糟,所以遇到点不能够以两旁
  • 假设A向下同样步到相遇点,那么B不克通往达移步相同步到相遇点,为了只相遇一不善,A只能再累朝下活动;同时,B向右侧走,B继续往右侧走;
  • 同理,假设A向右侧一步走及相遇点,A继续朝着右侧走;B向上走相同步到相遇点,B继续朝右侧走;
  • 季单样子的dp
    dp1[i][j] := 从 (1, 1) 到 (i, j) 的极端深分数
    dp2[i][j] := 从 (i, j) 到 (n, m) 的卓绝特别分数
    dp3[i][j] := 从 (n, 1) 到 (i, j) 的无限可怜分数
    dp4[i][j] := 从 (i, j) 到 (1, m) 的最为酷分数
    虽说分的最特别价值对许者的星星种植状态

View Code

4、HDU 3625 Examining the
Rooms(第一类似斯特林数)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1005;
int dp1[MAXN][MAXN];
int dp2[MAXN][MAXN];
int dp3[MAXN][MAXN];
int dp4[MAXN][MAXN];
int graph[MAXN][MAXN];
int n,m;
void init()
{
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    memset(dp3,0,sizeof(dp3));
    memset(dp4,0,sizeof(dp4));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp1[i][j]=max(dp1[i][j-1],dp1[i-1][j])+graph[i][j];
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            dp2[i][j]=max(dp2[i][j+1],dp2[i+1][j])+graph[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            dp3[i][j]=max(dp3[i][j+1],dp3[i-1][j])+graph[i][j];
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            dp4[i][j]=max(dp4[i][j-1],dp4[i+1][j])+graph[i][j];
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&graph[i][j]);
        }
    }
    init();
    int ans=0;
    for(int i=2;i<n;i++)
    {
        for(int j=2;j<m;j++)
        {
            ans=max(ans,dp1[i-1][j]+dp2[i+1][j]+dp3[i][j+1]+dp4[i][j-1]);
            ans=max(ans,dp1[i][j-1]+dp2[i][j+1]+dp3[i-1][j]+dp4[i+1][j]);
        }
    }
    printf("%d\n",ans);
}

  题意:有n个房,n!个钥匙,在房中,最多足打消k扇门,然后抱里的钥匙,去开任何的宗,但是首先扇门未可以破开,求好打开所有门的几率。

排计数

  思路:

排计数的首先维一般是1~i的排列的方案往往,第二维第三维根据标准来定义

Attack on
Titans
题意:
有R,G,B三栽士兵,一共来n个;求至少有m个连续G士兵,最多来k个连续R士兵的排列的种数。
题解:
优先管题目还转发成为到多连续的状:
至少m个连续G,至多k个连续R
=至多n个连G,至多k个连续连接R 减去 至多k个连续R,至多(m-1)个连续G
dp[i][j] 至多有u个连续G,至多有v个连续R的个数,u,v为常数
dp[i][0]代表第i只位置放G且到多起u独连续G,至多有v个连续R
dp[i][1]代表第i只位置放R且到多出u独连续G,至多生v个连续R
dp[i][2]意味着第i单职位放P且到多有u只连G,至多来v个连续R

  • 当第i个为P,前一个庸放都可以
    dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
  • 当第i个为G时
  • 要是i<=u 时 无论前一个庸推广都未会见超过u个连续的G士兵
  • dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
  • 万一i=u+1时不时,要免除前u个还放了G的情景
  • dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1;
  • 当 i > u + 1常常,我们尽操心的凡呀?第i – 1 到 i –
    u都是G士兵,那么这在i号位置放置G士兵,也用非合乎约束
    俺们好减去非称约束的方案往往,当 i – 1 到 i – u都是G士兵时
    有略种方案?肯定当位置i – u -1是R或者P啦
  • dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2]

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int MAXN=1000010;
const LL MOD=1000000007;
LL dp[MAXN][3];
int n,m,k;
LL work(int u,int v)
{
    dp[0][0]=dp[0][1]=0;
    dp[0][2]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%MOD;

        if(i<=u) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%MOD;
        else if(i==u+1) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1+MOD)%MOD;
        else if(i>u+1) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2]+MOD)%MOD;

        if(i<=v) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2])%MOD;
        else if(i==v+1) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2]-1+MOD)%MOD;
        else if(i>v+1) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2]-dp[i-v-1][0]-dp[i-v-1][2]+MOD)%MOD;
    }
    return (dp[n][0]+dp[n][1]+dp[n][2])%MOD;
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    printf("%lld\n",((work(n,k)-work(m-1,k))%MOD+MOD)%MOD);
    return 0;
}

Coin
Toss
题意;
长度为n的字符串仅出于H和T组成,求出足足包括k个连续的H的长度也n字符串的总额
题解:
跟齐;因为求出总数较充分,所以用java大数

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    private static BigInteger dp[][]=new BigInteger[110][2];
    private static BigInteger work(int n,int k)
    {
        dp[0][0]=new BigInteger("0");
        dp[0][1]=new BigInteger("1");
        for(int i=1;i<=n;i++)
        {
            dp[i][1]=dp[i-1][1].add(dp[i-1][0]);
            if(i<=k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]);
            else if(i+1==k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]).subtract(BigInteger.ONE);
            else if(i>k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]).subtract(dp[i-k-1][1]);
        }
        return dp[n][0].add(dp[n][1]);
    }
    public static void main(String[] args) {
        int n,k;
        Scanner in=new Scanner(System.in);
        while(in.hasNextInt())
        {
            n=in.nextInt();
            k=in.nextInt();
            System.out.println(work(n,n).subtract(work(n,k-1)));
        }
    } 
}

Mex
占用坑占坑
占据坑占坑
占坑占坑
霸占坑占坑
The King’s Ups and
Downs
题意:
有n个身高不雷同的兵,求出身高呈现波浪状(高低高还是高低)的排数
题解:
倘前面n-1个人都排除好,那么对第n个体来讲,他肯定是参天的,所以他插入到武装部队遭到,前面那段的结尾一定是由大到低位,后面那段的开始一定是没有及大;如果掌握前面结尾高低之不二法门数n和后开始没有高之方式数m。那么以拖欠职务的方法数就吧n*m;假设dp[i][0]代表来i个人还最后是高低的点子数,dp[i][1]代表来i个人都开头是底高的章程数,我们枚举前面的长短j
[0,i-1],那么方法数ans[i]+=dp[j][0]*dp[i-j-1][1]*C[i-1][j];c[i-1][j]也组合数,因为于i-1只数字选出j个放前面;由于镜像的涉嫌,dp[i][0]=dp[i][1]=ans[i]/2;

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=25;
long long dp[25][2];
long long cal[25][25];
long long ans[25];
int main()
{
   for(int i=0;i<21;i++)
   {
       cal[i][0]=1;
       for(int j=1;j<i;j++)
       {
           cal[i][j]=cal[i-1][j]+cal[i-1][j-1];
       }
       cal[i][i]=1;
   }
   dp[0][0]=1;
   dp[0][1]=1;
   dp[1][0]=1;
   dp[1][1]=1;
   memset(ans,0,sizeof(ans));
   ans[1]=1;
   for(int i=2;i<21;i++)
   {
       for(int j=0;j<i;j++)//枚举前面的长度
       {
           ans[i]+=dp[j][0]*dp[i-j-1][1]*cal[i-1][j];
       }
       dp[i][0]=dp[i][1]=ans[i]/2;
   }
   int t;
   scanf("%d",&t);
   int cas,n;
   while(t--)
   {
       scanf("%d%d",&cas,&n);
       printf("%d %lld\n",cas,ans[n]);
   }
    return 0;
}

Number
String
题意:
输入一错由’I’,’D’,’?’组成的长短为n的字符串;’I’表示前一个数字与目前数字是升序关系,’D’表示前一个数字和当前数字是降序关系,’?’表示任意顺序;比如排
{3, 1, 2, 7, 4, 6, 5} 表示也字符串 DIIDID。
算算有所能够产生被定字符串的行列数量,每个阵含n+1只数字,分别吗1~n+1,即于1发端都未还。
题解:
因为dp[i]的率先维是1-i底排的方案,为了体现大小关系,第二维应为数值;
假设dp[i][j]意味着前i个满足字符串条件的末梢也j的 i
的排列,注意是i的排,前面并没有数大于i;
如果s[i – 1]是’ I ‘,那么dp[i][j] = dp[i-1][j-1] +
dp[i-1][j-2] + .. + dp[i-1][1]
可是进一步简化,dp[i][j] = dp[i][j-1]+dp[i-1][j-1]
如果s[i – 1]是‘D’,那么dp[i][j] = dp[i-1][j] +
dp[i-1][j+1] + … + dp[i-1][i-1]
不过更简化,dp[i][j] = dp[i-1][j+1]+dp[i-1][j]
以要教时各类吗j,如果前方出现了j,就使前面的具有大于等于j的数+1,就可知组织出新的排列了。比如
{1, 3, 5, 2, 4},要以第六员插入3,令 >=
3的一再还+1,于是便布局出新的排列{1, 4, 6, 2, 5, 3}。

#include<cstdio>
#include<cstring>
using namespace std;
const int MOD=1000000007;
const int MAXN=1010;
char str[MAXN];
int dp[MAXN][MAXN];
int main()
{
    while(scanf("%s",str+1)!=EOF)
    {
        int len=strlen(str+1);
        memset(dp,0,sizeof(dp));
        dp[1][1]=1;
        for(int i=2;i<=len+1;i++)
        {
            if(str[i-1]=='I')
            {
                for(int j=2;j<=i;j++)
                {
                    dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%MOD;
                }
            }
            else if(str[i-1]=='D')
            {
                for(int j=i-1;j>=1;j--)
                {
                    dp[i][j]=(dp[i][j+1]+dp[i-1][j])%MOD;
                }
            }
            else
            {
                int sum=0;
                for(int j=1;j<=i-1;j++)
                {
                    sum=(sum+dp[i-1][j])%MOD;
                }
                for(int j=1;j<=i;j++)
                {
                    dp[i][j]=sum;
                }
            }
        }
        int ans=0;
        for(int i=1;i<=len+1;i++)
        {
            ans=(ans+dp[len+1][i])%MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}

求N个房间形成1~K只环有多少种或,然后除以总的分红方案往往便为问题要我们恳请的票房价值。

率先近乎斯特林数S(N, K) = S(N – 1, K – 1) +
(N – 1)*S(N – 1,
k)恰恰就是是求N个因素形成K个非空循环排列的法子数。

S(N,M)-S(N-1,M-1),表示N个要素形成M个环,减去1独门成环,即剩下的N-1独因素形成M-1个绕,算得之结果虽是所请值。

365bet体育投注 7365bet体育投注 8

 1 //求N个房间形成1~K个环有多少种可能,然后除以总的分配方案数即为题目要我们求的概率
 2 //第一类斯特林数S(N, K) = S(N - 1, K - 1) + (N - 1)*S(N - 1, k)恰恰就是求N个元素形成K个非空循环排列的方法数
 3 //S(N,M)-S(N-1,M-1),表示N个元素形成M个环,减去1独自成环,即剩下的N-1个元素形成M-1个环,算得的结果便是所求值
 4 #include<iostream>
 5 using namespace std;
 6 long long stl[25][25], cal[25];
 7 void Init()
 8 {
 9     cal[0] = cal[1] = 1;
10     for (int i = 2; i <= 20; i++) cal[i] = cal[i - 1] * i;
11     for (int i = 1; i <= 20; i++)
12     {
13         stl[i][i] = 1;
14         for (int j = 1; j < i; j++)
15         {
16             stl[i][j] = stl[i - 1][j - 1] + (i - 1)*stl[i - 1][j];
17         }
18     }
19 }
20 int main()
21 {
22     int t;
23     scanf("%d", &t);
24     Init();
25     while (t--)
26     {
27         int n, k;
28         scanf("%d%d", &n, &k);
29         long long ans = 0;
30         for (int i = 1; i <= k; i++)
31         {
32             ans += stl[n][i] - stl[n - 1][i - 1];
33         }
34         printf("%.4lf\n", 1.0*ans / cal[n]);
35     }
36     return 0;
37 }

View Code

5、hdu 4045 Machine
scheduling(组合+第二类斯特林数)

  题意:有N个机器,每天选出R个机器,而且每半独机器的编号差而盖等于K,而且每天以R个机器太多分为M组工作,问尽多出略种方案

  思路:

先是是自从N个机器中选出R个满足条件的机械出微微种。然后用R个机器太多分为M组有些许种,答案也两岸的积。

对于后人:

呢次好像Strling数的和 : S[n][1] +
S[n][2] + … + S[n][m]。

S(p,k)的递推公式是:S(p,k)=k*S(p-1,k)+S(p-1,k-1)
,1<= k<=p-1
分界条件:S(p,p)=1 ,p>=0 ;S(p,0)=0 ,p>=1。

于前者:

1:如果是将n个求放入k个盒子中(每个盒子必须要发生球),那么由插板法得
方案往往为 C(n-1,k-1);
2:如果是将n个求放入k个盒子中(盒子可为空),那么由插板法得
方案往往也 C(n + k – 1, k – 1);
假设起n个元素编号1~n中选出r个因素来,使得任意两只要素编号相差>=k
解法:先按照 1 k + 1 2 * k + 1 …. (r –
1)*k + 1 吧不怕是刚刚 间隔 k个排列下来
那么 总共n个元素,剩余 n – (r – 1)*k –
1只元素得以视作空格,极为space, 将其插入这r个要素的r +
1单空档中,
如此就会担保枚举了从的不二法门数,切满足任意两个因素编号相差
>= k的渴求
为此这题目简化为:将space个元素分配至r
+
1独区域受到,可以为空(每半个机械之前至少发生K个间隔,那么只要还余下部分职务,则把这些剩余的插到R个机器中。那么余下位置就是是N

  • ((R – 1)*K + 1), 对于R个机器,R + 1个职务,接下就是把N – ((R –
    1)*K + 1)分为R + 1个集,而且可以为空。做法是上加R +
    1只物品,然后据此插板法,这样保证
    每一个聚集都至少有一个,然后重新管各级一个聚都减掉一个即便是结果,最终结出虽是C[N
  • ((R – 1)*K + 1) + R + 1 – 1][R]。)

365bet体育投注 9365bet体育投注 10

 1 //有N个机器,每天选出R个机器,而且每两个机器的编号差要大于等于K,而且每天将R个机器最多分为M组工作,问最多有多少种方案 
 2 //1:如果是把n个求放入k个盒子中(每个盒子必须要有球),那么由插板法得 方案数为 C(n-1,k-1);
 3 //2:如果是把n个求放入k个盒子中(盒子可以为空),那么由插板法得 方案数为 C(n + k - 1, k - 1);
 4 //要从n个元素编号1~n中选出r个元素来,使得任意两个元素编号相差>=k
 5 //解法:先按照 1 k + 1 2 * k + 1 .... (r - 1)*k + 1 也就是刚好 间隔 k个排列下来
 6 //那么 总共n个元素,剩余 n - (r - 1)*k - 1个元素可以看成空格,极为space, 将它们插入这r个元素的r + 1个空档中,
 7 //这样就能保证枚举了素有的方法数,切满足任意两个元素编号相差 >= k的要求
 8 //所以这个问题简化为:将space个元素分配到r + 1个区域中,可以为空(每两个机器之前至少有K个间隔,那么如果还剩余一些位置,则把这些多余的插入到R个机器中。那么剩余位置便是N - ((R - 1)*K + 1), 对于R个机器,R + 1个位置,接下来便是把N - ((R - 1)*K + 1)分为R + 1个集合,而且可以为空。做法是添加R + 1个物品,然后用插板法,这样保证 每一个集合都至少有一个,然后再把每一个集合都减掉一个便是结果,最终结果便是C[N - ((R - 1)*K + 1) + R + 1 - 1][R]。)
 9 #include<iostream>
10 using namespace std;
11 const int maxn = 1010;
12 const int MOD = 1e9 + 7;
13 long long C[maxn][maxn];
14 long long stri2[maxn][maxn];//第二类斯特林数
15 void Init()
16 {
17     memset(C, 0, sizeof(C));
18     for (int i = 0; i < maxn; i++)
19     {
20         C[i][0] = 1;
21         for (int j = 1; j <= i; j++)
22         {
23             C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
24         }
25     }
26     for (int i = 1; i < maxn; i++)
27     {
28         stri2[i][0] = 0;
29         stri2[i][i]=stri2[i][1] = 1;
30         for (int j = 1; j < i; j++)
31         {
32             stri2[i][j] = (stri2[i - 1][j] * j + stri2[i - 1][j - 1]) % MOD;
33         }
34     }
35 }
36 int main()
37 {
38     Init();
39     int n, r, k, m;
40     while (~scanf("%d%d%d%d", &n, &r, &k, &m))
41     {
42         int res = n - (r - 1)*k - 1;
43         if (res < 0)
44         {
45             printf("0\n");
46             continue;
47         }
48         long long ans = 0;
49         for (int i = 0; i <= m; i++) ans = (ans + stri2[r][i]) % MOD;
50         ans = (ans*C[res + r][r]) % MOD;
51         printf("%lld\n", ans);
52     }
53     return 0;
54 }

View Code

6、HDU 1023 Train Problem
II(卡特兰数+模拟大数乘除<高精度递推>)

  题意:给您一个数n,表示来n辆火车,编号从1及n,从海外驶过来,问您生略种出站的可能。

  思路:

1.Catalan数底三结合公式为 Cn=C(2n,n) /
(n+1);
2.此数底递归公式为 h(n ) = h(n-1)*(4*n-2) / (n+1)。

http://blog.163.com/lz\_666888/blog/static/1147857262009914112922803/

365bet体育投注 11365bet体育投注 12

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int cat[110][110];//每一位存放大数的4位
 6 //Catalan数的组合公式为 Cn=C(2n,n) / (n+1);
 7 //递推公式为 h(n) = h(n - 1)*(4 * n - 2) / (n + 1);
 8 int length[110];//记录每一位卡特兰数的位数
 9 const int MOD = 10000;
10 void Init()
11 {//求出1~100位卡特兰数
12     memset(cat, 0, sizeof(cat));
13     cat[1][0] = 1;
14     int len = 1;
15     length[1] = 1;
16     for (int i = 2; i <= 100; i++)
17     {
18         //乘法
19         int r = 0;
20         for (int j = 0; j < len; j++)
21         {
22             int temp = cat[i - 1][j] * (4 * i - 2);
23             cat[i][j] = (temp+r)%MOD;
24             r = (temp + r) / MOD;
25         }
26         //进位
27         while (r)
28         {
29             cat[i][len++] = r %MOD;
30             r /= MOD;
31         }
32         //除法
33         r = 0;
34         for (int j = len - 1; j >= 0; --j)
35         {
36             int temp = r * MOD + cat[i][j];
37             cat[i][j] = temp / (i + 1);
38             r = temp % (i + 1);
39         }
40         //除法结束后高位0处理
41         while (cat[i][len - 1] == 0)
42         {
43             len--;
44         }
45         length[i] = len;
46     }
47 }
48 int main()
49 {
50     Init();
51     int n;
52     while (~scanf("%d", &n))
53     {
54         int len = length[n];
55         printf("%d", cat[n][len - 1]);
56         for (int j = len - 2; j >= 0; j--) printf("%.4d", cat[n][j]);
57         printf("\n");
58     }
59     return 0;
60 }

View Code

7、HDU 1297 Children’s
Queue(模拟大数加法<高精度递推>)

  题意:F代表女孩,M代表男孩,女孩无克独立出现而足以无起,即未可知起MFM这种景象,给一定一个数n,问有微种站队方式。

  思路:

一个长短n的班可以看作一个n –
1的队再添的1只小孩,这个娃娃就或是:
a.男孩,任何n –
1的合法队列追加1单男孩必然是法定的,情况屡屡为f[n – 1];
b.女孩,在前n –
1的因为女孩吧尾声的阵后长1位女孩为是官的,我们好转化为n –
2的序列中加进2位女孩;
同等栽情况是于n –
2的官队列中增2位女孩,情况屡屡也f[n – 2];
只是咱注意到本题的困难,可能前n –
2各项为女孩也末段的不合法队列(即单独因为1各女孩最后),也得以加2位女孩成官方队列,而这种n

  • 2未合法队列必然是由n – 4合法队列 + 1男孩 + 1女孩的组织,即情况屡屡为f[n
  • 4]。
    f[n] = f[n – 1] + f[n – 2] + f[n –
    4]。

365bet体育投注 13365bet体育投注 14

 1 //一个长度n的队列可以看成一个n - 1的队列再追加的1个小孩,这个小孩只可能是:
 2 //a.男孩,任何n - 1的合法队列追加1个男孩必然是合法的,情况数为f[n - 1];
 3 //b.女孩,在前n - 1的以女孩为末尾的队列后追加1位女孩也是合法的,我们可以转化为n - 2的队列中追加2位女孩;
 4 //一种情况是在n - 2的合法队列中追加2位女孩,情况数为f[n - 2];
 5 //但我们注意到本题的难点,可能前n - 2位以女孩为末尾的不合法队列(即单纯以1位女孩结尾),也可以追加2位女孩成为合法队列,而这种n - 2不合法队列必然是由n - 4合法队列 + 1男孩 + 1女孩的结构,即情况数为f[n - 4]。
 6 //f[n] = f[n - 1] + f[n - 2] + f[n - 4]
 7 #include<iostream>
 8 #include<cstring>
 9 using namespace std;
10 int f[1010][1010];
11 int length[1010];
12 void Init()
13 {
14     memset(f, 0, sizeof(f));
15     f[1][0] = 1;
16     f[2][0] = 2;
17     f[3][0] = 4;
18     f[4][0] = 7;
19     int len = 1;
20     length[1] = length[2] = length[3] = length[4] = 1;
21     for (int i = 5; i <= 1000; i++)
22     {
23         for (int j = 0; j < len; j++)
24         {
25             f[i][j] += f[i - 1][j] + f[i - 2][j] + f[i - 4][j];
26             f[i][j + 1] += f[i][j] / 10000;
27             f[i][j] %= 10000;
28         }
29         while (f[i][len]) len++;
30         length[i] = len;
31     }
32 }
33 int main()
34 {
35     Init();
36     int n;
37     while (~scanf("%d", &n))
38     {
39         int len = length[n];
40         printf("%d", f[n][len - 1]);
41         for (int i = len - 2; i >= 0; i--) printf("%04d", f[n][i]);
42         printf("\n");
43     }
44     return 0;
45 }

View Code

8、hdu 1466 计算直线交点数

  题意:平面上出n条直线,且无三丝共点,问这些直线能起微种不同交点数。比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。

  思路:

分析在第N久直线的景(这里坐N=4为条例): 
(分类方法:和第N长条直线平行的于a组,其余在b组) 
1、 第四修与外直线全部平行 :

0+4*0+0=0; 

2、 第四长达以及里有数长达平行:

交点数为0+(n-1)*1+0=3; 

3、 第四长条跟其中同样长平行:

立即简单漫长平行直线与另外两触及直线的交点数为(n-2)*2=4,

一旦另外两条直线既可能平行也说不定相交,

为此可能到点数也: 0+(n-2)* 2+0=4  
 或者  0+(n-2)*2+1=5     

4、
第四长条直线不跟外一样长直线平行,交点数为:0+(n-3)*3+0=3  或0+
(n-3)*3+2=5  或0+ (n-3)*3+3=6 

不畏n=4时,有0独,3独,4独,5个,6个不等交点数。

用由上述n=4的辨析过程中,我们发现: 

m条直线的交点方案往往 =(m –
r)条平行线与r条直线交叉的交点数 + r漫漫直线本身的交点方案 = (m – r )*
r + r 条之间自我的交点方案往往(0 < = r < m )

用 n 条直线排成一个行列,直线 2 与直线 1
最多但生一个交点,直线 3 和直线 1 和直线 2
最多生点儿只交点……直线n和任何 n – 1 久直线最多有 n – 1 个交点,由此得出
n 条直线互免平行且不论三丝一起点之卓绝多到点数:max = 1 + 2 + . . . + (n – 1)
= n * (n – 1) / 2。

其中每个自由直线与每个平行直线都生一个交点,j自由直线与i平行直线的交点数为
j *
i,所以n条直线的交点数等于随便直线与平直线的交点加上自由直线内部形成的交点。

————————以上摘自:http://blog.csdn.net/wang907553141/article/details/52165629

365bet体育投注 15365bet体育投注 16

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 210;
 4 bool dp[25][maxn];//dp[i][j]表示i条直线相交时是否有j个交点
 5 void Init()
 6 {
 7     for (int i = 0; i <= 20; i++) dp[i][0] = true;//所有的直线都平行
 8     for (int i = 2; i <= 20; i++)
 9     {//i条直线
10         for (int j = 1; j < i; j++)
11         {//枚举和第i条边相交的边的数目
12             for (int k = 0; k < maxn; k++)
13             {//枚举j条边的交点情况
14                 if (dp[j][k]) dp[i][(i - j)*j + k] = true;
15             }
16 
17         }
18     }
19 }
20 
21 int main()
22 {
23     Init();
24     int n;
25     while (~scanf("%d", &n))
26     {
27         for (int i = 0; i < maxn; i++)
28         {
29             if (dp[n][i])
30             {
31                 if (i > 0) printf(" ");
32                 printf("%d", i);
33             }
34         }
35         printf("\n");
36     }
37     return 0;
38 }

View Code

 9、SPOJ 2832 Find The Determinant
III(n阶行列式求值)

  题意:求矩阵行列式A的值%P。

  思路:辗转相除法求n阶行列式的价对mod取模。

 

365bet体育投注 17365bet体育投注 18

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int inf = 0x3f3f3f3f;
 7 const double eps = 1e-15;
 8 typedef long long LL;
 9 const int N = 250;
10 
11 LL mat[N][N];
12 
13 LL Det(int n, int mod)
14 {//辗转相除法求n阶行列式的值对mod取模
15     //输入:mat[][]矩阵
16     for (int i = 0; i < n; ++i)
17     {
18         for (int j = 0; j < n; ++j)
19         {
20             mat[i][j] %= mod;
21         }
22     }
23     LL res = 1;
24     for (int i = 0; i < n; ++i)
25     {
26         if (!mat[i][i])
27         {
28             bool flag = false;
29             for (int j = i + 1; j < n; ++j)
30             {
31                 if (mat[j][i])
32                 {
33                     flag = true;
34                     for (int k = i; k < n; ++k)
35                     {
36                         swap(mat[i][k], mat[j][k]);
37                     }
38                     res = -res;
39                     break;
40                 }
41             }
42             if (!flag)
43             {
44                 return 0;
45             }
46         }
47         for (int j = i + 1; j < n; ++j)
48         {
49             while (mat[j][i])
50             {
51                 LL t = mat[i][i] / mat[j][i];
52                 for (int k = i; k < n; ++k)
53                 {
54                     mat[i][k] = (mat[i][k] - t * mat[j][k]) % mod;
55                     swap(mat[i][k], mat[j][k]);
56                 }
57                 res = -res;
58             }
59         }
60         res = (res * mat[i][i]) % mod;
61     }
62     return (res + mod) % mod;
63 }
64 
65 int main()
66 {
67     int n;
68     LL p;
69     while (~scanf("%d%lld", &n, &p))
70     {
71         for (int i = 0; i < n; ++i)
72         {
73             for (int j = 0; j < n; ++j)
74             {
75                 scanf("%lld", &mat[i][j]);
76             }
77         }
78         LL ans = Det(n, p);
79         printf("%lld\n", ans);
80     }
81     return 0;
82 }

View Code

 

相关文章

网站地图xml地图