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

UVa 598 Bundling Newspapers

news 2026/6/25 16:04:21

题目描述

题目要求生成给定报纸列表的所有指定大小的子集，并按字典序输出。输入给出子集大小范围（单个数字、两个数字或*表示全部），每行一个报纸名。输出按子集大小分组，每组内按字典序输出所有子集。

输入格式

第一行一个整数MMM，表示数据集个数，后面跟一个空行。每个数据集的第一行是子集大小说明（*、n或a b）。接下来若干行报纸名，以空行结束。两个连续数据集之间由一个空行分隔。

输出格式

对于每个数据集，按子集大小分组输出。每组先输出Size X，然后每行一个子集（报纸名用逗号加空格分隔）。每组后跟一个空行。两个数据集输出间有一个空行。

样例

输入

1 2 3 Times Herald-Tribune Post New Advocate

输出

Size 2 Times, Herald-Tribune Times, Post Times, New Advocate Herald-Tribune, Post Herald-Tribune, New Advocate Post, New Advocate Size 3 Times, Herald-Tribune, Post Times, Herald-Tribune, New Advocate Times, Post, New Advocate Herald-Tribune, Post, New Advocate

题目分析

本题的核心是生成组合，并按字典序输出。

组合生成

使用回溯法生成所有大小为kkk的组合，按输入顺序依次选择，保证字典序。

输出格式

注意：每组输出后有一个空行，两个数据集输出间也有一个空行。

复杂度分析

最多C(12,6)=924C(12,6) = 924C(12,6)=924个组合，可接受。

代码实现

// Bundling Newspapers// UVa ID: 598// Verdict: Accepted// Submission Date: 2016-08-12// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intpapers[12],used[12],name_count;string names[12];voiddfs(intdepth,intlast,intn){if(depth==n){for(inti=0;i<n;i++){if(i>0)cout<<", ";cout<<names[papers[i]];}cout<<'\n';}else{for(inti=last;i<name_count-(n-1)+depth;i++){used[i]=1;papers[depth]=i;dfs(depth+1,i+1,n);used[i]=0;}}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intM=stoi(line);getline(cin,line);for(intcases=1;cases<=M;cases++){if(cases>1)cout<<'\n';string range;getline(cin,range);name_count=0;while(getline(cin,line),line.length()>0)names[name_count++]=line;inta,b;if(range.front()=='*')a=1,b=name_count;else{istringstreamiss(range);iss>>a;if(!(iss>>b))b=a;}for(inti=a;i<=b;i++){cout<<"Size "<<i<<'\n';memset(papers,-1,sizeof(papers));memset(used,0,sizeof(used));dfs(0,0,i);cout<<'\n';}}return0;}