数学

常用算法模版

判断n是否为素数 ：

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

求最大公约数：

int gcb(int a,int b){
 
   return b==0 ? a:gcb(b,a%b);
 
}

最长递增子序列

for ( j=1; j<len; j++ )
    for ( i=0; i<j; i++ )
        if ( a[j]>a[i] && dp[j]<dp[i]+1 )
            dp[j] = dp[i]+1;

X的二进制长度

 int BitLength(int x)
      {
          int d = 0;
          while (x > 0) {
              x >>= 1;
              d++;
          }
          return d;
      }

质因数分解

 int reduce(int prime[],int pn,int n,int rest[])
      {
      int i,k=0;
      for(i=0;i<pn;i++)
           {
           if (n==1) break;
           if (prime[i]*prime[i]>n) {rest[k++]=n;break;}
           while(n%prime[i]==0)
               {
               n/=prime[i];
               rest[k++]=prime[i];
               }
           }
      return k;
      }

任意进制转换

    void conversion(char s[],char s2[],long d1,long d2)
      {
          long i,j,t,num;
          char c;
          num=0;
          for (i=0;s[i]!='\0';i++)
              {
              if (s[i]<='9'&&s[i]>='0') t=s[i]-'0'; else t=s[i]-'A'+10;
              num=num*d1+t;
              }
          i=0;
          while(1)
              {
              t=num%d2;
              if (t<=9) s2[i]=t+'0'; else s2[i]=t+'A'-10;
              num/=d2;
              if (num==0) break;
              i++;
              }
          for (j=0;j<i/2;j++)
              {c=s2[j];s2[j]=s[i-j];s2[i-j]=c;}
          s2[i+1]='\0';
      }

大数加法

 string solve(string s, string t) {
        // write code here
        if(s.size()<t.size())
        {
            string temp=s;
            s=t;
            t=temp;
        }
        int len1=s.size();
        int len2=t.size();
        int num1,num2,flag=0,sum;
        while(len1>0)
        {
            num1=s[len1-1]-'0';
            if(len2>0)
                num2=t[len2-1]-'0';
            else
                num2=0;
            sum=num1+num2+flag;
            s[len1-1]=sum%10+'0';
            flag=sum/10;
            len1--;
            len2--;
        }
        if(flag==1)
            s="1"+s;
        return s;
    }

字符串查找

    int strfind(char str[],char key[])
      {
          int l1,l2,i,j,flag;
          l1=strlen(str);
          l2=strlen(key);
          for (i=0;i<=l1-l2;i++)
              {
              flag=1;
              for (j=0;j<l2;j++)
                  if (str[i+j]!=key[j]) {flag=0;break;}
              if (flag) return i;
              }
          return -1;
      } 

背包问题

给你ｎ个价值的东西及背包容量ｃ，然后知道ｎ个东西的价值ｖ［ｉ］以及重量ｗ［ｉ］ 求在背包容量范围为内可以装的最多的价值。

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int w[1005],v[1005],dp[1005];
int main()
{
    int i,j,tcase,n,c;
    scanf("%d",&tcase);
    while(tcase--)
    {
        scanf("%d%d",&n,&c); 
        for(i=0;i<n;i++)
        {
            scanf("%d",&v[i]);
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",&w[i]);
        }
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
          {
             for(j=c;j>=w[i];j--)
               {
                   dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
               }
          }
        printf("%d\n",dp[c]);
    }
    return 0;
}