模拟算法

按照题目要求一步一步写

枚举算法

又叫做暴力搜索算法

1、列举所有可能性

2、通过条件筛除正确答案

福尔摩斯密码

ABCDE*X=EDCBA

ABCDEX各是多少？

for(int a=1;a<10;a++)

for(int b=0;b<10;b++)

for(int c=0;c<10;c++)

for(int d=0;d<10;d++)

for(int e=1;e<10;e++)

for(int x=2;x<10;x++){

   if(互不相同){

       int num=---;

       int num2=---;

       if(num*x==num2){

           cout<<---;

       }

   }

}

枚举算法限制：

可能性过多->超时

可能性列不出来(小数)

条件表达不出来

枚举算法例题：

选手猜想：

A说：E是第一名

B说：我是第二名

C说：A肯定垫底

D说：C肯定拿不了第一名

E说：D应该是第一名

比赛结果：

E不是第二也不是第三，且只有第一和第二名猜对了

求他们的排名

for(int a=1;a<6;a++)

for(int b=1;b<6;b++)

for(int c=1;c<6;c++)

for(int d=1;d<6;d++)

for(int e=1;e<6;e++){

   if(互不相同){

       if(e不是2不是3){

           bool as=e==1;

           bool bs=b==2;

           bool cs=a==5;

           bool ds=c!=1;

           bool es=d==1;

           if(as+bs+cs+ds+es==2){

               if(a*b==2&&as+bs==2||

                   a*c==2&&as+cs==2||

                   a*d==2&&as+ds==2||...

               )

               cout<<---;

           }

       }

   }

}

快速幂

将a^b降幂处理，降低循环次数

通常求 a^b mod m 的结果

long long ksm(long long a,long long b,long long m){

   long long ans=1;

   while(b){

       if(b%2==1){

           ans*=a;

           ans%=m;

       }

       b/=2;

       a=a*a;

       a%=m;

   }

   return ans;

}

普及组算法：模拟、枚举、贪心(没讲)、递推、递归、二分(没讲)、倍增

高精度算法：加减乘除

核心思想：模拟小学数学列竖式

输入两个大整数（长度很长），输出他们的和

222222222222222222222

1111111

求和

222222222222223333333

解决策略：

   存数据：string

   对齐：倒序

   计算：转类型，进位，保存

   输出结果：倒序，去除前导零

string addll(string a,string b){

   int la=a.size(),lb=b.size();

   reverse(a.begin(),a.end());

   reverse(b.begin(),b.end());

   int n1[1000]={},n2[1000]={},n3[1000]={};

   for(int i=0;i<la;i++) n1[i]=a[i]-48;

   for(int i=0;i<lb;i++) n2[i]=b[i]-48;

   int jw=0;

   for(int i=0;i<=max(la,lb);i++){

       int num=jw+n1[i]+n2[i];

       n3[i]=num%10;

       jw=num/10;

   }

   int i=max(la,lb)+50;

   while(n3[i]==0&&i>0) i--;

   string ans="";

   for(;i>=0;i--){

       ans+=(char)(n3[i]+48);

   }

   return ans;

}

string subll(string a,string b){}