天天看點
傳回

[Contests]2016弱校聯盟十一專場10.7

G UmBasketella

題意：

漏鬥形(錐形)容器，輸入其表面積(包括底部)，求其容量，高度，半徑，精确到0.01

思路：

此題有兩種方法，一種是推公式，比較偷懶

還有一種是三分查找确定最值，這才是正統之路

代碼1（推公式）

/**************************************************************
    Problem: BNUOJ_3856
    User: soundwave
    Language: C++
    Result: Accepted
    Time: 0ms
    Memory: 692KB
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")//手動擴棧
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;
const double PI = 3.1415926;
int main(){
    double s;
    double v, h, r;

    while(~scanf("%lf", &s)){
        r = sqrt(s*1.0/4/PI);
        h = sqrt((s*s)/(PI*PI*r*r) - 2*s/PI);
        v = ((s*1.0/4/PI)*PI*h) / 3;
        printf("%.2f\n%.2f\n%.2f\n", v, h, r);
    }
    return 0;
}

代碼2（魔幻三分）

/**************************************************************
    Problem: BNUOJ_3856
    User: soundwave
    Language: C++
    Result: Accepted
    Time: 0ms
    Memory: 716KB
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <stdio.h>
#include <math.h>
/*
V = (PI*r*r*h)/3;
S = PI*r(r+l);
l = sqrt(r*r+h*h);
-------------------
V = r*sqrt(s*s-2*s*PI*r)/3;
*/
using namespace std;
//acos()是反餘弦函數，cosπ = -1，是以π = acos(-1)
const double PI = acos(-1.0);
const double EPS = 1e-10;
double s;
double calc(double r){
    return sqrt(s*s-2*s*PI*r*r)*r/3.0;
}
/*
double three_divide(double l, double r){
    double lmid, rmid;
    while(r-l > EPS){
        lmid = (l+r)/2.0;
        rmid = (lmid+r)/2.0;
        if(calc(lmid) > calc(rmid))
        if(x>y)
            r = rmid;
        else
            l = lmid;
    }
    return l;
}
*/
double three_divide(double l, double r){
    double lmid, rmid;
    while(r-l > EPS){
        lmid = l + (r-l)/3.0;
        rmid = r - (r-l)/3.0;
        if(calc(lmid) > calc(rmid))
            r = rmid;
        else
            l = lmid;
    }
    return (r+l)/2.0;
}
int main(){
    while(~scanf("%lf", &s)){
        double r = three_divide(0,sqrt(s*1.0/PI));
        double h = sqrt(s*s-2*s*PI*r*r)/PI/r;
        printf("%.2f\n%.2f\n%.2f\n", calc(r), h, r);
    }
    return 0;
}

反思：

不知道為什麼兩種三分查找的代碼隻能實作一個，奇怪……

D Blocks

題意：

用四種顔色去刷N個盒子，要求紅色和綠色的盒子都為偶數(0也是偶數)，求方案數。

思路：

可以用矩陣乘法(矩陣快速幂優化)，或者組合數學推公式(快速幂優化)

①這裡是排列組合+二次項定理推公式

來吧，推公式_(:зゝ∠)_

我們設奇數為1，偶數為0

倒着推比較簡單，4^n - 紅綠色(11/10/01)的情況

從n中選k(k∈[1,n])個，k為紅綠總數，從k中選取不符合題意（即紅綠色為11/10/01）的情況；

根據二項式定理 C(n,k)*2^(n-k) * C(2,1)*( C(k,1)+C(k,3)+C(k,5)+…… )

(1+x)^k=C(k,0)x^0+C(k,1)x^1+...+C(k,k)x^k

C(k,1)+C(k,3)+C(k,5)+…… = 2^(k-1);

C(k,0)+C(k,2)+C(k,4)+…… = 2^(k-1);

如果 k 是奇數，紅綠為一奇一偶，紅奇綠偶和紅偶綠奇為兩種情況，則

C(n,k)*2^(n-k) * C(2,1)*( C(k,1)+C(k,3)+C(k,5)+…… )

