列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[rockwyc992]

這題好像比賽時沒人寫出來
我分享一下想法
請幫忙想看看
有誰可以PO code上來
----------------------------
這題可以用對面固定的方式做
只要兩個骰子的對面3組相同
那就可以是相同的兩個骰子了
也不用管方向性
只要拆開反折，就是一樣的骰子了
時間複雜度大約是O((長*寬*骰子種類)^2)
p.s.所謂的種類是指形狀
例如
000b0   000a0
aaaaa   aaaaa
000a0跟000b0
只是翻轉，可以視為相同


然後相對的方式可以再存入的時候
規定大的數在前面
1-3
2-9
6-7
可以變成
9-2
7-6
3-1
比較時同種就只有1種順序
如果還不行的話
可以用3*4的方塊先做一次
看看有哪些方塊是相同的
可以節省時間
避免範例測資2這樣的圖

[david942j]

一點想法:
因為骰子展開圖一定可以包含在一個4*4的方格裡
可以窮舉C(16,6)並check是否為合法展開圖
再用bitmask紀錄一個合法展開圖的樣子

[esrever]

ㄨㄨㄨ　　
　　ㄨㄨㄨ

唔...這個超過4*4了...

[ck99126]

這題可以用對面固定的方式做
只要兩個骰子的對面3組相同
那就可以是相同的兩個骰子了
也不用管方向性
只要拆開反折，就是一樣的骰子了

題目裡有說:
"沿著兩個相鄰方格的邊邊往後摺下去"
所以還是得考慮鏡像的問題

[ck99126]

我個人沒有參加過NPSC，
但我可以理解如果在比賽解這題一點都不划算，
我解這題所花的零零碎碎的時間起碼有四五個小時，
更不要說那些對骰子展開圖不熟的人了!
既在ZJ裡AC了，我會趕快打完說明。
(在寒假內完成)

P.S.
想一下也知道我絕不是第一個解出來的...

[ck99126]

說明

我們可以將這個題目分成兩個部份：
一、剪開紙張，做成骰子
二、判斷有幾種不同的骰子

然而在做這兩件事之前，必須先決定出表示一個骰子的方式，
通常是用一個序列來表示，在本文接下來的部分將此稱作「編碼」。

第一部分

對紙張的每一個位置，將展開圖貼上去，
只要展開圖沒有超出紙張，就可記錄成一個骰子。
骰子展開圖的基本款有十一個，分三類：
(1)　中間四格
    Ｘ　　　 | Ｘ　　　 | Ｘ　　　 | Ｘ　　　 | 　Ｘ　　 | 　Ｘ　　
    ＸＸＸＸ | ＸＸＸＸ | ＸＸＸＸ | ＸＸＸＸ | ＸＸＸＸ | ＸＸＸＸ
    Ｘ　　　 | 　Ｘ　　 | 　　Ｘ　 | 　　　Ｘ | 　Ｘ　　 | 　　Ｘ　
(2)　中間三格
    ＸＸ　　 | ＸＸ　　 | ＸＸ　　
    　ＸＸＸ | 　ＸＸＸ | 　ＸＸＸ
    　Ｘ　　 | 　　Ｘ　 | 　　　Ｘ
(3)　點對稱但不屬於第一類
    ＸＸ　　 | ＸＸＸ　　
    　ＸＸ　 | 　　ＸＸＸ
    　　ＸＸ | 　　　　　
可以算出扣除旋轉、鏡射前共有64種。
分成三類是因為第一、二類可以透過開迴圈省去不少程式碼。

第二部分

在第一部分中，有可能編碼相異，卻仍代表相同的骰子。
因此，我們要把原本的編碼轉換成「標準」編碼，
讓同樣的骰子有相同的標準編碼，
不一樣的骰子的標準編碼會相異。

提供兩種作法：
(1) 同rockwyc992所說，互不相鄰的兩個面分在同一組，
    然後每組中編號較小（或較大）的排到第一個，
    這三組再依字典序排成小到大（或大到小）。
    然而，我們在做排序時用到許多的「交換」，
    而任何一種交換都能對應到一種「鏡射」，
    因此我們要記錄在此過程中交換的次數，
    模2之後記錄在骰子上。
    還要注意的是，有兩種類型的骰子做鏡像後仍和自己一樣，
    交換次數要算做零：
    1.有任何一組中的兩個面相同。Ex:a-a, b-c, d-e.
    2.有兩組以上相同。Ex:a-b, c-d, c-d.
