题解 UVA10328 【Coin Toss】

这道题目其实就是说有N张纸牌，问至少连续K张正面朝上的可能性是多少。

可以用递推做。
首先我们将题目所求从

至少K张

转化为

总数 - 至多K张

（为什么要这样自己想）

设F[i][j]为前i个纸牌至多K张的种数。其中j记录第i张纸牌的状态，1为正面朝上，0为反面。

那么可以总结出

f[i][] = f[i - ][] + f[i - ][];

 f[i][] = f[i - ][] + f[i - ][];

 if(i == k) f[i][] -= ;

 else if(i > k) f[i][] -= f[i - k][];

最后要记住这道题需要写高精，我第一次就是这么扑街的。

注：高精用的模板，手残就全加上了，事实上只用加减法。

AC代码如下（洛谷上不知道为什么被积极拒绝，只好去Vjudge上提交。。。没去UVa才不是因为我没有注册。）

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <vector>

 #include <cassert>

 using namespace std;

 const int maxn = ;

 struct BigInteger {

     typedef unsigned long long LL;

     static const int BASE = ;

     static const int WIDTH = ;

     vector<int> s;

     BigInteger& clean(){while(!s.back()&&s.size()>)s.pop_back(); return *this;}

     BigInteger(LL num = ) {*this = num;}

     BigInteger(string s) {*this = s;}

     BigInteger& operator = (long long num) {

         s.clear();

         do {

             s.push_back(num % BASE);

             num /= BASE;

         } while (num > );

         return *this;

     }

     BigInteger& operator = (const string& str) {

         s.clear();

         int x, len = (str.length() - ) / WIDTH + ;

         for (int i = ; i < len; i++) {

             int end = str.length() - i*WIDTH;

             int start = max(, end - WIDTH);

             sscanf(str.substr(start,end-start).c_str(), "%d", &x);

             s.push_back(x);

         }

         return (*this).clean();

     }

     BigInteger operator + (const BigInteger& b) const {

         BigInteger c; c.s.clear();

         for (int i = , g = ; ; i++) {

             if (g ==  && i >= s.size() && i >= b.s.size()) break;

             int x = g;

             if (i < s.size()) x += s[i];

             if (i < b.s.size()) x += b.s[i];

             c.s.push_back(x % BASE);

             g = x / BASE;

         }

         return c;

     }

     BigInteger operator - (const BigInteger& b) const {

         assert(b <= *this); // 减数不能大于被减数

         BigInteger c; c.s.clear();

         for (int i = , g = ; ; i++) {

             if (g ==  && i >= s.size() && i >= b.s.size()) break;

             int x = s[i] + g;

             if (i < b.s.size()) x -= b.s[i];

             if (x < ) {g = -; x += BASE;} else g = ;

             c.s.push_back(x);

         }

         return c.clean();

     }

     BigInteger operator * (const BigInteger& b) const {

         int i, j; LL g;

         vector<LL> v(s.size()+b.s.size(), );

         BigInteger c; c.s.clear();

         for(i=;i<s.size();i++) for(j=;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];

         for (i = , g = ; ; i++) {

             if (g == && i >= v.size()) break;

             LL x = v[i] + g;

             c.s.push_back(x % BASE);

             g = x / BASE;

         }

         return c.clean();

     }

     BigInteger operator / (const BigInteger& b) const {

         assert(b > );  // 除数必须大于0

         BigInteger c = *this;       // 商:主要是让c.s和(*this).s的vector一样大

         BigInteger m;               // 余数:初始化为0

         for (int i = s.size()-; i >= ; i--) {

             m = m*BASE + s[i];

             c.s[i] = bsearch(b, m);

             m -= b*c.s[i];

         }

         return c.clean();

     }

     BigInteger operator % (const BigInteger& b) const { //方法与除法相同

         BigInteger c = *this;

         BigInteger m;

         for (int i = s.size()-; i >= ; i--) {

             m = m*BASE + s[i];

             c.s[i] = bsearch(b, m);

             m -= b*c.s[i];

         }

         return m;

     }

     // 二分法找出满足bx<=m的最大的x

     int bsearch(const BigInteger& b, const BigInteger& m) const{

         int L = , R = BASE-, x;

         while () {

             x = (L+R)>>;

             if (b*x<=m) {if (b*(x+)>m) return x; else L = x;}

             else R = x;

         }

     }

     BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}

     BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}

     BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}

     BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}

     BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}

     bool operator < (const BigInteger& b) const {

         if (s.size() != b.s.size()) return s.size() < b.s.size();

         for (int i = s.size()-; i >= ; i--)

             if (s[i] != b.s[i]) return s[i] < b.s[i];

         return false;

     }

     bool operator >(const BigInteger& b) const{return b < *this;}

     bool operator<=(const BigInteger& b) const{return !(b < *this);}

     bool operator>=(const BigInteger& b) const{return !(*this < b);}

     bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}

     bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}

 };

 ostream& operator << (ostream& out, const BigInteger& x) {

     out << x.s.back();

     for (int i = x.s.size()-; i >= ; i--) {

         char buf[];

         sprintf(buf, "%08d", x.s[i]);

         for (int j = ; j < strlen(buf); j++) out << buf[j];

     }

     return out;

 }

 istream& operator >> (istream& in, BigInteger& x) {

     string s;

     if (!(in >> s)) return in;

     x = s;

     return in;

 }

 int n, k;

 BigInteger f[maxn][];

 int main() {

     while(cin >> n >> k) {

         memset(f, , sizeof(f));

         f[][] = ;

         for(int i = ; i <= n; i++) {

             f[i][] = f[i - ][] + f[i - ][];

             f[i][] = f[i - ][] + f[i - ][];

             if(i == k) f[i][] = f[i][] - ;

             else if(i > k) f[i][] = f[i][] - f[i - k][];

         }

         BigInteger a = , t = ;

         for(int i = ; i < n; i++) a = t * a;

         cout << a - f[n][] - f[n][] << endl;

     }

 }

巴特西

题解 UVA10328 【Coin Toss】

最新文章

热门文章