#P3519. [Zjoi2014]消棋子

    ID: 2730 传统题 2000ms 256MiB 尝试: 353 已通过: 137 难度: 7 上传者: 标签>难度分类提高+/省选-数据结构有序集合贪心交换论证模拟与实现技巧增量维护队列直接模拟CF2300

[Zjoi2014]消棋子

[ZJOI2014] 消棋子

题目描述

棋盘有 rr 行、cc 列,行和列都从 11 开始编号。棋盘上的格子为空,或放有一枚棋子。每种颜色恰有两枚棋子。

一次操作选择一个空格子及上、下、左、右四个方向中的两个不同方向。从该空格沿各选定方向前进,如果两个方向上都能遇到棋子,且最先遇到的两枚棋子颜色相同,就将这两枚棋子从棋盘上拿走。否则操作无效,棋盘保持原样。

先按顺序执行给出的一串操作,统计成功消去的同色棋子对数。然后将棋盘恢复到初始状态,给出一套能消去最多棋子对的合法操作。

输入格式

第一行有两个整数 r,cr,c。第二行有一个整数 nn,表示颜色数。

接下来 nn 行,第 ii 行有四个整数 ai,bi,ci,dia_i,b_i,c_i,d_i,表示颜色 ii 的棋子位于 (ai,bi)(a_i,b_i) 和 (ci,di)(c_i,d_i)。

接下来一行有一个整数 mm,表示给出的操作数。再接下来 mm 行,每行含两个整数 x,yx,y 和两个方向字母,分别表示所选格子的行、列和两个方向。字母 U、D、L、R 分别表示上、下、左、右。

输出格式

第一行一个整数,表示给出的操作成功消去的同色棋子对数。

第二行一个整数 kk,表示你给出的最优方案的操作数。接下来 kk 行,每行输出空格分隔的行号、列号和两个方向字母,格式与输入操作相同。方案中的操作按顺序从初始棋盘执行。

样例 #1

4 4
4
1 1 1 4
1 2 3 4
1 3 3 2
4 1 2 3
6
2 3 U R
2 1 D R
2 2 L R
2 4 L D
3 1 L R
3 3 L U
2
4
4 3 L U
3 3 L U
3 2 R U
1 2 L R

给出的操作在第 22 次和第 66 次各消去一对棋子。样例方案可消去全部四对棋子。

数据范围

1≤r,c,n,m≤1051\le r,c,n,m\le10^5,0≤k≤1060\le k\le10^6。

原赛数据比例 附加条件
10%10\% r,c,n,m≤10r,c,n,m\le10
20%20\% r,c,n,m≤100r,c,n,m\le100
40%40\% n,m≤100n,m\le100
50%50\% n,m≤1000n,m\le1000
60%60\% n≤1000n\le1000
另有 10%10\% c=1c=1