P2089 烤鸡
P2089 烤鸡
题目背景
猪猪 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 \leq 5000$。
我的尝试
Deepseek 解答
为了解决这个问题,我们需要找到所有可能的10种调料的组合,每种调料的克数可以是1到3克,使得它们的总和等于给定的美味程度n。我们需要按字典序输出所有可能的组合,并在没有解的情况下输出0。
方法思路
- 问题分析:每个调料的克数可以是1、2或3,总和必须等于给定的n。我们需要生成所有可能的组合,并按字典序排列。
- 递归与回溯:使用递归生成所有可能的组合,并在生成过程中剪枝,以避免不必要的计算。剪枝的条件是当前部分和加上剩余部分的最小可能和不能超过n,或者当前部分和加上剩余部分的最大可能和不能小于n。
- 字典序排列:在递归过程中按1、2、3的顺序尝试每个位置的数值,这样生成的组合自然按字典序排列。
解决代码
n = int(input())
if n < 10 or n > 30:
print(0)
else:
result = []
def backtrack(current, start_index, current_sum):
if start_index == 10:
if current_sum == n:
result.append(current.copy())
return
remaining_positions = 10 - start_index - 1
for a in [1, 2, 3]:
new_sum = current_sum + a
min_possible = new_sum + remaining_positions * 1
max_possible = new_sum + remaining_positions * 3
if n < min_possible or n > max_possible:
continue
current.append(a)
backtrack(current, start_index + 1, new_sum)
current.pop()
backtrack([], 0, 0)
print(len(result))
for solution in result:
print(' '.join(map(str, solution)))
代码解释
- 输入处理:读取输入的美味程度n,并检查其是否在有效范围内(10到30之间)。
- 回溯函数:
backtrack
函数递归生成所有可能的调料组合。参数包括当前组合、当前处理的调料位置和当前总和。 - 剪枝条件:在每一步递归中,计算剩余位置的最小和最大可能和,判断是否可能达到目标n,以决定是否继续递归。
- 结果收集:当递归处理完所有位置时,检查当前总和是否等于n,并将有效组合保存到结果列表中。
- 输出结果:输出结果的数量和所有有效组合,按字典序排列。
这种方法通过递归和剪枝高效地生成所有可能的解,并按字典序输出,确保在合理时间内处理所有可能的情况。
MetaXiao's solution
#include<bits/stdc++.h>
using namespace std;
int n, cnt = 0, curr[10];
vector<vector<int>> res;
void dfs(int* curr, int idx, int s, int trg, int& cnt, vector<vector<int>>& res)
{
if (idx == 10)
{
if (s == trg)
{
res.push_back(vector<int>(curr, curr + 10));
cnt++;
}
return;
}
if (s+(10-idx)>trg || s+(10-idx)*3<trg) return;
for (int i = 1; i <= 3; i++)
{
curr[idx]=i;
dfs(curr, idx+1, s+i, trg, cnt, res);
}
}
int main()
{
cin >> n;
if (n < 10 || n > 30)
{
cout << "0" << endl;
return 0;
}
dfs(curr, 0, 0, n, cnt, res);
cout << cnt << endl;
for (const auto& result : res)
{
for (size_t j = 0; j < result.size(); j++)
cout << result[j] << (j < 9 ? " " : "");
cout << endl;
}
}
P1044 [NOIP 2003 普及组] 栈
题目背景
栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。
栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。
题目描述

宁宁考虑的是这样一个问题:一个操作数序列,$1,2,\ldots ,n$(图示为 1 到 3 的情况),栈 A 的深度大于 $n$。
现在可以进行两种操作,
- 将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作)
- 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)
使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3
生成序列 2 3 1
的过程。

(原始状态如上图所示)
你的程序将对给定的 $n$,计算并输出由操作数序列 $1,2,\ldots,n$ 经过操作可能得到的输出序列的总数。
输入格式
输入文件只含一个整数 $n$($1 \leq n \leq 18$)。
输出格式
输出文件只有一行,即可能输出序列的总数目。
输入输出样例 #1
输入 #1
3
输出 #1
5
说明/提示
【题目来源】
NOIP 2003 普及组第三题
我的尝试
#include<bits/stdc++.h>
using namespace std;
int m;
long long nums[19];
long long getNum(int n){
if(n<0) return 0;
if(nums[n]!=0){
return nums[n];
}
for(int i=1;i<=n;i++){
nums[n]+=getNum(i-1)*getNum(n-i);
}
return nums[n];
}
int main(){
cin>>m;
nums[0]=1;
nums[1]=1;
nums[2]=2;
nums[3]=5;
cout<<getNum(m)<<endl;
}
P1928 外星密码
题目描述
有了防护伞,并不能完全避免 2012 的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力,小队终于收到了外星生命的回信。但是外星人发过来的却是一串密码。只有解开密码,才能知道外星人给的准确回复。解开密码的第一道工序就是解压缩密码,外星人对于连续的若干个相同的子串 $\texttt{X}$ 会压缩为 $\texttt{[DX]}$ 的形式($D$ 是一个整数且 $1\leq D\leq99$),比如说字符串 $\texttt{CBCBCBCB}$ 就压缩为 $\texttt{[4CB]}$ 或者$\texttt{[2[2CB]]}$,类似于后面这种压缩之后再压缩的称为二重压缩。如果是 $\texttt{[2[2[2CB]]]}$ 则是三重的。现在我们给你外星人发送的密码,请你对其进行解压缩。
输入格式
输入一行,一个字符串,表示外星人发送的密码。
输出格式
输出一行,一个字符串,表示解压缩后的结果。
输入输出样例 #1
输入 #1
AC[3FUN]
输出 #1
ACFUNFUNFUN
说明/提示
【数据范围】
对于 $50%$ 的数据:解压后的字符串长度在 $1000$ 以内,最多只有三重压缩。
对于 $100%$ 的数据:解压后的字符串长度在 $20000$ 以内,最多只有十重压缩。保证只包含数字、大写字母、[
和 ]
。