暴力枚举算法专项-题解(头都大了)

A - 一元三次方程求解

①【暴力枚举—出奇迹】

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. int main()
  5. {
  6.    double a,b,c,d;
  7.    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
  8.    for(double i=-100;i<=100;i+=0.001)
  9.    {
  10.       double j=i+0.001;
  11.       double y1=a*i*i*i+b*i*i+c*i+d;
  12.       double y2=a*j*j*j+b*j*j+c*j+d;
  13.       if(y1>=0&&y2<=0||y1<=0&&y2>=0)
  14.       {
  15.          double x=(i+j)/2;
  16.          printf("%.2lf ",x);
  17.       }
  18.    }
  19. }

②【二分】

因为区间很大，所以可以二分。
三个答案都在[-100,100]范围内，两个根的差的绝对值>=1,保证了每一个大小为1的区间里至多有1个解，也就是说当区间的两个端点的函数值异号时区间内一定有一个解，同号时一定没有解。那么我们可以枚举互相不重叠的每一个长度为1的区间，在区间内进行二分查找。

  1. #include<cstdio>
  2. double a,b,c,d;
  3. double fc(double x)
  4. {
  5.     return a*x*x*x+b*x*x+c*x+d;
  6. }
  7. int main()
  8. {
  9.     double l,r,m,x1,x2;
  10.     int s=0,i;
  11.     scanf("%lf%lf%lf%lf",&a,&b,&c,&d);  //输入
  12.     for (i=-100;i<100;i++)
  13.     {
  14.         l=i; 
  15.         r=i+1;
  16.         x1=fc(l); 
  17.         x2=fc(r);
  18.         if(!x1) 
  19.         {
  20.             printf("%.2lf ",l); 
  21.             s++;
  22.         }      //判断左端点，是零点直接输出。
  24.                         //不能判断右端点，会重复。
  25.         if(x1*x2<0)                             //区间内有根。
  26.         {
  27.             while(r-l>=0.001)                     //二分控制精度。
  28.             {
  29.                 m=(l+r)/2;  //middle
  30.                 if(fc(m)*fc(r)<=0) 
  31.                    l=m; 
  32.                 else 
  33.                    r=m;   //计算中点处函数值缩小区间。
  34.             }
  35.             printf("%.2lf ",r);  
  36.             //输出右端点。
  37.             s++;
  38.         }
  39.         if (s==3) 
  40.             break;             
  41.             //找到三个就退出大概会省一点时间
  42.     }
  43.     return 0;
  44. }

B - Cantor 表

①【暴力求解法】

  1. #include<iostream>
  2. int main(){
  3.     long n,a=1,b=1,i=2;//i初始化必须为2，否则出错（当然你如果有解决办法1或0也可以）
  4.     bool judge=true,become=false;//judge不得为false，否则一开始就错了
  5.     std::cin>>n;
  6.     while(i<=n){
  7.         if(judge&&a==1){
  8.             judge=false;
  9.             b++;
  10.             become=true;//这个变量是变换分母分子的关键点
  11.         }
  12.         else if(!judge&&b==1){
  13.             judge=true;
  14.             a++;
  15.             become=true;
  16.         }
  17.         if(become)i++;//因为是替交，所以无需再像下面操作
  18.         else if(judge){//分母增加分子减少
  19.             a--;
  20.             b++;
  21.             i++;
  22.         }
  23.         else{//分子增加分母减少
  24.             a++;
  25.             b--;
  26.             i++;
  27.         }
  28.         become=false;//不要忘，否则上面的if(become)一直为真则出错
  29.     }
  30.     std::cout<<a<<'/'<<b;
  31.     return 0;
  32. }

②【找规律】

思路：

首先我们观察到第i行，第j列的数就是i/j这是第 一个要发现的。

因为题目中要求是以Z字型编号

我们看题目中的表是：

1/1,1/2,1/3 ……

2/1,2/2,2/3 ……

Z字型编号以后（把头向左偏45度）：

