[我是传送门]
这是一道很经典的深搜与回溯(难度一般)
可是就这个"普及-"
让本蒟蒻做了一晚上+半个上午(实际我不会深搜回溯,全靠框架+去重);
下面让我分享下本蒟蒻的(全排列+暴搜去重)
#include<bits/stdc++.h> using namespace std; int n,r,ttt;//n是总数,r是选的数,ttt是答案 int a[1001],b2[1001],c[10001][101];//a用来储存排列的编号,b2用来储存输入的数,c用来去重(储存符合条件的数组的编号) bool b[1001];//用来判断是否用过 bool ss2(int t[]){//暴搜判重 int tot=0;//计数器 for(int i=1;i<=ttt;i++){//循环所有储存的数组 for(int j=1;j<=r;j++){//循环r次,比较每一个字符 if(t[j] != c[i][j])//判重 tot++; } if(tot==0)//如果没有一个不一样的说明重复 return 0; tot=0;//一定要清空!!!! } return 1;//如果全不重复,说明不重 } bool sus(int y){//判断素数 if(y==0||y==1)//防止特殊值 return 0; if(y==2) return 1; for(int i=2;i<=sqrt(y);i++){//循环到sqrt就够了 if(y%i==0) return 0; } return 1; } void print(){//其实不能叫print,因为没有输出 int y=0; int b3[r+1];//定义新数组避免动原先(a)数组 for(int i=1;i<=r;i++)//判断素数 y+=b2[a[i]]; if(sus(y)==1){//不是素数直接跳过 for(int i=1;i<=r;i++) b3[i]=a[i]; sort(b3+1,b3+r+1);//一定要排序,因为类似"组合" if(ss2(b3)==1){//如果不重复 u++;//这一步可以不要 ttt++;//答案加1 for(int i=1;i<=r;i++) c[u][i]=b3[i] ;//如果不要u++这里u要换成ttt } } } void ss(int k){//程序主体 for(int i=1;i<=n;i++){ if(b[i] ==0){//只要没标记过就能用 a[k]=i;//记录编号 b[i]=1;//标记 if(k==r) print();//到了r"输出" else ss(k+1);//否则继续 b[i]=0;//回溯 } } } int main(){ cin>>n>>r;//输入 for(int i=1;i<=n;i++) cin>>b2[i]; ss(1);//深搜 cout<<ttt;//输出答案 return 0; }