暴力求解 ----- 枚举

2023-12-26 15:41:15

暴力求解 ----- 枚举

1.1 如何快速判断该题是否可以使用枚举算法？

分析数据量

注意：

1000 1000 1000 ms = 1 0 7 10^7 107 运算

一个算法的时间复杂度	该算法1000ms内可以处理的数据量
O ( n ! ) O(n!) O(n!)	10 10 10
O ( 2 n ) O(2^n) O(2n)	20 20 20
O ( n 3 ) O(n^3) O(n3)	200 200 200
O ( n 2 ) O(n^2) O(n2)	3000 3000 3000
O ( n l o g n ) O(nlogn) O(nlogn)	1 0 6 10^6 106
n n n	1 0 7 10^7 107
n \sqrt{n} n	1 0 14 10^{14} 1014
l o g n logn logn	1 0 20 10^{20} 1020

如上表所示，可以根据题目所给数据量的大小来设计算法

例如：

若题目所给数据量大小为 1 0 7 10^7 107,那么就需要设计一个时间复杂度为n的算法，若大于该值，则必然会超时

1.2 王道例题：

1.2.1 abc

KY15 abc ------------题目链接

时间限制：1秒空间限制：64M

题目描述

设a、b、c均是0到9之间的数字，abc、bcc是两个三位数，且有：abc+bcc=532。

求满足条件的所有a、b、c的值。

输入描述：

题目没有任何输入。

输出描述：

请输出所有满足题目条件的a、b、c的值。 a、b、c之间用空格隔开。每个输出占一行。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    for(int i = 0; i <= 9; i++)
    {
        for(int j = 0; j <= 9; j++)
        {
            for(int k = 0; k <= 9; k++)
            {
                if(100 * i + 110 * j + 12 * k == 532)
                {
                    cout<<i<< ' '<< j << ' ' << k <<endl;
                }
            }
        }
    }
   return 0;
}

1.2.2 反序数

KY266 反序数---------题目链接

时间限制：1秒空间限制：32M

题目描述

设N是一个四位数，它的9倍恰好是其反序数（例如：1234的反序数是4321）

求N的值

输入描述：

程序无任何输入数据。

输出描述：

输出题目要求的四位数，如果结果有多组，则每组结果之间以回车隔开。

AC代码

#include<bits/stdc++.h>
using namespace std;
int fan_xue(int n)
{
    int ans = 0;
    while(1)
    {
        ans = ans + n%10;
        n = n / 10;
        if(n==0) break;
        ans = ans * 10 ;
    }
    return ans;
}
int main()
{
    for(int i = 1000; i <= 9999; i++)
    {
        if(i * 9 == fan_xue(i))
        {
            cout<<i<<endl;
        }
    }
    return 0;
}

1.2.3 对称平方数1

KY267 对称平方数1 -------题目链接

题目描述

打印所有不超过256，其平方具有对称性质的数。如2，11就是这样的数，因为 2 ∗ 2 = 4 2*2=4 2∗2=4， 11 ∗ 11 = 121 11*11=121 11∗11=121。

输入描述：

无任何输入数据

输出描述：

输出具有题目要求的性质的数。如果输出数据不止一组，各组数据之间以回车隔开。

应该要加上条件 0 < = n < = 256 0<= n <= 256 0<=n<=256要不然有可能是负的，也是可以的

AC代码：

#include<bits/stdc++.h>
using namespace std;
bool is_duichen(int n)
{
    string s1 = "";
    string s2 = "";
    vector<int> ve;
    while(n)
    {
        ve.push_back(n%10);
        n = n / 10;
    }
    for(int i = 0; i < ve.size(); i++)
    {
        s1 = s1 + to_string(ve[i]);
        s2 = to_string(ve[i]) + s2;
    }
    return s2 == s1;
}
int main()
{
    for(int i = 0; i <= 256; i++)
    {
        int t = i * i;
        if(is_duichen(t))
        {
            cout<< i << endl;
        }
    }
    return 0;
}

1.3 本节习题：

1.3.1 与7无关的数

KY50 与7无关的数 --------题目来源

时间限制：1秒空间限制：64M

题目描述：

一个正整数,如果它能被7整除,或者它的十进制表示法中某个位数上的数字为7, 则称其为与7相关的数.现求所有小于等于n(n<100)的与7无关的正整数的平方和。

输入描述：

案例可能有多组。对于每个测试案例输入为一行,正整数n,(n<100)

输出描述：

对于每个测试案例输出一行，输出小于等于n的与7无关的正整数的平方和。

示例1

输入：

输出：

思路：

确实破防了，求了半天的与7有关的数，唉

我是先将前100个的数据都求出来
然后存到数组里，并不是每次都是进入循环再重新开始求
因为我觉得以空间换时间还是很靠谱的，可能那样做会超时