第一行：1/1 (1号)

第二行：1/2 (2号) 2/1 (3号)

第三行：1/3 (6号) 2/2 (5号) 3/1 (4号)

↑ 观察法易得每一行比上一行多1

代码里那个while循环，就是为了通过循环枚举， 判断它在编号之后的第几行，第几个位置。

等差数列求和

公式：

解答 - 图1%7D%7B2%7D%0A#card=math&code=S%3D%5Cfrac%7Bn%28a_n%2Ba_1%29%7D%7B2%7D%0A)

所以，很显然Z字型排序之后，第k行的数编号n满足：

解答 - 图2%7D%7B2%7D%3Cn%E2%89%A4%20%5Cfrac%7Bk(k%2B1)%7D%7B2%7D%0A#card=math&code=%5Cfrac%7Bk%28k%E2%88%921%29%7D%7B2%7D%3Cn%E2%89%A4%20%5Cfrac%7Bk%28k%2B1%29%7D%7B2%7D%0A)

这样就可以把那个循环优化掉

  1. #include <cstdio>
  2. using namespace std; 
  3. int main() {
  4.     int n,k=1;
  5.     cin>>n;
  6.     while (n>k) {
  7.         n=n-k;
  8.         k++;
  9.     }
  10.     if(k%2==0) cout<<n<<"/"<<(k+1-n);
  11.     else cout<<k+1-n<<"/"<<n;
  12.     return 0;
  13. }

代码当中k用来记Z字型编号之后的行数，显然第k行有k个数，因此每次n要减去k。

最后用k判断奇偶，是判断这一行Z字型编号是正序（类似第二行）还是倒序（类似第三行）然后用最开始的结论输出原表中的行号除以列号就行了

C - 不高兴的津津

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. using namespace std;   //作为新手的我会的都写上 
  5. int main ()
  6. {
  7.     int a,b,s,max=0,i,day=0;  //a,b是我们津津（以下简称JJ）每天上课时间，s意为sum是上课时间之和 
  8.     for (i=1;i<8;i++)   // i为循环变量，day是JJ一周最不高兴的一天 
  9.       {
  10.         cin>>a>>b;    //输入a,b 
  11.         s=a+b;   //计算一天的上课时间 
  12.         if ((s>max)&&(s>8)) max=s,day=i;  //在超过8小时且比之前几天都大的s时，将s赋给最大值，并记录下JJ的这天 
  13.       }
  14.     cout<<day; //由于day初值是0，所以如果JJ一周都开心就输出0 
  15.     return 0;             
  16. }

D - 铺地毯

其实这道题，有些题解的方法有些复杂。我们可以有一些投机取巧，因为，是看特定的某个位置上最后一块覆盖了的地毯。所以说，你可以从最后一个输入的数据开始排查，如果说你找到了这个点上面 有地毯，那么就直接输出这个值，如果没找到就按 照题干的意思输出-1。

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int shuzu[10001][10001];//自定义一个二维数组，内存看自己。
  5. int main()
  6. {
  7.     int n,x,y;
  8.     int b=1;
  9.     cin>>n;
  10.     for(int i=1;i<=n;++i)
  11.     {
  12.         for(int ii=1;ii<=4;++ii)
  13.         cin>>shuzu[i][ii];                               //输入数据
  14.     }
  15.     cin>>x>>y;
  16.     for(int q=n;q>=1;--q)
  17.     {
  18.         if((shuzu[q][1]<=x)&&(shuzu[q][3]+shuzu[q][1]>=x)&&(shuzu[q][2]<=y)&&(shuzu[q][2]+shuzu[q][4]>=y))    //比较，如果包含了，就继续。
  19.         {
  20.             cout<<q;
  21.         b=2    ;
  22.         }
  23.         if(b==2)
  24.         break;
  25.         if(q==1)
  26.         {
  27.             cout<<-1;
  28.         break;
  29.         }
  30.     }
  31.     return 0;
  32. }

E - 三连击

