BigInt 的使用！

今天学长讲的卡特兰数真的是卡的一批，整个全是高精的题，这时我就使用重载运算符，然后一下午就过去了

首先来看一波水题（也就卡了2小时）

内存限制：512 MiB 时间限制：1000 ms 标准输入输出

原题来自：BZOJ 3907

某城市的街道呈网格状，左下角坐标为

这道题是把对角线上方的对角线翻折，然后，自己一看就是C（n+m,n）-C(n+m,n-1),然后就是高精部分，我就不说了;

先看一下我一开始打的代码：

前方高能！

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<cstdlib>
  6 #include<ctime>
  7 using namespace std;
  8 #define maxn 10000
  9 #define base 10000
 10 //可能重载运算符码量稍大qwq,而且巨难调试
 11 struct Bigint
 12 {
 13     int c[maxn],len,sign;
 14     Bigint(){memset(c,0,sizeof(c)),len=1,sign=0;}
 15     void Zero()
 16     {
 17         while(len>1&&c[len]==0)len--;
 18         if(len==1&&c[len]==0)sign=0;        
 19     } 
 20     void Write(char *s)
 21     {
 22         int k=1,l=strlen(s);
 23         for(int i=l-1;i>=0;i--)
 24         {
 25             c[len]+=(s[i]-'0')*k;
 26             k*=10;
 27             if(k==base)
 28                 k=1,len++;
 29         }
 30     }
 31     void Read()
 32     {
 33         char s[maxn]={0};
 34         scanf("%s",s);
 35         Write(s);
 36     }
 37     void Print()
 38     {
 39         if(sign)printf("-");
 40         printf("%d",c[len]);
 41         for(int i=len-1;i>=1;i--)printf("%d",c[i]);
 42         printf("
");
 43     } 
 44     bool operator < (const Bigint &a)const
 45     {
 46         if(len!=a.len)return len<a.len;
 47         for(int i=len;i>=1;i--)
 48             if(c[i]!=a.c[i])return c[i]<a.c[i];
 49         return 0;
 50     }
 51     bool operator > (const Bigint &a)const
 52     {
 53         return a<*this;
 54     }
 55     Bigint operator = (int a)
 56     {
 57         char s[100];
 58         sprintf(s,"%d",a);      //int ->string
 59         Write(s);
 60         return *this;
 61     }
 62     Bigint operator + (const Bigint &a)
 63     {
 64         Bigint r;
 65         r.len=max(len,a.len)+1;
 66         for(int i=1;i<=r.len;i++)
 67         {
 68             r.c[i]+=c[i]+a.c[i];
 69             r.c[i+1]+=r.c[i]/base;
 70             r.c[i]%=base; 
 71         }
 72         r.Zero();
 73         return r;
 74     } 
 75     Bigint operator + (const int &a)
 76     {
 77         Bigint b;b=a;
 78         return *this+b;
 79     }
 80     Bigint operator - (const Bigint &a)
 81     {
 82         Bigint b,c;
 83         b=*this;
 84         c=a;
 85         if(c>b)
 86         {
 87             swap(b,c);
 88             b.sign=1;
 89         }
 90         for(int i=1;i<=b.len;i++)
 91         {
 92             b.c[i]=b.c[i]-c.c[i];
 93             if(b.c[i]<0)
 94             {
 95                 b.c[i]+=base;
 96                 b.c[i+1]--;
 97             }
 98         }
 99         b.Zero();
100         return b;
101     } 
102     Bigint operator - (const int &a)
103     {
104         Bigint b;b=a;return *this-b;
105     }
106     Bigint operator * (const Bigint &a)
107     {
108         Bigint r;
109         r.len=len+a.len+2;
110         for(int i=1;i<=len;i++)
111         {
112             for(int j=1;j<=a.len;j++)
113                 r.c[i+j-1]+=c[i]*a.c[j];
114         } 
115         for(int i=1;i<=r.len;i++)
116         {
117             r.c[i+1]+=r.c[i]/base;
118             r.c[i]%=base;
119         }
120         r.Zero();
121         return r;
122     } 
123     Bigint operator * (const int &a)
124     {
125         Bigint b;b=a;
126         return *this*b;
127     }
128     Bigint operator / (const Bigint &b)
129     {
130         Bigint r,t,a;
131         a=b;
132         r.len=len;
133         for(int i=len;i>=1;i--)
134         {
135             t=t*base+c[i];
136             int div,ll=0,rr=base;
137             while(ll<=rr)
138             {
139                 int mid=(ll+rr)/2;
140                 Bigint k=a*mid;
141                 if(k>t)rr=mid-1;
142                 else
143                 {
144                     ll=mid+1;    
145                     div=mid; 
146                 } 
147             }
148             r.c[i]=div;
149             t=t-a*div;
150         }
151         r.Zero();
152         return r; 
153     }
154     Bigint operator / (const int &a)
155     {
156         Bigint b;b=a;
157         return *this/b;
158     }
159 };
160 int main()
161 {
162     //freopen("cd.txt","r",stdin);
163     Bigint a,b,c;
164     int n,m;
165     scanf("%d%d",&n,&m);
166     a=1,b=1;
167     for(int i=m+2;i<=n+m;i++)
168         a=a*i;
169     if(m+1-n>0)
170     a=a*(m+1-n);
171     for(int i=1;i<=n;i++)
172         b=b*i;
173     c=a/b;
174     c.Print();
175     //cout<<clock()<<endl;
176     return 0;
177 }

高能代码

然后，我就直接站一下，我今天一下午顺便集齐的BigInt操作：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 using namespace std;
  6 #define maxn 2000
  7 #define base 10000
  8  
  9 struct Bign
 10 {
 11     int c[maxn],len,sign;
 12     //初始化 
 13     Bign(){memset(c,0,sizeof(c)),len = 1,sign = 0;}
 14     //高位清零
 15     void Zero()
 16     {
 17         while(len > 1 && c[len] == 0)len--;
 18         if(len == 1 && c[len] == 0)sign = 0;        
 19     } 
 20     //压位读入 
 21     void Write(char *s)
 22     {
 23         int k = 1,l = strlen(s);
 24         for(int i = l - 1;i >= 0;i--)
 25         {
 26             c[len] += (s[i] - '0') * k;
 27             k *= 10;
 28             if(k == base)
 29             {
 30                 k = 1;
 31                 len++;
 32             }
 33         }
 34     }
 35     void Read()
 36     {
 37         char s[maxn] = {0};
 38         scanf("%s",s);
 39         Write(s);
 40     }
 41     //输出
 42     void Print()
 43     {
 44         if(sign)printf("-");
 45         printf("%d",c[len]);
 46         for(int i = len - 1;i >= 1;i--)printf("%04d",c[i]);
 47         printf("
");
 48     } 
 49     //重载 = 运算符，将低精赋值给高精 
 50     Bign operator = (int a)
 51     {
 52         char s[100];
 53         sprintf(s,"%d",a);
 54         Write(s);
 55         return *this;//this只能用于成员函数，表示当前对象的地址 
 56     } 
 57     //重载 < 运算符
 58     bool operator < (const Bign &a)const
 59     {
 60         if(len != a.len)return len < a.len;
 61         for(int i = len;i >= 1;i--)
 62         {
 63             if(c[i] != a.c[i])return c[i] < a.c[i];
 64         }
 65         return 0;
 66     }
 67     bool operator > (const Bign &a)const
 68     {
 69         return a < *this;
 70     }
 71     bool operator <= (const Bign &a)const
 72     {
 73         return !(a < *this);
 74     }
 75     bool operator >= (const Bign &a)const
 76     {
 77         return !(*this < a);
 78     }
 79     bool operator != (const Bign &a)const
 80     {
 81         return a < *this || *this < a;
 82     }
 83     bool operator == (const Bign &a)const
 84     {
 85         return !(a < *this) && !(*this < a);
 86     }
 87     bool operator == (const int &a)const
 88     {
 89         Bign b;b = a;
 90         return *this == b;
 91     }
 92  
 93     //重载 + 运算符
 94     Bign operator + (const Bign &a)
 95     {
 96         Bign r;
 97         r.len = max(len,a.len) + 1;
 98         for(int i = 1;i <= r.len;i++)
 99         {
100             r.c[i] += c[i] + a.c[i];
101             r.c[i + 1] += r.c[i] / base;
102             r.c[i] %= base; 
103         }
104         r.Zero();
105         return r;
106     } 
107     Bign operator + (const int &a)
108     {
109         Bign b;b = a;
110         return *this + b;
111     }
112     //重载 - 运算符
113     Bign operator - (const Bign &a)
114     {
115         Bign b,c;// b - c
116         b = *this;
117         c = a;
118         if(c > b)
119         {
120             swap(b,c);
121             b.sign = 1;
122         }
123         for(int i = 1;i <= b.len;i++)
124         {
125             b.c[i] -= c.c[i];
126             if(b.c[i] < 0)
127             {
128                 b.c[i] += base;
129                 b.c[i + 1]--;
130             }
131         }
132         b.Zero();
133         return b;
134     } 
135     Bign operator - (const int &a)
136     {
137         Bign b;b = a;
138         return *this - b;
139     }
140     //重载 * 运算符 
141     Bign operator * (const Bign &a)
142     {
143         Bign r;
144         r.len = len + a.len + 2;
145         for(int i = 1;i <= len;i++)
146         {
147             for(int j = 1;j <= a.len;j++)
148             {
149                 r.c[i + j - 1] += c[i] * a.c[j];
150             }
151         } 
152         for(int i = 1;i <= r.len;i++)
153         {
154             r.c[i + 1] += r.c[i] / base;
155             r.c[i] %= base;
156         }
157         r.Zero();
158         return r;
159     } 
160     Bign operator * (const int &a)
161     {
162         Bign b;b = a;
163         return *this * b;
164     }
165     //重载 / 运算符 
166     Bign operator / (const Bign &b)
167     {
168         Bign r,t,a;
169         a = b;
170         //if(a == 0)return r;
171         r.len = len;
172         for(int i = len;i >= 1;i--)
173         {
174             t = t * base + c[i];
175             int div,ll = 0,rr = base;
176             while(ll <= rr)
177             {
178                 int mid = (ll + rr) / 2;
179                 Bign k = a * mid;
180                 if(k > t)rr = mid - 1;
181                 else
182                 {
183                     ll = mid + 1;    
184                     div = mid; 
185                 } 
186             }
187             r.c[i] = div;
188             t = t - a * div;
189         }
190         r.Zero();
191         return r; 
192     }
193     Bign operator / (const int &a)
194     {
195         Bign b;b = a;
196         return *this / b;
197     }
198     //重载 % 运算符
199     Bign operator % (const Bign &a)
200     {
201         return *this - *this / a * a;
202     }
203     Bign operator % (const int &a)
204     {
205         Bign b;b = a;
206         return *this % b;
207     }
208 };
209  
210 int main()
211 {
212     freopen("Bign.in","r",stdin);
213     freopen("Bign.out","w",stdout);
214     Bign a,b,c,d,e,f,g;
215     a.Read();
216     b.Read();
217     c = a + b;
218     c.Print();
219     d = a - b;
220     d.Print();
221     e = a * b;
222     e.Print();
223     f = a / b;
224     f.Print();
225     g = a % b;
226     g.Print();
227     return 0;
228 }

BigInt

然后第二题也是卡特兰数的水题，但是.............我又卡了2个小时

重载运算符，确实很好用，但是不能拿重载之前的低精的复杂度来考虑，稍有不慎，重载运算符的复杂度就能高的惊人！

BigInt 的使用！

A. 网格

题目描述