[POJ1205]Water Treatment Plants

偏执的太偏执、 2021-12-19 14:49 140阅读 0赞

题目大意：  
　　有一排n个格子，要在它们上面装管道。  
　　每个格子上的管道都是T形的，但是可以有三种流动的方向。  
　　每种都是把两个方向的水往另一个方向排出。  
　　如果方向是向左或向右，就是排到相邻的格子里。  
　　特别地，最左边的格子不能向左排水，最右边的格子不能向右排水。  
　　现在每个格子都有一些积水等待排出，问能使所有格子的水最后都会从下面流出的方案数。

思路：  
　　我们不妨用f\[i\]\[0~2\]表示第i个格子排水方案数。  
　　0~2表示不同的方向。  
　　用0表示下，1表示左，2表示右。  
　　f\[i\]\[0\]=f\[i-1\]\[1\]+f\[i-1\]\[2\];  
　　f\[i\]\[1\]=f\[i-1\]\[0\]+f\[i-1\]\[1\]+f\[i-1\]\[2\];  
　　f\[i\]\[2\]=f\[i-1\]\[0\]+f\[i-1\]\[1\]+f\[i-1\]\[2\];  
　　压到一维就是f\[i\]=f\[i-1\]\*3-f\[i-2\]。  
　　然后又变成了一道入门题。  
　　然而题目并没有告诉你模数，所以需要高精度，总之就是特别恶心。

1 #include<cmath>
     2 #include<cstdio>
     3 #include<cstring>
     4 class BigInteger {
     5     private:
     6         static const int base=1e8;
     7         int len;
     8         int num[7];
     9     public:
    10         BigInteger() {
    11             len=0;
    12             memset(num,0,sizeof num);
    13         }
    14         BigInteger &operator = (const int &x) {
    15             len=0;
    16             num[0]=x;
    17             return *this;
    18         }
    19         BigInteger &operator = (const BigInteger &x) {
    20             len=x.len;
    21             memcpy(num,x.num,sizeof num);
    22             return *this;
    23         }
    24         BigInteger operator * (const int &x) const {
    25             BigInteger ans;
    26             for(register int i=0;i<=len;i++) {
    27                 ans.num[i]+=num[i]*x;
    28                 ans.num[i+1]=ans.num[i]/base;
    29                 ans.num[i]%=base;
    30             }
    31             ans.len=len;
    32             if(ans.num[len+1]) ans.len++;
    33             return ans;
    34         }
    35         BigInteger operator - (const BigInteger &x) const {
    36             BigInteger ans;
    37             for(register int i=0;i<=len;i++) {
    38                 ans.num[i]+=num[i]-x.num[i];
    39                 if(ans.num[i]<0) {
    40                     ans.num[i]+=base;
    41                     ans.num[i+1]--;
    42                 }
    43             }
    44             ans.len=len;
    45             if(!ans.num[len]&&len) ans.len--;
    46             return ans;
    47         }
    48         void println() {
    49             printf("%d",num[len]);
    50             for(register int i=len-1;i>=0;i--) {
    51                 if(!num[i]) {
    52                     printf("0000000");
    53                     continue;
    54                 }
    55                 for(register int j=log10(num[i]);j<=6;j++) {
    56                     putchar('0');
    57                 }
    58                 printf("%d",num[i]);
    59             }
    60             putchar('\n');
    61         }
    62 };
    63 BigInteger f[3];
    64 int main() {
    65     int n;
    66     while(~scanf("%d",&n)) {
    67         f[0]=0;
    68         f[1]=1;
    69         for(register int i=2;i<=n;i++) {
    70             f[i%3]=f[(i-1)%3]*3-f[(i-2)%3];
    71         }
    72         f[n%3].println();
    73     }
    74     return 0;
    75 }

转载于:https://www.cnblogs.com/skylee03/p/7738910.html