本文主要是介绍10601 - Cubes(Ploya),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
UVA 10601 - Cubes
题目链接
题意:给定正方体12条棱的颜色,要求用这些棱能组成多少不同的正方体
思路:利用ploya定理去求解,分类讨论,正方体一共24种旋转,对应的旋转方式有4种:
1、不动
2、沿两面中点连线旋转
3、沿对顶点连线旋转
4、沿两棱中点连线旋转
简单推算出每种情况对应的循环组数,在加上组合数学去进行选择颜色求解,注意第4种情况中,有两条棱和其他的循环长度是不同的,可以枚举然后扣掉讨论。
代码:
#include <stdio.h>
#include <string.h>int t, color[6], save[6], c[13][13];long long solve(int k) {long long sum = 0, ans = 1;for (int i = 0; i < 6; i++) {if (save[i] % k) return 0;save[i] /= k;sum += save[i];}for (int i = 0; i < 6; i++) {ans *= c[sum][save[i]];sum -= save[i];}return ans;
}long long solve1() {memcpy(save, color, sizeof(save));return solve(1);
}long long solve2() {memcpy(save, color, sizeof(save));long long ans = 6 * solve(4);memcpy(save, color, sizeof(save));return ans + 3 * solve(2);
}long long solve3() {memcpy(save, color, sizeof(save));return 8 * solve(3);
}long long solve4() {long long ans = 0;for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {memcpy(save, color, sizeof(save));save[i]--; save[j]--;if (save[i] < 0 || save[j] < 0) continue;ans += 6 * solve(2);} }return ans;
}int main() {for (int i = 0; i <= 12; i++) {c[i][0] = c[i][i] = 1;for (int j = 1; j < i; j++)c[i][j] = c[i - 1][j - 1] + c[i - 1][j];}scanf("%d", &t);while (t--) {int col;memset(color, 0, sizeof(color));for (int i = 0; i < 12; i++) {scanf("%d", &col);color[col - 1]++;}printf("%lld\n", (solve1() + solve2() + solve3() + solve4()) / 24);}return 0;
}
这篇关于10601 - Cubes(Ploya)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!