【复习】基础水小技巧

1.进制转换：

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 int n,k;
 5 string s;
 6 int main()
 7 {
 8     cin>>n>>k;
 9     while(n>0)
10     {
11         if( n%k >= 10 ) s=(char)( n%k + 55)+s;  //余数大于10的要用ABCD等来表示
12         else s=(char)( n%k +48)+s;
13         n/=k;
14     }
15     cout<<s<<endl;
16 }

样例输入：

第一个数是要转换的数第二种是转换的进制。

case1：23 2

case2：159 16

样例输出：

case1:10111

case2:9F

2.进制反转换

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 string s;
 5 int ans,num=1,k;
 6 int main()
 7 {
 8     cin>>k;
 9     cin>>s;
10     for(int i=s.size()-1;i>=0;i--)
11     {
12         if(s[i]>='A' && s[i]<='Z')
13         ans+=num*((int)(s[i])-55);
14         else
15         ans+=num*((int)(s[i])-48);
16         num*=k;
17     }
18     cout<<ans<<endl;
19 }

样例输入：

第一个数是要转换的进制第二种是转换出来的十进制数。

case1：2 10111

case2：16 9F

样例输出：

case1:23

case2:159

3.二进制小数转换

 1 #include<iostream>
 2 #include<cmath>
 3 #include<string>
 4 using namespace std;
 5 int ans,m;
 6 double n;
 7 int n2;
 8 string s;
 9 int main()
10 {
11     cin>>n>>m;
12     n2=(int)(n);
13     while(n2>0)
14     {
15         s+=(char)(n2%2 +48);
16         n2/=2;
17     }
18     s+='.'; 
19     n-=floor(n);
20     for(int i=0;i<m;i++)
21     {
22         ans=floor(n*2);
23         n=n*2-floor(n*2);
24         s+=ans+48;
25     }
26     cout<<s<<endl;
27     return 0;
28 }

样例输入：

第一个数为输入的转换的数第二要转换小数的位数

5.149 6

输出:

101.001001

4.大整数模板

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #define maxn 1010
 6 using namespace std;
 7 int a[maxn],b[maxn];
 8 string sa,sb;
 9 void inter(int x[maxn],string s)
10 {
11     for(int i=0;i<s.size();i++) x[s.size()-1-i]=s[i]-48;
12 }
13 void add(int a[],int b[],int lena,int lenb)
14 {
15     int c[maxn];
16     int l=0;
17     memset(c,0,sizeof(c));
18     int x=0;
19     while(l<=lena || l<=lenb)
20     {
21         c[l]=a[l]+b[l]+x;
22         x=c[l]/10;
23         c[l]%=10;
24         l++;
25     }
26     while(c[l]==0 && l>1) l--;
27     for(int j=l;j>=0;j--) cout<<c[j];
28     cout<<endl;
29 }
30 int subjudge(int lena,int lenb)
31 {
32     if(lena>=lenb) return 0;
33     if(lena<lenb) return 1;
34 }
35 void sub(int a[],int b[],int lena,int lenb)
36 {
37     int pd=subjudge(lena,lenb);
38     if(pd==1) 
39     {
40         cout<<"-";
41         sub(b,a,lenb,lena);
42         return;
43     }
44     int c[maxn];
45     int l=0;
46     memset(c,0,sizeof(c));
47     while(l<=lena || l<lenb)
48     {
49         if(b[l]>a[l])
50         {
51             a[l]+=10;
52             c[l]=a[l]-b[l];
53             a[l+1]--;
54         }
55         else
56          c[l]=a[l]-b[l];
57         l++; 
58     }
59       while(c[l]==0 && l>0) l--;
60           for(int j=l;j>=0;j--)  cout<<c[j]; 
61           cout<<endl;
62 }
63 void mul(int a[],int b[],int lena,int lenb)
64 {
65     int c[10010];//应该是c[maxn*maxn]但是这样是1e8数组超过最大上限。 
66     int l=0;
67     memset(c,0,sizeof(c));
68     int x;
69     for(int i=0;i<=lena;i++)
70     {
71         x=0;
72         for(int j=0;j<=lenb;j++)
73      {
74         c[i+j-1]+=a[i]*b[j]+x;
75         x=c[i+j-1]/10;
76         c[i+j-1]%=10;
77      }
78         c[i+lenb]=x;
79     }
80     l=lenb+lena;
81     while(c[l]==0 && l>1) l--;
82     for(int j=l;j>=0;j--) cout<<c[j];
83     cout<<a[lena]*b[lenb];
84     cout<<endl;
85 }
86 int main()
87 {
88     cin>>sa>>sb;
89     inter(a,sa);
90     inter(b,sb);
91     add(a,b,sa.size(),sb.size());    
92     sub(a,b,sa.size(),sb.size());
93     mul(a,b,sa.size(),sb.size());
94     return 0;
95 }

