team2012-D1-sol-0011

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 题目大意 ===
给出一个有 n 个结点(即有 n-1 段)折线段, 让你按顺序执行 m 个涂色/擦除操作. 求最后被涂色的折线段长度.

=== 数据范围 ===
1 <= n <= 100[[BR]]
1 <= m <= 1000

=== 解题思路 ===
由于颜色只有一种, 线段的状态只有涂色和无色两种. 我们可以对每一段线段做这 m 个操作, 然后求和即可. 而对于每一个线段, 每一个操作的矩阵依次和线段求交. 最后sort完之后处理一下就好了. 这题范围很小, 其实直接每次求完矩形和线段的交之后再直接和之前每一个每一个线段判断做操作就好了, 每次至多只会增加1个新的线段, 所以是 O(m*n) 的, 可以接受.

题目大意

给出一个有 n 个结点(即有 n-1 段)折线段, 让你按顺序执行 m 个涂色/擦除操作. 求最后被涂色的折线段长度.

数据范围

1 <= n <= 100

1 <= m <= 1000

解题思路

由于颜色只有一种, 线段的状态只有涂色和无色两种. 我们可以对每一段线段做这 m 个操作, 然后求和即可. 而对于每一个线段, 每一个操作的矩阵依次和线段求交. 最后sort完之后处理一下就好了. 这题范围很小, 其实直接每次求完矩形和线段的交之后再直接和之前每一个每一个线段判断做操作就好了, 每次至多只会增加1个新的线段, 所以是 O(m*n) 的, 可以接受.