多多君拼团购买了N个骰子,为了方便后面进行活动,多多君需要将这些骰子进行分类。
两个骰子为同类的定义是:
将其中一个骰子通过若干次上下、左右或前后翻转后,其与另一个骰子对应的6面数字均相等。
将其中一个骰子通过若干次上下、左右或前后翻转后,其与另一个骰子对应的6面数字均相等。
第一行1个整数N,表示骰子的数量。(1 <= N <= 1,000)接下来N行,每行6个数字(1~6,且各不相同)其中第i行表示第i个骰子当前上、下、左、右、前、后这6面的数字。
共2行:
第一行1个整数M,表示不同种类的骰子的个数
第二行M个整数,由大到小排序,表示每个种类的骰子的数量
2 1 2 3 4 5 6 1 2 6 5 3 4
1 2
第二个骰子相当于是第一个骰子从左向右旋转了一面得到,属于同类。
3 1 2 3 4 5 6 1 2 6 5 3 4 1 2 3 4 6 5
2 2 1
第三个骰子无法通过任何旋转变换成第一个或第二个骰子。
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
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))
#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; }
#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; }
贴一个无脑枚举的方法,因为骰子只有 4 种旋转方法,所以每获得一个新的骰子,就 BFS 一下,把所有可能都遍历到(最多可能 24 种?),然后后面如果在遇到一样的,就可以直接判断它属于哪一种了。
记录每一种的数量,最后输出答案即可。
#include <bits/stdc++.h> #include <cstdio> #include <functional> #include <tuple> #include <unordered_map> #include <vector> using namespace std; struct sieve{ int up, down, left, right, front, back; string to_string() { static char t[15]; // cout << up << ' ' << down << ' ' << left << ' ' << right << ' ' << front << ' ' << back << endl; sprintf(t, "%d%d%d%d%d%d", up, down, left, right, front, back); return string(t); } }; sieve toUp(sieve s) { tie(s.front, s.down, s.back, s.up) = make_tuple(s.down, s.back, s.up, s.front); return s; } sieve toDown(sieve s) { tie(s.front, s.down, s.back, s.up) = make_tuple(s.up, s.front, s.down, s.back); return s; } sieve toLeft(sieve s) { tie(s.front, s.right, s.back, s.left) = make_tuple(s.right, s.back, s.left, s.front); return s; } sieve toRight(sieve s) { tie(s.front, s.right, s.back, s.left) = make_tuple(s.left, s.front, s.right, s.back); return s; } int main() { int n; cin >> n; // 筛子序列化 -> 种类编号 unordered_map<string, int> mp; vector<int> cnt(n); for (int i = 0; i < n; i++) { sieve s; cin >> s.up >> s.down >> s.left >> s.right >> s.front >> s.back; // cout << s.to_string() << endl; if (mp.count(s.to_string())) { cnt[mp[s.to_string()]]++; continue; } // 种类命名为 i cnt[i]++; queue<sieve> q; q.push(s); // cout << "s: " << s.to_string() << endl; while (q.size()) { auto x = q.front(); q.pop(); // cout << x.to_string() << endl; for (auto &y : vector<sieve>{toUp(x), toDown(x), toLeft(x), toDown(x)}) { if (mp.count(y.to_string())) continue; mp[y.to_string()] = i; q.push(y); } } } vector<int> res; for (int i = 0; i < n; i++) { if (cnt[i] > 0) res.push_back(cnt[i]); } sort(res.begin(), res.end(), greater<int>()); cout << res.size() << endl; for (auto x : res) { cout << x << " "; } }
#include <iostream> #include <map> #include <vector> #include <algorithm> using namespace std; map<vector<pair<int, int>>, int> p; struct dice { vector<pair<int, int>> v; vector<pair<int, int>> f; dice(vector<pair<int, int>> v) : v(v) { } void dau() { f = {v[2], v[1], {v[0].second, v[0].first}}; v = f; if (v[0].first > v[0].second) { swap(v[0].first, v[0].second); swap(v[2].first, v[2].second); } } void lar() { f = {v[1], {v[0].second, v[0].first}, v[2]}; v = f; if(v[0].first > v[0].second) { swap(v[0].first, v[0].second); swap(v[1].first, v[1].second); } } void oao() { f = {v[0], v[2], {v[1].second, v[1].first}}; v = f; if (v[1].first > v[1].second) { swap(v[1].first, v[1].second); swap(v[2].first, v[2].second); } } void find() { int idx = 0; for (; idx < 3; idx++) { if (v[idx].first == 1 || v[idx].second == 1) break; } if (idx == 0) { lar(); lar(); oao(); if (v[1] > v[2] || v[1].first > v[2].second) oao(); } else if (idx == 1) { lar(); oao(); if (v[1] > v[2] || v[1].first > v[2].second) oao(); } else { dau(); oao(); if (v[1] > v[2] || v[1].first > v[2].second) oao(); } } }; vector<int> ans; int main() { int n; cin >> n; int a, b, c, d, e, f; for (int i = 0; i < n; i++) { cin >> a >> b >> c >> d >> e >> f; dice x({{a, b}, {c, d}, {e, f}}); x.find(); p[x.v]++; } for (auto &t: p) { ans.push_back(t.second); } sort(ans.begin(), ans.end(), greater<int>()); cout << ans.size() << endl; for (auto &t: ans) cout << t << " "; }
和大家一样的想法,想法子将骰子固定住,固定两个面就行了,我是1在上面,先固定上下两面,前后左右四面保证最小的在左侧,怎么转的就稍微想一下就行,很简单
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] matrix = new int[n][6]; for (int i = 0; i < n; i++) { for (int j = 0; j < 6; j++) { matrix[i][j] = sc.nextInt(); } } getDiffNum(matrix, n); } private static void getDiffNum(int[][] matrix, int n) { for (int i = 0; i < n; i++) { // 将数据全转成 1 在上且左侧比右侧小的排序 int[] nums = matrix[i]; for (int j = 0; j < 6; j++) { if (1 == nums[j]) { rotate(nums, j); } } } Map<String, Integer> map = new HashMap<>(); // 进行次数统计 for (int i = 0; i < n; i++) { int[] nums = matrix[i]; StringBuilder sb = new StringBuilder(); for (int j = 0; j < 6; j++) { sb.append(nums[j]); } String key = sb.toString(); if (map.containsKey(key)) { map.put(key, 1 + map.get(key)); } else { map.put(key, 1); } } System.out.println(map.size()); map.values().stream().sorted((t1, t2) -> { return t2 - t1; }).forEach(item -> { System.out.print(item + " "); }); System.out.println(); } private static void rotate(int[] nums, int pos) { if (1 == pos) { swap(nums, 0, 1); swap(nums, 4, 5); } else if (2 == pos) { swap(nums, 0, 2); swap(nums, 1, 3); swap(nums, 2, 3); } else if (3 == pos) { swap(nums, 0, 2); swap(nums, 1, 3); swap(nums, 0, 1); } else if (4 == pos) { swap(nums, 0, 4); swap(nums, 1, 5); swap(nums, 4, 5); } else if (5 == pos) { swap(nums, 0, 4); swap(nums, 1, 5); swap(nums, 0, 1); } rotateLeftMin(nums); } private static void rotateLeftMin(int[] nums) { int idx = -1, min = Integer.MAX_VALUE; for (int i = 2; i < 6; i++) { if (min > nums[i]) { min = nums[i]; idx = i; } } rotate2(nums, idx); } /** * 将第三个位置置为后四个最小值 * @param nums * @param idx */ private static void rotate2(int[] nums, int idx) { if (3 == idx) { swap(nums, 2,3); swap(nums, 4,5); } else if (4 == idx) { swap(nums, 2,4); swap(nums, 3,5); swap(nums, 4,5); } else if (5 == idx) { swap(nums, 2,4); swap(nums, 3,5); swap(nums, 2,3); } } private static void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }
将每个骰子固定两个面,骰子的排序就是固定的,我选择将1转到上,剩下最大的转到左边 #include<bits/stdc++.h> using namespace std; string i2j(vector<int> a){ int id1; for(int i=0;i<6;i++){ if(a[i]==1) { id1=i; break; } } if(id1>1){ if(id1%2==0){ swap(a[id1],a[0]); swap(a[id1+1],a[1]); swap(a[id1+1],a[id1]); } else{ swap(a[id1],a[1]); swap(a[id1-1],a[0]); swap(a[1],a[0]); } } else{ if(id1==1){ swap(a[0],a[1]); swap(a[2],a[3]); } } int num_next=6; if(a[1]==6){ num_next=5; } int id_next; for(int i=2;i<6;i++){ if(a[i]==num_next){ id_next=i; break; } } if(id_next!=2){ if(id_next==3){ swap(a[2],a[3]); swap(a[4],a[5]); } else if(id_next==4){ swap(a[2],a[4]); swap(a[3],a[5]); swap(a[4],a[5]); } else{ swap(a[2],a[4]); swap(a[3],a[5]); swap(a[2],a[3]); } } string out=""; for(int i=0;i<6;i++){ out+=to_string(a[i]); } return out; } int main(){ int num=0; cin>>num; unordered_map<string , int> a; for(int i=0;i<num;i++){ vector<int> tmp(6,0); for(int j=0;j<6;j++){ cin>>tmp[j]; } string b=i2j(tmp); a[b]++; } cout<<a.size()<<endl; vector<int > c; for(auto i:a){ c.push_back(i.second); } sort(c.begin(),c.end(),greater<int>()); for(auto i:c){ cout<<i<<" "; } }
class dice(): def __init__(self, a): self.a=a def switch_out(self,i,j): if i!=j: self.a[2*i], self.a[2*i+1], self.a[2*j], self.a[2*j+1] = \ self.a[2*j], self.a[2*j+1], self.a[2*i+1], self.a[2*i] def switch_in(self,i): if self.a[2*i]>self.a[2*i+1]: self.a[2*i], self.a[2*i+1] = self.a[2*i+1], self.a[2*i] self.a[2*i+2], self.a[2*i+3] = self.a[2*i+3], self.a[2*i+2] def tidy(self): i1=self.a.index(1)//2 self.switch_out(0, i1) self.switch_in(0) i2=self.a.index(min(self.a[2:]))//2 self.switch_out(1, i2) self.switch_in(1) return tuple(self.a) n=int(input()) dc={} for i in range(n): nd=dice(list(map(int, input().split()))).tidy() dc[nd]=dc.get(nd, 0)+1 print(len(dc.keys())) for v in sorted(dc.values(), reverse=True): print(v, end=" ")
#include<iostream> #include<vector> #include<algorithm> using namespace std; int a[24][6] = { {1,2,3,4,5,6}, {4,3,1,2,5,6}, {2,1,4,3,5,6}, {3,4,2,1,5,6}, {1,2,4,3,6,5}, {3,4,1,2,6,5}, {2,1,3,4,6,5}, {4,3,2,1,6,5}, {1,2,6,5,3,4}, {5,6,1,2,3,4}, {2,1,5,6,3,4}, {6,5,2,1,3,4}, {1,2,5,6,4,3}, {6,5,1,2,4,3}, {2,1,6,5,4,3}, {5,6,2,1,4,3}, {6,5,3,4,1,2}, {4,3,6,5,1,2}, {5,6,4,3,1,2}, {3,4,5,6,1,2}, {5,6,3,4,2,1}, {4,3,5,6,2,1}, {6,5,4,3,2,1}, {3,4,6,5,2,1} }; int shai[6], tmp[6]; vector<int> cnt; int out[1010][6]; bool check(int a[6], int b[6]) { int flag = 1; for(int k = 0; k < 6; k++) { if(a[k] != b[k]) { flag = 0; break; } } return flag; } int main() { int N; cin >> N; for(int i = 0; i < N; i++) { for(int j = 0; j < 6; j++) cin >> shai[j]; int flag = 0; for(int c = 0; c < cnt.size(); c++) { // 和每一个做对比 // 有24种可能 for(int j = 0; j < 24; j++) { for(int k = 0; k < 6; k++) { tmp[k] = shai[a[j][k] - 1]; } if(check(out[c], tmp)) { cnt[c]++; flag = 1; break; } } if(flag) break; } if(flag == 0) { for(int k = 0; k < 6; k++) out[cnt.size()][k] = shai[k]; cnt.push_back(1); } } sort(cnt.begin(), cnt.end()); cout << cnt.size() << endl; for(int i = cnt.size() - 1; i >= 0; i--) cout << cnt[i] << ' '; }
from collections import * N = int(input()) _d = defaultdict(int) for l in range(N): tou = input().split() for i in range(6): tou[i] = int(tou[i]) # 旋转骰子 # 上0、下1、左2、右3、前4、后5 high ,low ,left ,right ,front ,back = 0,1,2,3,4,5 whereis1 = tou.index(1) if whereis1 == low:# 1在下面 tou[high], tou[low] ,tou[left] , tou[right] = tou[low], tou[high] ,tou[right] , tou[left] elif whereis1 == left: # 1在左边 tou[high], tou[low] ,tou[left] , tou[right] = tou[left], tou[right], tou[low], tou[high] elif whereis1 == right:#右边 tou[high], tou[low] ,tou[left] , tou[right] = tou[right], tou[left], tou[high] , tou[low] elif whereis1 == front: tou[high], tou[low] , tou[front], tou[back] = tou[front], tou[back], tou[low],tou[high] elif whereis1 == back: tou[high], tou[low] , tou[front], tou[back] = tou[back],tou[front],tou[high],tou[low] _str = str(low)#让1在最上面了 #左0、右1、前2、后3 left, right, front ,back = 0,1,2,3 tou = tou[2:] whereismin = tou.index(min(tou)) # 让min在左边 if whereismin == right: tou[left] , tou[right], tou[front], tou[back] = tou[right], tou[left], tou[back], tou[front] elif whereismin == front: tou[left] , tou[right], tou[front], tou[back] = tou[front], tou[back], tou[right], tou[left] elif whereismin == back: tou[left] , tou[right], tou[front], tou[back] = tou[back], tou[front], tou[left], tou[right] _str += str(tou[left])+str(tou[front])+str(tou[right])+str(tou[back]) _d[_str]+=1 print(len(_d)) A= list(_d.values()) A.sort() A = A[::-1] for i in range(len(A)): print(A[i],end=" ")
并查集
#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; }