题解 | 附加题_牛客博客

解题思路

这是一个二阶魔方旋转问题。需要通过模拟旋转操作，找到最多5次旋转后能达到的最大优美度。

关键点：

记录每种旋转操作的位置变化
使用递归尝试所有可能的旋转组合
计算每个状态的优美度
需要考虑所有可能的旋转序列

算法步骤：

初始化6种基本旋转规则
递归尝试每种旋转操作
计算每次旋转后的优美度
返回最大可能的优美度值

代码

cpp
java
python

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

class Solution {
private:
    vector<vector<int>> record;
    
    void init_record() {
        record = {
            {0,2,6,12,16,18,20,22,4,5,11,10},
            {1,3,7,13,17,19,21,23,8,14,15,9},
            {4,5,6,7,8,9,23,22,0,2,3,1},
            {10,11,12,13,14,15,21,20,16,17,19,18},
            {0,1,9,15,19,18,10,4,20,22,23,21},
            {2,3,8,14,17,16,11,5,6,7,13,12}
        };
    }
    
    int calculate_beauty(vector<int>& cube) {
        return cube[0]*cube[1]*cube[2]*cube[3] +
               cube[4]*cube[5]*cube[10]*cube[11] +
               cube[6]*cube[7]*cube[12]*cube[13] +
               cube[8]*cube[9]*cube[14]*cube[15] +
               cube[16]*cube[17]*cube[18]*cube[19] +
               cube[20]*cube[21]*cube[22]*cube[23];
    }
    
    int turn(vector<int>& cube, int remain) {
        if (remain == 0) {
            return calculate_beauty(cube);
        }
        
        int result = INT_MIN;
        for (const auto& r : record) {
            vector<int> new_cube = cube;
            
            // 执行旋转操作
            int temp = new_cube[r[6]];
            for (int i = 4; i >= 0; i -= 2) {
                new_cube[r[i+2]] = new_cube[r[i]];
            }
            new_cube[r[0]] = temp;
            
            temp = new_cube[r[7]];
            for (int i = 5; i >= 1; i -= 2) {
                new_cube[r[i+2]] = new_cube[r[i]];
            }
            new_cube[r[1]] = temp;
            
            temp = new_cube[r[11]];
            for (int i = 10; i >= 8; i--) {
                new_cube[r[i+1]] = new_cube[r[i]];
            }
            new_cube[r[8]] = temp;
            
            result = max(result, turn(new_cube, remain - 1));
        }
        
        return max(calculate_beauty(cube), result);
    }
    
public:
    int solve(vector<int>& cube) {
        init_record();
        return turn(cube, 5);
    }
};

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<int> cube;
    int num;
    while (ss >> num) {
        cube.push_back(num);
    }
    
    Solution solution;
    cout << solution.solve(cube) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private List<int[]> record;
        
        public Solution() {
            record = new ArrayList<>();
            // 初始化6种旋转规则
            record.add(new int[] {0,2,6,12,16,18,20,22,4,5,11,10});
            record.add(new int[] {1,3,7,13,17,19,21,23,8,14,15,9});
            record.add(new int[] {4,5,6,7,8,9,23,22,0,2,3,1});
            record.add(new int[] {10,11,12,13,14,15,21,20,16,17,19,18});
            record.add(new int[] {0,1,9,15,19,18,10,4,20,22,23,21});
            record.add(new int[] {2,3,8,14,17,16,11,5,6,7,13,12});
        }
        
        public int solve(int[] cube) {
            return turn(cube, 5);
        }
        
        private int turn(int[] cube, int remain) {
            // 达到最大旋转次数，返回当前优美度
            if (remain == 0) {
                return calculateBeauty(cube);
            }
            
            int result = Integer.MIN_VALUE;
            // 尝试每种旋转操作
            for (int[] r : record) {
                int[] newCube = cube.clone();
                
                // 执行旋转操作
                int temp = newCube[r[6]];
                for (int i = 4; i >= 0; i -= 2) {
                    newCube[r[i+2]] = newCube[r[i]];
                }
                newCube[r[0]] = temp;
                
                temp = newCube[r[7]];
                for (int i = 5; i >= 1; i -= 2) {
                    newCube[r[i+2]] = newCube[r[i]];
                }
                newCube[r[1]] = temp;
                
                temp = newCube[r[11]];
                for (int i = 10; i >= 8; i--) {
                    newCube[r[i+1]] = newCube[r[i]];
                }
                newCube[r[8]] = temp;
                
                result = Math.max(result, turn(newCube, remain - 1));
            }
            
            return Math.max(calculateBeauty(cube), result);
        }
        
        private int calculateBeauty(int[] cube) {
            return cube[0]*cube[1]*cube[2]*cube[3] +
                   cube[4]*cube[5]*cube[10]*cube[11] +
                   cube[6]*cube[7]*cube[12]*cube[13] +
                   cube[8]*cube[9]*cube[14]*cube[15] +
                   cube[16]*cube[17]*cube[18]*cube[19] +
                   cube[20]*cube[21]*cube[22]*cube[23];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] inputs = sc.nextLine().split(" ");
        int[] cube = new int[inputs.length];
        for (int i = 0; i < inputs.length; i++) {
            cube[i] = Integer.parseInt(inputs[i]);
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(cube));
        sc.close();
    }
}

class Solution:
    def __init__(self):
        # 初始化6种旋转规则
        self.record = [
            [0,2,6,12,16,18,20,22,4,5,11,10],
            [1,3,7,13,17,19,21,23,8,14,15,9],
            [4,5,6,7,8,9,23,22,0,2,3,1],
            [10,11,12,13,14,15,21,20,16,17,19,18],
            [0,1,9,15,19,18,10,4,20,22,23,21],
            [2,3,8,14,17,16,11,5,6,7,13,12]
        ]
    
    def calculate_beauty(self, cube):
        return (cube[0]*cube[1]*cube[2]*cube[3] +
                cube[4]*cube[5]*cube[10]*cube[11] +
                cube[6]*cube[7]*cube[12]*cube[13] +
                cube[8]*cube[9]*cube[14]*cube[15] +
                cube[16]*cube[17]*cube[18]*cube[19] +
                cube[20]*cube[21]*cube[22]*cube[23])
    
    def turn(self, cube, remain):
        if remain == 0:
            return self.calculate_beauty(cube)
        
        result = float('-inf')
        for r in self.record:
            new_cube = cube.copy()
            
            # 执行旋转操作
            temp = new_cube[r[6]]
            for i in range(4, -1, -2):
                new_cube[r[i+2]] = new_cube[r[i]]
            new_cube[r[0]] = temp
            
            temp = new_cube[r[7]]
            for i in range(5, 0, -2):
                new_cube[r[i+2]] = new_cube[r[i]]
            new_cube[r[1]] = temp
            
            temp = new_cube[r[11]]
            for i in range(10, 7, -1):
                new_cube[r[i+1]] = new_cube[r[i]]
            new_cube[r[8]] = temp
            
            result = max(result, self.turn(new_cube, remain - 1))
        
        return max(self.calculate_beauty(cube), result)
    
    def solve(self, cube):
        return self.turn(cube, 5)

# 读取输入
cube = list(map(int, input().split()))
solution = Solution()
print(solution.solve(cube))

算法及复杂度

算法：递归 + 状态模拟
时间复杂度： $\mathcal{O(6^5)}$ ，每次可以选择6种旋转方式，最多旋转5次
空间复杂度： $\mathcal{O(5)}$ ，递归深度为5