手机网站设计企业,双语网站建设网站,python自学网站免费菜鸟教程,国外的一些网站今天打天梯赛模拟赛有一道全排列的题#xff08;在我看来是啦#xff0c;虽然只拿了25/30#xff0c;一个点超时了呜呜呜呜呜#xff09;
在此纪念一下自己推导得出的得到两种不同全排列的方法#xff1a;
方法一#xff1a;按照字典序大小推导得出的全排列顺序
p是全…今天打天梯赛模拟赛有一道全排列的题在我看来是啦虽然只拿了25/30一个点超时了呜呜呜呜呜
在此纪念一下自己推导得出的得到两种不同全排列的方法
方法一按照字典序大小推导得出的全排列顺序
p是全排列的总和pa是一条排列v数组表示该点是否被访问过
void dfs(int idx, vectorint pa){if(pa.size() ! 0) p.push_back(pa);if(idx m) return ;for(int i 1; i m; i){if(v[i] 0){v[i] 1;pa.push_back(i);dfs(idx1, pa);pa.pop_back();v[i] 0;}}return ;
}
如果需排列的位置有123输出结果应该如下
1
1 2
1 3
1 2 3
1 3 2
2
2 1
2 3
2 1 3
2 3 1
3
3 1
3 2
3 1 2
3 2 1方法二先按照排列的数字多少进行排列在这样的一个组合内再进行字典序的排列
void dfs(int idx, vectorint pa){if(pa.size() idx){p.push_back(pa);return ;}for(int i 1; i m; i){if(v[i] 0){v[i] 1;pa.push_back(i);dfs(idx, pa);pa.pop_back();v[i] 0;}}return ;
}
如果需排列的位置有123输出结果应该如下
1
2
3
1 2
1 3
2 1
2 3
3 1
3 2
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
2024天梯赛模拟赛L3-1题---25/30代码如下
#includebits/stdc.h
using namespace std;
int n, m;
int s[20][20];
int v[20];
vectorvectorint p;
void dfs(int idx, vectorint pa){// if(pa.size() ! 0) p.push_back(pa);// if(idx m) return ;// for(int i 1; i m; i){// if(v[i] 0){// v[i] 1;// pa.push_back(i);// dfs(idx1, pa);// pa.pop_back();// v[i] 0;// }// }
// return ;
//上面是按照字典序排序的全排列
//下面是按照个数多少排序的字典序排序的全排列if(pa.size() idx){p.push_back(pa);return ;}for(int i 1; i m; i){if(v[i] 0){v[i] 1;pa.push_back(i);dfs(idx, pa);pa.pop_back();v[i] 0;}}return ;
}
int main(){cin n m;for(int i 1; i m; i)for(int j 1; j n; j)cin s[i][j];vectorint pa;for(int i 1; i m; i)dfs(i, pa);// cout p.size() endl;// for(int i 0; i p.size(); i){// for(int j 0; j p[i].size(); j)// cout p[i][j];// cout endl;// }int a[n10], flag 0;for(int i 0; i p.size(); i){fill(a, an10, -1);for(int j 0; j p[i].size(); j){for(int k 1; k n; k){if(s[p[i][j]][k] -1)a[k] -1;else if(s[p[i][j]][k] 1)a[k] 1;}flag 1;for(int k 1; k n; k){if(a[k] ! 1) flag 0;}if(flag) break;}if(flag){for(int k 0; k p[i].size(); k){if(k) cout ;cout p[i][k];}break;}}return 0;
}