加减乘除没写……

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 5000
 6 using namespace std;
 7 struct SPH{
 8     int len,s[maxn];
 9     SPH(){
10         memset(s,0,sizeof(s));
11         len=1;
12     }
13     SPH operator = (const char* num)
14     {
15         len=strlen(num);
16         for(int i=0;i<len;++i) s[i]=num[len-i-1]-48;
17         return *this;
18     }
19     SPH operator=(const int num){
20         char a[maxn];
21         sprintf(a,"%d",num);
22         *this=a;
23         return *this;
24     }
25     SPH (const int num){ *this=num;
26     }
27     SPH (const char * num){ *this=num;
28     }
29     SPH operator+(const SPH & a)
30     {
31         SPH c;
32         c.len=max(len,a.len)+1;
33         int x=0;
34         for(int i=0;i<c.len;++i)
35         {
36             c.s[i]=s[i]+a.s[i]+x;
37             x=c.s[i]/10;
38             c.s[i]=c.s[i]%10;
39         }
40         if(c.s[c.len-1]==0) --c.len;
41         return c;
42     }
43     SPH operator+=(const SPH & a){
44         *this=*this+a;
45         return *this;
46     }
47     SPH operator*(const SPH & x){
48         SPH c;
49         c.len=len+x.len;
50         for(int i=0;i<len;++i){
51             for(int j=0;j<x.len;++j){
52                 c.s[i+j]+=s[i]*x.s[j];
53                 c.s[i+j+1]+=c.s[i+j]/10;
54                 c.s[i+j]%=10;
55             }
56             
57         }
58         if(c.len-1) --c.len;
59         return c;    }
60     SPH operator *=(const SPH & a){
61         *this=*this * a;
62         return *this;
63     }
64     bool operator < (const SPH & x) const{
65     if(len !=x.len) return len<x.len;
66     for(int i=len-1;i>=0;i--){
67         if(s[i]!=x.s[i]) return s[i]<x.s[i];
68     }
69     return false;}
70     bool operator >(const SPH & x) const {return x<*this;}
71     bool operator <=(const SPH & x) const {return !(x<*this);}
72     bool operator >=(const SPH & x) const {return !(x>*this);}
73     bool operator ==(const SPH & x) const {return !(x<*this||x>*this);}
74     bool operator !=(const SPH & x) const {return x<*this||x>*this;}
75     };
76     ostream& operator << (ostream &out,const SPH& x){
77         for(int i=x.len-1;i>=0;i--)
78         cout<<x.s[i];
79         return out;
80     }
81     istream& operator >> (istream &in,SPH& x)
82     {
83         char num[maxn];
84         in>>num;
85         x=num;
86         return in;
87     }
88 
89 int main()
90 {
91     SPH n,m,sum;
92     cin>>n>>m;
93     sum=n+m;
94     cout<<sum<<" ";
95     sum=n*m;
96     cout<<sum;
97     return 0;
98 }

只有加和乘

5.阶乘高精

 1 #include<iostream>
 2 #define maxn 10010
 3 using namespace std;
 4 int a[maxn];
 5 int n;
 6 int main()
 7 {
 8     cin>>n;
 9     a[1]=1;
10     for(int k=2;k<=n;k++)
11     {
12         for(int i=1;i<maxn;i++) a[i]*=k;
13         for(int i=1;i<maxn;i++)
14         {
15             a[i+1]+=a[i]/10;
16             a[i]%=10;
17         }
18     }
19     int l=maxn-1;
20     while(a[l]==0) l--;
21     for(int j=l;j>=1;j--) cout<<a[j];
22     cout<<endl;
23     return 0;
24 }

纪念曾经AC的第一道比赛题，MGR出题。

6.线性筛素数

 1 #include<iostream>
 2 #include<cmath>
 3 #define maxn 10000000
 4 using namespace std;
 5 int a[maxn];
 6 int n,m;
 7 int xx;
 8 void oulashai()
 9 {
10     a[1]=1;
11     for(int i=2;i<=(int)(sqrt(n));i++) if(!a[i]) for(int j=i*i;j<=n;j=j+i) a[j]=1;
12 }
13 int main()
14 {
15     cin>>n>>m;
16     oulashai();
17     for(int i=1;i<=m;i++)
18     {
19         cin>>xx;
20         if(a[xx]==0) cout<<"Yes"<<endl;
21         else if(a[xx]==1) cout<<"No"<<endl;
22     }
23     return 0;
24 }

