首页 > 其他分享 >AcWing 94. 递归实现排列型枚举

AcWing 94. 递归实现排列型枚举

时间:2023-01-31 23:35:31浏览次数:50  
标签:10 顺序 int 枚举 include 94 AcWing

顺序1:枚举每个数要放入哪个位置

查看代码
//暂时不想写

顺序1:时间复杂度

 

顺序2:枚举每个位置要放哪个数

相关题:

AcWing 1209.带分数

查看代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

const int N=10;//最大数据9个,有一个不用,故总共10个
int state[10];//各位置选的是谁
bool used[10];//对应下标的元素是否被使用
int n;

void dfs(int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++)
            printf("%d ",state[i]);
        puts("");
        return;
    }
    //按顺序选择第u个位置的元素
    for(int i=1;i<=n;i++)
    {
        if(!used[i])//i元素未被使用
        {
            state[u]=i;
            used[i]=true;
            dfs(u+1);
            //保护现场。state[]不需要保护,会自动覆盖
            state[u]=0;
            used[i]=false;
        }
    }
}

int main()
{
    scanf("%d",&n);
    dfs(1);//第几个空位
    
    return 0;
}

顺序2:时间复杂度O(n*n!)

 

标签:10,顺序,int,枚举,include,94,AcWing
From: https://www.cnblogs.com/FishSmallWorld/p/17078969.html

相关文章

  • Acwing 周赛88 题解
    比赛链接A题题目描述给定一个整数\(x\),请你找到严格大于\(x\)且各位数字均不相同的最小整数\(y\)。\(1000\lex\le9000\)做法分析发现数据范围很小,那么我们可以直......
  • 电动自行车CE认证EN15194测试报告
    2009年欧盟推出了新的电动助力自行车标准EN15194,EN15194标准为国际第一个针对电动助力自行车的安全标准,产品通过EN15194检测可以证明产品符合国际一流水平,并且对企业开拓市......
  • AcWing 92. 递归实现指数型枚举
    /*相关词:递归,递归搜索树,深搜*/#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;constintN=16;intarr[N];//0:还没考虑。1:选。2:不......
  • Acwing74
    k个k进制的数字进行不进位加法,结果为0时空复杂度O(n)classSolution{public:stringdecTok(intdec,intk){stringret="";while(dec){......
  • Acwing73
    哈希表时空复杂度O(n)classSolution{public:vector<int>findNumsAppearOnce(vector<int>&nums){unordered_map<int,int>m;vector<in......
  • Linux USB Gadget--设备枚举
    前面介绍了LinuxUSBGadget的软件结构与各软件层的整合过程。经过各种注册函数,Gadget功能驱动层,USB设备层与UDC底层结合在了一起形成了一个完整的USB设备。而这个设备已经......
  • lg8945题解
    考虑一个20分的\(O(n^2)\)做法:枚举答案区间\([l,r]\),那么显然要把尽可能多的1填入\([l,r]\)。使用前缀和计算\([l,r]\)中\(0\)的个数,那么填入后的价值可以\(O(1)\)计算。......
  • 枚举类list序列化与反序列化
    `packagecom.byd.plm.authority.auth.dto.jsonSerializer;importcom.byd.plm.authority.auth.dto.enums.AuthTypeEnum;importcom.fasterxml.jackson.core.JsonGenerat......
  • 邮件端口25、109、110、143、465、995、993、994
    全部常用邮件端口25、109、110、143、465、995、993、994全部常用邮件端口有:25、109、110、143、465、995、993等,常见各大邮箱协议和端口见下方 1)发邮件协议和端口:A......
  • 蓝桥杯备战日志(Python)2-相乘(逆向枚举)
    原题小蓝发现,他将  至  之间的不同的数与  相乘后再求除以  的余数,会得到不同的数。小蓝想知道,能不能在  至  之间找到一个数,与  相乘后再除以  后的余数......