开发者LT的博客
0%

洛谷P2089 -烤鸡 - 题解

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟
暴力&枚举

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 种配料（芥末、孜然等），每种配料可以放 到 克，任意烤鸡的美味程度为所有配料质量之和。

现在， Hanke 想要知道，如果给你一个美味程度 ，请输出这 种配料的所有搭配方案。

输入格式

一个正整数 ，表示美味程度。

输出格式

第一行，方案总数。

第二行至结束， 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 。

输入输出样例 #1

输入 #1

1
11

输出 #1

1
2
3
4
5
6
7
8
9
10
11
10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1

说明/提示

对于 的数据， 。

思路

首先注意到，每一个配料的范围只有1-3，很小，那么如果用暴力枚举的思路，套上十层for循环，时间复杂度也才3的十次方，也就是不到六万，完全在可接受范围内。所以用暴力枚举做：先定义一个二维数组用来存放答案。然后用十层究极for循环超级暴力地枚举，每一个变量都从1到3，在最底层的循环判断十个变量相加是否等于n，如果是的话则存进数组，最后输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	int cnt = 0;
	long long arr[10000][10] = { 0 };
	int index_x = 0;
	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 j = 1; j <= 3; j++)
									{
										for (int k = 1; k <= 3; k++)
										{
											if ((a + b + c + d + e + f + g + h + j + k) == n)
											{
												cnt++;											
												arr[index_x][0] = a;
												arr[index_x][1] = b;
												arr[index_x][2] = c;
												arr[index_x][3] = d;
												arr[index_x][4] = e;
												arr[index_x][5] = f;
												arr[index_x][6] = g;
												arr[index_x][7] = h;
												arr[index_x][8] = j;
												arr[index_x][9] = k;
												index_x++;
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	printf("%d\n", cnt);
	if (cnt > 0)
	{
		for (int i = 0; i < cnt; i++)
		{
			for (int j = 0; j < 10; j++)
			{
				printf("%d ", arr[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}