Codeforces Round 1051 (Div 2)

Problem - A. All Lengths Subtraction

思路：

我们希望 n 和 n - 1 相邻，n - 1, n 和 n - 2 相邻 ...

不断往外扩展

所以我们可以维护 l 和 r 表示当前扩展到了哪里

通过判断下一个数是否和 l 或者 r 相邻，判断 YES/NO

核心代码：

void solve()
{int n; cin >> n;vector<int> a(n + 1);for(int i = 1; i <= n; i++) {int x; cin >> x;a[x] = i; // 记录每个数在的位置 }int l = min(a[n], a[n - 1]), r = max(a[n], a[n - 1]);if(r - l != 1){cout << "NO" << '\n';return;}for(int i = n - 2; i >= 1; i--){if(l - a[i] == 1) l = a[i];else if(a[i] - r == 1) r = a[i];else{cout << "NO" << '\n';return;}}cout << "YES" << '\n';
}

Problem - B. Discounts

思路：

tag：贪心

1. 对于物品，我们希望每次都买更贵的，这样免费的就是能免费中的最贵的

2. 对于券，我们希望每次用优惠数量最少的，因为这样就能免费更贵的物品

   eg: 对于物品有 10 9 8 2， 券有 1 3

   如果用 1 就可以免费 10，但是用 3 只能免费 8

核心代码：

void solve()
{int n, k;cin >> n >> k;vector<int> a(n), b(k);for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < k; i++) cin >> b[i];sort(a.begin(), a.end(), [&](const int &a, const int &b){return a > b;});sort(b.begin(), b.end());int ia = 0, ib = 0; // ia 用到了那个物品， ib 用到了那个券int ans = 0;for(int i = ib; i < k; i++){int x = b[i];for(int j = 1; j < x && ia < n; j++)ans += a[ia++];ia++; if(ia >= n) break;}while(ia < n) ans += a[ia++];cout << ans << '\n';
}

Problem - C. Max Tree

思路：

tag：Topo

因为题目给的是一颗树，所以一定不会有三个点成环的情况，所以不存在矛盾

那么直接根据 x, y 的大小决定是由 u->v 还是 v->u 即可

• x 大 u -> v，dist(u, v) = x
• y 大 v -> u，dist(u, v) = y

然后 topo排序获得各个点之间的大小关系

核心代码：

void solve()
{int n; cin >> n;vector<int> in(n + 1);vector<vector<int>> adj(n + 1);for(int i = 1; i <= n - 1; i++){int u, v, x, y;cin >> u >> v >> x >> y;if(x > y) adj[u].push_back(v), in[v]++;else adj[v].push_back(u), in[u]++;}vector<int> q;for(int i = 1; i <= n; i++)if(!in[i]) q.emplace_back(i);for(int i = 0; i < q.size(); i++){int u = q[i];for(auto& v: adj[u]){in[v]--;if(!in[v]) q.emplace_back(v);}}vector<int> ans(n + 1);int m = n;for(auto t: q){ans[t] = m--; }for(int i = 1; i <= n; i++) cout << ans[i] << " ";cout << '\n';
}

Problem - D1. Inversion Graph Coloring (Easy Version)

思路：

tag：dp

很显然题目的意思是数组中不能存在长度 >= 3 的下降序列

换个意思就是，整个数组可以划分成两个不下降子序列

但是，现在我们要判断的是所有的子数组，如果一个个地判断很显然会超时

所以考虑用 dp

对于 dp[i][j]

• i 表示第一条不下降子序列的结尾
• j 表示第二调不下降子序列的结尾
• dp[i][j] 表示第一条以 i 结尾，第二条以 j 结尾的方案数

那么如何转移呢？

1. dp[0][0] = 1 表示空数组满足条件
2. 接着遍历 a 中的元素：
   • 如果 x 大于等于第一条不下降子序列的末尾 i，那么就可以更新第一条不下降子序列的末尾，变成 x
   • 如果 x 大于等于第二条不下降子序列的末尾 j，那么就可以更新第二条不下降子序列的末尾，变成 x
3. 最终统计 0-n所有可能的结尾的方案和即可

需要注意：

​ 因为我们的转移是从上一个数 a[i - 1] 的状态转移过来的，所以需要新开一个 dp，保证所有状态都是从之前的状态转移过来，而不是从已经更新过的状态转移过来

核心代码：