(2) 旋轉骰子，各個方向都試一遍，會得到6*4=24種序列。
    挑字典序最小（或最大）的序列取代原本的序列。

轉換成標準編碼之後，
便可透過一些簡單的方法算出有幾種不同的骰子。
提供三種作法：
(1) 排序
(2) 使用樹狀結構
(3) Hash Table

時間複雜度

第一部分：
我們令第一部分做出了X顆骰子
──X約為N*M*64（高度*寬度*展開圖數目）──
這樣是O(X)。

第二部分：
取決於用的排序方式或樹狀結構或Hash方式，
盡量是O(X)或O(XlogX)，O(X^2)恐怕會TLE。

[ck99126]

兩份code的共同部分

我用以下的方式表示骰子：
頂面存於[0]，底面存於[3]，
而側面，從上往下看，逆時針方向繞，
依序存於[1],[2],[4],[5]。
特性是[k]和[k+3]不相鄰(k=0~2)。

在剪開紙張的部分，就舉個例子：
根據訂好的表示法，
可以將面和序列做如下對應。
Ｘ　　　 | ０　　　 　 ３
ＸＸＸＸ | １２４５ 或 １５４２ 等等共24種
Ｘ　　　 | ３　　　 　 ０

所以若在紙張剪下此形狀，如下，
ＡＢＣＤ | Ｘ　　　
ＥＦＧＨ | ＸＸＸＸ
ＩＪＫＬ | Ｘ　　　
序列可以存成
‘A’, ‘E’, ‘F’, ‘I’, ‘G’, ‘H’或
‘I’, ‘E’, ‘H’, ‘A’, ‘G’, ‘F’等等

選一種就好了，因為之後會做標準化。
剩下的展開圖就是這樣以此類推。

第一份Code

轉換成標準編碼的部分：
用第一種作法，整理成較小的在前面。
計算骰子種類數的部分：
用第一種作法，排序成小到大，
接著開個迴圈去檢查。
耗時516ms，用了4.2MB。

代碼: [選擇]

