[COTS 2024] 分割 Segregacija
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目背景
译自 Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D2T2。。
请不要滥用本题评测。滥用本题评测将被封号。
题目描述
Pero 有一个 行 列的矩阵,每个格子里有一个红球或蓝球。
Pero 想要重排矩阵中的球,使得所有蓝球位于矩阵的左上侧,所有红球位于右下侧。更为具体地说,重排后,不能存在一个红球位于某个蓝球的上方或左侧。
为此,Pero 可以多次交换相邻的两个球。两个球是相邻的当且仅当它们所在的格子有公共边。 Pero 想知道达到目标所需的最少交换次数。
此外,Pero 会交换矩阵中的相邻两个球 次,并在每次变更后询问当前矩阵状态所需的最小交换次数。请帮助 Pero,输出初始矩阵下以及每次交换后所需的最小交换次数。
输入格式
第一行,两个整数 ,含义见题面。
接下来两行,每行一个长度为 的字符串,描述这个矩阵。其中 代表红球, 代表蓝球。
接下来 行,每行三个正整数 ,描述一次交换操作。
- 时,表示交换 ;
- 时,表示交换 。
保证交换的两个位置都在矩阵内。
输出格式
输出 行,分别表示初始矩阵的答案和每次修改后的答案。
5 2
CPCPC
PCCPC
1 1 4
1 1 2
3
4
5
5 0
CPPCC
PPCCP
4
10 7
CCPPPCCPCP
PPPCCCPCCC
1 2 7
2 1 4
2 1 8
1 1 9
2 1 1
1 2 7
1 1 4
8
9
10
10
9
8
7
8
提示
样例解释
样例 解释:对于初始状态,只需要依次交换 ,, 即可。
数据范围
对于 的数据,保证 ,。
子任务编号 | 分值 | 约束 |
---|---|---|
最多只有 个 | ||
无额外约束 |
20250225集训
- Status
- Done
- Rule
- IOI
- Problem
- 3
- Start at
- 2025-2-25 19:00
- End at
- 2025-2-25 21:00
- Duration
- 2 hour(s)
- Host
- Partic.
- 12