当前位置: 首页 > news >正文

深圳技术大学oj C : 生成r子集

Description

输出给定序列按字典序的 � 组合,按照所有 � 个元素出现与否的 01 标记串 ����−1,...,�1 的字典序输出.

此处01串的字典序指:先输入的数字对应低位,后输入的数字对应高位,从高位到低位第一个不一样的位为1的字典序靠后.

Input

第一行集合元素个数 1≤�≤10 及子集元素个数 1≤�≤�,第二行 � 个空格隔开的正整数 1≤��≤100.

Output

每组数据输出所有对应的每个组合,每个一行用空格隔开。

Sample

#0
Input

Copy

5 3
3 1 2 4 5
Output

Copy

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

Hint

样例中:{3,1,4}表示01011——5(0)4(1)2(0)1(1)3(1),{1,2,5}表示10110——5(1)4(0)2(1)1(1)3(0),则{1,2,5}的字典序比{3,1,4}靠后.

题目有点难懂

方法用回溯求组合数然后排序

#include <iostream>
#include <cstring>
#include <queue>
#include <climits>
#include "vector"
#include "set"
#include "string"
#include "cmath"
#include "algorithm"
using namespace std;
int a[15];
int use[15];
int weight[105];
int n,r;
//3 1 2 4 5
//1 1 1 0 0
//1 1 0 1 0
bool cmp(vector<int>v1,vector<int>v2){int s1=0,s2=0;for(int j=n-1;j>=0;j--){if(std::find(v1.begin(), v1.end(),a[j])!=v1.end()){s1=1;}if(std::find(v2.begin(), v2.end(),a[j])!=v2.end()){s2=1;}if(s1!=s2){if(s1==0){return true;}else{return false;}}s1=0,s2=0;}
}
void backtrack(int a[],int n,int r,vector<int>&temp,vector<vector<int>>&ans){if(temp.size()==r){ans.push_back(temp);return;}for(int i=0;i<n;i++){if(use[i]==0&&((!temp.empty()&&weight[a[i]]<weight[temp[temp.size()-1]])||temp.empty())){use[i]=1;temp.push_back(a[i]);backtrack(a,n,r,temp,ans);temp.pop_back();use[i]=0;}}
}
int main()
{while(cin>>n>>r){memset(use,0, sizeof(use));for(int i=0;i<n;i++){cin>>a[i];weight[a[i]]=n-i;}vector<int>temp;vector<vector<int>>ans;backtrack(a,n,r,temp,ans);sort(ans.begin(),ans.end(), cmp);for(int i=0;i<ans.size();i++){for(int j=0;j<r;j++){cout<<ans[i][j]<<" ";}cout<<endl;}cout<<endl;}return 0;
}

http://www.lryc.cn/news/390544.html

相关文章:

  • 不同操作系统下的换行符
  • Transformation(转换)开发-switch/case组件
  • Android Gradle 开发与应用 (二): Android 项目结构与构建配置
  • 02:vim的使用和权限管控
  • GNeRF代码复现
  • EXCEL返回未使用数组元素(未使用值)
  • 系统调用简单介绍
  • Mac可以读取NTFS吗 Mac NTFS软件哪个好 mac ntfs读写工具免费
  • AI是否能够做决定
  • 【Excel操作】Python Pandas判断Excel单元格中数值是否为空
  • C# Opacity 不透明度
  • 推荐三款常用接口测试工具!
  • 【Qt】Qt多线程编程指南:提升应用性能与用户体验
  • PyTorch之nn.Module、nn.Sequential、nn.ModuleList使用详解
  • C++Primer Plus 第十四章代码重用:编程练习,第4题
  • 01 Docker 概述
  • c++的const
  • Git不想跟踪某个文件
  • DB-GPT 文档切分报错
  • #如何使用 Qt 5.6 在 Android 上启用 NFC
  • 合并排序的数组
  • js 复制文本带样式
  • 服务器之BIOS基础知识总结
  • FFmpeg 实现从摄像头获取流并通过RTMP推流
  • 学生管理系统
  • 【linux】网络基础(3)——tcp协议
  • [Day 21] 區塊鏈與人工智能的聯動應用:理論、技術與實踐
  • 使用ps给gif动图抠图
  • pmp顺利通关总结
  • 未来的钥匙在于过去:学历史的真正意义,震惊!历史竟然是偶然的?从历史中寻找未来的方向!