题目链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1269

10328 - Coin Toss

Time limit: 3.000 seconds
#### 问题描述
> Toss is an important part of any event. When everything becomes equal toss is the ultimate decider.
> Normally a fair coin is used for Toss. A coin has two sides head(H) and tail(T). Superstition may work
> in case of choosing head or tail. If anyone becomes winner choosing head he always wants to choose
> head. Nobody believes that his winning chance is 50-50. However in this problem we will deal with a
> fair coin and n times tossing of such a coin. The result of such a tossing can be represented by a string.
> Such as if 3 times tossing is used then there are possible 8 outcomes.
> HHH HHT HTH HTT THH THT TTH TTT
> As the coin is fair we can consider that the probability of each outcome is also equal. For simplicity
> we can consider that if the same thing is repeated 8 times we can expect to get each possible sequence
> once.
> In the above example we see 1 sequence has 3 consecutive H, 3 sequence has 2 consecutive H and 7
> sequence has at least single H. You have to generalize it. Suppose a coin is tossed n times. And the
> same process is repeated 2n times. How many sequence you will get which contains a sequence of H of
> length at least k.

输入

The input will start with two positive integer, n and k (1 ≤ k ≤ n ≤ 100). Input is terminated by

EOF.

输出

For each test case show the result in a line as specified in the problem statement.

样例输入

4 1

4 2

4 3

4 4

6 2

样例输出

15

8

3

1

43

题意

给你n个硬币，考虑正反的所有排列数：比如n=2:{HH,HT,TH,TT)，然后问至少有k个的硬币连续正面朝上的总数。

题解

至少k个=2^n-最多k-1个。

所以我们可以转换成去求最多k个的问题

dp[k][i][0]表示前i个最多k个连续正面朝上，且第i个反面朝上的总数，

dp[k][i][1]表示前i个最多k个连续正面朝上，且第i个反面朝上的总数，

则我们只需要考虑扣掉最后连续k+1个正面朝上这种情况就可以转移了，写完之后上大整数。

代码

c++(没考虑数据溢出):

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=111;

LL dp[maxn][maxn][2];

int n,m;

void pre(){

    clr(dp,0);

    for(int k=0;k<maxn;k++){

        dp[k][0][0]=1;

        for(int i=1;i<maxn;i++){

            dp[k][i][1]=dp[k][i][0]=dp[k][i-1][0]+dp[k][i-1][1];

            if(i>k) dp[k][i][1]-=dp[k][i-k-1][0];

        }

    }

}

int main() {

    pre();

    while(scf("%d%d",&n,&m)==2){

        LL x=1;

        rep(i,0,n) x*=2;

        prf("%lld\n",x-dp[m-1][n][0]-dp[m-1][n][1]);

    }

    return 0;

}

//end-----------------------------------------------------------------------

java:

import java.util.*;

import java.math.*;

public class Main {

	final static int maxn = 111;

	public static void main(String args[]) {

		Scanner cin = new Scanner(System.in);

		BigInteger[][][] dp = new BigInteger[maxn][maxn][2];

		for (int i = 0; i < maxn; i++) {

			for (int j = 0; j < maxn; j++) {

				dp[i][j][1]=dp[i][j][0] = BigInteger.ZERO;

			}

		}

		for (int k = 0; k < maxn; k++) {

			dp[k][0][0] = BigInteger.ONE;

			for (int i = 1; i < maxn; i++) {

				dp[k][i][1]=dp[k][i][0] = dp[k][i - 1][0].add(dp[k][i - 1][1]);

				if (i > k)

					dp[k][i][1] = dp[k][i][1].subtract(dp[k][i - k - 1][0]);

			}

		}

		BigInteger[] x = new BigInteger[maxn];

		x[0] = BigInteger.ONE;

		for (int i = 1; i < maxn; i++)

			x[i] = x[i - 1].add(x[i - 1]);

		while (cin.hasNext()) {

			int n, m;

			n = cin.nextInt();

			m = cin.nextInt();

			BigInteger ans = x[n].subtract(dp[m - 1][n][0]).subtract(dp[m - 1][n][1]);

			System.out.println(ans.toString());

		}

	}

}

巴特西

UVA 10328 - Coin Toss dp+大数

题目链接：

10328 - Coin Toss

输入

输出

样例输入

样例输出

题意

题解

代码

最新文章

热门文章