51nod 算法馬拉松18 A 染色問題，51nod馬拉松

51nod 算法馬拉松18 A 染色問題，51nod馬拉松

染色問題

基准時間限制：1 秒 空間限制：10240 KB 分值: 40 一個n(3<=n<=100)個點的完全圖，現在給出n，要求將每條邊都染上一種顏色k(1<=k<=n)，最終使得所有三個點構成的環（C(n,3)個不同的換）上三條邊的顏色和在所有顏色中任選三種顏色的組合（C(n,3)種方案）一一對應，由你來給出染色方案。 本題有多組數據   Input

第一行一個整數T，表示數據組數
接下來T行每行一個整數n，表示完全圖的點數

Output

輸出由T個部分組成
每個部分的第一行一個整數n，表示完全圖的點數
第二行表示構造結果
如果無解輸出No solution
否則輸出n*(n-1)/2條邊的起點、終點和顏色

Input示例

2
4
3

Output示例

4
No solution
3
1 2 3 2 3 1 3 1 2

    一開始看這個題又是環又是圖又是排列組合的還以為很麻煩，不過讀完題發現其實沒有那麼復雜。題目的樣例也完全不用糾結，輸入3可以像樣例那樣輸出，也完全可以按自己想的顏色輸出（我的程序跑3的結果就是1 2 1 1 3 2 2 3 3，但是可以AC）。然後再找一下規律，就是兩個點間染一個顏色，然後以這兩個點為一個端點的線都不能再染這個顏色了，這樣下來就是自己找規律看如何填顏色了。如果輸入的是偶數那麼無論如何都做不到這一點，所以偶數就直接輸出"No solution"就好了，奇數的話再找下規律，我是先順著填的顏色，最後填完發現顏色數量正好再觀察下我畫的表的規律，寫出了程序。

    下面是我以輸入7為例填的表格，兩邊表示兩個點，裡面的代號是這兩個點間邊的顏色

  1 2 3 4 5 6 7 1 \ 1 2 3 4 5 6 2 1 \ 3 4 5 6 7 3 2 3 \ 5 6 7 1 4 3 4 5 \ 7 1 2 5 4 5 6 7 \ 2 3 6 5 6 7 1 2 \ 4 7 6 7 1 2 3 4 \

 

    填顏色的方法應該不止一種，找出來一種就好了，然後我根據我的表的規律寫的代碼，下面是AC代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1005];

int main()
{
     int T;
     int n;
     int i,j;
     int k,t;
     scanf("%d",&T);
     while(T--)
     {
          scanf("%d",&n);
          cout<<n<<endl;
          if(n%2==0)
               cout<<"No solution"<<endl;
          else
          {
               t=1;
               for(i=1;i<n-1;i++)
               {
                    k=t;
                    for(j=i+1;j<=n;j++)
                    {
                         cout<<i<<" "<<j<<" "<<k<<" ";
                         k=(k+1)%n;
                         if(k==0)
                              k=n;
                    }
                    t=(t+2)%n;
                    if(t==0)
                         t=n;
               }
               cout<<n-1<<" "<<n<<" "<<k<<endl;
          }
     }
     return 0;
}