## 25年程设期末

------

#### 1. 日志压缩

**题目描述**
服务器的日志文件中存储了一连串重复字符. 为了节省空间, 采用一种简单的压缩格式对其进行压缩. 压缩格式为: `[字符][重复次数]`. 如果重复次数为 `1`, 则不显示重复次数. 
例如: `EEEerr` 压缩为 `E3er2`. 
请编写程序, 压缩一个字符串. 注意区分大小写. 

**输入描述**
一行, 一个字符串 (长度不超过 100, 仅包含大小写英文字母) . 

**输出描述**
一行, 表示压缩后的字符串. 

**样例输入**

```
aabcccccaaa
```

**样例输出**

```
a2bc5a3
```

------

#### 2. 逻辑小岛

**题目描述**
在逻辑岛上住着 $N$ ($N \le 10$) 个人, 编号为 ($1 \sim N$). 每个人是如下两种类型之一:

- **诚实者**: 永远说真话;
- **说谎者**: 永远说假话.

某一天, 他们排成一排, 每个人各说了一句话. 每句话都只讨论部分人, 形式如下: “在我提到的这些人 (允许包括自己) 中, 说真话的人 **至少/至多/恰好** 有 (k) 个.”

你的任务是判断: 根据所有人的发言, 是否能够确定每个人究竟是在说真话还是在说假话. 你需要输出: 

- 若**不存在任何一种真假话情况**能让所有人的发言成立, 输出 `Impossible`;
- 若**存在多种可能情况**都能符合条件, 输出 `Ambiguous`;
- 若**恰好只有一种符合条件的情况**, 则输出一个长度为 $N$ 的字符串表示结果:
  - 如果第 `i` 个字符为 `T` 表示第 (i) 个人说真话;
  - 如果第 `i` 个字符为 `L` 表示第 (i) 个人说假话.
    示例: `LTTT` 表示 1 号说假话、2/3/4 号说真话.

**输入描述**
输入从标准输入读取. 每组测试数据包含多个测试用例.

- 第一行包含一个正整数 $T$ ($T \le 10$), 表示测试用例个数.

- 第二行包含一个正整数 $N$ ($N \le 10$), 表示岛上的人数 (后续每个测试用例中岛上均有 $N$ 人)

- 随后给出 $T$ 个测试用例. 每个测试用例包含 $N$ 行描述, 第 $i$ 行表示第 $i$ 个人的发言, 格式为:

  ```
  op k m x1 x2 ... xm
  ```

  各字段含义:

  - `op`为一个字符, 表示比较类型, 只可能为`g`, `l`, `e`三类之一: 
    - `g` 表示“至少” (大于等于);
    - `l` 表示“至多” (小于等于);
    - `e` 表示“恰好” (等于).
  - `k`为一个整数, 表示比较值; `m`为一个整数, 表示提到的人的数量. 保证 $0\le k \le m \le N$
  - `x1..xm`为 $m$ 个整数, 表示被提到的人的编号 (互不重复), 且 $1 \le x_j \le N$.
    例如: `g 2 3 1 3 5` 表示: 在 $1、3、5$ 号中, 至少有 $2$ 个人在说真话. 

**输出描述**
共输出 $T$ 行, 每行一个字符串, 对应该测试用例的答案: `Impossible` / `Ambiguous` / 或唯一确定的 `T/L` 串. 

**样例输入**

```
3
3
g 2 2 1 2
e 0 2 1 2
g 1 1 2
e l 1 1
g 0 2 2 3
g 3 3 1 2 3
l 0 3 1 2 3
l 2 3 1 2 3
e 0 2 2 3
```

**样例输出**

```
Impossible
Ambiguous
LTL
```

**数据范围**

- $T \le 10$, $N \le 10$

------

#### 3. 汉语拼音

**题目描述**
在中文学习中, 汉语拼音是记录汉字读音的一种规范方式, 通常由**声母、韵母、声调**组成. 
本题要求对给定**文本文件**中的拼音进行分析, 统计各**声母及各声调**出现的个数. 

注意: 

- 所有数据从文本文件 `input.txt` 中读入, 输出到文本文件 `output.txt`; 
- 声母表等拼音知识详见注释部分.

**输入描述**
一个文本文件`input.txt` 中包含多行英文标点和拼音文本 (每行以换行符结束) . 至少有一个拼音. 拼音的格式: 

