NOIP 2004 普及组算法题解

零、背景

今天继续分享 2004 年 NOIP 普及组题解。

一、不高兴的津津

题意：津津每天白天上课 a 小时，然后补习班上课 b 小时。
如果当天上课总时长超过 8 小时，津津就会不高兴。
问津津在哪天会不高兴，如果存在，输出最不高兴的那一天。

思路：枚举

枚举找到上课最长的那一天，然后判断是否超过 8 小时。

int n = 7;
int maxVal = 8, day = 0;
for (int i = 1; i <= 7; i++) {
  int a, b;
  scanf("%d%d", &a, &b);
  if (a + b > maxVal) {
    maxVal = a + b;
    day = i;
  }
}
printf("%d\n", day);

二、花生采摘

题意：路边有一个矩阵花生田，某些位置的花生株有一些的花生。
路边进入花生田需要一个代价，然后花生田中上下左右移动，每移动一次也需要划分一个代价，采摘需要一个代价，从花生田边上返回路边也需要划分一个代价。
有花生的位置，花生的个数互不相同。
现在要求按花生数量从大到小一次采摘。
问在指定总代价内，路边进入花生田再返回路边，最多可以采摘多少个花生。

思路：模拟。

路边去第一个花生株，代价只需要关心行的距离。
最后一个花生株去路边，代价也是只需要关心行的距离。两个花生株之间代价是曼哈顿距离。

pair<int, int> GetGoOut(int x0, int y0, int x1, int y1) {
  int go = abs(x0 - x1) + abs(y0 - y1) + 1;
  int out = x1;
  return {go, out};
}

题目要求花生数量互不相同，而且必须从多到少的采摘，那花生株的遍历顺序就是固定的。
每次判断从当前花生株到达下个花生株后是否可以到达路边，可以了，就去下个花生株。
因此，需要计算两个值，一个是到达下个花生株并采摘的代价，一个是下个花生株到路边的代价。

// 从大到小排序，下标从 1 开始。
sort(g.begin(), g.end(), greater<tuple<int, int, int>>());
int ans = 0;
if (!g.empty()) {
  auto [_, x0, y0] = g[0];
  x0 = 0; // 对齐列，0 代表路边
  for (auto [val, x1, y1] : g) {
    auto [go, out] = GetGoOut(x0, y0, x1, y1);
    if (go + out <= k) {
      k -= go; // 到达下个花生株并采摘
      ans += val;
    } else {
      break;
    }
    x0 = x1;
    y0 = y1;
  }
}
printf("%d\n", ans);

三、FBI 树

题意：我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。
FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。
给一个完全二叉树的 01 值中序遍历序列请构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。

思路：递归

按照题意边构造完全二叉树，边统计 0 与 1 的个数，从而计算出子树的 FBI 值。
小技巧：利用区间大小与区间和，也可以推导出 0 与 1 的个数。

void Dfs(int l, int r) {
  if (l != r) {
    int mid = (l + r) / 2;
    Dfs(l, mid);
    Dfs(mid + 1, r);
  }
  int sum = RangeSum(l, r);
  int len = r - l + 1;
  if (sum == 0) {
    ans.push_back('B');
  } else if (sum == len) {
    ans.push_back('I');
  } else {
    ans.push_back('F');
  }
}

四、火星人

题意：给一个不重复数字的排列，求下个排列数。

思路：贪心

下个排列数，本质上是在修改尽量短的后缀，得到更大的字符串。

例如 1 2 3, 只修改 2 3 就可以得到下个字符串 1 3 2。
同理，对于 1 3 2，则需要修改 1 3 2，可以得到下个字符串 2 1 3。

由此，可以发现三个规律。

规律1：需要从后到前，找到第一个非逆向递增的位置，例如 1 3 2 的 1。
规律2：找到后缀中 1 3 2，下个大于边界值 1 的值，这里是 2。
规律3：剩余的数字，需要从小到大排列，这里是 1 3。
综合，得到序列 2 1 3。

小技巧1：处理规律1时，列表记录下逆向的数字，从而规律2可以在列表中二分查找。
小技巧2：下个值与边界进行交换，得到的依旧是有序列表，故可以直接应用到规律3。

每次不超过 O(n)，共 k 次。
综合复杂度：k O(n)

vector<int> buf;
void Process(int p) {  //
  const int oldVal = nums[p];
  auto it = upper_bound(buf.begin(), buf.end(), oldVal);
  int nextVal = *it; // 规律2，找到下个值
  *it = oldVal;
  nums[p++] = nextVal;
  for (auto v : buf) { // 规律3，剩余升序排列
    nums[p++] = v;
  }
}
void Next() {  //
  buf.clear();
  for (int i = n - 1; i >= 0; i--) {
    int v = nums[i];
    if (buf.empty() || v > buf.back()) {
      buf.push_back(v);
    } else {
      Process(i); // 规律1，找到边界
      break;
    }
  }
}

五、最后

2004年普及组的比赛还算简单。
第一题，签到题。
第二题，矩阵下标从 1 开始处理，把路边当做 0 处理，就会简单很多。
第三题，二叉树递归构造树，基础题。
第四题，下个排列数，稍微复杂一些，但是也不难。

《完》

-EOF-

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

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。