topscoding主题库模板题

目录

模板题

【模板题】分因数（P1101）

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

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

A+B Problem（高精度加法）

A-B Problem（高精度减法）

 A*B Problem（高精度乘法）

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

查找m个数字 

子串查找 

差分

set的插入和遍历 

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

---

模板题

【模板题】分因数（P1101）

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

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

#include 
using namespace std;
 
const int N = 1e8+10;
bitset 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
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
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
	{ 
        c[i]=a[i]+b[i];
    }
    for(int i=0;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
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
	{
        cout <
        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
	{ 
        if(a[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
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//处理进位 
        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<
    }
    return 0;
}
 
 

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

#include
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<
        //cout<<"..."<
    }
    else{
        cout << 0;//判断是否出现小数除以大数的情况 
    }
    
    return 0;
}
 
 
 

查找m个数字 

#include
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
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<
			s++;
			nops=a.find(b,nops+1);
		}
	}
	if(f==0)
	{
		cout<
	}
	
}

差分

//***wuhaotian***//
#include
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<" ";
	} 
}

set的插入和遍历 

#include
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，之后的话会不定期的发布文章，请大家谅解。