7.优先队列实现大根堆小根堆

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 #define maxn 201
 5 using namespace std;
 6 struct sph{
 7        int c;                //重载！ 
 8        sph(){}
 9        sph(int c):c(c){}
10        bool operator < (const sph& a)const {return c>a.c;} 
11 };
12 int main()
13 {
14     int a[maxn];
15     int n=0;
16     cin>>n;
17     int xx;
18     sph x1;
19     priority_queue<int>q1;
20     priority_queue<sph>q2;
21     for(int i=0;i<n;i++)
22     {
23         cin>>xx;
24         q1.push(xx);
25         q2.push((sph)(xx));
26      } 
27     for(int i=0;i<n;i++)  //大根堆 
28     {
29         cout<<q1.top()<<" ";
30         q1.pop();
31     }
32     cout<<endl;
33     for(int i=0;i<n;i++)     //小根堆 
34     {
35         x1=q2.top();
36         cout<<x1.c<<" ";
37         q2.pop();
38     }
39     return 0;
40 }

8.快速幂模板

 1 #include<iostream>
 2 using namespace std;
 3 long long a,b,m;
 4 long long power(long long a, long long b, long long c){
 5     long long ans=1,t=a;
 6     while (b){if(b%2==1) ans=ans*t %c;
 7     b>>=1;t=t*t %c;}
 8     return ans;}
 9 int main()
10 {
11     cin>>a>>b>>m;
12     cout<<a<<'^'<<b<<" mod "<<m<<'='<<power(a,b,m);
13     return 0;
14 }

9.压位高精4位（只实现+）

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define maxn 1010
using namespace std;
int a[maxn],b[maxn];
string sa,sb;
int inter(int x[maxn],string s)
{
int l=s.size();
int i=0,t=0;
for(l-=1;l>2;l-=4)
{
if(l-3>=0)
x[i++]=(s[l-3]-48)*1000+(s[l-2]-48)*100+(s[l-1]-48)*10+(s[l]-48);
}
if(l==0)
x[i++]=s[0]-48;
else if(l==1)
x[i++]=(s[0]-48)*10+(s[1]-48);
else if(l==2)
x[i++]=(s[0]-48)*100+(s[1]-48)*10+(s[2]-48);
while(i>0&&x[i-1]==0)
i--;
return i;
}
void add(int a[],int b[],int lena,int lenb)
{
int c[maxn];
int l=0;
memset(c,0,sizeof(c));
int x=0;
while(l<=lena || l<=lenb)
{
c[l]=a[l]+b[l]+x;
x=c[l]/10000;
c[l]%=10000;
l++;
}
while(c[l]==0 && l>1) l--;
for(int j=l;j>=0;j--) cout<<c[j];
cout<<endl;
}
int subjudge(int lena,int lenb)
{
if(lena>=lenb) return 0;
if(lena<lenb) return 1;
}
void sub(int a[],int b[],int lena,int lenb)
{
int pd=subjudge(lena,lenb);
if(pd==1)
{
cout<<"-";
sub(b,a,lenb,lena);
return;
}
int c[maxn];
int l=0;
memset(c,0,sizeof(c));
while(l<=lena || l<lenb)
{
if(b[l]>a[l])
{
a[l]+=10;
c[l]=a[l]-b[l];
a[l+1]--;
}
else
c[l]=a[l]-b[l];
l++;
}
while(c[l]==0 && l>0) l--;
for(int j=l;j>=0;j--) cout<<c[j];
cout<<endl;
}
void mul(int a[],int b[],int lena,int lenb)
{
int c[10010];//应该是c[maxn*maxn]但是这样是1e8数组超过最大上限。
int l=0;
memset(c,0,sizeof(c));
int x;
for(int i=0;i<=lena;i++)
{
x=0;
for(int j=0;j<=lenb;j++)
{
c[i+j-1]+=a[i]*b[j]+x;
x=c[i+j-1]/10;
c[i+j-1]%=10;
}
c[i+lenb]=x;
}
l=lenb+lena;
while(c[l]==0 && l>1) l--;
for(int j=l;j>=0;j--) cout<<c[j];
cout<<a[lena]*b[lenb];
cout<<endl;
}
int main()
{
cin>>sa;
cin>>sb;
inter(a,sa);
inter(b,sb);
for(int i=0;i<inter(a,sa);i++) cout<<a[i];
cout<<endl;
add(a,b,sa.size()-1,sb.size()-1);
// sub(a,b,sa.size()/4,sb.size()/4);
// mul(a,b,sa.size()/4,sb.size()/4);
return 0;

}