侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【模拟, 数学】Excel地址【蓝桥杯】

GabrielxD
2022-09-26 / 0 评论 / 0 点赞 / 28 阅读 / 760 字 / 正在检测是否收录...

题目

试题 历届真题 Excel地址【第八届】【省赛】【C组】

3159. Excel地址


Excel 单元格的地址表示很有趣,它使用字母来表示列号。

比如,AA 表示第 11 列,BB 表示第 22 列,ZZ 表示第 2626 列,AAAA 表示第 2727 列,ABAB 表示第 2828 列,BABA 表示第 5353 列 …

当然 Excel 的最大列号是有限度的,所以转换起来不难。

如果我们想把这种表示法一般化,可以把很大的数字转换为很长的字母序列呢?

本题目既是要求对输入的数字,输出其对应的 Excel 地址表示方式。

输入格式

一个正整数。

输出格式

一个字母序列,表示输入数字对应的 Excel 地址表示方式。

数据范围

输入的整数范围 [1,2147483647][1,2147483647]

输入样例1:

26

输出样例1:

Z

输入样例2:

2054

输出样例2:

BZZ

解题

方法一:模拟(TLE)

思路

根据样例我们发现:低位每增加到 27 时就会进位,低位变为 1,高位进 1,例如:26->27==>Z->AA、52->53 ==> AZ->BA。
所以开一个大小合理的数组(arr)用来模拟进位,数组中数字 1261 \sim 26 表示 AZA \sim Z ,每次都往最低位上加1,然后从低位到高位依次判断需不需要进位。最后把数组反向从第一个部位 0 的位置输出对应字母即可。

代码

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); 
        int n = (int) in.nval;
        int[] arr = new int[10];
        for (int i = 1; i <= n; ++i) {
            ++arr[0];
            boolean carry = false;
            // 进位
            if (arr[0] == 27) {
                carry = true;
                arr[0] = 1;
                // 循环判断后面需不需要进位
                for (int j = 1; j < 10 && carry; ++j) {
                    ++arr[j];
                    if (arr[j] == 27) arr[j] = 1;
                    else carry = false;
                }
            }
        }
        for (int i = 9; i >= 0; --i) {
            if (arr[i] > 0) {
                System.out.print((char) (arr[i] - 1 + 'A'));
            }
        }
        System.out.println();
    }
}

时间复杂度:O(n)O(n)

方法二:进制转换

思路

上面的规律也可以理解成带有特殊规则的 1010 进制转 2626 进制,特殊的点在于:当要转换的数可以被 26 除尽时不这么做,而是保留一个 26 放到最低位用 ZZ 表示,其余的不变。

image-20220926172859178

代码

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); 
        int n = (int) in.nval;
        StringBuilder ans = new StringBuilder();
        while (n > 0) {
            if (n % 26 == 0) {
                // 特殊情况 在能除尽的情况下把 26 作为余数
                ans.insert(0, 'Z');
                n = n / 26 - 1; // 商减一作为下一轮被除数
            } else {
                // 正常情况 短除法做进制转换
                ans.insert(0, (char) (n % 26 - 1 + 'A'));
                n /= 26;
            }
        }
        System.out.println(ans);
    }
}

0

评论区