美团资格赛题解：4

05:09 Jun.17-2017

n 个小区排成一列，编号为从 0 到 n-1 。一开始，美团外卖员在第0号小区，目标为位于第 n-1 个小区的配送站。给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ，在每个小区 i 里你有两种选择：

选择a：向前 a[i] 个小区。
选择b：向前 b[i] 个小区。

把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中，字典序最小的字符串。如果做出某个选择时，你跳出了这n个小区的范围，则这个选择不合法。

当没有合法的选择序列时，输出 “No solution!”。
当字典序最小的字符串无限长时，输出 “Infinity!”。
否则，输出这个选择字符串。

字典序定义如下：串s和串t，如果串 s 字典序比串 t 小，则

存在整数 i ≥ -1，使得∀j，0 ≤ j ≤ i，满足s[j] = t[j] 且 s[i+1] < t[i+1]。
其中，空字符 < ‘a’ < ‘b’。

输入描述:

输入有 3 行。
第一行输入一个整数 n (1 ≤ n ≤ 10^5)。
第二行输入 n 个整数，分别表示 a[i] 。
第三行输入 n 个整数，分别表示 b[i] 。
−n ≤ a[i], b[i] ≤ n

输出描述:

输出一行字符串表示答案。

输入例子:

7
5 -3 6 5 -5 -1 6
-6 1 4 -2 0 -2 0

输出例子:

abbbb

思路

这是一个图问题，只需要贪心+dfs即可，唯一需要注意的是需要判定从起点到终点之间的路径上有没有环，如果有，则应该输出“Infinity!”。好吧，其实实现得有点啰嗦，坐等大神们的题解。

bool dfs(vector<int>& a, vector<int>& b, vector<bool>&v, vector<bool>& hasCycle, int cur, string& result) {
    if (cur == a.size() - 1) {
        return true;
    }
    else {
        v[cur] = true;
        int tos[2] = {cur + a[cur], cur + b[cur]};
        char chars[2] = {'a', 'b'};
        for (int i = 0; i < 2; i ++) {
            auto to = tos[i];
            if (to >= 0 && to < a.size()) {
                if (v[to]) {
                    hasCycle[to] = true;
                }
                else {
                    result += chars[i];
                    if (dfs(a, b, v, hasCycle, to, result)) return true;
                    result.pop_back();
                }
            }
        }
    }
    return false;
}

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    vector<bool> v(n, false);
    vector<bool> hasCycle(n, false);
    string ans = "";
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i ++) {
        cin >> b[i];
    }
    auto result = dfs(a, b, v, hasCycle, 0, ans);
    if (result == false) {
        cout << "No solution!" << endl;
    }
    else {
        bool isInf = false;
        int cur = 0;
        for (auto c: ans) {
            if (hasCycle[cur]) {
                isInf = true;
                break;
            }
            cur += (c == 'a' ? a[cur] : b[cur]);
        }
        cout << (isInf ? "Infinity!" : ans) << endl;
    }
    return 0;
}

🏷

« 美团资格赛题解：3 美团资格赛题解：5 »