首页 > 编程语言 >算法 —— 暴力枚举

算法 —— 暴力枚举

时间:2024-07-25 23:25:59浏览次数:15  
标签:arr 暴力 int 算法 cin ++ 枚举 include

目录

循环枚举

P2241 统计方形(数据加强版)

P2089 烤鸡

P1618 三连击(升级版)

子集枚举

P1036 [NOIP2002 普及组] 选数

P1157 组合的输出

排列枚举 

P1706 全排列问题

P1088 [NOIP2004 普及组] 火星人


循环枚举

顾名思义,通过for循环或者while循环枚举所有可能方案。 

P2241 统计方形(数据加强版)

很显然这是一道找规律的题目:正方形和长方形的唯一区别在于长宽是否相等,根据此条件可以统计矩形个数,先研究规律:

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)

首先是横着的长方形,宽始终为1,长不断发生改变,可以看出长为2的时候,第一行个数为6个,总共有6 x 6个,长为3的时候,总共有6 x 5个……以上述循环条件来看可以得出一个规律:

长发生变化后的矩形总个数为m * ( n - j + 1)个。

第二看纵向宽发生改变,长重置为1,长为1,宽为2的时候,第一行个数为7个,总共有5 x 7 个,长为2,宽为2的时候 第一行个数为6个,共有5 x 6个……综上所述,可以得出普遍规律:
( m - i + 1) * ( n - j + 1)为每次发生长变化或者宽变化的矩形总个数,又因为长方形与正方形唯一区别是长宽是否相等,因此代码如下:

#include<iostream>
using namespace std;
int main()
{
	int n, m; cin >> n >> m;
	long count1 = 0, count2 = 0;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			if (i == j)
				count1 += (m - i + 1) * (n - j + 1);
			else
				count2 += (m - i + 1) * (n - j + 1);
	cout << count1 << ' ' << count2 << endl;
	return 0;
}

P2089 烤鸡

 暴力枚举,用十个循环解决此问题,注意:n如果小于10或者大于30直接输出0即可,原因是十种配料之和最小为10,最大为30。

#include <iostream>
using namespace std;

int main()
{
	int n, count = 0; cin >> n;
	if (n < 10 || n > 30)
	{
		cout << 0 << endl;
		return 0;
	}
	else
	{
        for (int a = 1; a <= 3; a++)
            for (int b = 1; b <= 3; b++)
                for (int c = 1; c <= 3; c++)
                    for (int d = 1; d <= 3; d++)
                        for (int e = 1; e <= 3; e++)
                            for (int f = 1; f <= 3; f++)
                                for (int g = 1; g <= 3; g++)
                                    for (int h = 1; h <= 3; h++)
                                        for (int i = 1; i <= 3; i++)
                                            for (int j = 1; j <= 3; j++)
                                                if (a + b + c + d + e + f + g + h + i + j == n)
                                                    count++;
        cout << count << endl;
        for (int a = 1; a <= 3; a++)
            for (int b = 1; b <= 3; b++)
                for (int c = 1; c <= 3; c++)
                    for (int d = 1; d <= 3; d++)
                        for (int e = 1; e <= 3; e++)
                            for (int f = 1; f <= 3; f++)
                                for (int g = 1; g <= 3; g++)
                                    for (int h = 1; h <= 3; h++)
                                        for (int i = 1; i <= 3; i++)
                                            for (int j = 1; j <= 3; j++)
                                                if (a + b + c + d + e + f + g + h + i + j == n)
                                                    cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << ' ' << f << ' ' << g << ' ' << h << ' ' << i << ' ' << j << ' ' << endl;
	}
	return 0;
}

P1618 三连击(升级版)

 本人比较喜欢用stl接口,下面附上代码,注意:输入123,456,789,输出123,456,789

#include<bits/stdc++.h>
using namespace std;

int a, b, c, t1, t2, t3; string def;

int main()
{
	cin >> a >> b >> c;
	for (int i = 1; i <= 1000 / c; i++) //记得从1开始  原因:123,456,789满足
	{
		t1 = i * a; t2 = i * b; t3 = i * c;
		string s1 = to_string(t1), s2 = to_string(t2), s3 = to_string(t3);
		string tmp; tmp += s1; tmp += s2; tmp += s3;
		sort(tmp.begin(), tmp.end()); //排序
		auto it = unique(tmp.begin(), tmp.end()); //去重操作
		tmp.resize(distance(tmp.begin(), it)); //计算两个迭代器之间的距离
		if (tmp.size() == 9 && tmp[0] == '1')
		{
			cout << s1 << ' ' << s2 << ' ' << s3 << endl;
			def = tmp;
		}
	}
	if(def.size()==0) //空的说明都不满足
		cout << "No!!!" << endl;
	return 0;
}

子集枚举

P1036 [NOIP2002 普及组] 选数

这是一道简单的模拟题,枚举出所有可能情况,不会超过规定时间的,以下附上k<=3的代码,如果需要更大的k,继续仿照写即可。

#include <bits/stdc++.h>
using namespace std;

int n, k;

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

int main()
{
	cin >> n >> k;
	vector<int> arr(n), pri;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		int tmp = arr[i];
		if (is_prinum(tmp) && k == 1)
			count++;
		if (k == 1)
			continue;
		for (int j = i + 1; j < n; j++)
		{
			int tmp = arr[i] + arr[j];
			if (is_prinum(tmp) && k == 2)
				count++;
			if (k == 2)
				continue;
			for (int z = j + 1; z < n; z++)
			{
				int tmp = arr[i] + arr[j] + arr[z];
				if (is_prinum(tmp) && k == 3)
					count++;
				if (k == 3)
					continue;
			}
		}
	}
	cout << count << endl;
	return 0;
}