暴力，加简化的判断，数学原理，2个集合内所有数相加相乘结果一样，2个集合的内容一样

①【代码1】

  1. #include <stdio.h>
  2. int main()
  3. {
  4.     int a,b,c;
  5.     for(a=123;a<=333;a++)
  6.             {
  7.                 b=a*2;
  8.                 c=a*3;
  9.                 if((a/100+a/10%10+a%10+b/100+b/10%10+b%10+c/100+c/10%10+c%10==1+2+3+4+5+6+7+8+9)&&((a/100)*(a/10%10)*(a%10)*(b/100)*(b/10%10)*(b%10)*(c/100)*(c/10%10)*(c%10)==(1)*(2)*(3)*(4)*(5)*(6)*(7)*(8)*(9)))
  10.                     printf("%d %d %d\n",a,b,c);
  11.             }
  12.     return 0;
  13. }

②【代码二】

  1. #include<cstdio>
  2. #include<cstring>
  3. int i,j,v;bool a[10];//ai表示第i个数已经用过了
  4. int main()
  5. {
  6.     for(i=192;i<=327;i++)//第一个数最小192，最大327。其实不知道的情况下简单来说是从123-329的但是算出来是最值就稍微改了下下
  7.     {
  8.         memset(a,0,sizeof(a));v=0;//清零
  9.         a[i%10]=a[i/10%10]=a[i/100]=a[i*2%10]=a[i*2/10%10]=a[i*2/100]=a[i*3%10]=a[i*3/10%10]=a[i*3/100]=1;//统计数字
  10.         for(j=1;j<=9;j++) v+=a[j];//v表示1-9这些数字是否全部齐了
  11.         if(v==9) printf("%d %d %d\n",i,i*2,i*3);//如果齐了就输出
  12.     }
  13. return 0;
  14. }

F -最大公约数和最小公倍数问题(辗转相除法)

思路：把两数相乘，再遍历他的因子即可

  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4. typedef long long ll;
  5. int m,n,ans,flag;
  6. ll gcd(ll x,ll y)
  7. {
  8.     if(y==0)    {return x;}
  9.     return gcd(y,x%y);
  10. }
  11. int main()
  12. {
  13.     cin>>n>>m;
  14.     for(int i=1;i<=sqrt(1ll*m*n);i++)
  15.     {
  16.         if((1ll*n*m)%i==0&&gcd(i,(1ll*n*m)/i)==n)
  17.         {
  18.             ans++;
  19.             if(1ll*i*i==1ll*n*m)  flag=1;
  20.         }
  21.     }
  22.     cout<<ans*2-flag;//最后乘以二是因为只遍历了一半
  23.     return 0;
  24. }

G - 连续自然数和

特意去学了数学公式的代码 头都大了

设首项为 L，末项为 R，那么

解答 - 图3%3D%20%5Cfrac%7B(L%2BR)(R%E2%88%92L%2B1)%7D%7B2%7D%3DM%0A#card=math&code=sum%28L%2CR%29%3D%20%5Cfrac%7B%28L%2BR%29%28R%E2%88%92L%2B1%29%7D%7B2%7D%3DM%0A)

即

解答 - 图4(R-L%2B1)%3D2M%0A#card=math&code=%20%28L%2BR%29%28R-L%2B1%29%3D2M%0A)

可以把 2M分解成两个数之积，枚举假设分成了两个数 k1,k2，我们令 k1<k2，可以列一个二元一次方程组

解答 - 图5

解得

解答 - 图6

显然当k1 k2一奇一偶 时，L,R才是整数.

但是 L = R的情况是被不允许的，即

解答 - 图7

即

解答 - 图8

  1. #include<cstdio>
  2. #include<iostream>
  3. using namespace std;
  4. int m;
  5. int main(){
  6.     cin>>m;
  7.     for(int k1=sqrt(2*m);k1>1;k1--)//枚举k1(注意是k1>1而不是k1>=1)
  8.         if(2*m%k1==0 && (k1+2*m/k1)%2){//如果K2是整数而且与K1一奇一偶
  9.             int k2=2*m/k1;
  10.             cout<<(k2-k1+1)/2<<" "<<(k1+k2-1)/2<<endl;//输出答案
  11.         }
  12.     return 0;
  13. }

