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：贪心
-
对于物品，我们希望每次都买更贵的，这样免费的就是能免费中的最贵的
-
对于券，我们希望每次用优惠数量最少的，因为这样就能免费更贵的物品
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) = xy大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结尾的方案数
那么如何转移呢？
dp[0][0] = 1表示空数组满足条件- 接着遍历
a中的元素：- 如果
x大于等于第一条不下降子序列的末尾i，那么就可以更新第一条不下降子序列的末尾，变成x - 如果
x大于等于第二条不下降子序列的末尾j，那么就可以更新第二条不下降子序列的末尾，变成x
- 如果
- 最终统计
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开始的，需要注意+ 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
核心思路：
-
消去所有两两成对的括号，剩下的都是相邻不同的括号
-
如果剩下相邻不同的括号不是偶数，很显然不能变成合法括号
-
如果消去的括号对数不是偶数对，而剩下相邻不同的括号已经可以两两匹配了，那么一定会出现多出两个朝同一方向的括号，很显然这样也不能变成合法括号
eg: (( )) (( ()() -
如果没有消去一个两两成对的括号，而且字符串的第一个是
)，那么我们就无法通过题目给的转换操作将)变成(，很显然这样也不能变成合法括号
剩下的情况，我们都可以通过不断交换，让左边的括号都变成 (，右边的括号都变成 )
eg: )) )( (( )) ))
)) )) )( )) ))(( (( )( )) ))
核心代码：
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';
}