微软笔试题 HihoCoder#1136: Professor Q's Software 题解

发表于 更新于 Disqus：

题目来源

题目： http://hihocoder.com/problemset/problem/1136

Professor Q develops a new software. The software consists of N modules which are numbered from 1 to N. The i-th module will be started up by signal Si. If signal Si is generated multiple times, the i-th module will also be started multiple times. Two different modules may be started up by the same signal. During its lifecircle, the i-th module will generate Ki signals: E1, E2, ..., EKi. These signals may start up other modules and so on. Fortunately the software is so carefully designed that there is no loop in the starting chain of modules, which means eventually all the modules will be stoped. Professor Q generates some initial signals and want to know how many times each module is started.

大意如下：

有点像Workflow的结构：每个模块可以产生若干个信号，每个信号可以触发若干个模块。给你初始的几个信号，输出最终每个模块被触发了多少次（注意不是总和，是每个模块）。可以保证这个Workflow里没有环，不然就死循环了。

解题思路

第一反应想到的是模拟，但是这样效率显然不足以处理 \(10^5\) 的数据。只能 DP。

首先这个题目很容易想到能用图表示，而且还是个DAG（有向无环图），DAG最可爱的特征是可以拓扑排序啊！排序之后就变成一维序列，对序列就能理所当然地DP了。所以我们解题也分两步：

  • 构建图，并拓扑排序（用DFS，不会请复习《算法导论》）
  • 按拓扑序做DP，DP[i]表示第i个模块被触发的次数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 100001;
int T, M, N, S, K;
vector<int> init;
vector<int> SM[MAX]; // Signal -> Module
vector<int> MS[MAX]; // Module -> Signal
bool visited[MAX];
vector<int> sorted;
int dp[MAX];

void dfs(int m) {
  if (visited[m]) return;
  visited[m] = true;
  for (int signal : MS[m]) {
    for (int module : SM[signal]) {
      dfs(module);
    }
  }
  sorted.push_back(m);
}

int main() {
  scanf("%d", &T);
  while (T--) {
    init.clear();
    memset(visited, 0, sizeof(visited));
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
      scanf("%d", &S);
      init.push_back(S);
    }
    for (auto &v : SM) v.clear();
    for (auto &v : MS) v.clear();
    for (int i = 0; i < N; i++) {
      scanf("%d %d", &S, &K);
      SM[S].push_back(i);
      for (int j = 0; j < K; j++) {
        scanf("%d", &S);
        MS[i].push_back(S);
      }
    }
    sorted.clear();
    for (int i = 0; i < N; i++) {
      dfs(i);
    }
    memset(dp, 0, sizeof(dp));
    for (int s : init) {
      for (int m : SM[s]) {
        dp[m] += 1;
      }
    }
    for (auto it = sorted.rbegin(); it != sorted.rend(); it++) {
      int m = *it;
      for (int signal : MS[m]) {
        for (int module : SM[signal]) {
          dp[module] += dp[m];
          if (dp[module] >= 142857) dp[module] -= 142857;
        }
      }
    }
    for (int i = 0; i < N; i++)
      printf("%d%c", dp[i], i == N - 1 ? '\n' : ' ');
  }
}

Ref:

  1. http://www.cnblogs.com/njczy2010/p/4391823.html