topscoding主题库模板题

目录

模板题

【模板题】分因数（P1101）

【模板题】区间素数 III（P1113）

进制转换 III (任意转任意)    （P2463）

A+B Problem（高精度加法）

A-B Problem（高精度减法）

 A*B Problem（高精度乘法）

A/B Problem（高精除以低精） 

查找m个数字 

子串查找 

差分

set的插入和遍历 

应为最近比较忙所以一直没有更新对不起sorry，之后的话会不定期的发布文章，请大家谅解。

---

模板题

【模板题】分因数（P1101）

#include<bits/stdc++.h> 
//#include<cmath>
using namespace std;
int main()
{int n;cin>>n;//输入cout<<n<<"=";while(n > 1){for ( int i = 2;i <= n; i++){if (n %i==0){n=n/i;cout<<i;if(n!=1){cout<<"*";}break;}}}return 0;
} 

【模板题】区间素数 III（P1113）

#include <bits/stdc++.h>
using namespace std;const int N = 1e8+10;
bitset<N> flag;void prime(int n)
{flag[0] = flag[1] = 1;flag[2] = 0;for(int i = 2; i <= n; i++){if(!flag[i]){for(int j = i+i; j <= n; j+=i)flag[j] = 1;}}
}int main()
{int m, n, ans = 0;cin >> m >> n;prime(n);for(int i = m; i <= n; i++){if(!flag[i])ans++;}cout << ans;return 0;
}

进制转换 III (任意转任意)    （P2463）

#include<bits/stdc++.h>
using namespace std;
long long _zhuan10(string a,long long b)
{long long s=0,k=1,t,len=a.size();for(long long i=len-1;i>=0;i--){t=(a[i]>='A'?a[i]-65+10:a[i]-48);s=s+t*k;k=k*b;}return s;
}
string _10zhuan(long long a,long long b)
{string c;while(a!=0){char t=a%b+48;if(t>'9'){t=64+t-'9'; } c=c+t;a=a/b;}reverse(c.begin(),c.end());return c;   
} 
int main()
{string a;long long b,c;cin>>a>>b>>c;if(a=="0"){cout<<0;return 0;}long long t=_zhuan10(a,b);cout<<_10zhuan(t,c); 
}   

A+B Problem（高精度加法）

//***wuhaotian***//
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[250],b[250],c[250];
int k=0,t=0,p;
int main(){cin >> s1>> s2;int len1=s1.size(),len2=s2.size(),len;for(int i=len1-1;i>=0;i--){a[k]=s1[i]-48;k++;}for(int i=len2-1;i>=0;i--){b[t]=s2[i]-48;t++;}len=max(len1,len2);for(int i=0;i<len;i++){ c[i]=a[i]+b[i];}for(int i=0;i<len;i++){ if(c[i]>=10){c[i+1]=c[i+1]+c[i]/10;c[i]=c[i]%10;} }for(int i=len;i>=0;i--){if(c[i] != 0){p=i;break;}}for(int i=p;i>=0;i--){cout << c[i];}
}

A-B Problem（高精度减法）

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[260],b[260],c[260];
int main(){int k=0,t=0,p=0;char f='-';cin >> s1>> s2;int len1= s1.size(),len2=s2.size();if(len1<len2 || len1==len2&&s1<s2){cout <<f;swap(s1,s2);}len1= s1.size(),len2=s2.size(); for(int i=len1-1;i>=0;i--){ a[k]=s1[i]-48;k++;} for(int i=len2-1;i>=0;i--){b[t]=s2[i]-48;t++;}for(int i=0;i<len1;i++){ if(a[i]<b[i]){a[i+1]-=1; a[i]=a[i]+10;}c[i]=a[i]-b[i];} for(int i=len1-1;i>=0;i--){if(c[i]!=0){p=i;break;}}for(int i=p;i>=0;i--){cout << c[i];} 
}

 A*B Problem（高精度乘法）

