技术标签： 题解 # 《算法竞赛进阶指南》 # AcWing
从 1 ∼ n 1\sim n 1∼n的整数中选出 m m m个，输出所有的选择方案。
输出格式：对于每种方案，从小到大空格隔开；对于不同的方案，字典序升序输出。
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
类似于递归实现指数型枚举，我们只需要在选取数量恰好是 m m m的时候再输出就行了。
但是需要注意的是，数据范围变成了25。所以需要剪枝，即在已经不可能达到最终结果的时候提前退出递归。
这一题如果选取的元素已经大于 m m m个了，就不可能正好选 m m m个了，就需要退出。同理，如果所选元素的个数加上剩下的所有元素也达不到 m m m，也需要退出。
如果把上一题的代码直接搬过来，加上剪枝，就是：
错误示范：
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
vector<int>v;
int n,m;
void prt()
{
for(int i=0;i<v.size();i++)
printf("%d ",v[i]);
puts("");
}
void calu(int x)
{
if(x>n)return x==n+1&&v.size()==m?prt():void();
if(v.size()>m||v.size()+(n-x+1)<m)return;
calu(x+1);
v.push_back(x);
calu(x+1);
v.pop_back();
}
int main()
{
cin>>n>>m;
calu(1);
return 0;
}
运行会发现结果是倒序的，大的结果在前面
3 4 5
2 4 5
2 3 5
2 3 4
1 4 5
1 3 5
1 3 4
1 2 5
1 2 4
1 2 3
这是由 我们先不选第 x x x个元素再选第 x x x个元素 造成的。
calu(x+1);
v.push_back(x);
calu(x+1);
v.pop_back();
而第 x x x个元素是比较小的（从小到大递归），本来应该在前面才对。
所以我们只需要调整一下push和pop的顺序即可。
总的就为：
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
vector<int>v;
int n,m;
void prt()
{
for(int i=0;i<v.size();i++)
printf("%d ",v[i]);
puts("");
}
void calu(int x)
{
if(x>n)return x==n+1&&v.size()==m?prt():void();
if(v.size()>m||v.size()+(n-x+1)<m)return;
v.push_back(x);
calu(x+1);
v.pop_back();
calu(x+1);
}
int main()
{
cin>>n>>m;
calu(1);
return 0;
}
原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/119254698
TextField想要实现输入类型、长度限制需要先引入import ‘package:flutter/services.dart’;例如import 'package:flutter/services.dart';TextField( keyboardType: TextInputType.number,//键盘类型，数字键盘 style: TextStyle(...
以下内容不需要入门的时候立刻阅读和理解，建议逐渐深入学习后，不时回来看看即可。什么是GPU?GPU:Graphic Processing Unit，中文翻译为“图形处理器”。显卡包括（GPU,显存，显卡BIOS,显卡PCB板）。什么是Shader?Shader程序:GPU执行的，针对3D对象进行操作的程序。Shader有哪几种？CG：与DirectX 9.0
目录1 软件环境2 问题模拟2.1 新建分区表2.2 初始化数据2.3 查看分区信息2.4 删除分区P13 问题分析与解决3.1 ORA ERR分析3.2 问题解决最近做数据库上线脚本的评审时，开发人员遇到了ORA-14758错误，本篇就针对这一错误进行分析，并给出解决方案。1 软件环境本实验的演示环境如下：SQL> SELECT * f...
LiveNVR功能-接收无人机、IPC等设备RTMP推流转码分发WEB视频播放也可以GB28181输出1、无人机推流转国标2、获取RTMP推流地址2.1、RTMP推流地址格式2.2、推流地址示例2、设备RTMP推流3、配置拉转RTMP3.1、直播流地址格式3.2、直播流地地址示例3.3、通道配置直播流地址4、推流并发多时处理5、配置级联到GB28181国标平台6、非国标直播流转GB28181服务搭建1、无人机推流转国标目前不是所有的无人机都支持GB28181的国标注册，有的只能输出直播流，有的只能支持R
报错：找不到gpedit.msc（或 secpol.msc）原因：Win10的Home版没有secpol.msc和gpedit.msc，无法更改本地策略的相关设置。解决方案：1、新建文本文档并复制如下内容@echo offpushd "%~dp0"dir /b C:\Windows\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientExtensions-Package~3*.mum &g...
前言：本教程是写给刚学会C语言基本语法不久的新生们。因为在学习C语言途中，往往只能写控制台代码，而还能没接触到图形，也就基本碰不到游戏开发。所以本教程希望可以给仍在学习C语言的新生们能提前感受到游戏开发技术的魅力和乐趣。先来看看本次教程程序大概的运行画面：游戏循环机制下面是一个简单而熟悉的C程序。#include <stdio.h>int main() { ...
Ubuntu 18.04中安装VMware14.1.0踩坑96 GodfansMa2018.09.04 10:50* 字数 465 阅读 88评论 0喜欢 1转载自： https://www.jianshu.com/p/5fc43bbbac5a如果只想快速安装VMware 请直接看文章最后。一、网上找了14.1.0的破解安装包,下载地址如下:https://www.macxin.com...
对于CNN前馈神经网络，如果前馈一次写一个forward函数会有些麻烦，在此就有两种简化方式，ModuleList和Sequential。Sequential1 、模型建立方式(1)nn.Sequential()对象.add_module(层名，层class的实例）net1 = nn.Sequential()net1.add_module('conv', nn.Conv2d(3, 3, 3))net1.add_module('batchnorm', nn.BatchNorm2d(3))net1
初步练习numpy，最后一关有惊喜哦。
<br /><br />华清远见系列图书<br />51单片机应用开发实战手册<br />华清远见嵌入式培训中心 袁东 等编著<br />ISBN 978-7-121-12858-5<br />2011年4月出版<br />定价：59.00元（含DVD光盘1张）<br />16开<br />496页<br />宣传语<br />深入浅出，依靠深厚行业经验讲透技术原理<br />循序渐进，详解典型应用案例提升实战能力<br />内 容 简 介<br />本书通过30个案例的设计过程详细介绍了51单片机开发
只有2~3年左右的开发经验，为什么年薪就可以达到50万+？
Cinemachine在2D横版游戏中的使用方法简介Cinemachine的下载及导入Cinemachine基础设置Cinemachine高级Cinemachine的下载及导入下载现在的版本不再需要从assets store中下载了，直接从package manager中就能找到Cinemachine这个插件。初次找到，请点击Download下载！创建Cinemachine对象我们选择创建虚拟摄像机Virtual Camera后，便会出现一个名为CM vcam1的虚拟摄像机。C.