草庐IT

「枚举」组合的输出

孤星·璀璨 2023-03-28 原文

本题为3月23日23上半学期集训每日一题中B题的题解

题面

(写题解的时候学校oj已不可查看此题,下面的题面来自洛谷第1157题)

题目描述

排列与组合是常用的数学方法，其中组合就是从 \(n\) 个元素中抽出 \(r\) 个元素（不分顺序且 \(r \le n\)），我们可以简单地将 \(n\) 个元素理解为自然数 \(1,2,\dots,n\)，从中任取 \(r\) 个数。

现要求你输出所有组合。

例如 \(n=5,r=3\)，所有组合为：

\(123,124,125,134,135,145,234,235,245,345\)。

输入

一行两个自然数 \(n,r(1<n<21,0 \le r \le n)\)。

输出

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

注意哦！输出时，每个数字需要 \(3\) 个场宽。以 C++ 为例，你可以使用下列代码：

cout << setw(3) << x;

输出占 \(3\) 个场宽的数 \(x\)。注意你需要头文件 iomanip。

样例输入

5 3

样例输出

  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5

思路分析

非常经典的暴力枚举问题,直接对每一位枚举就行了.学校oj的题目上明确要求用递归的方法进行枚举,所以这里给出的参考代码是递归形式的.其实还可以使用迭代形式的二进制枚举,以及使用C++内置的next_permutation函数.

参考代码

时间复杂度: \(O(\tbinom{N}{R})\)

空间复杂度: \(O(R)\) (计入递归消耗空间)

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

vector<int> res; // 存放答案

// 爆搜所有组合
void dfs(int n, int i, int r) {
    // 基线条件,当前答案已完成填写,输出
    if (r == 0) {
        for (const auto &i : res) {
            cout << setw(3) << i;
        }
        cout << "\n";
        return;
    }

    // 枚举当前位置的所有可能
    for (; i <= n; i++) {
        res.push_back(i);
        dfs(n, i + 1, r - 1); // 继续枚举下一位置
        res.pop_back(); // 因为是递归,运行到这行时后续位的枚举已经完成,为了当前位枚举下一个可能,需要消除掉本次枚举,所以把最后一个数踢掉(其他数在相应的递归中会被踢掉)
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);W

    int n, r;
    cin >> n >> r;

    res.reserve(r);
    dfs(n, 1, r);

    return 0;
}

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德

枚举组合spanclassinline算法与数据结构

有关「枚举」组合的输出的更多相关文章

  1. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  2. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  3. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  4. ruby - 将 spawn() 的标准输出/标准错误重定向到 Ruby 中的字符串 - 2

    我想使用spawn(针对多个并发子进程)在Ruby中执行一个外部进程，并将标准输出或标准错误收集到一个字符串中，其方式类似于使用Python的子进程Popen.communicate()可以完成的操作。我尝试将:out/:err重定向到一个新的StringIO对象，但这会生成一个ArgumentError，并且临时重新定义$stdxxx会混淆子进程的输出。 最佳答案 如果你不喜欢popen，这是我的方法:r,w=IO.pipepid=Process.spawn(command,:out=>w,:err=>[:child,:out])

  5. ruby - Ruby 是否使用 $stdout 来写入 puts 和 return 的输出？ - 2

    我想知道Ruby用来在命令行打印这些东西的输出流:irb(main):001:0>a="test"=>"test"irb(main):002:0>putsatest=>nilirb(main):003:0>a=>"test"$stdout是否用于irb(main):002:0>和irb(main):003:0>？而且，在这两次调用之间，$stdout的值是否有任何变化？另外，有人能告诉我打印/写入这些内容的Ruby源代码吗？ 最佳答案 是的。而且很容易向自己测试/证明。在命令行试试这个:ruby-e'puts"foo"'>test.

  6. ruby-on-rails - 无法在 Rails 助手中捕获 block 的输出 - 2

    我在使用自定义RailsFormBuilder时遇到了问题，从昨天晚上开始我就发疯了。基本上我想对我的构建器方法之一有一个可选block，以便我可以在我的主要content_tag中显示其他内容。:defform_field(method,&block)content_tag(:div,class:'field')doconcatlabel(method,"Label#{method}")concattext_field(method)capture(&block)ifblock_given?endend当我在我的一个Slim模板中调用该方法时，如下所示:=f.form_field:e

  7. ruby-on-rails - 连接字符串时如何在 <%=%> block 内输出 html_safe？ - 2

    考虑一下:现在这些情况:#output:http://domain.com/?foo=1&bar=2#output:http://domain.com/?foo=1&bar=2#output:http://domain.com/?foo=1&bar=2#output:http://domain.com/?foo=1&bar=2我需要用其他字符串输出URL。我如何保证＆符号不会被转义？由于我无法控制的原因，我无法发送&。求助!把我的头发拉到这里:\编辑:为了澄清，我实际上有一个像这样的数组:@images=[{:id=>"fooid",:url=>"http://

  8. ruby - 最多 n 的组合 - 2

    给定一个数组a，什么是实现其组合直到第n的最佳方法？例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案 做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合，我

  9. ruby - 捕获 Ruby Logger 输出以进行测试 - 2

    我有一个像这样的ruby​​类:require'logger'classTdefdo_somethinglog=Logger.new(STDERR)log.info("Hereisaninfomessage")endend测试脚本行如下:#!/usr/bin/envrubygem"minitest"require'minitest/autorun'require_relative't'classTestMailProcessorClasses当我运行这个测试时，out和err都是空字符串。我看到消息打印在stderr上(在终端上)。有没有办法让Logger和capture_io一起玩得

  10. ruby - 引用具有指定索引的枚举器值 - 2

    假设我有一个可枚举对象enum，现在我想获取第三个项目。我知道一种通用方法是转换成数组，然后使用索引访问，如:enum.to_a[2]但这种方式会创建一个临时数组，效率可能很低。现在我使用:enum.each_with_index{|v,i|breakvifi==2}但这非常丑陋和多余。执行此操作最有效的方法是什么？ 最佳答案 你可以使用take剥离前三个元素，然后剥离last从take给你的数组中获取第三个元素:third=enum.take(3).last如果您根本不想生成任何数组，那么也许:#Ifenumisn'tanEnum

随机推荐