NOI 1998 题解 - day2

零、背景

之前已经分享了 1998 年 NOIP 的《普及组题解》和《提高组题解》。
也分享了 NOI 的《1998年 题解》。

当时只有两道题，一道是《围巾裁剪》，一道是《免费的馅饼》。

后来准备写 1997 年的题解时，发现 1998 年 NOI 又多了两道题，所以就当做 day2 来继续分享吧。

一、个人所得税

题意：个人所得税是按超额累进税率来征税的。
一般有一个免税额度，剩下的按征税表来递增收税。

例如下图的一个所得税征税表，假设免税额度是 1万，则征税分四种情况：

1）收入低于 1万的，免税。
2）收入在 1万到3万的，1万免税，剩下的按 20% 收税。
3）收入在 3万到6万之间的，1万免税，2万按 20% 收税，剩下的按 30% 征收。
4）收入大于 6万时，1万免税，2万按 20% 收税，3万按 30% 征收，剩下的按 40% 征收。

现在有两个征税表，一个是按月征收，一个是一次性劳动报酬所得，按次征收。
告诉你一个公司的员工收入流水表，计算这个公司的员工累计需要交多少税。

思路：模拟。

对于一次性收入，直接按征税表计算需要交多少税。
对于工资，计算出每个员工每月的收入，然后依次计算需要交多少税即可。

二、SERNET 模拟

题意：SERNET 网络是一个特殊的网络，用于在网络中转发数据包。
数据包包含三个字段：数据包编号、源服务器、目的服务器。

网络中的一个服务器收到一个数据包后，会原封不动地转发给相邻的所有服务器。
只有三种情况才会停止转发数据包：

1）源服务器与本服务器相同。
2）目的服务器与本服务器相同。
3）这个编号的数据包之前已经转发过了。

数据包在两个服务器之间传输需要一定的时间，转发不需要时间。
现在告诉你网络拓扑图，包含每条边的传输时间。
还告诉你 K 个数据包的编号、起始发送时间、源服务器地址、目的服务器地址。
问时刻 T 时，还在网络中传输的数据包个数。

思路：最短路。

很容易想到一个基于 Floyd 的最短路方法。

先使用 Floyd 预处理整个网络任意两个顶点的最短路。
对于每个数据包，枚举每个服务器，如果这个服务器在 T 时刻之内可以到达，但是转发出去的数据包在 T 时刻无法到达下一个服务器，则说明这个数据包还在网络中传输。

怎么判断一个服务器是否存在一条边在 T 时刻无法到达呢？
预处理计算每个服务器的最大相邻边即可。

复杂度：O(n^3 + K*n)

遗憾的是，这个方法是错误的，只能得 40 分。
如果目的服务器恰好是图中的一个割点，那么割点另一侧的服务器永远无法收到数据包，但上面的方法会错误地认为数据包能到达那些服务器。

如下图，B 是源点，A 是目的服务器。
数据包从 B 发出后到达 A 就会停止转发，所以 C、D、E 永远无法收到数据包。
但 Floyd 方法会错误地计算出数据包在 D->E 这条线路上传输。

        (B)
         |
         2
         |
(C)--2--(A)--3--(D)--100000--(E)

正确的方法：对每个数据包，从源服务器出发，用 Dijkstra 逐层求单源最短路，遇到目的服务器就停止扩展。
这样就能准确模拟数据包的传播过程。

复杂度：O(K * n^2)

三、最后

这两道题相对简单。
其中 SERNET 这道题难度其实不大，但很容易想到错误的贪心方法，导致只能得到 40 分。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code