ACM.暴力枚举

我就是我 2023-06-28 11:10 58阅读 0赞

\#有一类问题可以采用一种盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不符合要求的，保留那些符合要求的，这种方法叫枚举算法。

暴力枚举适用于数据较少的题目。

一.NEFU-8  
二倍的问题  
Problem:8  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。  
Input  
输入包括n组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。  
Output  
对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。  
Sample Input  
3  
1 4 3 2 9 7 18 22 0  
2 4 8 10 0  
7 5 11 13 1 3 0  
Sample Output  
3  
2  
0

#include <stdio.h>
    using namespace std;
    int main()
    {
        
        int t,cnt,ans,a[20];
        scanf("%d",&t);
        for(int ca=1;ca<=t;ca++)//while(t--)
        {
        
            cnt=0;ans=0;             //依旧桶排序
            int x;
            while(~scanf("%d",&x))
            {
        
                if(x==0) break;
                cnt++;
                a[cnt]=x;
            }
    for(int i=1;i<=cnt-1;i++)
            {
        
                for(int j=i+1;j<=cnt;j++)
                {
        //扫一遍，看符合条件的个数
                        if(a[i]==2*a[j]||a[j]==2*a[i])
                            ans++;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

二.NEFU-573  
大乐透  
Problem:573  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
在小明曾经玩过的一种对号码的纸牌游戏(乐透)里,玩家必须从\{1,2,……，49\}中选择6个数。玩Lotto的一个流行策略是（虽然它并不增加你赢的机会）：就是从这49个数中，选出k（k>6）个数组成一个子集S，然后只从S里拿出牌来玩几局游戏。例如，k=8，s=\{1,2,3,5,8,13,21,34\}，那么有28场可能的游戏：\[1,2,3,5,8,13\],\[1,2,3,5,8,21\],\[1,2,3,5,8,34\],\[1,2,3,5,13,21\],……,\[3,5,8,13,21,24\]。  
读取数字k和一组数S，输出由S中的数组成的所有可能的游戏。  
Input  
输入数据有多组，每组一行，每行有多个整数，其中第一个整数为数字k，接下来有k个整数，即子集S。当k为0，输入结束。  
Output  
输出由S中的数组成的所有可能的游戏。每种游戏一行。  
Sample Input  
7 1 2 3 4 5 6 7  
0  
Sample Output  
1 2 3 4 5 6  
1 2 3 4 5 7  
1 2 3 4 6 7  
1 2 3 5 6 7  
1 2 4 5 6 7  
1 3 4 5 6 7  
2 3 4 5 6 7

6层循环遍历所有情况，也只有数据量小的时候可以这么做了，不然必超时间。

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int a[50],k,i1,i2,i3,i4,i5,i6;
        while(scanf("%d",&k)!=-1)
        {
        
            if(k==0)break;
            for(i1=1;i1<=k;i1++)
            scanf("%d",&a[i1]);
            for(i1=1;i1<=k;i1++)
            {
        
                for(i2=i1+1;i2<=k;i2++)
                {
        
                    for(i3=i2+1;i3<=k;i3++)
                    {
        
                        for(i4=i3+1;i4<=k;i4++)
                        {
        
                            for(i5=i4+1;i5<=k;i5++)
                            {
        
                                for(i6=i5+1;i6<=k;i6++)
                                printf("%d %d %d %d %d %d\n",a[i1],a[i2],a[i3],a[i4],a[i5],a[i6]);
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }

三.NEFU-574  
丑数  
Problem:E  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
只有质数2,3,5,7这几个作为因子的数叫做,丑数,比如前20个丑数是(从小到大来说) 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24和25.  
Input  
我们给你个n（1<=m<=5842）当输入n为0结束。  
Output  
输出第n个丑数。每个数一行。  
Sample Input  
1  
2  
3  
4  
11  
Sample Output  
1  
2  
3  
4  
12

这题比较恶心，卡了很长时间，最合理的算法，丑数都是由最先4个最小的丑数乘以2、3、5、7产生之后的丑数，关键是怎么产生之后的丑数，并且让之后产生的所有丑数按升序排列，详见注释。

#include <bits/stdc++.h>
    #define min4(a,b,c,d) min(min(a,b),min(c,d))
    using namespace std;
    int n,p2,p3,p5,p7,a[5850];//定义min4(a,b,c,d)，找四个数中的最小值
    int main()
    {
        
        a[1]=1;p2=p3=p5=p7=1;
        for(int i=2;i<=5842;i++)//打表5842个丑数
        {
        
            a[i]=min4(a[p2]*2,a[p3]*3,a[p5]*5,a[p7]*7);//a[p2]、a[p3]、a[p5]、a[p7]分别为*2、*3、*5、*7的次数
            if(a[i]%2==0)p2++;//如果选择的最小值a[i]是乘以了2，则*2的丑数下标位置后移一位
            if(a[i]%3==0)p3++;
            if(a[i]%5==0)p5++;
            if(a[i]%7==0)p7++;
        }
        while(cin>>n&&n)
        printf("%d\n",a[n]);
        return 0;
    }

四.NEFU-575  
矩形  
Problem:575  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
在测试超大规模集成电路时，对给定的一个设计，专家要检测元件是否相互遮盖。一个元件可视为一个矩形，假设每个矩形都是水平排列的（边与x轴或y轴平行），所以长方形由最小的和最大的x，y坐标表示。  
编程计算完全被覆盖的矩形个数。  
Input  
输入有多组长方形实例。对每组长方形，第一个数字是长方形的数量，然后是长方形的最小和最大x，y坐标（最小x，最大x，最小y，最大y）。  
Output  
对每组输入数据，输出一行，是被完全覆盖的长方形数量。  
Sample Input  
3  
100 101 100 101  
0 3 0 101  
20 40 10 400  
4  
10 20 10 20  
10 20 10 20  
10 20 10 20  
10 20 10 20  
Sample Output  
0  
4  
两组循环暴力枚举所有符合情况的条件即可。

#include <bits/stdc++.h>
    using namespace std;
    struct node
    {
        
        int x1,x2,y1,y2;
    }p[1001];
    int main()
    {
            
        int i,j,n;
        while(scanf("%d",&n)!=-1)
        {
        
            for(i=1;i<=n;i++)
            scanf("%d%d%d%d",&p[i].x1,&p[i].x2,&p[i].y1,&p[i].y2);
            int sum=0;
            for(i=1;i<=n;i++)
            {
        
                int s=0;
                for(j=1;j<=n;j++)
                {
        
                    if(p[i].x1>=p[j].x1&&p[i].x2<=p[j].x2&&p[i].y1>=p[j].y1&&p[i].y2<=p[j].y2)
                        s++;
                }
                if(s==n)
                    sum++;
            }
            printf("%d\n",sum);
        }
        return 0;
    }

五.NEFU-1642  
楼层编号  
Problem:1642  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
小林在 NOIP 比赛期间住在“新世界”酒店。和其他酒店不一样的是，这个酒店每天都有一个高能的数字 t，这个数字在楼层中是不会出现的，以 t=3 为例，则 3、13、31、33 等楼层是不存在的，楼层编号为 1，2，4，5，…所以实际上的 4 楼才是 3 楼。  
已知小林预订了编号为 m 层的房间，并且当天高能数字是 t，现在他想知道房间所在的真实楼层是多少。  
Input  
一行两个整数 m 和 t，1≤m≤100000，0≤t≤9，保证 m 对 t 合法。  
Output  
一行一个整数，表示真实楼层。  
Sample Input  
14 3  
Sample Output  
12  
关键在于判断函数的写法

#include <bits/stdc++.h>
    using namespace std;
    int m,t,i,ans;
    bool judge(int n)//若这个房间存在，即这个房间编号不包含数字t，为true
    {
        
        int d;
        while(n)
        {
        
            d=n%10;
            n=n/10;
            if(d==t)return 0;
        }
        return 1;
    }
    int main()
    {
        
        cin>>m>>t;
        ans=0;
        for(i=1;i<=m;i++)
        {
        if(judge(i))ans++;}
        printf("%d\n",ans);
        return 0;
    }

六.NEFU-1643  
比例简化  
Problem:1643  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某观点表示支持的有 1498 人，反对的有 902 人，那么其比例可以简单地记为1498∶902。  
因该比例的数值太大，难以一眼看出它们的关系。若把比例记为 5∶3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。  
现给出支持人数 A 和反对人数 B，以及一个上限 L，请将 A 比 B 化简为 A′ 比 B′，要求在 A′和 B′ 均不大于 L，且 A′ 和 B′ 互质（两个整数的最大公约数为 1）的前提下，A′/B′≥ A/B 且 A′/B′-A/B 的值尽可能小。  
Input  
一行三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。  
Output  
一行两个整数 A′ 和 B′，中间用一个空格隔开，表示化简后的比例。  
Sample Input  
1498 902 10  
Sample Output  
5 3  
通过暴力枚举找到符合的条件，推荐三个if句分开写，放在一起用&&连接过不了，原因未知。

#include <bits/stdc++.h>
    using namespace std;
    int gcd(int a,int b)
    {
        return b?gcd(b,a%b):a;}
    int main()
    {
        
        int a,b,i,j,l,ans1,ans2;
        double s1,s2,d,min;
        while(cin>>a>>b>>l)
        {
        
            min=10000;
            for(i=l;i>=1;i--)
            {
        
                for(j=l;j>=1;j--)
                {
        
                    if(gcd(i,j)==1)
                    {
        
                        s1=1.0*i/j;
                        s2=1.0*a/b;
                        if(s1>=s2)
                        {
        
                            d=s1-s2;
                            if(d<min)
                            {
        
                                min=d;
                                ans1=i;
                                ans2=j;
                            }
                        }
                    }
                }
            }
            printf("%d %d\n",ans1,ans2);
        }
        return 0;
    }

七NEFU-1644  
奶牛碑文  
Problem:1644  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
小伟暑假期间到大草原旅游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C、O 和 W。尽管小伟看不懂，但是令他高兴的是，C、O、W的顺序形式构成了一句他最喜欢的奶牛单词“COW”。现在，他想知道有多少次 COW 出现在文本中。  
如果 COW 内穿插了其他字符，只要 COW 字符出现在正确的顺序，小伟也不介意。甚至，他也不介意出现不同的 COW 共享一些字母。例如，CWOW 出现了 1 次 COW，CCOW 算出现了2 次 COW，CCOOWW 算出现了 8 次 COW。  
Input  
第 1 行为 1 个整数 N。  
第 2 行为 N 个字符的字符串，每个字符是一个 C、O 或 W。  
Output  
输出 COW 作为输入字符串的字串出现的次数（不一定是连续的）。  
提示：答案会很大，建议用 64 位整数（long long）。  
Sample Input  
6  
COOWWW  
Sample Output  
6

题干中提示了数据将会很大，直接进行暴力枚举一定会超时，下面介绍第一种方法，先在数组中找到中间字母O的位置，在从当前位置出发，向前找C的个数，再向后找W的个数，num1\*num2，即为这个o可形成的cow个数。

#include <bits/stdc++.h>
    using namespace std;
    long long n,i,k1,k2,ans,c[100010],w[100010];
    char str[100010];
    int main()
    {
        
        scanf("%lld%s",&n,str);
        k1=k2=ans=0;//k1，k2为临时计数变量
        for(i=0;i<n;i++)
        {
        
            if(str[i]=='C') k1++;   某位置上，前面c的数量。
            c[i]=k1;            
        }
        for(i=n-1;i>=0;i--)
        {
        
            if(str[i]=='W') k2++;  某位置上，后面w的数量。
            w[i]=k2;
        }
        for(i=0;i<n;i++)
        {
        
            if(str[i]=='O')
            ans=ans+c[i]*w[i];
        }
        printf("%lld\n",ans);
        return 0;
    }

第二种方法代码更简洁，本质上原理是相同的

//COPYRIGHT RESERVED.BY 二班吴有霖
    #include<cstdio>
    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    long long sum=0,sum1=0,sum2=0;;
    char arr[100000];
    int main (void)
    {
        
     int n,i,j,i2,i3;
     scanf("%d",&n);
     scanf("%s",arr);
     for (int i=0; i<n; ++i)
        {
        
            if (arr[i] == 'C')
            {
        
     //C就直接加K
                ++sum;
            }
            else if (arr[i] == 'O')
            {
        
     //O就接上之前的所有C的量(如果前面没有C，那么sum值为0，这里的O的个数也就加不上）
                sum1 += sum;
            }
            else if (arr[i] == 'W')
            {
        
     //W就接上所有O的量（与上面类似）
                sum2 += sum1;
            }
        //这种做法有效的减少了循环次数，防止tle
        }
     printf("%lld\n",sum2);
     return 0;
    }