#include<bits/stdc++.h>
using namespace std;    
int p,a[1010],b[1010],c[2010];
int k=0,t=0;
string s1,s2; 
int main(){cin>>s1>>s2;if(s1=="0"||s2=="0"){cout << 0;return 0;} int len1=s1.size(),len2=s2.size();//注意长度在外面定义for(int i=len1-1;i>=0;i--){ //逆序存储到数组中  a[k]=s1[i]-48; k++;    } for(int i=len2-1;i>=0;i--){  b[t]=s2[i]-48;t++;     }for(int i=0;i<=len1-1;i++){   for(int j=0;j<=len2-1;j++){  //第i位和第j位相乘的结果一定是对应在i+j位//一定要注意是+=，因为某一位上可能存放着多组乘积  c[i+j]=c[i+j]+a[i]*b[j];}}int len=s1.size()+s2.size();//结果的长度最长a.size()+b.size()for(int i=0;i<len;i++){//处理进位 c[i+1]=c[i+1]+c[i]/10;c[i]=c[i]%10;}for(int i=len;i>=0;i--){if(c[i]!=0){  p=i;break;}//找出最高不为0的位置 }for(int i=p;i>=0;i--){cout<<c[i];}return 0;
}

A/B Problem（高精除以低精） 

#include<bits/stdc++.h>
using namespace std;
int b,c[10001],t=0,f;//c表示商 ，t表示被除数 
int main()
{string a;cin>>a>>b;int la=a.size(),i,p;for(i=0;i<=la-1;i++){t=t*10+a[i]-48;c[i]=t/b;t=t%b;}for(i=0;i<=la-1;i++){if(c[i]!=0){ p=i;f=1;break;}}if(f==1){for(i=p;i<=la-1;i++){   cout<<c[i];   }//cout<<"..."<<t;//输出余数 }else{cout << 0;//判断是否出现小数除以大数的情况 }return 0;
}

查找m个数字 

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[2*N], n, m, q;
int check(int q)
{int l = 1, r = n;while(l <= r){int mid = (l+r) >> 1;if(a[mid] == q)return q;else if(a[mid] > q)r = mid - 1;else l = mid + 1;}return -1;
}
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i ++)scanf("%d", &a[i]);sort(a+1, a+n+1);scanf("%d", &m);for(int i = 1; i <= m; i ++){scanf("%d", &q);printf("%d\n", check(q));}return 0;
} 

子串查找 

#include<bits/stdc++.h>
using namespace std;
int main()
{string a,b;int s=0;int f=0;getline(cin,a);getline(cin,b);int nops=a.find(b);	if(nops==-1){cout<<-1;f=1;}else{while(nops!=-1){//cout<<nops<<endl;s++;nops=a.find(b,nops+1);}}if(f==0){cout<<s;}}

差分

//***wuhaotian***//
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int q[N], s[N];
void w( int l,int r,int c)
{s[l] =s[l]+ c;s[r+1]=s[r+1]- c;
}
int main()
{int n , m ; cin>> n >> m;for( int i = 1 ; i <= n ; i++ ){cin >>q[i];w(i,i,q[i]);}while(m--){int l , r , c;cin>>l>>r>>c; w(l,r,c);}for( int i = 1 ; i <= n ; i++ ){s[i]=s[i]+s[i-1];} for( int i = 1 ; i <= n ; i++ ){cout<<s[i]<<" ";} 
}

set的插入和遍历 

#include<bits/stdc++.h>
using namespace std;
int main(){set<int> s;//set可以自动去重和排序，默认升序 int n,t;cin >> n;for(int i=1;i<=n;i++){cin >> t;s.insert(t);//set没有push_back操作 }set<int>::iterator it;//set需要使用迭代器遍历数据 for(it=s.begin();it!=s.end();it++){//set支持双向迭代器 cout << *it << " ";}
}

应为最近比较忙所以一直没有更新对不起sorry，之后的话会不定期的发布文章，请大家谅解。