专栏文章

题解：B3761 [信息与未来 2021] 三角魔方

FForever_Rain
B3761题解参与者 9已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@mioslegq
此快照首次捕获于
2025/12/03 00:28
3 个月前
此快照最后确认于
2025/12/03 00:28
3 个月前
查看原文

题目分析

一眼模拟。
我一开始的思路：
用二维数组存储状态。
CPP
char c[5][9]={"        "," A      "," BCD    "," EFGHI  "," JKLMNOP"},o[5][9];// 状态存储，c[1][1]到c[4][7]分别对应魔方的各个位置
定义旋转操作。
CPP
void R3(){
    char t=c[2][3];// 保存最后一个字符
    for(int i=3;i>=2;i--)c[2][i]=c[2][i-1];// 后移
    c[2][1]=t;// 将最后一个字符放到第一个
}
void R5(){
    char t=c[3][5];
    for(int i=5;i>=2;i--)c[3][i]=c[3][i-1];
    c[3][1]=t;
}
void R7(){
    char t=c[4][7];
    for(int i=7;i>=2;i--)c[4][i]=c[4][i-1];
    c[4][1]=t;
}
void U3(){
    char t=c[3][1];
    c[3][1]=c[4][2];
    c[4][2]=c[4][3];
    c[4][3]=t;
}
void U5(){
    char t=c[2][1];
    c[2][1]=c[3][2];
    c[3][2]=c[3][3];
    c[3][3]=c[4][4];
    c[4][4]=c[4][5];
    c[4][5]=t;
}
void U7(){
    char t=c[1][1];
    c[1][1]=c[2][2];
    c[2][2]=c[2][3];
    c[2][3]=c[3][4];
    c[3][4]=c[3][5];
    c[3][5]=c[4][6];
    c[4][6]=c[4][7];
    c[4][7]=t;
}
void D3(){
    char t=c[4][5];
    c[4][5]=c[4][6];
    c[4][6]=c[3][5];
    c[3][5]=t;
}
void D5(){
    char t=c[4][3];
    c[4][3]=c[4][4];
    c[4][4]=c[3][3];
    c[3][3]=c[3][4];
    c[3][4]=c[2][3];
    c[2][3]=t;
}
void D7(){
    char t=c[4][1];
    c[4][1]=c[4][2];
    c[4][2]=c[3][1];
    c[3][1]=c[3][2];
    c[3][2]=c[2][1];
    c[2][1]=c[2][2];
    c[2][2]=c[1][1];
    c[1][1]=t;
}
然后把主函数接进去就写完了。第一版代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
char c[5][9]={"        "," A      "," BCD    "," EFGHI  "," JKLMNOP"},o[5][9];
void R3(){
    char t=c[2][3];
    for(int i=3;i>=2;i--)c[2][i]=c[2][i-1];
    c[2][1]=t;
}
void R5(){
    char t=c[3][5];
    for(int i=5;i>=2;i--)c[3][i]=c[3][i-1];
    c[3][1]=t;
}
void R7(){
    char t=c[4][7];
    for(int i=7;i>=2;i--)c[4][i]=c[4][i-1];
    c[4][1]=t;
}
void U3(){
    char t=c[3][1];
    c[3][1]=c[4][2];
    c[4][2]=c[4][3];
    c[4][3]=t;
}
void U5(){
    char t=c[2][1];
    c[2][1]=c[3][2];
    c[3][2]=c[3][3];
    c[3][3]=c[4][4];
    c[4][4]=c[4][5];
    c[4][5]=t;
}
void U7(){
    char t=c[1][1];
    c[1][1]=c[2][2];
    c[2][2]=c[2][3];
    c[2][3]=c[3][4];
    c[3][4]=c[3][5];
    c[3][5]=c[4][6];
    c[4][6]=c[4][7];
    c[4][7]=t;
}
void D3(){
    char t=c[4][5];
    c[4][5]=c[4][6];
    c[4][6]=c[3][5];
    c[3][5]=t;
}
void D5(){
    char t=c[4][3];
    c[4][3]=c[4][4];
    c[4][4]=c[3][3];
    c[3][3]=c[3][4];
    c[3][4]=c[2][3];
    c[2][3]=t;
}
void D7(){
    char t=c[4][1];
    c[4][1]=c[4][2];
    c[4][2]=c[3][1];
    c[3][1]=c[3][2];
    c[3][2]=c[2][1];
    c[2][1]=c[2][2];
    c[2][2]=c[1][1];
    c[1][1]=t;
}
int main(){
    string s;
    int a,b;
    cin>>s>>a>>b;
    memcpy(o,c,sizeof(c));
    for(int k=0;k<pow(a,b);k++){
        for(int i=0;i<s.size();i+=2){
            string p;
            p+=s[i];
            p+=s[i+1];
            if(p=="R3")R3();
            if(p=="R5")R5();
            if(p=="R7")R7();
            if(p=="U3")U3();
            if(p=="U5")U5();
            if(p=="U7")U7();
            if(p=="D3")D3();
            if(p=="D5")D5();
            if(p=="D7")D7();
        }
    }
    for(int i=1;i<=4;i++)for(int j=1;j<=2*i-1;j++)cout<<c[i][j];
    return 0;
}
然后就 TLE 了 44 个点。
再看一眼数据范围：
对于 50%50\% 的数据，b=1b=1。
对于 100%100\% 的数据，1≤a,b≤1031\leq a,b\leq 10^3。操作序列中“旋转” 操作的数量不超过 100100。
怎么这么大， 还是需要优化一下。

