题目分析

题意简述

科学家发现一种古老装置，其键盘有 $26$ 个标有 $'A'$ 到 $'Z'$ 的按键，每个按键有一个$LED$，初始时全灭。在离散时间步中，若某时刻无LED亮则磁带无输出，若有 $i$ 个$LED$亮则输出英文字母表第 $i$ 个字母。输入包含多个测试用例，每个测试用例中先给出按键操作次数 $n$，然后每行包含一个按键字母和该按键首次与再次按下的时间步 $a$ 和 $b$（$0 \leq a < b \leq 1000$），按键在区间 $a, a + 1, \dots, b -1$ 内$LED$亮，且每个测试用例中字母不同。要求编写程序模拟该装置并输出磁带上的输出字符串。

输入

• 多组测试用例，每组先给出测试用例数量 $t$。
• 每个测试用例中，先给出按键操作次数 $n$（$0 \leq n \leq 26$），然后每行包含一个大写字母（按键）和两个整数 $a$ 和 $b$（$0 \leq a < b \leq 1000$）。

输出

每个测试用例输出一行，包含写在磁带上的输出字符串。

解题思路

记录按键状态变化

使用一个长度为 $1000$ 的数组 $output$ 来记录每个时间步亮着的$LED$数量。对于每个按键操作，在其对应的时间步区间内增加 $output$ 数组中相应位置的值。

生成输出字符串

遍历 $output$数组，对于每个非零值的位置，将其值加上 $64$ 后转换为对应的大写字母输出，从而得到磁带上的输出字符串。

代码实现

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        char ch;
        int beg, end;
        vector<int> output(1000, 0);
        while (n--)
        {
            cin >> ch >> beg >> end;
            for (int j = beg; j < end; j++)
                ++output[j];
        }
        for (int k = 0; k < end; k++)
            if (output[k]!= 0)
                cout << (char)(output[k] + 64);
        cout << endl;
    }
    return 0;
}

代码说明

1. 输入处理
   • 首先读取测试用例数量 $t$。
   • 对于每个测试用例，读取按键操作次数 $n$。
   • 然后依次读取每个按键操作的字母 $ch$ 以及首次按下时间步 $beg$ 和再次按下时间步 $end$。
2. 记录按键状态变化
   • 使用 $vector<int> output(1000, 0)$ 初始化一个长度为 $1000$ 的数组，用于记录每个时间步亮着的LED数量，初始值都为 $0$。
   • 通过 $for (int j = beg; j < end; j++) ++output[j];$来更新 $output$ 数组中对应时间步的LED亮着的数量。
3. 生成输出字符串
   • 遍历 $output$ 数组，对于每个非零值的位置 $k$，通过 $cout << (char)(output[k] + 64);$ 将其值加上 $64$ 后转换为对应的大写字母输出。
   • 每个测试用例输出完毕后换行。

题目来源

Tehran 2005