BestCoder-Machine（三进制-彩灯变换）

ゞ浴缸里的玫瑰 2022-08-21 07:45 171阅读 0赞

# Machine #

Accepts: 580

Submissions: 1890

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

有一个机器，它有 m(2≤m≤30)m (2\leq m\leq 30)m(2≤m≤30) 个彩灯和一个按钮。每按下按钮时，最右边的彩灯会发生一次变换。变换为：
    
    1. 如果当前状态为红色，它将变成绿色；
    
    2.如果当前状态为绿色，它将变成蓝色；
    
    3.如果当前状态为蓝色，它将变成红色，并且它左边的彩灯（如果存在）也会发生一次变换。
    
    初始状态下所有的灯都是红色的。
    询问按下按钮 n(1≤n<263)n (1\leq n< {2}^{63})n(1≤n<263) 次以后各个彩灯的颜色。

输入描述

输入包含多组数据. 第一行有一个整数T(1≤T≤15)T (1\leq T\leq 15)T(1≤T≤15), 表示测试数据的组数. 对于每组数据:
    唯一的一行包含2个整数 m(2≤m≤30)m (2\leq m\leq 30)m(2≤m≤30) 和 n(1≤n<263)n (1\leq n< {2}^{63})n(1≤n<263) 。

输出描述

对于每组数据，输出一个长度为mmm的字符串，表示从左到右mmm个彩灯的颜色。
    R代表红色；G代表绿色；B代表蓝色。

输入样例

2
    3 1
    2 3

输出样例

RRG
    GR
    
    解题思路：
    最后一位按照RGBRGBRGB……的顺序改变，按照题目意思： “3.如果当前状态为蓝色，它将变成红色，并且它左边的彩灯（如果存在）也会发生一次变换。”
    所以从最后一位向前，例如倒数第二位按照RRRGGGBBBRRRGGGBBB的顺序改变，即原问题就转化为求nn的三进制表示的最低的mm位。
     
    
     /*
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院
    * All rights reserved.
    * 文件名称：3.cpp
    * 作    者：单昕昕
    * 完成日期：2016年4月22日
    * 版 本 号：v1.0
    */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    char p[3]= {'R','G','B'};
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            long long m,n,a[32];
            cin>>m>>n;
            int i;
            for(i=m; i>=1; --i)
            {
                a[i]=n%3;
                n/=3;
            }
            for(i=1; i<=m; i++)
                cout<<p[a[i]];
            cout<<endl;
        }
        return 0;
    }