P1157 组合的输出

与上面一题类似,也是求子集,直接for循环叠加:,下面只举例到3:

#include <bits/stdc++.h>
using namespace std;

int n, k;

int main()
{
	cin >> n >> k;
	vector<string> arr(n), ans;
	for (int i = 0; i < n; i++)
		arr[i] = to_string(i + 1);
	for (int i = 0; i < n; i++)
	{
		if (k == 1)
		{
			cout << setw(3) << stoi(arr[i]) << endl;
			continue;
		}
		for (int j = i + 1; j < n; j++)
		{
			if (k == 2)
			{
				cout << setw(3) << arr[i] << setw(3) << arr[j] << endl;
				continue;
			}
			for (int z = j + 1; z < n; z++)
			{
				if (k == 3)
				{
					cout << setw(3) << arr[i] << setw(3) << arr[j] << setw(3) << arr[z] << endl;
					continue;
				}
			}
		}
	}
	return 0;
}

排列枚举 

P1706 全排列问题

本题可以点击此链接看我另一篇文章,其中解释了如何使用stl库的函数解决该问题。


P1088 [NOIP2004 普及组] 火星人

本题不过多赘述,与上题一样也是stl的使用,以下为代码:

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n, m; cin >> n >> m;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	for (int j = 1; j <= m; j++)
		next_permutation(arr.begin(), arr.end());
	for (auto e : arr)
		cout << e << ' ';
	return 0;
}

标签:arr,暴力,int,算法,cin,++,枚举,include
From: https://blog.csdn.net/fen_0108/article/details/140675417

相关文章

  • python实现图像特征提取算法1
    python实现Marr-Hildreth算法、Canny边缘检测器算法1.Marr-Hildreth算法详解算法步骤公式Python实现详细解释优缺点2.Canny边缘检测器算法详解算法步骤公式Python实现详细解释优缺点1.Marr-Hildreth算法详解Marr-Hildreth算法是一个......
  • python实现盲反卷积算法
    python实现盲反卷积算法盲反卷积算法算法原理算法实现Python实现详细解释优缺点应用领域盲反卷积算法盲反卷积算法是一种图像复原技术,用于在没有先验知识或仅有有限信息的情况下,估计模糊图像的原始清晰图像和点扩散函数(PSF)。盲反卷积在摄影、医学成......
  • 2024“钉耙编程”中国大学生算法设计超级联赛(1)
    2024“钉耙编程”中国大学生算法设计超级联赛(1)循环位移HDU-7433思路字符串哈希,将A串拼接两遍记为AA,然后对其哈希一下,用map/set记录哈希值,因为\(|A|\le|B|\),所以只要检查B中长度为\(|A|\)的子串哈希值是否存在AA中即可。代码#include<bits/stdc++.h>usingna......
  • [数据压缩] LZ4压缩算法 [转]
    1LZ4压缩算法概述由来、特点LZ4是一种快速的压缩算法,具有高压缩比、高解压缩速度。特别适用于对大量数据进行高效压缩和解压缩的场景。Lz4压缩算法是由YannCollet在2011年设计实现的,lz4属于lz77系列的压缩算法。lz77严格意义上来说不是一种算法,而是一种编码理论,它只定义了......
  • 基于De-Jitter Buffer算法的无线网络业务调度matlab仿真,对比RR调度算法
    1.程序功能描述     去抖动缓冲器(动态缓冲技术)通常在用户终端的流式播放器处采用,以最小化分组延迟对用户体验的降级。然而,由于无线电信道的波动,在无线分组网络中,为流用户提供服务质量(QoS)仍然是一项具有挑战性的任务。在这个项目中,我们将提出一种去抖动缓冲区感知调度器,......
  • *算法训练(leetcode)第三十一天 | 1049. 最后一块石头的重量 II、494. 目标和、474. 一
    刷题记录*1049.最后一块石头的重量II*494.目标和474.一和零*1049.最后一块石头的重量IIleetcode题目地址本题与分割等和子集类似,要达到碰撞最后的石头重量最小,则尽可能把石头等分为两堆。时间复杂度:O......
  • 汉明权重(Hamming Weight)(统计数据中1的个数)VP-SWAR算法
    汉明权重(HammingWeight)(统计数据中1的个数)VP-SWAR算法定义汉明重量是一串符号中非零符号的个数。它等于同样长度的全零符号串的汉明距离(在信息论中,两个等长字符串之间的汉明距离等于两个字符串对应位置的不同字符的个数)。汉明重量在常见的数据位符号串中,它是1的个数。......
  • 三维点云中常用的表面重建算法
    表面重建算法起源于计算机视觉和计算几何学领域。早期的研究集中在从二维图像中提取三维信息。然而,随着三维扫描技术的进步,越来越多的研究转向了如何从点云数据中重建表面。三维点云表面重建技术的发展,始于20世纪90年代,主要推动力是激光扫描和结构光扫描的广泛应用。Resulto......
  • 从信息论的角度看微博推荐算法
    引言在数字时代,推荐系统已成为社交媒体和其他在线服务平台的核心组成部分。它们通过分析用户行为和偏好,为用户提供个性化的内容,从而提高用户满意度和平台的参与度。推荐系统不仅能够增强用户体验,还能显著提升广告投放的效率和效果。随着技术的不断进步,信息论在推荐系统中的......
  • 两数之和-枚举
    题目描述:个人题解:    可以先枚举出数组中的每一个数x,寻找数组中是否存在(target-x),当我们使用遍历整个数组的方式寻找(target-x)时,需要注意到每一个位于x之前的元素都已经和x匹配过,因此不需要再进行匹配。而每一个元素不能被使用两次,所以我们只需要在x......