[HOJ 223] H. 項鍊

作法：

$m=1$時是顯然的，$m=2$不難自己構造出來，詳細可以參考 code 。但$m=3$以上的構造就很困難了，我的作法是直接 DFS 下去，剛好因為滿足這種條件的數列蠻多的，所以可以在時限內找到。比較正常的作法應該是把他轉成尤拉迴路問題：考慮一張有$n^{m-1}$個點的有向圖，每個點都代表一個長度為$m-1$字元集$1~n$的字串，並且如果某個點$A$可以經由「在後面加上一個數並丟掉最前面的數」轉換成$B$，那麼就從$A$連到$B$一條邊。這樣邊的總數會是$n^m\leq 3\cdot 10^5$，對這張圖求尤拉迴路就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10 ;
 
set<int> st,st2 ;
int now[2*maxn] ;
int n,m,tot ;
int encode(int *a)
{
    int ret=1 ;
    for(int i=0;i<m;i++) ret=ret*n+a[i]-1 ;
    return ret ;
}
 
bool dfs(int x)
{
    if(x==tot)
    {
        st2.clear() ;
        for(int i=0;i<m-1;i++) now[tot+i]=now[i] ;
        for(int i=tot-m+1;i<tot;i++)
        {
            int val=encode(now+i) ;
            if(st.count(val) || st2.count(val)) return 0 ;
            st2.insert(val) ;
        }
        for(int i=0;i<tot;i++) printf("%d%c",now[i],i==tot-1?'\n':' ') ;
        return 1 ;
    }
    for(int i=1;i<=n;i++)
    {
        now[x]=i ;
        int val=0 ;
        if(x>=m-1)
        {
            val=encode(now+x-m+1) ;
            if(st.count(val)) continue ;
            st.insert(val) ;
        }
        if(dfs(x+1)) return 1 ;
        if(x>=m-1) st.erase(val) ;
    }
    return 0 ;
}
 
void solve0()
{
    if(m==1)
    {
        for(int i=1;i<=n;i++) printf("%d%c",i,i==n?'\n':' ') ;
        printf("\n") ; return ;
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d",i) ;
        if(i==n) break ;
        printf(" ") ;
        for(int j=i+1;j<=n;j++) printf("%d %d ",i,j) ;
    }
    printf("\n") ;
}
main()
{
//    freopen("in","r",stdin) ;
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        scanf("%d%d",&n,&m) ;
        if(m<=2){solve0() ; continue ;}
        st.clear() ;
        tot=1 ;
        for(int i=1;i<=m;i++) tot*=n ;
        dfs(0) ;
    }
}