首页 > ACM题库 > HDU-杭电 > HDU 3547-DIY Cube-计算几何-[解题报告]HOJ
2014
11-05

HDU 3547-DIY Cube-计算几何-[解题报告]HOJ

DIY Cube

问题描述 :

Mr. D is interesting in combinatorial enumeration. Now he want to find out the number of ways on painting the vertexes of a cube. Suppose there are C different colors and two paintings are considered the same if they can transform from one to another by rotation.

输入:

There are multiple test cases in the input, the first line of input contains an integer denoting the number of test cases.
For each test case, there are only one integer C, denoting the number of colors. (1 <= C <= 1000000000)

输出:

There are multiple test cases in the input, the first line of input contains an integer denoting the number of test cases.
For each test case, there are only one integer C, denoting the number of colors. (1 <= C <= 1000000000)

样例输入:

3
1
2
112

样例输出:

Case 1: 1
Case 2: 23
Case 3: 031651434916928

来源:http://acm.hdu.edu.cn/showproblem.php?pid=3547

题意:用n中颜色涂一个正方体的八个顶点,求有多少种方法。如果得到的结果大于等于10^15,则输出后15位即可。

思路:Ploya定理啊,是组合数学课本上的原题。对应于四种不同类型的旋转,1:不动,即恒等旋转有1个;2:绕三对对立面的中心旋转,有旋转90度,旋转180度,旋转270度,分别有3个;3:绕对边终点连线旋转,有6个;4:绕对角点旋转,有旋转120度和旋转240度,分别有4个。因此共有24个对称。最后可以转化成公式(k^8 + 17*k^4 + 6 * k^2)/ 24 。由于涉及到了大数,所以这道题我使用java写的,唉,不会java,乱搞一通。

代码:

import java.util.*;
import java.math.BigInteger;
public class Main {
	/*
	public static BigInteger pow(int x){
		BigInteger a;
		a=a.pow(12)
	}*/
	public static void main(String[] args){
		int numcase;
		Scanner cin = new Scanner(System.in);
		numcase = cin.nextInt();
		for(int i = 1;i <= numcase;++i){
			BigInteger color,pow8,pow4,pow2;
			color = cin.nextBigInteger();
			pow8 = color.pow(8);
			//System.out.println(pow8);
			pow4 = color.pow(4);
			BigInteger x = new BigInteger("17");
			pow4 = pow4.multiply(x);
			BigInteger y = new BigInteger("6");
			pow2 = color.pow(2);
			pow2 = pow2.multiply(y);
			BigInteger sum = new BigInteger("0");
			sum = sum.add(pow8);
			sum = sum.add(pow4);
			sum = sum.add(pow2);
			BigInteger z = new BigInteger("24");
			sum = sum.divide(z);
		//	System.out.println("sum = "+sum);
			BigInteger p = new BigInteger("10");
			p = p.pow(15);
			System.out.print("Case "+i+": ");
			if(sum.compareTo(p) < 0){
				System.out.println(sum);
			}
			else{
				BigInteger q = sum.mod(p);
				String ss = q.toString();
				int len = ss.length();
				if(len < 15){
					int xx = 15 - len;
					for(int j = 0; j < xx; ++j)
						System.out.print(0);
				}
				System.out.println(q);
			}
		}
	}
}

参考:http://blog.csdn.net/wmn_wmn/article/details/7823935


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }