算法 - 暴力枚举枚举的基本条件：解题思路一、P2241 统计方形P1618 三连击（升级版）P3392 涂国旗P3799 妖梦拼木棒 D：货物摆放

62 阅读 0 评论 41 点赞

我是靠谱客的博主寂寞胡萝卜，最近开发中收集的这篇文章主要介绍算法 - 暴力枚举枚举的基本条件：解题思路一、P2241 统计方形P1618 三连击（升级版）P3392 涂国旗P3799 妖梦拼木棒 D：货物摆放，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

枚举的基本条件：

　　（1）时间条件：

首先是时间条件。一般来说主流的OJ当中，1000ms的时间限制下可以运行操作数为10^7以内的运算（通常10^6以内较为保险），所以在采用枚举方法之前最好看一下数据范围，确保整个程序的执行操作数不会超过10^6-10^7这个量级，如果超过了就尝试更换枚举的维度或者使用其他算法吧。

　　（2）编程上的实现条件：

其次是编程上的实现条件。在编程实现上，一般来说暴力枚举需要两个条件，一是枚举的范围一般需要连续，如果枚举范围是离散的，那么一般很难使用for循环枚举出所有状态，也就不能保证解的完整性（不过有些时候数据看似离散，但实际上可以经过处理变得连续）。第二个条件是枚举内容需要已知，不能在枚举到某个地方的时候出现未知（不过这个一般都被满足）。

解题思路

（1）找到枚举变量（尽量由已知推未知）

（2）找到并尽量缩小范围（根据题意但无需太过精确，可以过大，条件在if中判断即可）

（3）依据题意进行操作（尽量剪枝）

P2241 统计方形

P1618 三连击（升级版）

P3392 涂国旗

P3799 妖梦拼木棒

D：货物摆放

一、P2241 统计方形

易得:

子矩形构成的矩阵的长宽是由原矩形长宽减去不同数而得，即(n-b)*(m-a) (a≠b)

子正方形构成的矩阵的长宽由原矩形长宽减去相同数而得，即(n-b)*(m-a) (a=b)

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m,zfx=0,jx=0;    //贼大，记得long long
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			if(i==j) zfx+=(n-i)*(m-j);
			else jx+=(n-i)*(m-j);
		}
	cout<<zfx<<" "<<jx;
	return 0;
	
}

P1618 三连击（升级版）

思路：因为刚好三组数，占尽1 - 9，所以用特判观察是否占尽1 - 9

for(j=1;j<=9;j++)    
    if(num[j]==0)

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,i,j=0,num[10]={0},t=0;
	cin>>a>>b>>c;
	for(i=1;i<=999;i++)
	{
		if(a*i>100&&c*i<999)
		{
			int x=a*i;
			num[x/100]++;
			num[x/10%10]++;
			num[x%10]++;
			
			int y=b*i;
			num[y/100]++;
			num[y/10%10]++;
			num[y%10]++;
			
			int z=c*i;
			num[z/100]++;
			num[z/10%10]++;
			num[z%10]++;
		}
		else continue;
		
		for(j=1;j<=9;j++)    //核心特判
			if(num[j]==0)
				break;
		if(j>=10)
		{
			cout<<a*i<<" "<<b*i<<" "<<c*i<<endl;
			t=1;
		}
		for(j=1;j<=9;j++)
			num[j]=0;
		
	}
	if(t==0)
		cout<<"No!!!";
	return 0;
}

P3392 涂国旗

只用枚举每种颜色的分界线即可。

#include<bits/stdc++.h>
using namespace std;
const int N=51;
int w[N],b[N],r[N];
int n,m;
int main()
{
	char ch;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) //每一行三种颜色数量
		{
			cin>>ch;
			if(ch=='W') w[i]++;
			if(ch=='B') b[i]++;
			if(ch=='R') r[i]++;
		}
	}
	int minv=10000000;
	for(int i=1;i<=n-2;i++) //白色分界，n-2至少有两行不是白
	{
		for(int j=i+1;j<=n-1;j++) //i+1从白色行后面开始，n-1后面至少一行不蓝
		{
			int sum=0;
			for(int k=1;k<=n;k++) //判断，只需要找出涂白蓝的行，剩下就是红
			{
				if(k<=i) sum+=m-w[k];
				else if(k<=j) sum+=m-b[k];
				else sum+=m-r[k];
			}
			minv=min(minv,sum); //判断涂色更少的总数
		}
	}
	cout<<minv<<endl;
	return 0;
}

P3799 妖梦拼木棒

洛谷P3799 妖梦拼木棒_Study_Study_X的博客-CSDN博客https://blog.csdn.net/Study_Study_X/article/details/122931184我不理解，但是觉得很好的一题......

D：货物摆放

在这里插入图片描述

#include<iostream>
#include<cmath>
using namespace std;
typedef  long long ll;
ll n = 2021041820210418;
ll a[100010],c,res; 
int main()
{

  for(int i = 1; i <=sqrt(n); i++)//必须sqrt不然爆long long 
  {
    if(n % i == 0)
	{
      a[++c] = i;
      a[++c] = n/i;//找出sqrt左右两边的因子 
    }
  }
  for(int l = 1; l <= c; l++)
  	for(int w = 1; w <= c; w++)
  		for(int h = 1; h <= c; h++)
    		if(a[l]*a[w]*a[h] == n) res++;
 
  cout <<res;
  return 0;
}