const int mod = 1e9 + 7;
void solve()
{int n; cin >> n;vector<int> a(n);for(auto& t: a) cin >> t;vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));dp[0][0] = 1;for(int i = 0; i < n; i++){int x = a[i];vector<vector<int>> ndp(n + 1, vector<int>(n + 1, 0));for(int t1 = 0; t1 <= n; t1++){for(int t2 = 0; t2 <= n; t2++){int c = dp[t1][t2];if(c == 0) continue;ndp[t1][t2] = (ndp[t1][t2] + c) % mod;if(t1 <= x){ndp[x][t2] = (ndp[x][t2] + c) % mod;}else if(t2 <= x){ndp[t1][x] = (ndp[t1][x] + c) % mod;}}}dp = ndp;}int ans = 0;for(int t1 = 0; t1 <= n; t1++){for(int t2 = 0; t2 <= n; t2++){ans = (ans + dp[t1][t2]) % mod;}}cout << ans % mod << '\n';
}

Problem - D2. Inversion Graph Coloring (Hard Version)

思路：

tag：树状数组

上面的代码是 \(O(n^3)\)，很显然会超时，需要优化

观察上面的代码：

• \[ndp[x][t2] += \sum\limits_{t1=0}^x dp[t1][t2] \]

• \[ndp[t1][x] += \sum_{t2=0}^x dp[t1][t2] \]

这时就很自然地想到对于每一个 t1 都维护一个前缀和，对每一个 t2 也维护一个前缀和

可以将 dp 看成一个矩阵，分别按列和行求前缀和

因为需要状态转移，所以我们还需要对点进行修改

⭐单点修改，区间查询 \(\Rightarrow\) 树状数组

需要注意：

1. 对于要修改的点，因为既在行上，也在列上，所以都要修改
2. 因为这一次的状态修改是根据上一次的状态转移的，所以需要先将要修改的点存起来，最后一起修改，防止覆盖
3. 树状数组的索引是从 1 开始的，需要注意 + 1

核心代码：

using PII = pair<int, int>;
const int mod = 1e9 + 7;struct Fenwick
{vector<int> tree;int n;Fenwick(int size) : n(size + 1), tree(size + 2, 0) {}void update(int idx, int val){for(; idx <= n; idx += idx & -idx)tree[idx] = (tree[idx] + val) % mod;}int query(int idx){int res = 0;for(; idx > 0; idx -= idx & -idx)res = (res + tree[idx]) % mod;return res;}int query(int l, int r){if(l > r) return 0;return (query(r) - query(l - 1) + mod) % mod;}
};void solve()
{int n; cin >> n;vector<int> a(n);for(auto& t: a) cin >> t;vector<Fenwick> row(n + 2, Fenwick(n + 2)); // 最大vector<Fenwick> col(n + 2, Fenwick(n + 2)); // 次大row[0].update(0 + 1, 1); // 树状数组索引从 1 开始col[0].update(0 + 1, 1);for(int x: a){vector<pair<PII, int>> updatepoint;// x 是最大for(int t2 = 0; t2 <= x; t2++){int sum = col[t2].query(0 + 1, x + 1);if(sum > 0) updatepoint.push_back({{x, t2}, sum});}// x 是次大for(int t1 = x + 1; t1 <= n; t1++){int sum = row[t1].query(0 + 1, x + 1);if(sum > 0) updatepoint.push_back({{t1, x}, sum});}// 更新for(auto [dot, val] : updatepoint){auto [x, y] = dot;row[x].update(y + 1, val);col[y].update(x + 1, val);}}int ans = 0;for (int t1 = 0; t1 <= n; t1++) {for (int t2 = 0; t2 <= n; t2++) {// 从行树状数组中获取最终结果int val = row[t1].query(t2 + 1, t2 + 1);ans = (ans + val) % mod;}}cout << ans % mod << '\n';
}

Problem - E. Make Good

核心思路：

1. 消去所有两两成对的括号，剩下的都是相邻不同的括号

2. 如果剩下相邻不同的括号不是偶数，很显然不能变成合法括号

3. 如果消去的括号对数不是偶数对，而剩下相邻不同的括号已经可以两两匹配了，那么一定会出现多出两个朝同一方向的括号，很显然这样也不能变成合法括号

   eg: (( )) (( ()()

4. 如果没有消去一个两两成对的括号，而且字符串的第一个是 )，那么我们就无法通过题目给的转换操作将 ) 变成 (，很显然这样也不能变成合法括号

剩下的情况，我们都可以通过不断交换，让左边的括号都变成 (，右边的括号都变成 )

eg: )) )( (( )) ))

1. )) )) )( )) ))
2. (( (( )( )) ))

核心代码：

void solve()
{int n; cin >> n;string s; cin >> s;vector<char> v;for(auto t: s){if(v.size() && v.back() == t) v.pop_back();else v.push_back(t);}int m = v.size();if(m % 2 == 1 || (n - m) / 2 % 2 == 1){cout << -1 << '\n';return;}if(n == m && v[0] == ')'){cout << -1 << '\n';return;}for(int i = 1; i <= (n - m) / 2; i++) cout << '(';for(int i = 0; i < v.size(); i++) cout << v[i];for(int i = 1; i <= (n - m) / 2; i++) cout << ')';cout << '\n';
}