= C(n,k)*2^(n-k+1)*2^(k-1) 

= C(n,k)*2^n;

如果 k 為偶數，則

C(n,k)*2^(n-k) * ( C(k,1)+C(k,3)+C(k,5)+…… )

= C(n,k)*2^(n-k)*2^(k-1) 

= C(n,k)*2^(n-1);

于是推出總公式為 

4^n - C(n,1)*2^n - C(n,2)*2^(n-1) - C(n,3)*2^n - C(n,4)*2^(n-1) - ……

= 4^n - 2^n*( C(n,1)+C(n,3)+……) - 2^(n-1)*( C(n,2)+C(n,4)+…… )

= 4^n - 2^n*2^(n-1) - 2^(n-1)*(2^(n-1)-1);

= 2^(2n) - 2^(2n-1) - 2^(2n-2) + 2^(n-1);

= 2^(n-1) * ( 2^(n-1) + 1 );

好了_(:зゝ∠)_，終于推出來了，就是 2^(n-1) * ( 2^(n-1) + 1 ) 這個公式

②(指數型)生成函數(母函數)推公式

生成函數(母函數)是說，構造這麼一個多項式函數G(x)，使得x的n次方系數為a(n)。

母函數的思想很簡單，就是把離散數列和幂級數一一對應起來，把離散數列間的互相結合關系對應成為幂級數間的運算關系，最後由幂級數形式來确定離散數列的構造

注：二項展開式，即（a+b）的n次展開式

生成函數為

G(x) = (1+x^2/2!+x^4/4!+...)²*(1+x+x^2/2!+x^3/3!+...)²  

= [0.5(e^x+e^-x)]²*e^2x            

= 1/4*(e^4x+e^2x+1)  

= 1/4∑((4x)^n/n!)+1/2∑((2x)^n/n!)+1/4   n=0,1,2……

是以x^n項的系數為

a(n) = 4^(n-1) + 2^(n-1) = 2^(n-1) * ( 2^(n-1) + 1 );

如何構造生成函數真心好迷啊，估計下次見到也不會寫_(:зゝ∠)_

代碼1（推公式）：

/**************************************************************
    Problem: BNUOJ_3853
    User: soundwave
    Language: C++
    Result: Accepted
    Time: 0ms
    Memory: 696KB
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <stdio.h>
/*
2^(n-1) * (2^(n-1) + 1)
*/
using namespace std;
typedef __int64 LL;
const int mod = 10007;
//二分快速幂
LL my_pow(LL x, LL c){
    LL re = 1;
    while(c>0){
        if(c&1) re = (re*x) % mod;
        x = (x*x) % mod;
        c>>=1;
    }
    return re;
}
int main(){
    int t, n;
    scanf("%d", &t);
    while(t-->0){
        scanf("%d", &n);
        LL re = my_pow(2,n-1);
        printf("%I64d\n", (re*(re+1))%mod);
    }
    return 0;
}
/*
5
1
2
3
4
5
---------
2
6
20
72
272
*/

③矩陣乘法才是王道(๑•̀ㅂ•́)و✧，推公式太麻煩了_(:зゝ∠)_

設奇為1，偶為0

設 n 塊磚頭的染色情況為四種abcd

a(n)：N塊磚頭中紅色綠色都為偶數

b(n)：N塊磚頭中紅色為偶數，綠色為奇數

c(n)：N塊磚頭中紅色為奇數，綠色為偶數

d(n)：N塊磚頭中紅色綠色都為奇數

可知 (n+1) 塊磚頭的染色情況可以由 n 塊磚頭的染色情況推出

a(n+1) = 2a(n) + b(n) + c(n);

b(n+1) = a(n) + 2b(n) + d(n);

c(n+1) = a(n) + 2c(n) + d(n);

d(n+1) = b(n) + c(n) + 2d(n);

a(n+1)：(黃/藍)*a + 綠*b + 紅*c + 0*d

b(n+1)：綠*a + (黃/藍)*b + 0*c + 紅*d

