Codeforces Round 1086 (Div. 2)

Codeforces Round 1086 (Div. 2)

A. Bingo Candies

Solution

对于同一种颜色，最好的情况就是每行摆$n-1$个，每列也$n-1$个。假设第$i$行空了第$a_i$列，则只要保证$a_1, a_2, \cdots, a_n$是一个$1, 2, \cdots, n$的排列，就可以保证每一行都空了一个，且每一列都空了一个。

特别地，可以取$a_i=i$，则得到的就是除了对角线全部填满的矩阵。

所以一种颜色最多有$n(n-1)$个，如果每种颜色都$\leq$这个数量就是可以的，否则不可以。$O(n^2)$数数。

Code

Show Code

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> a(n * n + 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int x; cin >> x;
                a[x]++;
            }
        }
        int maxn = 0;
        for (int i = 1; i <= n * n; ++i) {
            if (maxn < a[i]) maxn = a[i];
        }
        cout << (maxn <= n * (n - 1) ? "YES" : "NO") << endl;
    }
    return 0;
}

---

B. Cyclists

Solution

贪心法则：

• 如果前$k$个中有win-condition，就直接打出；
• 否则取前$k$个中花销最小的。

证明：

• 如果其中有一步有win-conditon但是不打，得到了一个最优方案，那么1. 如果这个最优方案在这一步后面没有打过win-condition，那么打win-condition只可能更优，矛盾；2. 如果后面打过，那么交换打win-condition那一步和打其他牌的一步，win-condition的位置会更靠前，更优。
• 如果不打花销最小的，同理可以证明，先打最小的不会更劣。

$O(n^2)$模拟就好了。

Code

