Codeforces Round #731 (Div. 3) A~G （G 树形DP）

比赛链接：Here

1547A. Shortest Path with Obstacle

3个点 ，前提 点为不可经过点，问 最短路径长度

A题没什么难度，注意同列和同行在两者之间的情况即可

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int a, b, c, d, e, f;
        cin >> a >> b >> c >> d >> e >> f;
        int  s = abs(a - c) + abs(b - d);
        if (a == c && a == e && (f > b && f < d || f > d && f < b) || b == d && b == f && (e > a && e < c || e > c && e < a))
            s += 2;
        cout << s << '\n';
    }
}

1547B. Alphabetical Strings

构造出一个按 字母序的字符串

• 首先，构造空串
• 重复 次： or

• 首先，我们如果可以找出字母“a”在字符串s中的位置。如果这个位置不存在，那么答案是 NO

• 假设这个位置存在并且等于 。让我们创建两个指针L和R。最初 ，。我们将尝试使用语句中的算法来左右构建字符串
  当我们能迭代 次时输出 YES，否则 输出 NO

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        function<int(string)> check = [&](string s) {
            if (s.empty())return 1;
            if (s[0] == 'a' + s.size() - 1)return check(s.substr(1));
            if (s.back() == 'a' + s.size() - 1)return check(s.substr(0, s.size() - 1));
            return 0;
        };
        string s; cin >> s;
        cout << (check(s) ? "YES\n" : "NO\n");
    }
}

1547C. Pair Programming

一项工作有 Monocarp 和 Polycarp 两人各 和 工时合作完成

他们都有两种操作：

• 0，新添加一行
• x > 0 ，在第 x 行上修改为 x

但这项工作原本已经存在 行被完成，请 Monocarp 和 Polycarp 操作的任何正确公共序列，如果不存在则输出 -1

模拟，

对于两人的操作 是不能超过 的，所以使用双指针模拟两人的操作即可

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int k, n, m;
        cin >> k >> n >> m;
        vector<int>a(n), b(m), ans;
        for (int &x : a)cin >> x;
        for (int &x : b)cin >> x;
        for (int i = 0, j = 0; i < n or j < m;) {
            if (i < n and a[i] <= k) {
                k += a[i] == 0;
                ans.push_back(a[i++]);
            } else if (j < m and b[j] <= k) {
                k += b[j] == 0;
                ans.push_back(b[j++]);
            } else break;
        }
        if (ans.size() != n + m)cout << "-1\n";
        else {
            for (int i : ans)cout << i << " ";
            cout << "\n";
        }
    }
}

1547D. Co-growing Sequence

• 如同
  $[0,0,0] \to [0_2,0_2,0_2] $
  均为增长序列

现在给一个长度为 的 数组，请输出一组 使得 为增长序列

思路待补

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n; cin >> n;
        int x, p = 0;
        for (int i = 0; i < n; ++i) {
            cin >> x;
            cout << (p | x) - x << " ";
            p |= x;
        }
        cout << "\n";
    }
}

1547E. Air Conditioners

对于每个位置的空调的最小值来说肯定是和左右（+1）比较

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n, 2e9), v(k), t(k);
        for (int &x : v) cin >> x;
        for (int &x : t) cin >> x;
        for (int i = 0; i < k; ++i)a[v[i] - 1] = t[i];
        for (int i = 1; i < n; ++i) a[i] = min(a[i - 1] + 1, a[i]);
        for (int i = n - 2; i >= 0; --i)a[i] = min(a[i + 1] + 1, a[i]);
        for (int x : a)cout << x << " ";
        cout << "\n";
    }
}

1547F. Array Stabilization (GCD version)

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n, d = 0;
        cin >> n;
        vector<int> v(n * 2);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            v[i + n] = v[i];
            d = __gcd(d, v[i]);
        }
        int ans = 0;
        vector<pair<int, int>>vt;
        for (int i = 2 * n - 1; i >= 0; i--) {
            vector<pair<int, int>> wp;
            vt.push_back({0, i});
            for (auto [x, y] : vt) {
                x = __gcd(x, v[i]);
                if (not wp.empty() and x == wp.back().first) wp.back().second = y;
                else wp.push_back({x, y});
            }
            swap(vt, wp);
            if (i < n) ans = max(ans, vt[0].second - i);
        }
        cout << ans << "\n";
    }
}

1547G. How Many Paths?

邻接表 + 树形DP

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> G(n), H(n);
        for (int i = 0, u, v; i < m; i += 1) {
            cin >> u >> v;
            u -= 1;
            v -= 1;
            G[u].push_back(v);
            H[v].push_back(u);
        }
        vector<int> order, id(n);
        function<void(int)> dfs1 = [&](int u) {
            id[u] = -1;
            for (int v : H[u])
                if (not id[v])dfs1(v);
            order.push_back(u);
        };
        for (int i = 0; i < n; i += 1) if (not id[i]) dfs1(i);
        reverse(order.begin(), order.end());
        int count = 0;
        function<void(int)> dfs2 = [&](int u) {
            id[u] = count;
            for (int v : G[u])
                if (not ~id[v])
                    dfs2(v);
        };
        for (int i : order) if (not ~id[i]) {
                dfs2(i);
                count += 1;
            }
        vector<vector<int>> g(count);
        for (int i = 0; i < n; i += 1)
            for (int j : G[i]) {
                g[id[i]].push_back(id[j]);
                assert(id[i] >= id[j]);
            }
        vector<int> dp(count);
        for (int i = id[0]; i >= 0; i -= 1) {
            if (i == id[0]) dp[i] = 1;
            if (dp[i]) {
                for (int j : g[i]) if (j == i) dp[i] = -1;
            }
            for (int j : g[i]) {
                if (dp[i] == -1) dp[j] = -1;
                if (dp[i] == 2 and dp[j] != -1) dp[j] = 2;
                if (dp[i] == 1 and dp[j] != -1 and dp[j] <= 1) dp[j] += 1;
            }
        }
        for (int i = 0; i < n; i += 1) cout << dp[id[i]] << " ";
        cout << "\n";
    }
}