解法思路

在玩了一个小时魔方之后， 发现如果你一直重复一个操作，魔方总会回到初始状态（例如三阶魔方需要“上左下右”66 次）。所以我们充分发扬人类智慧，知道了需要找到操作序列的周期。
  1. 首先需要记录周期 mm。
这部分用于模拟操作和比较周期。
CPP
bool d(string s){
    for(int i=0;i<s.size();i+=2){
        string p; 
        p+=s[i]; 
        p+=s[i+1];
        if(p=="R3")R3();
        if(p=="R5")R5();
        if(p=="R7")R7();
        if(p=="U3")U3();
        if(p=="U5")U5();
        if(p=="U7")U7();
        if(p=="D3")D3();
        if(p=="D5")D5();
        if(p=="D7")D7();
    }
    return !memcmp(c,o,sizeof(c));// 比较状态
}
找周期。
CPP
for(int i=0;!f||i<a;i++,m++)if(d(s))break;
// PS.这部分是在主函数中的，所以目前不是很通顺
  1. 只需模拟 aa 的 bb 次幂对 mm 取余次操作，写一个快速幂就可以了。
  2. 针对每种旋转操作编写对应的字母循环移动函数。
这部分直接接入前文定义的操作函数。

完整代码

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

// 状态存储，c[1][1]到c[4][7]分别对应魔方的各个位置
char c[5][9]={"        "," A      "," BCD    "," EFGHI  "," JKLMNOP"},o[5][9];

// 定义旋转操作
void R3(){
    char t=c[2][3];// 保存最后一个字符
    for(int i=3;i>=2;i--)c[2][i]=c[2][i-1];// 后移
    c[2][1]=t;// 将最后一个字符放到第一个
}
void R5(){
    char t=c[3][5];
    for(int i=5;i>=2;i--)c[3][i]=c[3][i-1];
    c[3][1]=t;
}
void R7(){
    char t=c[4][7];
    for(int i=7;i>=2;i--)c[4][i]=c[4][i-1];
    c[4][1]=t;
}
void U3(){
    char t=c[3][1];
    c[3][1]=c[4][2];
    c[4][2]=c[4][3];
    c[4][3]=t;
}
void U5(){
    char t=c[2][1];
    c[2][1]=c[3][2];
    c[3][2]=c[3][3];
    c[3][3]=c[4][4];
    c[4][4]=c[4][5];
    c[4][5]=t;
}
void U7(){
    char t=c[1][1];
    c[1][1]=c[2][2];
    c[2][2]=c[2][3];
    c[2][3]=c[3][4];
    c[3][4]=c[3][5];
    c[3][5]=c[4][6];
    c[4][6]=c[4][7];
    c[4][7]=t;
}
void D3(){
    char t=c[4][5];
    c[4][5]=c[4][6];
    c[4][6]=c[3][5];
    c[3][5]=t;
}
void D5(){
    char t=c[4][3];
    c[4][3]=c[4][4];
    c[4][4]=c[3][3];
    c[3][3]=c[3][4];
    c[3][4]=c[2][3];
    c[2][3]=t;
}
void D7(){
    char t=c[4][1];
    c[4][1]=c[4][2];
    c[4][2]=c[3][1];
    c[3][1]=c[3][2];
    c[3][2]=c[2][1];
    c[2][1]=c[2][2];
    c[2][2]=c[1][1];
    c[1][1]=t;
}

// 快速幂计算a^b mod p
int ksm(int a,int b,int p){
    long long s=1;
    while(b){
        if(b%2)s=s*a%p;
        a=a*a%p;
        b/=2;
    }
    return s;
}

// 执行操作、检查状态
bool d(string s){
    for(int i=0;i<s.size();i+=2){
        string p; 
        p+=s[i]; 
        p+=s[i+1];
        if(p=="R3")R3();
        if(p=="R5")R5();
        if(p=="R7")R7();
        if(p=="U3")U3();
        if(p=="U5")U5();
        if(p=="U7")U7();
        if(p=="D3")D3();
        if(p=="D5")D5();
        if(p=="D7")D7();
    }
    return !memcmp(c,o,sizeof(c));// 比较状态
}

int main(){
    int a,b,t,m=1;
    string s;
    cin>>s>>a>>b;
    t=a;
    memcpy(o,c,sizeof(c));// 保存状态
    bool f=1;
    int tt=a;
    a=1;
    int l=0;
    for(int i=0;i<b;i++){// 检查溢出
        a*=t;
        if(a<l){
            f=0;
            break;
        }
        l=a;
    }
    for(int i=0;!f||i<a;i++,m++)if(d(s))break;// 找周期
    memcpy(c,o,sizeof(c));// 重置
    int k=ksm(tt,b,m);// 计算次数k = a^b mod m
    for(int i=0;i<k;i++)d(s); // 执行k次操作
    for(int i=1;i<=4;i++)for(int j=1;j<=2*i-1;j++)putchar(c[i][j]); //输出
    return 0;
}
成功 AC 了。

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...