Show Code

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int T; cin >> T;
    while (T--) {
        int n, k, p, m; cin >> n >> k >> p >> m;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        int tot = 0;
        int cnt = 0;
        auto move = [&](int x) {
            if (x == p) p = n, ++cnt;
            else if (p > x) --p;
            int now = a[x];
            tot += now;
            a.erase(a.begin() + x);
            a.push_back(now);
        };
        while (tot < m) {
            // for (int i = 1; i <= n; ++i) {
            //     cout << a[i] << ' ';
            // }
            // cout << endl;
            if (p <= k) {
                if (tot + a[p] <= m) {
                    move(p);
                    continue;
                } else {
                    break;
                }
            }
            int mink = 1;
            for (int i = 1; i <= k; ++i) {
                if (a[mink] > a[i]) mink = i;
            }
            if (tot + a[mink] <= m) {
                move(mink);
            } else {
                break;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

---

C. Stamina and Tasks

Solution

首先可以发现，从某一步开始的所有决策和到这一步前的$S$无关。

所以可以倒过来dp：令$f_i$表示从$i$开始，假设一开始$S=1$，$i\cdots n$决策完毕之后得到的最优值。

可以得出：

$$f(n) = \begin{cases} c_i & i = n \\ \max \{c_i + (1 - \frac{p_i}{100}) f_{i + 1}, f_{i + 1}\} & i < n \end{cases}$$

$O(n)$解决。

Code

注意setprecision呜呜呜。

Show Code

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int T; cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> c(n + 1), p(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> c[i] >> p[i];
        }
        vector<double> f(n + 1, 0);
        f[n] = c[n];
        for (int i = n - 1; i >= 1; --i) {
            f[i] = max(f[i + 1] * (100 - p[i]) / 100 + c[i], f[i + 1]);
        }
        cout << fixed << setprecision(10) << f[1] << endl;
    }
    return 0;
}

---

D. Tree Orientation

Solution

一个可能合法的图，一定满足这些性质（$x\rightarrow y$表示$x$能到达$y$）：

1. 这个图是一个传递闭包（如果$a\rightarrow b, b\rightarrow c$，则一定有$a\rightarrow c$）；
2. 一定有$x\rightarrow x$；
3. 没有环，即不存在$x\rightarrow y, y\rightarrow x, x\neq y$。

我们不妨先假设一个图满足这三个性质，看看能不能把树抽出来。

首先，以上条件都满足，意味着对于任意一个节点$x$，它能到达的所有节点$y$，都满足：$y$能到达的节点是$x$能到达的节点的子集。（这是个废话）

再考虑这一个事：如果$x\rightarrow y$，$y\rightarrow z$，则$x$一定不会有一条边直接连到$z$，因为有路径从$x$到$y$到$z$，如果再来一个$x$到$z$的边，就形成环了，不满足树的性质。

再考虑一件事：如果$x\rightarrow y$，且不存在$z$满足$x\rightarrow z, z\rightarrow y$，那么$x$到$y$一定有一条边，否则$x$没有办法连到$y$。

根据以上分析，大概可以猜测出$x$会直接连向：$x$能到达的，且不存在其他路径到达的点$y$。

这样就可以确定一个很好的算法：

1. 遍历所有点$x$；
2. 把点$x$能到达的点，按照能到达的点数从大到小排序；
3. 初始化一个$vis$数组。按照排好的顺序遍历每个$x$能到达的节点$y$，再遍历$y$能到达的每个节点，把这些节点的$vis$标记为$1$。
4. 如果遍历到$y$时，$vis[y]$已经为$1$了，那么这个$y$是间接到达的，直接跳过；
5. 如果标记$vis$的时候，发现某个点被标记过了，说明$x$直接连边的两个点能够到达同一个点，这将形成一个$x\rightarrow y_1, x\rightarrow y_2, y_1\rightarrow z, y_2\rightarrow z$的结构，这会导致成环，直接报错。

这个算法是在之前的三点要求基础上提出的，但是只需要稍微改进就可以不需要以上三点条件就可以构造出一个“可能合理的图”：

6. 如果遍历完所有$y$之后，$x$能到达的点的$vis$没有全部变成$1$（除了$x$自己），那么说明这个图不满足传递性，直接报错；
7. 如果这个图成环，那么肯定会有一个节点$x$的能到达的节点也有$x$，直接报错（或者由于传递性已经保证，所以肯定会出现$x\rightarrow y$且$x$和$y$能到达的点数量一样多的情况）；
8. 干所有事之前先检查自己能不能到达自己。

这样就可以得到一个很不错的图。接下来只要检测这个图是不是树就好了。

1. 使用并查集检测是否成环（这个算法只能保证这是一个有向的DAG）；
2. 看看是不是所有点都连通。

这样就好了。时间复杂度$O(n^2\log n)$。可以用桶排序优化到$O(n^2)$，但是这样可能不如sort快。

如果只管D1的话可以很容易写出一个$O(n^3)$的方法。

Code

注意快读。

Show Code

int find(vector<int>& fa, int x) {
    return fa[x] == x ? x : (fa[x] = find(fa, fa[x]));
}
using it = vector<int>::iterator;
signed main() {
    int T; io >> T;
    while (T--) {
        int n; io >> n;
        vector<vector<int> > sons(n + 1);
        vector<vector<bool> > a(n + 1, vector<bool>(n + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                char c; io >> c;
                while (c != '0' && c != '1') io >> c;
                a[i][j] = (c == '1');
                if (c == '1') sons[i].push_back(j);
            }
        }
        vector<int> idx(n + 1);
        for (int i = 1; i <= n; ++i) idx[i] = i;
        auto cmp = [&](int x, int y) {
            return sons[x].size() < sons[y].size();
        };
        auto cmpr = [&](int x, int y) {
            return sons[x].size() > sons[y].size();
        };
        sort(idx.begin() + 1, idx.begin() + n + 1, cmp);
        for (int i = 1; i <= n; ++i) sort(sons[i].begin(), sons[i].end(), cmpr);
        // auto bsort = [&](it begin, it end, bool rev) {
        //     vector<vector<int> > tmp(n + 1);
        //     for (it x = begin; x != end; ++x) {
        //         tmp[sons[*x].size()].push_back(*x);
        //     }
        //     if (rev) {
        //         it x = begin;
        //         for (int i = n; i >= 1; --i) {
        //             for (auto y : tmp[i]) {
        //                 (*x) = y;
        //                 ++x;
        //             }
        //         }
        //     } else {
        //         it x = begin;
        //         for (int i = 1; i <= n; ++i) {
        //             for (auto y : tmp[i]) {
        //                 (*x) = y;
        //                 ++x;
        //             }
        //         }
        //     }
        // };
        // bsort(idx.begin() + 1, idx.begin() + n + 1, false);
        // for (int i = 1; i <= n; ++i) bsort(sons[i].begin(), sons[i].end(), true);
        bool flag = 0;
        vector<pair<int, int> > edges;
        for (int i = 1; i <= n && !flag; ++i) {
            int x = idx[i];
            int l = sons[x].size();
            if (l == 0) flag = 1;
            if (l > 1) {
                vector<bool> vis(n + 1, 0); 
                for (auto y : sons[x]) {
                    if (y == x) continue;
                    if (sons[y].size() >= sons[x].size()) {
                        flag = 1;
                        break;
                    }
                    if (!vis[y]) {
                        edges.push_back({x, y});
                        // printf("add %d %d\n", x, y);
                        for (auto z : sons[y]) {
                            if (vis[z]) {
                                flag = 1;
                                break;
                            }
                            vis[z] = 1;
                        }
                    }
                    if (flag) break;
                }  
                for (int y = 1; y <= n; ++y) {
                    if ((y != x && a[x][y] && !vis[y]) || (!a[x][y] && vis[y])) {
                        flag = 1;
                        break;
                    }
                }
            }
        }
        if (edges.size() != size_t(n - 1)) flag = 1;
        vector<int> fa(n + 1);
        for (int i = 1; i <= n; ++i) fa[i] = i;
        for (auto e : edges) {
            int x = e.first, y = e.second;
            if (find(fa, x) == find(fa, y)) {
                flag = 1;
                break;
            }
            fa[find(fa, x)] = find(fa, y);
        }
        for (int i = 1; i <= n; ++i) {
            if (find(fa, i) != find(fa, 1)) {
                flag = 1;
                break;
            }
        }
        if (flag) {
            io << "No\n";
        } else {
            io << "Yes\n";
            for (auto x : edges) {
                io << x.first << ' ' << x.second << '\n';
            }
        }
    }
    return 0;
}

---

E. Counting Cute Arrays

我说比D简单有没有懂的。

Solution

对于一个数列$[X_1, X_2, \cdots, X_n]$，它合法（cute）当且仅当：

1. 对于$X_i\neq -1$，不存在$X_i\geq i$；
2. 对于$X_i, X_j\neq -1$，不存在$X_j < X_i < j < i$。

证明：

• 第一个条件是显然的；
• 第二个条件可以这样理解：每个$X_i$是一组约束：$\forall j\in [X_i + 1, i - 1], a_j \geq a_i$且$a_{X_i} < a_i$。由于$a$数组的取值是任意的，所以只要约束没有矛盾，一定能凑出一个数组$a$。约束矛盾的条件就是条件$2$。

先假设条件$1, 2$都成立（这个判断很简单）。

其实我们现在得到的所有$X_i\neq -1$组成了一个括号序列（不存在互相嵌套的情况）。

假设一堆$X_i = -1$都在同一个括号$(X_i, i)$里面（不在更小的括号里面），那么他们的取值就是只要不插到前面的括号中间就行了。所以只要知道每个$X_i=-1$之前的点有几个可以插左括号的点，我们可以写一个简单的dp解决这个问题（这里写法应该很多）。

但问题是如何确定每个点在哪个括号里面。这里可以使用一个栈来解决，类似括号匹配问题，给每个点打上标记，表示它在哪个括号内，再遍历所有括号，答案乘起来就好了。

这样所有点都只会遍历一遍，遍历的时候会做一个$O(n)$的dp更新（对于$X_i=-1$），或者$O(n)$的可插入点更新（对于$X_i\neq -1$）。总的复杂度就是$O(n^2)$。

好像确实有点难讲🤔。代码清晰一点。

Code

Show Code

#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 998244353;
using LL = long long;
signed main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> X(n + 2, 0);
        for (int i = 1; i <= n; ++i) {
            cin >> X[i];
        }
        X[n + 1] = 0; // 最外面套一个括号

        vector<vector<int> > G(n + 1); // 每个括号左端点的右端点

        int ans = 1;
        for (int i = 1; i <= n + 1; ++i) {
            if (X[i] == -1) continue;
            if (X[i] >= i) {
                ans = 0;
                break;
            }
            G[X[i]].push_back(i);
        }
        if (!ans) {
            cout << 0 << endl;
            continue;
        } // 判断合法性

        vector<int> st; // 栈，存右端点
        vector<int> tag(n + 1); // 标记i在右端点为tag[i]的括号内

        for (int i = 1; i <= n; ++i) {
            for (size_t j = G[i - 1].size() - 1; ~j; --j) {
                int r = G[i - 1][j];
                if (!st.empty() && r > st.back()) {
                    // 如果r > top，说明出现了交叉
                    ans = 0;
                    break;
                }
                st.push_back(r);
            }
            while (!st.empty() && st.back() <= i) st.pop_back();
            if (!ans) break;
            assert(!st.empty());
            tag[i] = st.back(); // 找到每个i所在的括号
            // printf("i = %d, tag = %d\n", i, tag[i]);
        }

        if (!ans) {
            cout << 0 << endl;
            continue;
        }

        vector<bool> vis(n + 1, 0);
        vector<int> f(n + 1, 0); // f[i]表示用掉了i个点的方案数
        // 比如说有x1, x2, x3三个可以插入的点
        // 如果插入了x3，则一个都没用掉；
        // 如果插入x2，则用掉一个点（后面只能插x1, x2，不能插x_3）
        // 所以每次f[i] <- f[0] + f[1] + ... + f[i]
        auto solve = [&](int x) {
            // 解决括号右端点在x的问题
            for (int i = X[x] + 1; i < x; ++i) {
                vis[i] = 0;
                // vis = 0 说明可以插入
            }
            for (int i = 0; i < x - X[x]; ++i) {
                f[i] = 0;
            }
            f[0] = 1;
            
            int cnt = 1;
            for (int i = X[x] + 1; i < x; ++i, ++cnt) {
                if (tag[i] == x) {
                    if (X[i] != -1) {
                        for (int j = X[i] + 1; j < i; ++j) {
                            if (!vis[j]) --cnt;
                            vis[j] = 1;
                        }
                    } else {
                        for (int j = 1; j < cnt; ++j) {
                            f[j] = (f[j - 1] + f[j]) % MOD;
                        }
                    }
                }
            }

            int res = 0;
            for (int i = 0; i < cnt; ++i) {
                res = (res + f[i]) % MOD;
            }
            return res;
        };

        for (int i = 1; i <= n + 1; ++i) {
            if (X[i] != -1) ans = LL(ans) * solve(i) % MOD;
        }

        cout << ans << endl;
    }
    return 0;
}/*
1
4
-1 -1 1 2

*/

---