H - 约瑟夫

  1. #include <stdio.h>
  2. int main()
  3. {
  4.     int k,i;
  5.     scanf("%d",&k);
  6.     int flag=1,m=k;
  7.     while (flag)
  8.     {
  9.         m++;//m至少为k+1
  10.         int cursor=0;//设置光标的移动
  11.         for (i=0; i<k; i++)
  12.         {
  13.             cursor=(cursor+m-1)%(2*k-i);//下一次出列之人的编号
  14.             if (cursor<k)break;//判断出列的那个人是否小于k，小于就进行下一个m的判断
  15.             if (i==k-1)flag=0;//说明已经找到最小的m
  16.         }
  17.     }
  18.     printf("%d\n",m);
  19.     return 0;
  20. }

I - 子数整除

暴力就是最优解

  1. #include<cstdio>
  2. #include<iostream>
  3. using namespace std;
  4. bool f;//f用来判断是否有符合条件的数
  5. int main()
  6. {
  7.     int k,a1;
  8.     cin>>k;
  9.     for(int i=10000;i<=30000;i++)
  10.     {
  11.       if(i/100%k==0)//判断1到3位
  12.           if((i/10-i/10000*1000)%k==0)//判断2到4位
  13.             if((i-i/1000*1000)%k==0) cout<<i<<endl,f=1;//判断2到5位，若都符合，输出该数，f为真，继续搜索
  14.     }
  15.     if(!f) cout<<"No";
  16.     return 0;
  17. }

J - 手机

暴力枚举

  1. #include<iostream>
  2. #include<string>
  3. #include<cstring>
  4. using namespace std;
  5. int a[10005],totals=0;
  6. string s;
  7. int main()
  8. {
  9.       //这......就是我的打表大法
  10.       //把每一个字母对应的ascll码值在数组中的位置标记成需要按多少次
  11.     a[int('a')]=1;
  12.     a[int('b')]=2;
  13.     a[int('c')]=3;
  14.     a[int('d')]=1;
  15.     a[int('e')]=2;
  16.     a[int('f')]=3;
  17.     a[int('g')]=1;
  18.     a[int('h')]=2;
  19.     a[int('i')]=3;
  20.     a[int('j')]=1;
  21.     a[int('k')]=2;
  22.     a[int('l')]=3;
  23.     a[int('m')]=1;
  24.     a[int('n')]=2;
  25.     a[int('o')]=3;
  26.     a[int('p')]=1;
  27.     a[int('q')]=2;
  28.     a[int('r')]=3;
  29.     a[int('s')]=4;
  30.     a[int('t')]=1;
  31.     a[int('u')]=2;
  32.     a[int('v')]=3;
  33.     a[int('w')]=1;
  34.     a[int('x')]=2;
  35.     a[int('y')]=3;
  36.     a[int('z')]=4;
  37.     getline(cin,s);
  38.     for(int i=0;i<=s.size()-1;i++)
  39.     {
  40.         if(s[i]==' ')//空格特殊处理
  41.         {
  42.             totals+=1;
  43.         }
  44.         else
  45.         {
  46.             totals+=a[int(s[i])];
  47.         }
  48.     }
  49.     cout<<totals;
  50.     return 0;
  51. }

K - 回文日期

枚举后面四位（月份+日期）会更快。

枚举后四位然后求出整个日期，判断是否在范围内即可。

