

<center><h3>TDOG非专业级软件能力认证集训营模拟</h3></center>

<center><h3> CSP-S模拟 </h3> </center>

|   题目名称   | 石子合并  |  翻转游戏  | 优美的旋律 |  基站建设   |
| :----------: | :-------: | :--------: | :--------: | :---------: |
| 可执行文件名 | stone.cpp | carpet.cpp | melody.cpp | station.cpp |
|  输入文件名  | stone.in  | carpet.in  | melody.in  | station.in  |
|  输出文件名  | stone.out | carpet.out | melody.out | station.out |
|   时间限制   |    1s     |     3s     |     1s     |     6s      |
|   空间限制   |   512MB   |   512MB    |   512MB    |    512MB    |
|  测试点数目  |    20     |     10     |     10     |     20      |
|  测试点分值  |     5     |     10     |     10     |      5      |
|   题目类型   |  传统题   |   传统题   |   传统题   |   传统题    |
|   比较方式   | 全文比较  |  全文比较  |  全文比较  |  全文比较   |
| 是否有部分分 |    是     |     是     |     是     |     是      |



石子合并(stone)
===============

题目描述
--------

操场上有$N$堆石子排成一排，每次Kiana可以选择两堆相邻的石子进行合并，并在原地得到一堆新的石子，直到所有的石子都被合并为一堆。

Kiana的石子自然是与众不同的，具体而言，初始时每堆石子都有一个奇妙值，这个值可能是任意整数。在合并两堆石子后，得到的新石子堆的奇妙值为两堆石子的奇妙值之差。由于两个正整数作差不满足交换律，因此Kiana可以自由决定是由哪堆石子的奇妙值减去另一堆石子的奇妙值来得到结果。

现在Kiana想知道，将操场上所有石子合并为一堆后，能得到的最大的奇妙值是多少。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式
------------

### 输入格式

第一行包含一个正整数$T$，表示输入数据的组数。

接下来依次输入各组数据，每组数据第一行包含一个正整数$N$，表示操场上石子堆数。

每组数据第二行包含$N$个整数，其中第$i$个数$S_i$表示初始时第$i$堆石子的奇妙值。

### 输出格式

输出共一行，包含一个整数，表示将操场上所有石子合并为一堆后能得到的最大的奇妙值。

输入输出样例
------------

**输入样例#1：**

```
1
3
-1 0 2 
```

**输出样例#1：**

```
3
```

**输入样例#2：**