#include <algorithm>
#include <cstdio>
using namespace std;
int N, M;
char paper[50][51];
struct diceid
{
    int num[7];
};
diceid dice[1000000];
void cut(int x, int y, int &c)
{
    int i, j;
    if(N - x >= 3 && M - y >= 4)
    {
        for(i = 0;i < 4; i++) for(j = 0; j < 4; j++) dice[c].num[0] = paper[x][y + i], dice[c].num[1] = paper[x + 1][y], dice[c].num[2] = paper[x + 1][y + 1], dice[c].num[3] = paper[x + 2][y + j], dice[c].num[4] = paper[x + 1][y + 2], dice[c].num[5] = paper[x + 1][y + 3], c++;
        for(i = 1; i < 4; i++) dice[c].num[0] = paper[x][y], dice[c].num[1] = paper[x + 1][y + 1], dice[c].num[2] = paper[x][y + 1], dice[c].num[3] = paper[x + 1][y + 2], dice[c].num[4] = paper[x + 1][y + 3], dice[c].num[5] = paper[x + 2][y + i], c++;
        for(i = 1; i < 4; i++) dice[c].num[0] = paper[x + 2][y], dice[c].num[1] = paper[x + 2][y + 1], dice[c].num[2] = paper[x + 1][y + 1], dice[c].num[3] = paper[x + 1][y + 2], dice[c].num[4] = paper[x][y + i], dice[c].num[5] = paper[x + 1][y + 3], c++;
        for(i = 0; i < 3; i++) dice[c].num[0] = paper[x + 2][y + 3], dice[c].num[1] = paper[x + 1][y + 2], dice[c].num[2] = paper[x + 2][y + 2], dice[c].num[3] = paper[x + 1][y + 1], dice[c].num[4] = paper[x + 1][y], dice[c].num[5] = paper[x][y + i], c++;
        for(i = 0; i < 3; i++) dice[c].num[0] = paper[x][y + 3], dice[c].num[1] = paper[x][y + 2], dice[c].num[2] = paper[x + 1][y + 2], dice[c].num[3] = paper[x + 1][y + 1], dice[c].num[4] = paper[x + 2][y + i], dice[c].num[5] = paper[x + 1][y], c++;
        dice[c].num[0] = paper[x + 2][y], dice[c].num[1] = paper[x + 2][y + 1], dice[c].num[2] = paper[x + 1][y + 1], dice[c].num[3] = paper[x + 1][y + 2], dice[c].num[4] = paper[x][y + 2], dice[c].num[5] = paper[x][y + 3], c++;
        dice[c].num[0] = paper[x][y], dice[c].num[1] = paper[x + 1][y + 1], dice[c].num[2] = paper[x][y + 1], dice[c].num[3] = paper[x + 1][y + 2], dice[c].num[4] = paper[x + 2][y + 3], dice[c].num[5] = paper[x + 2][y + 2], c++;
    }
    if(N - x >= 4 && M - y >= 3)
    {
        for(i = 0; i < 4; i++) for(j = 0; j < 4; j++) dice[c].num[0] = paper[x + i][y + 2], dice[c].num[1] = paper[x][y + 1], dice[c].num[2] = paper[x + 1][y + 1], dice[c].num[3] = paper[x + j][y], dice[c].num[4] = paper[x + 2][y + 1], dice[c].num[5] = paper[x + 3][y + 1], c++;
        for(i = 1; i < 4; i++) dice[c].num[0] = paper[x][y + 2], dice[c].num[1] = paper[x + 1][y + 1], dice[c].num[2] = paper[x + 1][y + 2], dice[c].num[3] = paper[x + 2][y + 1], dice[c].num[4] = paper[x + 3][y + 1], dice[c].num[5] = paper[x + i][y], c++;
        for(i = 1; i < 4; i++) dice[c].num[0] = paper[x][y], dice[c].num[1] = paper[x + 1][y], dice[c].num[2] = paper[x + 1][y + 1], dice[c].num[3] = paper[x + 2][y + 1], dice[c].num[4] = paper[x + i][y + 2], dice[c].num[5] = paper[x + 3][y + 1], c++;
        for(i = 0; i < 3; i++) dice[c].num[0] = paper[x + 3][y], dice[c].num[1] = paper[x + 2][y + 1], dice[c].num[2] = paper[x + 2][y], dice[c].num[3] = paper[x + 1][y + 1], dice[c].num[4] = paper[x][y + 1], dice[c].num[5] = paper[x + i][y + 2], c++;
        for(i = 0; i < 3; i++) dice[c].num[0] = paper[x + 3][y + 2], dice[c].num[1] = paper[x + 2][y + 2], dice[c].num[2] = paper[x + 2][y + 1], dice[c].num[3] = paper[x + 1][y + 1], dice[c].num[4] = paper[x + i][y], dice[c].num[5] = paper[x][y + 1], c++;
        dice[c].num[0] = paper[x + 3][y], dice[c].num[1] = paper[x + 2][y + 1], dice[c].num[2] = paper[x + 2][y], dice[c].num[3] = paper[x + 1][y + 1], dice[c].num[4] = paper[x][y + 2], dice[c].num[5] = paper[x + 1][y + 2], c++;
        dice[c].num[0] = paper[x][y], dice[c].num[1] = paper[x + 1][y], dice[c].num[2] = paper[x + 1][y + 1], dice[c].num[3] = paper[x + 2][y + 1], dice[c].num[4] = paper[x + 2][y + 2], dice[c].num[5] = paper[x + 3][y + 2], c++;
    }
    if(N - x >= 2 && M - y >= 5)
    {
        dice[c].num[0] = paper[x][y], dice[c].num[1] = paper[x][y + 1], dice[c].num[2] = paper[x + 1][y + 4], dice[c].num[3] = paper[x][y + 2], dice[c].num[4] = paper[x + 1][y + 3], dice[c].num[5] = paper[x + 1][y + 2], c++;
        dice[c].num[0] = paper[x + 1][y], dice[c].num[1] = paper[x + 1][y + 1], dice[c].num[2] = paper[x][y + 2], dice[c].num[3] = paper[x + 1][y + 2], dice[c].num[4] = paper[x][y + 3], dice[c].num[5] = paper[x][y + 4], c++;
    }
    if(N - x >= 5 && M - y >= 2)
    {
        dice[c].num[0] = paper[x][y], dice[c].num[1] = paper[x + 1][y], dice[c].num[2] = paper[x + 2][y + 1], dice[c].num[3] = paper[x + 2][y], dice[c].num[4] = paper[x + 3][y + 1], dice[c].num[5] = paper[x + 4][y + 1], c++;
        dice[c].num[0] = paper[x][y + 1], dice[c].num[1] = paper[x + 1][y + 1], dice[c].num[2] = paper[x + 4][y], dice[c].num[3] = paper[x + 2][y + 1], dice[c].num[4] = paper[x + 3][y], dice[c].num[5] = paper[x + 2][y], c++;
    }
}
void mir1(int n, int i, int &r)
{
    if(dice[n].num[i] > dice[n].num[i + 3])
    {
        swap(dice[n].num[i], dice[n].num[i + 3]);
        r++;
    }
}
void mir2(int n, int i, int &r)
{
    if(dice[n].num[i] > dice[n].num[i + 1])
    {
        swap(dice[n].num[i], dice[n].num[i + 1]);
        swap(dice[n].num[i + 3], dice[n].num[i + 4]);
        r++;
    }
    if(dice[n].num[i] == dice[n].num[i + 1] && dice[n].num[i + 3] > dice[n].num[i + 4])
    {
        swap(dice[n].num[i + 3], dice[n].num[i + 4]);
        r++;
    }
}
void standardize(int n)
{
    int i, r = 0;
    for(i = 0;i < 3;i++) mir1(n,i,r);
    mir2(n,0,r);
    mir2(n,1,r);
    mir2(n,0,r);
    for(i = 0;i < 3;i++) if(dice[n].num[i] == dice[n].num[i + 3]) r = 0;
    if(dice[n].num[0] == dice[n].num[1] && dice[n].num[3] == dice[n].num[4]) r = 0;
    if(dice[n].num[1] == dice[n].num[2] && dice[n].num[4] == dice[n].num[5]) r = 0;
    dice[n].num[6] = r%2;
}
bool cmp(diceid a, diceid b)
{
    int i;
    for(i = 0; i < 7; i++)
        if(a.num[i] != b.num[i])
            return a.num[i] < b.num[i];
    return 0;
}
int main()
{
    int i, j, T;
    scanf("%d", &T);
    while(T--)
    {
        int tot = 0;
        scanf("%d%d", &N, &M);
        for(i = 0; i < N; i++) scanf("%s", paper[i]);
        for(i = 0; i < N; i++) for(j = 0; j < M; j++) cut(i, j, tot);
        if(tot == 0) printf("0\n");
        else
        {
            int cat = 1;
            for(i = 0; i < tot; i++) standardize(i);
            sort(dice, dice + tot, cmp);
            for(i = 1; i < tot; i++)
                if(cmp(dice[i - 1], dice[i]))
                    cat++;
            printf("%d\n", cat);
        }
    }
    return 0;
}