2月不需要判断是否是闰年，因为0229反过来是9220，整个日期是92200229，而9220年是闰年

  1. #include<cstdio>
  2. #include<iostream>
  3. using namespace std;
  4. int a, b, ans;//a,b=从a->b中的年份,ans=计数器(有几个回文年数) 
  5. int x, y;//从x年至y年 
  6. int t[1000000], q[25] = { 31,29,31,30,31,30,31,31,30,31,30,31 };//一年的月份 
  7. int hw(int u)//对数字u进行反序处理 
  8. {
  9.     int k = 0;
  10.     while (u != 0)
  11.     {
  12.         k = k * 10 + u % 10;//每次加新数时,k往前挪一个位置 
  13.         u /= 10;
  14.     }
  15.     return k;
  16. }
  17. int main()
  18. {
  19.     //20191101
  20.     int i, j, k1, k2, k;
  21.     cin >> a >> b;
  22.     x = a % 100000 / 10000 + a % 1000000 / 100000 * 10 + a % 10000000 / 1000000 * 100 + a % 100000000 / 10000000 * 1000;//算出是几几年 
  23.     y = b % 100000 / 10000 + b % 1000000 / 100000 * 10 + b % 10000000 / 1000000 * 100 + b % 100000000 / 10000000 * 1000;//同理 
  24.     //对x->y年进行枚举 
  25.     for (i = x; i <= y; i++)//年 
  26.         for (k1 = 1; k1 <= 12; k1++)//月 
  27.             for (k2 = 1; k2 <= q[k1 - 1]; k2++)//日 
  28.             {
  29.                 //                cout<<i<<" "<<k1<<" "<<k2<<endl;
  30.                 k = i * 10000 + k1 * 100 + k2;//构成这天用8位数表达方式 
  31.                 if (k == hw(k))//判断是否回文 
  32.                     ans++;
  33.             }
  34.     cout << ans;//输出 
  35.     return 0;//好习惯 
  36. }

L- 棋盘问题

①【暴力枚举】

  1. #include<cstdio>
  2. #include<iostream>
  3. using namespace std;
  4. int m, n, z, c, i, j, k, l;    //z用来记正方形个数，c来记长方形
  5. int main()
  6. {
  7.     cin >> m >> n;           //输入
  8.     for (i = 0; i <= m; i++)    //枚举
  9.         for (j = 0; j <= n; j++)    //枚举
  10.             for (k = i + 1; k <= m; k++)  //还是枚举
  11.                 for (l = j + 1; l <= n; l++)  //仍然是枚举
  12.                     if (k - i == l - j)z++;     //是正方形
  13.                     else c++;            //是长方形
  14.     cout << z << " " << c;     //输出
  15. }

②【找规律】

说说公式是怎么推导的吧

找规律:

正方形:

边长为1的正方形个数为n*m

边长为2的正方形个数为(n-1)*(m-1) （自己动手想想）

边长为3的正方形为个数(n-2)*(m-2)

边长为min(n,m)的正方形为个数s1=(n-min(n,m)+1)*(m-min(n,m)+1)

然后从边长为1到min（m，m）的正方形个数全部加起来；

长方形:(包括正方形，好像正方形属于长方形来着？)

长为1的长方形（包括正方形）有n个

长为2的长方形（包括正方形）有n-1个

长为n的长方形（包括正方形）有1个

长为1到n的长方形1+2+…+n个

同理 宽为1的长方形（包括正方形）有m个

宽为2的长方形（包括正方形）有m-1个

宽为m的长方形（包括正方形）有1个

宽为1-m的长方形1+2+…+m个

然后把它们乘起来，根据乘法原理，总数s2=((1+n)_(1+m)_n*m)/4

题目要求的是“非正方形的长方形”，因此要减去s1

  1. #include<cstdio>
  2. #include<iostream>
  3. using namespace std;
  4. int main()
  5. {
  6.     int n, m, s1 = 0, s2;
  7.     cin >> n >> m;
  8.     s2 = ((m + 1)*(n + 1)*m*n) / 4;
  9.     for (; m >= 1 && n >= 1; m--, n--)
  10.         s1 += m * n;
  11.     cout << s1 << " " << s2 - s1;
  12.     return 0;
  13. }

能看到这里 说明你非常认真 加油！！！