[stone2.in](https://tdog-homework.oss-cn-shenzhen.aliyuncs.com/oj/2021QZ_CSP/Day3/stone2.in)

**输出样例#2：**

[stone2.ans](https://tdog-homework.oss-cn-shenzhen.aliyuncs.com/oj/2021QZ_CSP/Day3/stone2.ans)

样例解释
--------

操场上有$3$堆石子，其奇妙值依次为$-1,0$和$2$。

Kiana首先将第$2$堆和第$3$堆石子合并，并用第$3$堆石子的奇妙值减去第$2$堆石子的奇妙值得到新石子堆奇妙值为$2$。然后将新石子堆和第$1$堆石子合并，并用前者奇妙值减去后者奇妙值得到最终的奇妙值为$3$，可以证明这是奇妙值最大的方案。

数据范围
--------

对于$20\%$的数据，保证$1\leq N\leq 200$。

对于$40\%$的数据，保证$1\leq N\leq 2000$。

对于$70\%$的数据，保证$1\leq N\leq 2\times 10^5$。

对于$100\%$的数据，保证$1\leq N\leq 2\times 10^6,1\leq T\leq 5,-1000\leq S_i\leq 1000$。







铺地毯(carpet)
==============

题目描述
--------

Kiana非常喜欢装潢，尤其是喜欢铺地毯，对于地毯她还有自己的讲究：铺一层地毯是不够的，要铺很多很多层才会松软，这样自己就可以放心大胆地在地毯上打滚了。

Kiana的房间可以看作一个长宽分别为$P$和$Q$的矩形，某一天Kiana买回了$n$块新的矩形地毯铺在房间的地上，使得每块地毯的边缘都和房间的边缘平行。Kiana认为一个区域足够松软，当且仅当该区域被至少$n-1$块地毯所覆盖。为了方便说明地毯的位置，Kiana在房间内建立了一个坐标系，坐标范围为$(0,0)$到$(P,Q)$，现在只需要给出每块地毯左下角和右上角的坐标就能唯一确定这块地毯的位置了。

现在Kiana想知道，自己房间里足够松软的区域总面积有多大。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式
------------

### 输入格式

第一行包含一个正整数$T$，表示输入数据的组数。

接下来依次输入各组数据，每组数据第一行包含三个正整数$P,Q$和$n$，分别表示Kiana房间的长宽与购买地毯的数量。

每组数据接下来$n$行，第$i$行包含四个整数$a_i,b_i,c_i$和$d_i$，表示第$i$块地毯左下角的坐标为$(a_i,b_i)$，右上角的坐标为$(c_i,d_i)$。

### 输出格式

输出共一行，包含一个正整数，表示Kiana房间里足够松软的区域的总面积。

输入输出样例
------------

**输入样例#1：**

```
1
5 5 5
0 0 5 5
0 0 4 4
1 1 5 5
0 0 3 3
2 2 5 5
```

**输出样例#1：**

```
7
```

**输入样例#2：**

[carpet2.in](https://tdog-homework.oss-cn-shenzhen.aliyuncs.com/oj/2021QZ_CSP/Day3/carpet2.in)

**输出样例#2：**

[carpet2.ans](https://tdog-homework.oss-cn-shenzhen.aliyuncs.com/oj/2021QZ_CSP/Day3/carpet2.ans)

样例解释
--------

下图按照输入顺序从下到上画出了Kiana房间内的所有地毯：

![](https://s3.bmp.ovh/imgs/2021/10/0b36d410c9c81b96.png)

其中黄色表示第$1$块地毯，浅红色表示第$2$块地毯，浅蓝色表示第$3$块地毯，浅紫色表示第$4$块地毯，浅绿色表示第$5$块地毯。阴影部分即为被至少$n-1$块地毯所覆盖的区域，可以看出其面积为$7$。

数据范围
--------

对于$20\%$的数据，保证$1\leq n\leq 1000$。

对于$50\%$的数据，保证$1\leq n\leq 30000$。

对于$100\%$的数据，保证$1\leq n\leq 3\times 10^5,1\leq P,Q\leq 10^9,1\leq T\leq 5$。

上面每一档数据中，各有一组数据保证不存在被$n$块地毯覆盖的区域，还有一组数据保证$P,Q\leq 10^4$。





优美的旋律(melody)
==================

题目描述
--------

旋律是音乐的首要要素，若干乐音经过艺术构思而形成的有组织、节奏的序列。Kiana最近也开始研究旋律，她认为一段旋律可以用一个字符串$S$来表示，其中不同的字母代表不同的音高。

不同的旋律有不同的美感，Kiana觉得一段优美的旋律是连续重复的数个音节，换句话说，如果一段旋律能够通过若干个连续音符重复至少两次得到，则称这段旋律是优美的，比如$abcdabcd$和$abababab$是优美的旋律，而$abcdefg$和$abababa$则不是优美的。

记某一段优美的旋律中，重复形成它的连续音符数为$x$、重复的次数为$y$，Kiana定义其优美度为$ax+by$，其中$a,b$是两个给定的常数。现在Kiana想知道，在一段给定的旋律中，优美度最高的子旋律优美度是多少。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式
------------

### 输入格式

第一行包含两个正整数$a$和$b$，表示计算优美度时的两个参数。

第二行包含一个字符串$S$，表示给定的旋律。

### 输出格式

输出共一行，包含一个正整数，表示给定的旋律中最高的子旋律优美度。

输入输出样例
------------

**输入样例#1：**

```
2 3
aaaababab
```

**输出样例#1：**

```
14
```

**输入样例#2：**

[melody2.in](https://tdog-homework.oss-cn-shenzhen.aliyuncs.com/oj/2021QZ_CSP/Day3/melody2.in)

**输出样例#2：**

[melody2.ans](https://tdog-homework.oss-cn-shenzhen.aliyuncs.com/oj/2021QZ_CSP/Day3/melody2.ans)

样例解释
--------

在输入输出样例1中，给定的旋律中共有$7$段优美的子旋律，其优美度分别计算如下：

-   $aa$：由音符$a$重复$2$次而得，优美度为$2\times 1+3\times 2=8$

-   $aaa$：由音符$a$重复$3$次而得，优美度为$2\times 1+3\times 3=11$

-   $aaaa$：由音符$a$重复$4$次而得，优美度为$2\times 1+3\times 4=14$

-   $aaaa$：由音符$aa$重复$2$次而得，优美度为$2\times 2+3\times 2=10$

-   $abab$：由音符$ab$重复$2$次而得，优美度为$2\times 2+3\times 2=10$

-   $ababab$：由音符$ab$重复$3$次而得，优美度为$2\times 2+3\times 3=13$

-   $baba$：由音符$ba$重复$2$次而得，优美度为$2\times 2+3\times 2=10$

综上所述，最高的子旋律优美度为$14$，此外需要注意的是，同一段旋律可能有不同的形成方式，也就可以有不同的优美度。

数据范围
--------

对于$20\%$的数据，保证$1\leq|S|\leq 10$。

对于$40\%$的数据，保证$1\leq|S|\leq 30$。

对于$60\%$的数据，保证$1\leq|S|\leq 300$。

对于$100\%$的数据，保证$1\leq|S|\leq 3000,1\leq a,b\leq 1000$，保证$S$中只含小写字母。





基站建设(station)
=================

题目描述
--------

为普及8G网络，Kiana决定在全国各地建立起8G基站来，此计划的第一步就是在某些已经侦测好的位置中选出几个地点来，建设测试基站以供实验。

Kiana的团队一共侦测了$n$个地点，其中第$i$个地点的可靠度为$R_i$，有$m$条光纤架在这些地点之间，每条光纤都将两个地点连接了起来，且光纤是双向的。测试基站是由$4$座信号塔一组构成的，信号塔只能建立在侦测好的地点上，且每个地点最多建立$1$座信号塔。

在这$4$座信号塔中，有$2$座信号塔为主信号塔，另外$2$座为副信号塔，为保证实验顺利进行，Kiana规定每组测试基站中的每座主信号塔必须与其它$3$座信号塔通过光纤直接相连，而每座副信号塔必须与该组基站中的主信号塔直接相连，但副信号塔之间不必有光纤连接（如果有的话，也不违反规定）。

经过计算，Kiana发现假设选择第$i,j$个地点建立主信号塔，第$p,q$个地点建立副信号塔，测试基站的总可靠度为主信号塔所在地可靠度加1后的乘积加上副信号塔所在地可靠度的乘积，即总可靠度$S=(R_i+1)\times (R_j+1)+R_p\times R_q$。

现在Kiana团队想建设一组测试基站，她想知道选取哪几个地点建立信号塔能使得测试基站的总可靠度最大。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式
------------

### 输入格式

第一行包含两个正整数$n$和$m$，分别表示Kiana团队侦测好的地点数量与这些地点之间架有的光纤数量。

第二行包含$n$个正整数，其中第$i$个数$R_i$表示第$i$个地点的可靠度。

接下来$m$行，每行包含两个正整数$u$和$v$，表示在第$u$个地点和第$v$个地点之间架有光纤，数据保证$u\neq v$，且两个地点之间至多架有一条光纤。数据还保证至少存在一种合法的基站建设方式，即Kiana团队总可以选出$4$个符合条件的地点建立信号塔。

### 输出格式

输出共一行，包含一个正整数，表示Kiana能建设起的基站的最大总可靠度。

输入输出样例
------------

**输入样例#1：**

```
4 6
3 5 7 9 
1 2
1 3
1 4
2 3
2 4
3 4
```

**输出样例#1：**

```
95
```

**输入样例#2：**

[station2.in](https://tdog-homework.oss-cn-shenzhen.aliyuncs.com/oj/2021QZ_CSP/Day3/station2.in)

**输出样例#2：**

[station2.ans](https://tdog-homework.oss-cn-shenzhen.aliyuncs.com/oj/2021QZ_CSP/Day3/station2.ans)

样例解释
--------

Kiana团队共测绘了$4$个地点，其可靠度依次为$3,5,7,9$，这些地点之间一共架有$6$条光纤，其中任意两个地点之间都有光纤连接。Kiana团队有$6$种合法的基站建设方案：

-   选择第$1,2$个地点建立主信号塔，第$3,4$个地点建立副信号塔，这种方案的总可靠度为$(3+1)\times (5+1)+7\times 9=87$

-   选择第$1,3$个地点建立主信号塔，第$2,4$个地点建立副信号塔，这种方案的总可靠度为$(3+1)\times (7+1)+5\times 9=77$

-   选择第$1,4$个地点建立主信号塔，第$2,3$个地点建立副信号塔，这种方案的总可靠度为$(3+1)\times (9+1)+5\times 7=75$

-   选择第$2,3$个地点建立主信号塔，第$1,4$个地点建立副信号塔，这种方案的总可靠度为$(5+1)\times (7+1)+3\times 9=75$

-   选择第$2,4$个地点建立主信号塔，第$1,3$个地点建立副信号塔，这种方案的总可靠度为$(5+1)\times (9+1)+3\times 7=81$

-   选择第$3,4$个地点建立主信号塔，第$1,2$个地点建立副信号塔，这种方案的总可靠度为$(7+1)\times (9+1)+3\times 5=95$

所以Kiana团队选择最后一种建设方案，此时总可靠度最大为$95$。

数据范围
--------

对于$10\%$的数据，保证$1\leq n\leq 50,1\leq m\leq 25$。

对于$20\%$的数据，保证$1\leq n\leq 50,1\leq m\leq 200$。

对于$30\%$的数据，保证$1\leq n\leq 500,1\leq m\leq 250$。

对于$40\%$的数据，保证$1\leq n\leq 500,1\leq m\leq 2000$。

对于$60\%$的数据，保证$1\leq n\leq 50000,1\leq m\leq 25000$。

对于$100\%$的数据，保证$1\leq n\leq 50000,1\leq m\leq 2\times 10^5,1\leq R_i\leq 10^4$。

有六组数据满足每一个被光纤连接起来构成的连通块内，任意两个地点之间都有光纤连接。
