#P12425. 【MX-X12-T7+】「ALFR Round 5」地铁(Hard Version)

【MX-X12-T7+】「ALFR Round 5」地铁(Hard Version)

题目背景

原题链接:https://oier.team/problems/X12H


本题与 Easy Version 的区别在于数据范围和时间限制不同,且本题需要输出构造方案。

题目描述

为了方便市民出行,缓解地面上的道路拥堵问题,S 市决定在地底下建一些地铁。

根据城市规划,S 市的地下网络将由 nn 条横向通道和 mm 条纵向通道构成。地铁站将设置在所有横向通道与纵向通道的交叉处,共 n×mn\times m 处。

地下网络的所有站点都需要被地铁线路覆盖,地铁线路之间可以有重叠部分。

每一条地铁线路都不应「绕路」。如果一条地铁线路,在从其中一个起点站开到终点站的过程中,存在两段列车朝相反方向行驶的平行道路,则我们称这条地铁线路是「绕路」的。

在下图所示的地下网络中,灰线代表地下通道(深灰色的格子为地铁站,即道路交叉处)。红、绿、蓝线所代表的地铁线路没有「绕路」,而黄、橙、紫线所代表的地铁线路「绕路」了。

此外,地铁线路网必须是连通的。也就是说,无论从哪个地铁站出发乘坐地铁,经过若干次换乘(可以不换乘),都一定可以到达其它所有地铁站。

因为盾构一条地铁线路的流程十分麻烦,S 市不想要建造太多的地铁线路。现在,你知道了 S 市的地下网络大小为 n×mn\times m,请你求出 S 市最少要建几条地铁线路,并给出一个方案。如果你求出的数不是最少需要的地铁线路数量,也可以获得一部分分数。具体评分标准请参照题目最后面。

输入格式

本题有多组测试数据,第一行输入一个整数 TT,表示数据组数。对于每组数据:

  • 仅一行,两个正整数 n,mn,m

输出格式

按顺序输出每组数据的答案。对于每组数据:

  • 第一行输出一个整数 ansans,表示 S 市最少需要建造的地铁线路数量。
  • 接下来输出 ansans 行,每一行输出三个正整数和一个非空字符串 x,y,l,sx,y,l,s,表示一条地铁线路。其中,x,yx,y 表示地铁的一端位于第 xx 行第 yy 列,ll 表示 ss 的长度(即该地铁线路有 l+1l+1 个站点),ssUDLR 中的两个互相垂直的方向组成,表示这条地铁线路从起点(第 xx 行第 yy 列)开始到终点的过程中,每经过一个路口后要去往哪个方向。
2
5 7
9 8
4
1 1 10 RRRDDDDRRR
5 7 10 UULLLLLLUU
5 1 10 URUURRRURR
1 7 10 DLDDLLLDLL
6
1 1 15 RRRDDRRRDDDDRDD
1 1 14 DDRRDDRRRDDDRD
5 1 11 RDDDRRRDRRR
7 1 12 RRURUURRUURR
9 1 15 RRRUURURRRUUUUU
9 1 15 UUUUURUURRRURRR

提示

【样例解释】

第一组数据的构造方案如下图。要覆盖所有深灰色的交叉路口,至少需要四条地铁线路。

第二组数据的构造方案如下图。要覆盖所有深灰色的交叉路口,至少需要六条地铁线路。

【数据范围】

具体评分标准请参照题目最后面。

对于 100%100\% 的数据,1T101\le T\le101n,m1031\le n,m\le10^3nm>1nm>1

子任务 测试点个数 总分 特殊性质
11 55 1010 n,m10n,m\le10
22 55 mn2m\ge n^2
33 1515 n=mn=m
44 66 3030 n10n\le10
55 1010 4040

其中 Subtask 5 保证第 k(k[1,10])k(k\in[1,10]) 个测试点满足 max(nm,mn)[arrk1,arrk)\max(\frac n m,\frac m n)\in[arr_{k-1},arr_{k})arrarr 的值如下:

xx 00 11 22 33 44 55 66 77 88 99 1010
arrxarr_x 11 1110\frac{11}{10} 65\frac{6}{5} 43\frac{4}{3} 32\frac{3}{2} 53\frac{5}{3} 22 33 55 1010 10001000

【评分标准】

每个子任务得分为该子任务各个测试点得分向下取整之和。每个测试点得分为该测试点每组测试数据得分的平均值。

每组测试数据评分标准如下:

  • 如果程序未按格式要求输出或输出不符合题意,将获得 0%0\% 的分数。一个测试点中,只要有一个测试数据因此获得 0%0\% 的分数,则整个测试点都不会得分。
    • 未按格式要求输出的例子:没有另外输出 ansans 行,ss 的长度不为 ll 等。
    • 输出不符合题意的例子:有地铁线路「绕路」或超出 n×mn\times m 的范围了,所有地铁线路并没有连通,有路口没有被任何线路经过等。
  • 否则,若程序在本测试数据输出了一个答案 ansans 并正确构造出了一个对应的方案,设 X=min(n,m)+1X=\min(n,m)+1AA 为该测试数据的正确答案,即最少需要的地铁线路数量,则将会获得 $\lfloor-\frac{100}{X-A}ans+\frac{100X}{X-A}\rfloor\%$ 的分数。除去下取整,这是一个经过 (A,100%)(A,100\%)(X,0%)(X,0\%) 的一次函数。