a219 - 限制排列
題目描述
題目要求生成所有可能的 N 個人排列，但受到限制：第 i 個人不能排在第 k 個位置（由輸入指定）。輸出時，只輸出與前一個排列不同的部分，以避免輸出檔過大。
解題思路
這題的核心是生成所有可能的排列，並在生成過程中檢查是否符合限制條件。程式使用 std::next_permutation 產生所有排列，並使用一個二維布林陣列 an 記錄每個人的限制位置。在輸出時，程式會比較當前排列與前一個排列，只輸出不同的部分。為了避免重複輸出，程式使用一個 tmp 陣列儲存上一個輸出的排列。程式使用 putchar_unlocked 和 getchar_unlocked 來優化輸入輸出。
複雜度分析
- 時間複雜度: O(N! * N)，其中 N 是人數。
std::next_permutation的時間複雜度是 O(N)，而生成所有排列需要 O(N!) 的時間。比較排列的過程需要 O(N) 的時間。 - 空間複雜度: O(N)，主要用於儲存排列
a和tmp陣列。an陣列的大小是 O(N^2)，但由於 N 的最大值是 15，因此空間複雜度可以忽略不計。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <algorithm>
int n,k;
bool an[16][16];
char a[16];
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
while(n=read()){
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j)
an[i][j]=0;
for(int i=0;i<n;++i){
a[i]='A'+i;
while(k=read()){
if(k==0)break;
an[i][k-1]=1;
}
}
int it=0;
char tmp[16]="",chache=' ';
do{
if(a[it]==chache)continue;
int s=1;
for(int i=0;i<n&&s;++i)
if(an[a[i]-'A'][i]){
s=0;
it=i;
chache=a[i];
}
if(s){
for(int i=0;i<n;++i){
if(a[i]!=tmp[i])putchar_unlocked(a[i]);
tmp[i]=a[i];
}
putchar_unlocked('\n');
}
}while(std::next_permutation(a,a+n));
}
}