NOIP 2003 提高组算法题解

作者: tiankonguse | 更新日期:

涉及拓扑排序、区间动态规划等算法

本文首发于公众号：天空的代码世界，微信号：tiankonguse

零、背景

今天继续分享 2003 年 NOIP 提高组题解。

一、神经网络

题意：给一个有向无环图神经网络，告诉你所有输入节点的状态，只有一个节点的状态大于0时，才能把信号传递给所有后驱节点。
每个节点的状态由所有激活的前驱节点加权计算得到。
求所有激活的输出节点，以及对应的状态。

思路：拓扑排序

原题介绍的非常抽象，根本看不出来是啥意思。
上面是总结提炼出来的含义。

理解了题意，就简单了。
直接拓扑排序计算每个节点的状态，最后统计激活的输出节点的答案。

while (!que.empty()) {
  int u = que.front();
  que.pop();
  for (auto [v, w] : G[u]) {
    inDeg[v]--;
    if (C[u] > 0) {
      C[v] += C[u] * w;
    }
    if (inDeg[v] == 0) {
      que.push(v);
    }
  }
}
vector<pair<int, ll>> ans;
ans.reserve(n);
for (int i = 0; i < n; i++) {
  if (outDeg[i] == 0 && C[i] > 0) {
    ans.push_back({i, C[i]});
  }
}

注意事项：输入节点不需要加权计算，只有有入度的节点才需要加权计算。

二、侦探推理

题意：有一个人是罪犯，M 个人说了 P 句话，其中 N 个人说了谎话，其他人说的都是真话。
问可以判断几个人可能是罪犯。

每个人说的话有6类：
1）我是罪犯。
2）我不是罪犯。
3）XX是罪犯。
4）XX不是罪犯。
5）今天是星期几。
6）其他

思路：枚举

枚举谁是罪犯和今天是星期几，判断所有话之间是否有矛盾。
没矛盾了，判断说假话的人是否为 N 个，是的，则枚举成立。

int CheckName(const int nameId, const int guiltyId, const int day) {
  int ans = 0;  // 1 真话, 2 假话, 0 可真可假， -1 矛盾
  for (const auto& state : nameToWords[nameId]) {
    const int xxx = state.xxx;
    if (state.type == GUILTY) {
      if (xxx == guiltyId) {
        ans |= 1;
      } else {
        ans |= 2;
      }
    } else if (state.type == NOT_GUILTY) {
      if (xxx == guiltyId) {
        ans |= 2;
      } else {
        ans |= 1;
      }
    } else if (state.type == DAY) {
      if (xxx == day) {
        ans |= 1;
      } else {
        ans |= 2;
      }
    }
  }
  if (ans == 3) {
    ans = -1;
  }
  return ans;
}

特殊情况：某些人可能没说话，从而无法判断说的是真话还是假话。
此时，就需要假设这几个人由于部分人说假话，从而凑够 N 个假话。

// 假设 nameId 是 guilty ，day 是 week，判断是否成立
bool Check(const int guiltyId, const int day) {
  int ans[3] = {0, 0, 0}; // 1 真话, 2 假话, 0 可真可假
  for (int nameId = 1; nameId <= m; nameId++) {
    int ret = CheckName(nameId, guiltyId, day);
    if (ret == -1) return false;
    ans[ret]++;
  }
  return ans[2] <= n && n <= ans[0] + ans[2];
}

三、加分二叉树

题意：给一个二叉树的中序序列，问怎么构造二叉树，才能使得根的加分最大。
子树根的加分：左子树加分 * 右子树加分 + 子树根的基础分。
如果其中一个子树为空，加分按1计算。
叶子节点的两个子树都为空，加分定义为叶子的基础分。
输出根加分最大时，对于二叉树的前序序列。

思路：区间动态规划

状态定义：dp(l,r) 表示区间 [l, r] 子树可以得到的最大加分，以及树根的位置
状态转移方程：

dp(l, r) = max(dp(l, mid-1) * dp(mid+1, r) + baseVal[mid]);

完整的代码如下：