第二份Code

轉換成標準編碼的部分：
用第二種作法，先定義三種轉軸相異的旋轉，
各方向轉過一遍後，挑字典序最小的存起來。
計算骰子種類數的部分：
用第二種作法，用的是C++的set，
不斷進行insert，最後取size。
耗時2.5s，用了10.8MB。

代碼: [選擇]

#include <cstdio>
#include <string>
#include <set>
using namespace std;
int N, M;
char paper[50][51];
string dice[1000000];
void cut(int x, int y, int &c)
{
    int i, j;
    if(N - x >= 3 && M - y >= 4)
    {
        for(i = 0;i < 4; i++) for(j = 0; j < 4; j++) dice[c].resize(6), dice[c][0] = paper[x][y + i], dice[c][1] = paper[x + 1][y], dice[c][2] = paper[x + 1][y + 1], dice[c][3] = paper[x + 2][y + j], dice[c][4] = paper[x + 1][y + 2], dice[c][5] = paper[x + 1][y + 3], c++;
        for(i = 1; i < 4; i++) dice[c].resize(6), dice[c][0] = paper[x][y], dice[c][1] = paper[x + 1][y + 1], dice[c][2] = paper[x][y + 1], dice[c][3] = paper[x + 1][y + 2], dice[c][4] = paper[x + 1][y + 3], dice[c][5] = paper[x + 2][y + i], c++;
        for(i = 1; i < 4; i++) dice[c].resize(6), dice[c][0] = paper[x + 2][y], dice[c][1] = paper[x + 2][y + 1], dice[c][2] = paper[x + 1][y + 1], dice[c][3] = paper[x + 1][y + 2], dice[c][4] = paper[x][y + i], dice[c][5] = paper[x + 1][y + 3], c++;
        for(i = 0; i < 3; i++) dice[c].resize(6), dice[c][0] = paper[x + 2][y + 3], dice[c][1] = paper[x + 1][y + 2], dice[c][2] = paper[x + 2][y + 2], dice[c][3] = paper[x + 1][y + 1], dice[c][4] = paper[x + 1][y], dice[c][5] = paper[x][y + i], c++;
        for(i = 0; i < 3; i++) dice[c].resize(6), dice[c][0] = paper[x][y + 3], dice[c][1] = paper[x][y + 2], dice[c][2] = paper[x + 1][y + 2], dice[c][3] = paper[x + 1][y + 1], dice[c][4] = paper[x + 2][y + i], dice[c][5] = paper[x + 1][y], c++;
        dice[c].resize(6), dice[c][0] = paper[x + 2][y], dice[c][1] = paper[x + 2][y + 1], dice[c][2] = paper[x + 1][y + 1], dice[c][3] = paper[x + 1][y + 2], dice[c][4] = paper[x][y + 2], dice[c][5] = paper[x][y + 3], c++;
        dice[c].resize(6), dice[c][0] = paper[x][y], dice[c][1] = paper[x + 1][y + 1], dice[c][2] = paper[x][y + 1], dice[c][3] = paper[x + 1][y + 2], dice[c][4] = paper[x + 2][y + 3], dice[c][5] = paper[x + 2][y + 2], c++;
    }
    if(N - x >= 4 && M - y >= 3)
    {
        for(i = 0; i < 4; i++) for(j = 0; j < 4; j++) dice[c].resize(6), dice[c][0] = paper[x + i][y + 2], dice[c][1] = paper[x][y + 1], dice[c][2] = paper[x + 1][y + 1], dice[c][3] = paper[x + j][y], dice[c][4] = paper[x + 2][y + 1], dice[c][5] = paper[x + 3][y + 1], c++;
        for(i = 1; i < 4; i++) dice[c].resize(6), dice[c][0] = paper[x][y + 2], dice[c][1] = paper[x + 1][y + 1], dice[c][2] = paper[x + 1][y + 2], dice[c][3] = paper[x + 2][y + 1], dice[c][4] = paper[x + 3][y + 1], dice[c][5] = paper[x + i][y], c++;
        for(i = 1; i < 4; i++) dice[c].resize(6), dice[c][0] = paper[x][y], dice[c][1] = paper[x + 1][y], dice[c][2] = paper[x + 1][y + 1], dice[c][3] = paper[x + 2][y + 1], dice[c][4] = paper[x + i][y + 2], dice[c][5] = paper[x + 3][y + 1], c++;
        for(i = 0; i < 3; i++) dice[c].resize(6), dice[c][0] = paper[x + 3][y], dice[c][1] = paper[x + 2][y + 1], dice[c][2] = paper[x + 2][y], dice[c][3] = paper[x + 1][y + 1], dice[c][4] = paper[x][y + 1], dice[c][5] = paper[x + i][y + 2], c++;
        for(i = 0; i < 3; i++) dice[c].resize(6), dice[c][0] = paper[x + 3][y + 2], dice[c][1] = paper[x + 2][y + 2], dice[c][2] = paper[x + 2][y + 1], dice[c][3] = paper[x + 1][y + 1], dice[c][4] = paper[x + i][y], dice[c][5] = paper[x][y + 1], c++;
        dice[c].resize(6), dice[c][0] = paper[x + 3][y], dice[c][1] = paper[x + 2][y + 1], dice[c][2] = paper[x + 2][y], dice[c][3] = paper[x + 1][y + 1], dice[c][4] = paper[x][y + 2], dice[c][5] = paper[x + 1][y + 2], c++;
        dice[c].resize(6), dice[c][0] = paper[x][y], dice[c][1] = paper[x + 1][y], dice[c][2] = paper[x + 1][y + 1], dice[c][3] = paper[x + 2][y + 1], dice[c][4] = paper[x + 2][y + 2], dice[c][5] = paper[x + 3][y + 2], c++;
    }
    if(N - x >= 2 && M - y >= 5)
    {
        dice[c].resize(6), dice[c][0] = paper[x][y], dice[c][1] = paper[x][y + 1], dice[c][2] = paper[x + 1][y + 4], dice[c][3] = paper[x][y + 2], dice[c][4] = paper[x + 1][y + 3], dice[c][5] = paper[x + 1][y + 2], c++;
        dice[c].resize(6), dice[c][0] = paper[x + 1][y], dice[c][1] = paper[x + 1][y + 1], dice[c][2] = paper[x][y + 2], dice[c][3] = paper[x + 1][y + 2], dice[c][4] = paper[x][y + 3], dice[c][5] = paper[x][y + 4], c++;
    }
    if(N - x >= 5 && M - y >= 2)
    {
        dice[c].resize(6), dice[c][0] = paper[x][y], dice[c][1] = paper[x + 1][y], dice[c][2] = paper[x + 2][y + 1], dice[c][3] = paper[x + 2][y], dice[c][4] = paper[x + 3][y + 1], dice[c][5] = paper[x + 4][y + 1], c++;
        dice[c].resize(6), dice[c][0] = paper[x][y + 1], dice[c][1] = paper[x + 1][y + 1], dice[c][2] = paper[x + 4][y], dice[c][3] = paper[x + 2][y + 1], dice[c][4] = paper[x + 3][y], dice[c][5] = paper[x + 2][y], c++;
    }
}
void CW(string& ori)
{
    char tem = ori[1];
    ori[1] = ori[2], ori[2] = ori[4], ori[4] = ori[5], ori[5] = tem;
}
void left(string& ori)
{
    char tem = ori[0];
    ori[0] = ori[5], ori[5] = ori[3], ori[3] = ori[2], ori[2] = tem;
}
void down(string& ori)
{
    char tem = ori[0];
    ori[0] = ori[1], ori[1] = ori[3], ori[3] = ori[4], ori[4] = tem;
}
void standardize(int n)
{
    int i;
    string res;
    for(i = 0; i < 4; i++) res = max(dice[n], res), CW(dice[n]);
    left(dice[n]);
    for(i = 0; i < 4; i++) res = max(dice[n], res), CW(dice[n]);
    down(dice[n]);
    for(i = 0; i < 4; i++) res = max(dice[n], res), CW(dice[n]);
    left(dice[n]);
    for(i = 0; i < 4; i++) res = max(dice[n], res), CW(dice[n]);
    down(dice[n]);
    for(i = 0; i < 4; i++) res = max(dice[n], res), CW(dice[n]);
    left(dice[n]);
    for(i = 0; i < 4; i++) res = max(dice[n], res), CW(dice[n]);
    dice[n] = res;
}
int main()
{
    int i, j, T;
    scanf("%d", &T);
    while(T--)
    {
        int tot = 0;
        set<string> cat;
        scanf("%d%d", &N, &M);
        for(i = 0; i < N; i++) scanf("%s", paper[i]);
        for(i = 0; i < N; i++) for(j = 0; j < M; j++) cut(i, j, tot);
        for(i = 0; i < tot; i++) standardize(i);
        for(i = 0; i < tot; i++) cat.insert(dice[i]);
        printf("%d\n", cat.size());
    }
    return 0;
}