查看: 625|回復: 2

[CF] 464B - Restore Cube

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2014-9-23 23:14:53 | 顯示全部樓層 |閱讀模式

    題意: 有正立方體頂點座標(8個) , 但是座標點的x,y,z可能是對調的(不同點之間不對調),求原本的正立方體頂點座標(任一解或無解)


    方法:暴力
    基本上就是dfs下去
    要枚舉所有點的排列情況
    這DFS怎麼樣比較好寫呢?
    這裡有一個交換方法枚舉一個點的所有排列(6種)

    交換次序如下

    原本 -> 123
    213
    312
    132
    231
    321
    回到 -> 123

    其實其中的數學原理我並不懂(待高手補充)
    總之交換順序就是 第1,2交換;第1,3交換;第1,2交換;第1,3交換......
    因為會回到原點,所以沒什麼後遺症,只要每一層遞迴for寫下去就對了
    像這樣,找到答案就 return 了不要真的枚舉完
    [C++] 純文本查看 復制代碼
    for(int i = 1 ; i <= 6 ; i++)
            {
                    swap(point[p][0], point[p][2-(i&1)]);
                    if(p==7)
                    {
                            if(check_cube())
                                    return true;
                    }
                    else if(dfs(p+1))
                            return true;
            }
            return false;



    最後要檢查是否是正立方體
    方法是利用邊長
    所有點對之間的邊長長度只有3種,數量也是固定的
    暴力的下去判斷他(但也別把常數搞得太大)
    還有邊長可以存平方避免sqrt下去會有浮點誤差問題

    記得開long long


    AC CODE:
    購買主題 本主題需向作者支付 1 枚金幣 才能瀏覽
    <這是個人簽名欄位>
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表