vector<vector<pair<ll, int>>> dp; 
pair<ll, int> Dfs(int l, int r) {
  if (l > r) return {1, 0};  // 空树的加分为 1
  auto& [maxVal, rootPos] = dp[l][r];
  if (maxVal != 0) return {maxVal, rootPos};

  // 叶子的加分就是叶节点本身的分数
  if (l == r) {
    maxVal = middleList[l];
    rootPos = l;
    return {maxVal, rootPos};
  }

  for (int root = l; root <= r; root++) {
    auto [leftVal, leftPos] = Dfs(l, root - 1);
    auto [rightVal, rightPos] = Dfs(root + 1, r);
    ll val = leftVal * rightVal + middleList[root];
    if (val > maxVal) {
      maxVal = val;
      rootPos = root;
    }
  }
  return {maxVal, rootPos};
}

由于记录了最大得分对应的根，再递归构造出二叉树，从而构造出前序序列。

vector<ll> preOrderList;
void DfsAns(int l, int r) {
  if (l > r) return;
  int root = dp[l][r].second;
  preOrderList.push_back(root);
  DfsAns(l, root - 1);
  DfsAns(root + 1, r);
}

四、传染病控制

题意：告诉你一个树，起始树根被染色。
每一秒染色的节点可以把相邻的节点染色。
同时，我们可以删除一条边。
最终树中未删除的就会被全部染色。
问如何操作，才能使得染色的节点个数最小，输出最小值。

思路：搜索

根据题意，可以发现，每一秒就会把树的一层全部染色，同时，我们也会从这一层删除一个节点以及对应的子树。
删除哪个节点无法确定是否是最优的，所以需要枚举所有情况。

这道题没有多项式解法，只能暴力搜索来做。
复杂度：O(能过)

搜索时，需要存每一层的节点。
我自己维护了一个栈 que，把这层的节点都压到栈 que 上，从而不需要每次申请一个数组。
由于每个节点最多入栈一次，所以栈大小最大不超过 n。

vector<int> que;
void Dfs(const int l, const int r, const int preDelNum) {
  if (l == r) {
    UpdateAns(r - preDelNum);
    return;
  }
  for (int i = l; i < r; i++) {  // [l, r)
    // 枚举删除节点 i 与父节点的边
    int p = r;
    for (int j = l; j < r; j++) {
      if (i == j) continue;
      for (auto v : G[que[j]]) {
        que[p] = v;
        p++;
      }
    }
    Dfs(r, p, preDelNum + 1);
  }
}

剪枝：显然，一层所有节点中，先删除最大的子树可能得到更小的答案。
故构造树时，可以对儿子按树大小排序。

void DfsLevel(int u, int pre) {
  childNum[u] = 1;
  for (int v : g[u]) {
    if (v == pre) continue;
    G[u].push_back(v);
    DfsLevel(v, u);
    childNum[u] += childNum[v];
  }
  // 儿子节点按子树大小降序排列，方便后续枚举删除节点时，优先删除子树大的节点
  sort(G[u].begin(), G[u].end(), [&](int a, int b) { return childNum[a] > childNum[b]; });
}

搜索时，假设这一层都可以删除，是否依旧比当前答案差，是的话就剪枝掉。
一层所有节点子树的大小定义为 forestNum。
到下一层时，删除了一个子树，减少了一层，两个重叠一个子树根，多删除了需要加回来。
故下层子树的大小为 forestNum - childNum[u] - len + 1。

void Dfs(const int l, const int r, const int preDelNum, const int forestNum) {
  if (l == r) {
    UpdateAns(preDelNum);
    return;
  }
  // 森林都删除依旧比当前答案大，则不需要继续枚举删除节点
  if (n - (preDelNum + forestNum) >= ans) return;

  int len = r - l;
  for (int i = l; i < r; i++) {  // [l, r)
    // 枚举删除节点 i 与父节点的边
    int p = r;
    for (int j = l; j < r; j++) {
      if (i == j) continue;
      for (auto v : G[que[j]]) {
        que[p] = v;
        p++;
      }
    }
    Dfs(r, p, preDelNum + childNum[que[i]], forestNum - childNum[que[i]] - len + 1);
  }
}

五、最后

这次比赛出的不好。

第一题我看了一个小时，也没看懂。
最后看题解发现就是有向图，从输入节点到同一个节点，深度都是相同的。
那直接拓扑排序即可。

第四题同样没看懂。
看了题解发现是树分层染色，暴力枚举即可。

《完》

-EOF-

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

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

关注公众号,接收最新消息

置顶文章

tiankonguse + ≡
穿越