首页 > 试题广场 > 多多的骰子组合
[编程题]多多的骰子组合
  • 热度指数:423 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
多多君拼团购买了N个骰子,为了方便后面进行活动,多多君需要将这些骰子进行分类。



两个骰子为同类的定义是:
将其中一个骰子通过若干次上下、左右或前后翻转后,其与另一个骰子对应的6面数字均相等。

现在多多君想知道不同种类的骰子的数量分别有多少。

输入描述:
第一行1个整数N,表示骰子的数量。
(1 <= N <= 1,000)
接下来N行,每行6个数字(1~6,且各不相同)
其中第i行表示第i个骰子当前上、下、左、右、前、后这6面的数字。


输出描述:
共2行:
第一行1个整数M,表示不同种类的骰子的个数
第二行M个整数,由大到小排序,表示每个种类的骰子的数量
示例1

输入

2
1 2 3 4 5 6
1 2 6 5 3 4

输出

1
2

说明

第二个骰子相当于是第一个骰子从左向右旋转了一面得到,属于同类。
示例2

输入

3
1 2 3 4 5 6
1 2 6 5 3 4
1 2 3 4 6 5

输出

2
2 1

说明

第三个骰子无法通过任何旋转变换成第一个或第二个骰子。
示例3

输入

10
2 5 1 3 4 6
5 4 3 2 1 6
1 4 6 2 3 5
1 5 6 3 4 2
6 4 2 1 5 3
3 6 4 5 2 1
1 6 3 4 2 5
5 1 4 2 6 3
6 2 3 1 5 4
5 3 6 1 4 2

输出

9
2 1 1 1 1 1 1 1 1

说明

只有第4个骰子(1 5 6 3 4 2)与第8个骰子(5 1 4 2 6 3)属于同一类。

一种可能的变换方式:
1) 首先从右向左翻转1次
 (1 5 6 3 4 2) -> (1 5 4 2 3 6)
2) 然后从上向下翻转2次
 (1 5 4 2 3 6) -> (6 3 4 2 1 5) -> (5 1 4 2 6 3)

备注:
对于50%的数据,有: 1 <= N <= 50
对于100%的数据,有:1 <= N <= 1,000
我们取每个骰子:以1作为上面,然后得到侧边四面的4个数字的顺序。
如果任意两个骰子的这个侧面4个数字顺序是一样的,那么这两个骰子就是同类。

比如示例2
骰子1:123456,侧边的四面数字为 3546(或5463、..)
骰子2:126534,侧边的四面数字为 6354(或3546、..)
骰子3:123465,侧边的四面数字为 3645(或6453、..)
调整骰子2的侧边的四面数字顺序 3546,这就和骰子1一样了。(这里为了实现匹配是通过将四位数字转为int型整数,然后取不同顺序中最小的值)

此外结合如下规律:
1. 骰子6面可以分为3对,每对两面,比如 12 、34 、56
2. 骰子按对顺序调换不改变骰子顺序,比如 123456 与 561234 是同一类
3. 举例:骰子为 123456, 1位上面侧边四面为 3564
4. 举例:骰子为 345612, 1位上面侧边四面为 3564
5. 举例:骰子为 213456, 1位上面侧边四面为 6453
6. ...

#include<bits/stdc++.h>
using namespace std;

int main() {
	int N; 
	cin >> N;
	unordered_map<int, int> um;
	for(int n=1; n<=N; ++n){
		int a[6];
		for(int i=0; i<6; ++i) cin >> a[i];
		int val = 0;
		for(int i=0; i<6; ++i) {
			if(a[i]==1) {
				if(i%2==0) 
					val = a[(i+2)%6]*1000 + a[(i+4)%6]*100 + a[(i+3)%6]*10 + a[(i+5)%6];
				else  
					val = a[(i+4)%6]*1000 + a[(i+2)%6]*100 + a[(i+3)%6]*10 + a[(i+1)%6];
				break;
			}
		}

		for(int i=0, tmp = val; i<3; ++i) {
			tmp = tmp/10 + (tmp%10*1000);
			val = min(val, tmp);
		}
		um[val]++;
	}

	vector<int> res;
	for(auto iter : um) res.push_back(iter.second);
	sort(res.begin(), res.end());
	
	cout << res.size() << endl;
	for(int i=res.size()-1; i>=0; --i) cout << res[i] << " ";
	return 0;	
}


