UVA 10601 - Cubes

題目鏈接

題意：給定正方體12條棱的顏色，要求用這些棱能組成多少不同的正方體

思路：利用ploya定理去求解，分類討論，正方體一共24種旋轉(zhuǎn)。相應(yīng)的旋轉(zhuǎn)方式有4種：
1、不動(dòng)
2、沿兩面中點(diǎn)連線旋轉(zhuǎn)
3、沿對(duì)頂點(diǎn)連線旋轉(zhuǎn)
4、沿兩棱中點(diǎn)連線旋轉(zhuǎn)

簡(jiǎn)單推算出每種情況相應(yīng)的循環(huán)組數(shù)。在加上組合數(shù)學(xué)去進(jìn)行選擇顏色求解。注意第4種情況中，有兩條棱和其它的循環(huán)長(zhǎng)度是不同的，能夠枚舉然后扣掉討論。

代碼：

#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; }

轉(zhuǎn)載于:https://www.cnblogs.com/wzzkaifa/p/6897858.html

總結(jié)

以上是生活随笔為你收集整理的10601 - Cubes(Ploya)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。