NOIP 2000 普及组算法题解

零、背景

今天继续分享 2000 年 NOIP 普及组题解，洛谷只有两道题。

一、计算器的改良

题意：给你只有加减法的一个一元一次方程，求解方程。

思路：表达式解析。

只有加减法，可以当做只有加法，对符号进行拆分，合并同类项。

小技巧1：分别处理等号左边与右边，然后合并时其中一边符号翻转。

int n = S.size();
int pos = S.find('=');
string left = S.substr(0, pos);
string right = S.substr(pos + 1);
exprs.clear();
Parse(left.data(), 1);
Parse(right.data(), -1);

小技巧2：假设存在多个符号，循环输入，计算最终符号。

node.sign = 1;
while (*p == '-' || *p == '+') {
  if (*p == '-') {
    node.sign *= -1;
  }
  p++;
}

注意事项，假设输入变量是 x，可能有下面几种情况：

0
+0
-0
1
+1
-1
x
-x
123x
-123x

二、税收与补贴问题

题意：对于一个商品，随着商品的价格升高，销量也会线性降低。
现在告诉你成本价与对应的销量，以及中间若干个价格与对应的销量，每两个价格之间销量呈线性关系，最后一个价格每升高 1 块钱销量降低 K 个。

政府给出了一个指导价，以及政府有两个调控手段：补贴或加税。
问政府如何操作，才能让商品在指导价下得到最大利润。
如果有多个答案，输出绝对值最小的调控值。
数据范围：10^5。

PS：好神奇的调控手段。

思路：数学计算。

补贴定义为正整数，加税定义为负整数。
则对于每一个价格与销量，对应的利润不能超过指导价的利润，从而可以列出一个不等式。

根据题意，可以预先计算出所有合法价格对应的销量，从而得到 N 个不等式。

每个不等式要么计算出调控价不大于一个值，要么是不小于一个值，即调控价在一个区间内。

如果区间都是负数，则输出最大的负数。
如果区间都是正数，则输出最小的正数。
否则输出 0。

利润计算公式：(价格 - 成本 + 调控) * 销量。

三、最后

这两道题都有一些陷阱。
计算器需要考虑的情况比较多，漏一种就会丢分。
税收与补贴则题目理解难度比较大，需要花费不少时间来理解题。
题目理解后，就会发现就是一个不等式的解方程，而且一定存在答案。

《完》

-EOF-

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