编辑于 2021-05-18 21:32:42 回复(0)
将每一个骰子按一定规律旋转,以 “前后左右上下” 的顺序来看一个骰子 12 34 56
前后固定旋转,可得到
12 34 56
12 56 43
12 43 65
12 65 34
同理,固定左右
56 34 21
21 34 65
65 34 12
12 34 56
固定上下
43 12 56
21 43 56
43 12 56
12 34 56
观察 “12 34 56” 变成 “12 56 43”,”12 65 34“也就是说每一次旋转固定一个面,剩余四个面交换位置,其中“一对”再交换
或者 “12 34 56” 变成 “12 43 65” 其中“两对” 各自交换
那么我们把骰子旋转到“最小”的样子
p1代表前后,p2代表左右, p3代表上下
让 p1最小值 < p2最小值 < p3最小值
让 p1[0]<p1[1] , p2[0]<p2[1]
import collections
n = int(input())
counter = collections.Counter()
finger={}
res = []
for i in range(n):
    l=list(map(int,input().strip().split()))
    p1 = l[:2]
    p2 = l[2:4]
    p3 = l[4:]
    if min(p1)>min(p2):
        p1,p2=p2,p1[::-1]
    if min(p1)>min(p3):
        p1,p3=p3,p1[::-1]
    if min(p2)>min(p3):
        p2,p3=p3,p2[::-1]
    if p1[0]>p1[1]:
        p1,p3=p1[::-1],p3[::-1]
    if p2[0]>p2[1]:
        p2,p3=p2[::-1],p3[::-1]
    s = (p1[0],p1[1],p2[0],p2[1],p3[0],p3[1])
    if s not in finger:
        finger[s]=len(res)
        res.append(1)
    else:
        res[finger[s]]+=1
print(len(res))
res=map(str,sorted(res,reverse=True))
print(' '.join(res))


