每日一题 第二十期 洛谷 烤鸡

烤鸡

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

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

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

输入格式

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

输出格式

第一行，方案总数。

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

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

样例 #1

样例输入 #1

11

样例输出 #1

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

提示

对于 $100\%$ 的数据，$n\le 5000$。

AC代码：

#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e6 + 10;

int n;
int main()
{
	int cnt = 0;
	cin >> n;
	if(n > 30) cout << 0 << endl;
	else {
		for(int i = 1; i <= 3; i ++)
		{
			for(int j = 1; j <= 3; j ++)
			{
				for(int k = 1; k <= 3; k ++)
				{
					for(int q = 1; q <= 3; q ++)
					{
						for(int w = 1; w <= 3; w ++)
						{
							for(int e = 1; e <= 3; e ++)
							{
								for(int r = 1; r <= 3; r ++)
								{
									for(int t = 1; t <= 3; t ++)
									{
										for(int y = 1; y <= 3; y ++)
										{
											for(int u = 1; u <= 3; u ++)
											{
												if(i + j + k + q + w + e + r + t + y + u == n)
												{
													cnt ++;
													//printf("%d %d %d %d %d %d %d %d %d %d\n", i, j, k, q, w, e, r, t, y, u);
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		cout << cnt << endl;
		for(int i = 1; i <= 3; i ++)
		{
			for(int j = 1; j <= 3; j ++)
			{
				for(int k = 1; k <= 3; k ++)
				{
					for(int q = 1; q <= 3; q ++)
					{
						for(int w = 1; w <= 3; w ++)
						{
							for(int e = 1; e <= 3; e ++)
							{
								for(int r = 1; r <= 3; r ++)
								{
									for(int t = 1; t <= 3; t ++)
									{
										for(int y = 1; y <= 3; y ++)
										{
											for(int u = 1; u <= 3; u ++)
											{
												if(i + j + k + q + w + e + r + t + y + u == n)
												{
													printf("%d %d %d %d %d %d %d %d %d %d\n", i, j, k, q, w, e, r, t, y, u);
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	
	return 0;
}

//不懂为啥这种题也算的上普及题