- 一般为: `声母 + 韵母 + 声调数字`; 
- “**零声母拼音**”没有声母部分; 
- “**轻声拼音**”没有声调数字部分; 
- 非轻声拼音的声调数字限定为 `1/2/3/4` (分别表示一声到四声) ; 
- 拼音之间可能由一个或多个**空白符** (空格、制表符、换行符) 或一个或多个**英文标点**分隔; 标点可能紧挨拼音, 也可能与拼音间有空白. 

**输出描述**
`output.txt` 包含两行文本 (两行均以换行符结束) : 

1. 第一行: 按“标准声母表顺序”输出声母 (统一小写) 及其出现次数 (用一个空格分隔) , **仅输出次数大于 0 的声母**. 
2. 第二行: 5 个整数, 分别为**声调 1-4** 和 **轻声** 的出现次数 (用空格分隔) . 

**样例输入** (`input.txt`) 

```
a,biAnl yi4 Shi2 chul xiaN4 cuo4 wu4 !
ginG3 Tiao2 shi4 Yi2 xia4 ou.
```

**样例输出** (`output.txt`) 

```
blt1g1x2ch1sh2cly2w1
2 3 1 6 2
```

**注释**

1. 输出样例解释

   第二行含义表示: 一声 2 个, 二声 3 个, 三声 1 个, 四声 6 个, 轻声 2 个. 

2. 所有无声母拼音如下 : 

   ```
   a o e ai ei ao ou er an en ang eng
   ```

3. 汉语拼音共有 23 个声母, 标准声母表如下: 

   ```cpp
   vector<string> initials = {
   	"b", "p", "m", "f",
     "d", "t", "n", "l",
     "g", "k", "h",
     "j", "q", "x",
     "zh", "ch", "sh",
     "r", "z", "c", "s",
     "y", "w"
   }
   ```

------

#### 4. 面板修复

**题目描述**
一块老旧显示面板可抽象为大小为 $H \times W$ 的单色网格: 

- 亮起像素用 `.` 表示, 允许信号通过; 
- 熄灭像素用 `#` 表示, 会阻断信号. 

信号从左上角 ((1,1)) 注入, 只能向右或向下传播, 目标到达右下角 ((H,W)). 
工程师可以进行“单点翻转”: 选择任意像素, 将其状态翻转 (亮↔暗) , 每次成本为 1. 要求: 信号经过的路径上 (含起点终点) 所有像素最终都必须为 `.`. 若某个路径像素原本是 `#`, 则必须付出成本翻转. 
请计算使信号从起点到终点的**最少翻转次数**. 

**输入描述**

- 第一行两个整数 (H, W). 
- 接下来 (H) 行, 每行 (W) 个字符 (`.` 或 `#`) , 表示面板初始状态. 

**输出描述**
输出一行, 一个整数, 表示最少翻转次数. 

**样例输入**

> 你提供的样例区域出现了明显乱码 (看不到 `.` / `#` 网格) , 这里保留“样例输入 1/2”的结构占位, 便于你后续替换成清晰版本: 

```
样例输入 1
3 3
.##
.##
##.

样例输入 2
2 2
#.
.#

样例输入 3
4 4
..##
#...
###.
###.

样例输入 4
5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.
```

------

#### 5. 能量捕捉

**题目描述**
未来将有 $N$个高能粒子波束出现. 每个波束有: 抵达时刻 $S$、消散时刻 $E$、能量值 $V$. 
能量捕捉器同一时刻只能捕捉一个波束. 若要捕捉某波束, 必须在其抵达时刻 $S$ 开始捕捉, 并在时间区间 $[S, E)$ 内无法捕捉其他波束; 在 $E$ 时刻捕捉结束并获得能量 $V$, 此时可立即开始捕捉其他波束 (允许下一个波束的 $S$ 恰好等于当前的 $E$) . 
请从 $N$ 个波束中选择一组进行捕捉, 使总能量最大. 

**输入描述**

- 第一行一个整数 $N$. 
- 接下来 $N$ 行, 每行三个整数 `S E V`, 满足: 
  $1 \le S < E \le 10^6,\quad 1 \le V \le 10^4$
- 数据范围: 
  - 对于 60% 的测试数据, ($N \le 1000$)
  - 对于 100% 的测试数据, ($N \le 10^5$)
  - 其中 $20\%$: 所有时间区间均不重叠; 另 $20\%$: 所有能量值均为 1. 

**输出描述**
输出一个整数, 表示能够捕捉到的最大总能量值. 

**样例输入**

```
4
1 3 50
2 4 10
3 5 60
1 5 90
```

**样例输出**

```
110
```