首页 > 代码库 > [ CodeVS冲杯之路 ] P1294

[ CodeVS冲杯之路 ] P1294

2024-08-14 06:05:53   220人阅读

　　不充钱，你怎么AC？

　　题目：http://codevs.cn/problem/1294/

 

　　随手一打就是这么漂亮的全排列，想当年我初一还是初二的时候，调了1个多小时才写出来（蒟蒻一枚）

　　直接DFS每次枚举当前数字，记得判断是否重复，取完后打上标记并保存当前位置的数，最后到n+1层时打出来

　　因为极限数据的方案比较多，所以可以加上输出优化，不过不加也不会TL

　　上面那个是加了读入优化的，快了将近3倍

　　技术分享

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8  9 const int N=11;10 bool f[N];11 int a[N],n;12 inline void write(int x)13 {14     if (x>9) write(x/10);15     putchar(x%10+‘0‘);16 }17 void dfs(int x)18 {19     int i;20     if (x>n)21     {22         for (i=1;i<n;i++) write(a[i]),putchar(‘ ‘);23         write(a[n]);24         putchar(‘\n‘);25         return;26     }27     for (i=1;i<=n;i++)28     {29         if (f[i]) continue;30         f[i]=1;31         a[x]=i;32         dfs(x+1);33         f[i]=0;34     }35 }36 int main()37 {38     scanf("%d",&n);39     for (int i=1;i<=n;i++) f[i]=0;40     dfs(1);41     return 0;42 }

　　不加输出优化的话直接输出就行了

[ CodeVS冲杯之路 ] P1294


联系
我们