c(n+1)：紅*a + 0*b + (黃/藍)*c + 綠*d

d(n+1)：0*a + 紅*b + 綠*c + (黃/藍)d

如果不能了解，我們可以采用dp的思想了解，然後轉化為矩陣(๑•̀ㅂ•́)و✧

用dp[N][4]來表示N塊磚塊的染色情況，一共有四種狀态：

dp[N][0]：N塊磚頭中紅色綠色都為偶數

dp[N][1]：N塊磚頭中紅色為偶數，綠色為奇數

dp[N][2]：N塊磚頭中紅色為奇數，綠色為偶數

dp[N][3]：N塊磚頭中紅色綠色都為奇數

狀态轉移方程如下：

dp[N+1][0] = 2 * dp[N][0] + 1 * dp[N][1] + 1 * dp[N][2] + 0 * dp[N][3]

dp[N+1][1] = 1 * dp[N][0] + 2 * dp[N][1] + 0 * dp[N][2] + 1 * dp[N][3]

dp[N+1][2] = 1 * dp[N][0] + 0 * dp[N][1] + 2 * dp[N][2] + 1 * dp[N][3]

dp[N+1][3] = 0 * dp[N][0] + 1 * dp[N][1] + 1 * dp[N][2] + 2 * dp[N][3]

可以清楚地看出來，和上一個公式的想法是一樣的，(n+1) 塊磚頭的染色情況可以由 n 塊磚頭的染色情況推出

然後我們就可以轉化為矩陣啦

[Contests]2016弱校聯盟十一專場10.7

然後求矩陣A的n次幂即可

或者，紅奇綠偶和紅偶綠奇合成一種情況，那麼矩陣為

[Contests]2016弱校聯盟十一專場10.7

來，矩陣快速幂接住(๑•̀ㅂ•́)و✧

代碼2（矩陣快速幂）

/**************************************************************
    Problem: BNUOJ_3853
    User: soundwave
    Language: C++
    Result: Accepted
    Time: 47ms
    Memory: 736KB
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

typedef vector<int> Vint;
typedef vector<Vint> VVint;
typedef __int64 LL;
const int MOD = 10007;
//矩陣乘法
VVint calc(VVint &A, VVint &B){
    VVint C(A.size(), Vint(A.size()));
    for(int i=0; i<A.size(); i++)
    for(int j=0; j<B[0].size(); j++)
    for(int k=0; k<B.size(); k++)
        C[i][j] = (C[i][j] + (A[i][k]*B[k][j])%MOD) % MOD;
    return C;
}
//二分快速幂
VVint my_pow(VVint A, LL c){
    VVint B(A.size(), Vint(A.size()));
    for(int i=0; i<A.size(); i++)
        B[i][i] = 1;
    while(c>0){
        if(c&1)
            B = calc(B,A);
        A = calc(A,A);
        c>>=1;
    }
    return B;
}
int main(){
    int t, n;
    scanf("%d", &t);
    while(t-->0){
        scanf("%d", &n);
        VVint A(4,Vint(4));
        A[0][0]=2, A[0][1]=1, A[0][2]=1, A[0][3]=0;
        A[1][0]=1, A[1][1]=2, A[1][2]=0, A[1][3]=1;
        A[2][0]=1, A[2][1]=0, A[2][2]=2, A[2][3]=1;
        A[3][0]=0, A[3][1]=1, A[3][2]=1, A[3][3]=2;
        A = my_pow(A,n);
        /*
        VVint A(3,Vint(3));
        A[0][0]=2, A[0][1]=1, A[0][2]=0;
        A[1][0]=2, A[1][1]=2, A[1][2]=2;
        A[2][0]=0, A[2][1]=1, A[2][2]=2;
        A = my_pow(A,n);
        */
        cout << A[0][0] << endl;
    }
    return 0;
}

反思：

盡管比起公式慢了，但是擺脫了推導公式的恐懼_(:зゝ∠)_

Contests
上一篇: UVA-DNA Consensus String
下一篇: 涼脾的比賽補題

繼續閱讀