P2089 烤鸡

Yama-lei2025年2月22日大约 7 分钟

P2089 烤鸡

题目描述

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

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

输出格式

第一行，方案总数。

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

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

输入输出样例 #1

输出 #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

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 普及组] 栈

题解 P1044 【栈】 - 洛谷专栏

题目背景

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

题目描述

宁宁考虑的是这样一个问题：一个操作数序列，$1,2,\ldots ,n$（图示为 1 到 3 的情况），栈 A 的深度大于 $n$。

现在可以进行两种操作，

将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。

（原始状态如上图所示）

你的程序将对给定的 $n$，计算并输出由操作数序列 $1,2,\ldots,n$ 经过操作可能得到的输出序列的总数。

我的尝试

#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]]]}$ 则是三重的。现在我们给你外星人发送的密码，请你对其进行解压缩。

AC[3FUN]

输出 #1

ACFUNFUNFUN

说明/提示

【数据范围】

对于 $50%$ 的数据：解压后的字符串长度在 $1000$ 以内，最多只有三重压缩。

对于 $100%$ 的数据：解压后的字符串长度在 $20000$ 以内，最多只有十重压缩。保证只包含数字、大写字母、[ 和 ]。

P2089 烤鸡

P2089 烤鸡

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

我的尝试

Deepseek 解答

方法思路

解决代码

代码解释

MetaXiao's solution

P1044 [NOIP 2003 普及组] 栈

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

我的尝试

P1928 外星密码

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示