以前用C++的next_permutation做题，现在用Java却找不到对应的全排列函数，不知怎么写，百度一搜，花里胡哨的一大堆，洋洋洒洒写了上百行代码，实在是看不下去，还是看题能找到简洁的代码。
裸题P1706：https://www.luogu.com.cn/problem/P1706
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<ctime> #define ll long long #define inf 0x3f3f3f3f const double pi=3.1415926; using namespace std; int a[10]; bool vis[10]; int n; void dfs(int x) { if(x==n+1) { for(int i=1;i<=n;i++) printf(" %d",a[i]); printf(" "); return; } for(int i=1;i<=n;i++) { if(vis[i]==false) { vis[i]=true; a[x]=i; dfs(x+1); vis[i]=false; } } } int main() { while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); memset(vis,false,sizeof(vis)); dfs(1); } return 0; }
NOJ1337：[蓝桥杯2017初赛]9数算式
观察如下的算式：9213 x 85674 = 789314562
左边的乘数和被乘数正好用到了1~9的所有数字，每个1次。
而乘积恰好也是用到了1~9的所有数字，并且每个1次。
请你借助计算机的强大计算能力，找出满足如上要求的9数算式一共有多少个？
注意：
1. 总数目包含题目给出的那个示例。
2. 乘数和被乘数交换后作为同一方案来看待。
思路：全排列，中间暴力插空*号，判断乘积，最后/2去掉对称。
import java.util.*; public class Main{ static int[] vis=new int[10]; static int[] a=new int[10]; static int ans=0; public static void main(String []args){ Scanner scan=new Scanner(System.in); dfs(1); System.out.println(ans/2); } public static void dfs(int x) { if(x==10) { for(int i=1;i<=8;i++) { //第1个乘数有多少位 int c=0,d=0;//计算两个乘数 for(int j=1;j<=9;j++) { if(j<=i) c=c*10+a[j]; else d=d*10+a[j]; } if(check(c*d)) ans++; } return; } for(int i=1;i<=9;i++){ if(vis[i]==0) { vis[i]=1; a[x]=i; dfs(x+1); vis[i]=0; } } } public static boolean check(int a) {//将结果转化为字符串进行判断 int[] flag=new int[10]; int cnt=0; String s=String.valueOf(a); for(int i=0;i<s.length();i++) { char now=s.charAt(i); int x=(int)(now-'0'); if(1<=x && x<=9 && flag[x]==0) { flag[x]=1; cnt++; }else return false; } if(cnt==9) return true; else return false; } }
NOJ1338:[蓝桥杯2017初赛]纸牌三角形
A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。
下图就是一种排法这样的排法可能会有很多。
如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？
思路：看作是一行数字，1-4、4-7、7-9+1位置求和判断，最后/3去掉三角形的特性，再/2去掉镜像。
import java.util.*; public class Main{ static int[] vis=new int[10]; static int[] a=new int[10]; static int ans=0; public static void main(String []args){ Scanner scan=new Scanner(System.in); dfs(1); System.out.println(ans/6); } public static void dfs(int x) { if(x==10) { if(check()) ans++; return; } for(int i=1;i<=9;i++){ if(vis[i]==0) { vis[i]=1; a[x]=i; dfs(x+1); vis[i]=0; } } } public static boolean check() {//将结果转化为字符串进行判断 int x=a[1]+a[2]+a[3]+a[4]; int y=a[4]+a[5]+a[6]+a[7]; int z=a[7]+a[8]+a[9]+a[1]; if(x==y && y==z) return true; else return false; } }
P4163:[SCOI2007]排列
题意：t组数据，给个字符串和除数，求多少种全排列能被除数整除。t<=15,字符串长度n<=10,除数<=1000
这道题做了很久，不断优化查阅。
1.像上面的dfs一样找到一个全排列后数组遍历求值再判断，同时用HashMap去重，超时。(15*10!*log(10!)*10)
2.边dfs边求值，不必等到剪枝时遍历求值，超时。(15*10!*log(10!))
3.不用HashMap去重，HashMap要logn复杂度，对于有重复数字的情况用组合数求出重复多少次，结果再除去。例如333221这样的数每种排列会重复3!*2!*1!次。超时。(15*10!)
4.对我来说已经是极限优化了，还是过不了。去重的全排列或许能减少时间复杂度，但是不会写。Java代码改写成C++提交还是一样，开起O2优化多过了一组。其他数据还是超时。(15*10!)
5.正解是状压，可是我还不会状压，听着都唬人，强行用全排列做题。改用C++调用库函数next_permutation，全排列能自动去重。堂堂省选级别的题居然被库函数卡掉了。
import java.util.*; public class Main{//P4163 static int[] vis=new int[11];//是否访问过b数组的位置 static int[] num=new int[11];//每个数字出现多少次 static int[] a=new int[11];//dfs全排列数组 static int[] b=new int[11];//存原序列，用来找各个位置上的数字 static int[] fact=new int[11];//阶乘 static int ans=0; static int d=0; static int len=0; static HashMap<Long, Integer> map=new HashMap<Long, Integer>(); public static void main(String []args){ Scanner scan=new Scanner(System.in); //打印阶乘表 fact[0]=1; for(int i=1;i<11;i++) fact[i]=i*fact[i-1]; int t=scan.nextInt(); while(t!=0){ t--; //清空后重新输入 ans=0; String s=scan.next(); d=scan.nextInt(); len=s.length(); for(int i=0;i<len;i++) { int x=(int)(s.charAt(i)-'0'); num[x]++; b[i+1]=x; } int q=1;//相同排列出现的次数 for(int i=0;i<11;i++) { q=q*fact[ num[i] ]; num[i]=0;//顺便清空 } dfs(1,0); System.out.println(ans/q); } } public static void dfs(int x,long now) {//十位数int溢出 if(x==len+1) { if(now%d==0) ans++; return ; } for(int i=1;i<=len;i++){ if(vis[i]==0)//i不是数字，而是数组b各个位置 { vis[i]=1; a[x]=b[i]; dfs(x+1,now*10+b[i]); vis[i]=0; } } } }
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<ctime> #define ll long long #define inf 0x3f3f3f3f const double pi=3.1415926; using namespace std; int t,len,d; int a[11]; char s[15]; int ans=0; int main() { scanf("%d",&t); while(t--) { scanf("%s%d",s,&d); ans=0; len=strlen(s); for(int i=0;i<len;i++) { int x=(int)(s[i]-'0'); a[i+1]=x; } sort(a+1,a+len+1);///先排序 do{ ll sum=0; for(int i=1;i<=len;i++) sum=sum*10+a[i]; if(sum%d==0) ans++; }while(next_permutation(a+1,a+len+1)); printf("%d ",ans); } return 0; }
追：请教了大佬之后，修改一下代码用计数方法去重，在java50分代码的基础上化简后能够AC。
import java.util.*; public class Main{//P4163 static int[] num=new int[11];//每个数字出现多少次 static int[] a=new int[11];//dfs全排列数组 static int ans=0; static int d=0; static int len=0; static HashMap<Long, Integer> map=new HashMap<Long, Integer>(); public static void main(String []args){ Scanner scan=new Scanner(System.in); int t=scan.nextInt(); while(t!=0){ t--; Arrays.fill(num, 0); //清空后重新输入 ans=0; String s=scan.next(); d=scan.nextInt(); len=s.length(); for(int i=0;i<len;i++) { int x=(int)(s.charAt(i)-'0'); num[x]++; } dfs(1,0); System.out.println(ans); } } public static void dfs(int x,long now) {//十位数int溢出 if(x==len+1) { if(now%d==0) ans++; return ; } for(int i=0;i<=9;i++){ if(num[i]>0) {//用计数方法排列 num[i]--; dfs(x+1, now*10+i); num[i]++; } } } }
NOJ1341：[蓝桥杯2017决赛]平方十位数
题意：求0-9这10个数字组成的数中，最大的平方数。
import java.util.*; public class Main{ static int[] vis=new int[12]; static int[] a=new int[12]; static long ans=Long.MIN_VALUE; public static void main(String []args){ Scanner scan=new Scanner(System.in); dfs(0); System.out.println(ans); } public static void dfs(int x) { if(x==10 && a[0]!=0) {//首位不为0 long sum=0; for(int i=0;i<=9;i++) { //第1个乘数有多少位 sum=sum*10+a[i]; } long q=(long)Math.sqrt(sum); if(q*q==sum) ans=(long) Math.max(ans, sum); return; } for(int i=0;i<=9;i++){ if(vis[i]==0) { vis[i]=1; a[x]=i; dfs(x+1); vis[i]=0; } } } }
天上不会掉馅饼，努力奋斗才能梦想成真。