AC代码：

#include<bits/stdc++.h>
using namespace std;
bool is_have7(int n)
{
    while(n)
    {
        if(n%10==7)
        {
            return true;
        }
        n = n / 10;
    }
    return false;
}
int main()
{
    int ans[100] = {0};
    int sum = 0;
    for(int i = 0; i < 100; i++)
    {
        if(i%7!=0&&!is_have7(i))
        {
            sum = sum + i * i;
        }
        ans[i] = sum;
    }
    int x;
    while(cin>>x)
    {
        cout<<ans[x]<<endl;
    }
    return 0;
}

1.3.2 百鸡问题

KY156 百鸡问题 --------题目来源

题目描述

用小于等于n元去买100只鸡，大鸡5元/只，小鸡3元/只,还有1/3元每只的一种小鸡，分别记为x只,y只,z只。编程求解x,y,z所有可能解。

输入描述：

测试数据有多组，输入n。

输出描述：

对于每组输入,请输出x,y,z所有可行解，按照x，y，z依次增大的顺序输出。

示例1

输入：

输出：

x=0,y=0,z=100
x=0,y=1,z=99
x=0,y=2,z=98
x=1,y=0,z=99

思路

不是很好：
我设的数量分别为x,y,z,但是，在循环嵌套时，循环的退出条件设置的不好

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        for(int x = 0;5 * x <= n ; x++)
        {
            for(int y = 0; 3 * y <= n - 5 * x; y++)
            {
                if((n - 5 * x - 3 * y) * 3 + x + y >= 100)
                {
                    int z = 100 - x - y;
                    if(5 * x + 3 * y + 1/3*z <=n&& z>=0)
                    {
                       cout<<"x="<<x<<','<<"y="<<y<<','<<"z="<<z<<endl; 
                    }
                }
            }
        }  
    }
    return 0;
}

更好的解法：

#include<stdio.h>

int main() {
	int n;
	while (scanf("%d",&n)>0){
		float b = 5.0, s = 3.0, ms = 1.0 / 3;
		for (int x = 0; x <= 100; x++) {
			for (int y = 0; y <= 100; y++) {
				int z = 100 - x - y;
				if (x * b + s * y + ms * z == n) {
					printf("x=%d,y=%d,z=%d\n",x,y,z);
				}
			}
		}
	}
	
	return 0;
}

1.3.3 Old Bill

KY95 Old Bill ------题目链接

题目描述

Among grandfather’s papers a bill was found. 72 turkeys $679 The first and the last digits of the number that obviously represented the total price of those turkeys are replaced here by blanks (denoted _), for they are faded and are illegible. What are the two faded digits and what was the price of one turkey? We want to write a program that solves a general version of the above problem. N turkeys $XYZ The total number of turkeys, N, is between 1 and 99, including both. The total price originally consisted of five digits, but we can see only the three digits in the middle. We assume that the first digit is nonzero, that the price of one turkeys is an integer number of dollars, and that all the turkeys cost the same price. Given N, X, Y, and Z, write a program that guesses the two faded digits and the original price. In case that there is more than one candidate for the original price, the output should be the most expensive one. That is, the program is to report the two faded digits and the maximum price per turkey for the turkeys.

输入描述：

The first line of the input file contains an integer N (0<N<100), which represents the number of turkeys. In the following line, there are the three decimal digits X, Y, and Z., separated by a space, of the original price $XYZ.

输出描述：

For each case, output the two faded digits and the maximum price per turkey for the turkeys.

示例1

输入：

输出：

3 2 511
9 5 18475
0

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,y,z;
    while(cin>>n)
    {
         cin>>x>>y>>z;
        int maxx = 0;
        int maxx_l = -1;
        int maxx_r = -1;
        int tt = x*100 + y*10 + z;
        for(int i = 1; i <= 9; i++)
        {
            tt = i*1000 + tt;
            for(int j = 0; j <= 9; j++)
            {
                tt = tt * 10 + j;
                if(tt%n==0)
                {
                    if(maxx<tt/n)
                    {
                        maxx = tt / n;
                        maxx_l = i;
                        maxx_r = j;
                    }
                }
                tt = tt / 10;
            }
            tt = tt % 1000;
        }
        if(maxx_l!=-1)
        {
           cout<<maxx_l<<' '<<maxx_r<<' '<<maxx<<endl; 
        }
        else
        {
            cout<<maxx<<endl;
        }
        
    }
   return 0;
}

码农公寓

暴力求解 ----- 枚举

1.1 如何快速判断该题是否可以使用枚举算法？

1.2 王道例题：

1.2.1 abc

1.2.2 反序数

1.2.3 对称平方数1

1.3 本节习题：

1.3.1 与7无关的数

1.3.2 百鸡问题

1.3.3 Old Bill

相关文章