首页 > 代码库 > UVa 11375 Matches

UVa 11375 Matches

2024-07-20 10:43:09   211人阅读

第一次用lrj的高精度类模板，感觉还是很好用的

c[x]表示数字x需要的火柴根数

将已经使用的火柴数i看做状态，每添加一个数字x状态就从i转移到i+c[x]

d[i]表示从节点0到节点i路径的条数，则答案f(n) = d(1) + d(2) + …… + d(n)

开始的时候不计入0，最后的时候如果n≥6答案再加一

 

 1 #define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 struct bign 8 { 9     int len, s[1000];10     bign() { memset(s, 0, sizeof(s)); len = 1; }11     bign operator = (const char* num)12     {13         len = strlen(num);14         for(int i = 0; i < len; ++i)15             s[i] = num[len - i - 1] - ‘0‘;16         return *this;17     }18     bign operator = (int num)19     {20         char s[1000];21         sprintf(s, "%d", num);22         *this = s;23         return *this;24     }25     bign (int num) { *this = num; }26     bign (const char* num) { *this = num; }27     string  str() const28     {29         string res = "";30         for(int i = 0; i < len; ++i)31             res = (char)(s[i] + ‘0‘) + res;32         if(res == "")    res = "0";33         return res;34     }35 36     bign operator + (const bign b) const37     {38         bign c;39         c.len = 0;40         for(int i = 0, g = 0; g || i < max(len, b.len); ++i)41         {42             int x = g;43             if(i < len)    x += s[i];44             if(i < b.len)    x += b.s[i];45             c.s[c.len++] = x % 10;46             g = x / 10;47         }48         return c;49     }50 51     bign operator += (const bign& b)52     {53         *this = *this + b;54         return *this;55     }56 };57 58 istream& operator >> (istream& in, bign& x)59 {60     string s;61     in >> s;62     x = s.c_str();63     return in;64 }65 66 ostream& operator << (ostream &out, const bign& x)67 {68     out << x.str();69     return out;70 }71 72 const int maxn = 2000;73 bign d[maxn + 10];74 int c[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};75 76 int main(void)77 {78     #ifdef LOCAL79         freopen("11375in.txt", "r", stdin);80     #endif81 82     memset(d, 0, sizeof(d));83     d[0] = 1;84     for(int i = 0; i <= maxn; ++i)85         for(int j = 0; j < 10; ++j)86             if(!(i==0 && j==0) && i+c[j]<=maxn)87                 d[i+c[j]] += d[i];88     for(int i = 2; i <= maxn; ++i)89         d[i] += d[i-1];90     int x;91     while(scanf("%d", &x) == 1)92     {93         if(x < 6)    cout << d[x] << endl;94         else    cout << d[x] + 1 << endl;95     }96     return 0;97 }
代码君

 

UVa 11375 Matches


联系
我们