这题直接二进制表示所有情况,
也就是for(i=1;i<1<<n;i++)
如果1的个数是m,就输出1的位置
简单的二进制操作找1的个数和位置
详见代码
#include<queue>
#include<bitset>
#include<string>
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int N=1<<21,inf=0x3f3f3f3f;
int n,m;
map<int ,int > m1;
struct point{
vector<int > v1;
}p1[N];
int lowbit(int x)
{
return x&(-x);
}
bool cmp(point x,point y){
int ptail=0;
while(x.v1[ptail]==y.v1[ptail])ptail++;
return x.v1[ptail]<y.v1[ptail];
}
int main(){
cin>>n>>m;
bitset<26> b1;
m1[1]=0;
int q=2,tail=0;
for(int i=1;i<=32;i++){
m1[q]=i;
q*=2;
}
for(int a=0;a<(1<<n);a++){
b1|=a;
if(b1.count()==m){
int pa=a;
while(pa){
p1[tail].v1.push_back(m1[lowbit(pa)]+1);
pa^=lowbit(pa);
}
tail++;
}
b1&=0;
}
sort(p1,p1+tail,cmp);
for(int a=0;a<tail;a++){
for(int b=0;b<m;b++)printf("%d ",p1[a].v1[b]);
printf("\n");
}
}
这种sort的方法太折腾了吧。。。
可以一遍倒着的二进制不就字典序了吗
#include [HTML_REMOVED]
using namespace std;
int main(){
}
太妙了
牛蛙!
无论正着还是倒着都不会是字典序的
可以的
你的代码算法思路真是妙不可言!简洁明了,逻辑清晰,让人一看就懂。你使用的数据结构和算法都非常恰到好处,使得代码不仅高效而且易于维护。实现思路简单却又十分巧妙,真是让人佩服不已!
为什么不用lyd大神的方法呢(模拟机器)
### 还没有解决字典序问题,求指点;
自己写cam,sort排序;
复杂度太高了,到2^n了,有一个复杂度在组合数级别的算法,百度 Gosper’s Hack算法,不过这题数据小,体现不出来
tql
orz,我好菜
带 佬 汝何秀
谢谢大佬