编辑于 2021-05-22 11:26:53 回复(0)
对于每个筛子都搜索一趟搞到对应的那个字典序最小的作为key,开map<KeyType, int> cnt计数即可(此处KeyType为vector<int>
本地跑了下6的全排列,每个排列通过搜索都能得到24中不同的排列,即每24种排列视为1种,总共6!24 = 30总不同的筛子(具体见注释掉的那段代码)

#include <bits/stdc++.h>
using namespace std;

const string dirs[] = {"上","下","左","右","前","后"}; // 默认的顺序
map<string, int> s_idx; // 维护字符串在dirs中的位置

/* 3种不同的旋转方式:
**   例如第一种为
**   [上 -> 右 ], [右 -> 下], [下 -> 左], [左 -> 上]  
**   即        上 -> 右 -> 下 -> 左 -> ...
*/
const string turn[3][4] = {
	{"上","右","下","左"}, /*前后不动*/
	{"上","前","下","后"}, /*左右不动*/
	{"前","右","后","左"}  /*上下不动*/
};


vector<vector<int> > get_nexts(vector<int> vv) {
	/**
	 * 获取vv的3个下一种状态
	 */
	vector<vector<int> > ret;
	for (int i = 0; i < 3; ++i){
		auto v = vv;
		/* 完成“旋转”操作*/
		int t = v[s_idx[turn[i][0]]];
		for (int j = 1; j < 4; ++j){
			v[s_idx[turn[i][j-1]]] = v[s_idx[turn[i][j]]];
		}
		v[s_idx[turn[i][3]]] = t;
		ret.push_back(v);
	}

	return ret;
}

ostream & operator << (ostream &cout, vector<int> v) {
	cout << "[";
	for ( auto i : v ) {
		cout << i << " ";
	}
	cout << "]";

}

vector<int> get_min(vector<int> v) {
	/**
	 * 搜索一趟,获取v通过旋转可达的最小的
	 */
	map<vector<int>, bool> vis;
	queue<vector<int> > q;
	vis[v] = 1;
	q.push(v);
	vector<int> ret = v;
	while (q.size()) {
		vector<int> curr = q.front(); q.pop();
		if ( curr < ret ) {
			ret = curr;
		}
		auto nexts = get_nexts(curr);
		for ( auto next : nexts ) {
			if ( vis.find(next)==vis.end() ) {
				vis[next] = 1;
				q.push(next);
			}
		}
	}
	return ret;
}

int main(int argc, char const *argv[]){

	for (int i = 0; i < 6; ++i){
		s_idx[dirs[i]] = i;
	}

/*
	vector<int> v = {1,2,3,4,5,6};
	set<vector<int>> s;
	do{
		s.insert(get_min(v));
	}while(next_permutation(v.begin(), v.end()));
	for ( auto& item : s ) {
		for(auto i : item ) {
			cout << i << " ";
		}
		cout << "" << endl;
	}
	clog << "s.size() = " << s.size() << endl; //log
	return 0;
//	*/
	int n;
	cin>>n;
	map<vector<int>, int> mp;
	for ( int i = 0; i < n; ++i ) {
		vector<int> v;
		for ( int i = 0; i < 6; ++i ) {
			int x;
			cin>>x;
			v.push_back(x);
		}
		mp[get_min(v)]++;
	}
	vector<int> ans;
	for ( auto &item : mp ) {
		ans.push_back(item.second);
	}
	sort(ans.begin(), ans.end(), 
		[](int a, int b) -> bool {return a>b;}); // 降序
	cout << ans.size() << endl;
	for ( auto i : ans ) {
		cout << i << " ";
	}

	return 0;
}





发表于 2021-05-26 20:25:20 回复(0)

并查集

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> fa, sz;
int find(int x)
{
    return x == fa[x] ? fa[x] : (fa[x] = find(fa[x]));
}
bool merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
    {
        return false;
    }
    if (sz[x] < sz[y])
    {
        swap(x, y);
    }
    fa[y] = x;
    sz[x] += sz[y];
    return true;
}
int main()
{
    cin >> n;
    vector<vector<int>> S(n, vector<int>(6));
    fa.resize(n), sz.resize(n, 1);
    iota(fa.begin(), fa.end(), 0);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            cin >> S[i][j];
        }
    }
    auto f = [&](int i) -> vector<int>
    {
        if (S[i][0] == 1)
        {
            return vector<int>{S[i][5], S[i][3], S[i][4], S[i][2]};
        }
        else if (S[i][1] == 1)
        {
            return vector<int>{S[i][4], S[i][3], S[i][5], S[i][2]};
        }
        else if (S[i][2] == 1)
        {
            return vector<int>{S[i][0], S[i][4], S[i][1], S[i][5]};
        }
        else if (S[i][3] == 1)
        {
            return vector<int>{S[i][0], S[i][5], S[i][1], S[i][4]};
        }
        else if (S[i][4] == 1)
        {
            return vector<int>{S[i][0], S[i][3], S[i][1], S[i][2]};
        }
        return vector<int>{S[i][0], S[i][2], S[i][1], S[i][3]};
    };
    auto alike = [&](int i, int j) -> bool
    {
        auto a = f(i), b = f(j);
        for (int ii = 0; ii < 4; ++ii)
        {
            for (int jj = 0; jj < 4; ++jj)
            {
                if (a[ii] == b[jj])
                {
                    for (int k = 0; k < 4; ++k)
                    {
                        if (a[(ii + k) % 4] != b[(jj + k) % 4])
                        {
                            return false;
                        }
                    }
                    return true;
                }
            }
        }
        return false;
    };
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (alike(i, j))
            {
                merge(i, j);
            }
        }
    }
    vector<int> T;
    for (int i = 0; i < n; ++i)
    {
        if (i == fa[i])
        {
            T.emplace_back(sz[i]);
        }
    }
    sort(T.begin(), T.end(), greater<>());
    int m = T.size();
    cout << m << '\n';
    for (int i = 0; i < m; ++i)
    {
        cout << T[i] << " \n"[i == m - 1];
    }
    return 0;
}
发表于 2021-05-12 19:02:19 回复(0)