Educational Codeforces Round 183 (Rated for Div. 2)题解

Educational Codeforces Round 183 (Rated for Div. 2) 题解

A

直接提前分给三人，看看余下多少，然后用 3 去相减就行了。不过注意 3 的倍数的情况是 0。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long longint n;void solve () {cin >> n;int res = n%3;if (!res) cout << "0\n";else cout << 3-res << "\n";
}int main () {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int _ = 1; cin >> _;while (_--) solve();return 0;
}

B

挺有意思的一道题目。

其实通过手推我们不难发现，如果有一个操作是 2，那么只要后面跟了个 0 或者 1，只能保证将 2 带来的 ? 再往里面缩一格，因为此时只能保证原来的最外面的那一层被 0 或者 1 带走，但是里面一层的情况未知。

所以我们可以发现规律，我们先统计出所有的 0 和 1 的数量，提前操作出 -，然后再在剩下的里面填入 ? 以及 +，但是注意，如果剩下的牌的数量如果 \(\leq cnt_2\)，那么剩下的牌也一定会被全部删除，可以全部填上 -。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int N = 2e5+100;int n, k;
char ans[N];void solve () {cin >> n >> k;for (int i = 1;i <= n;i++) ans[i] = ' ';string s; cin >> s;int zero = 0, one = 0, two = 0, l = 1, r = n;for (int i = 0;i < k;i++) {if (s[i] == '0') zero++;else if (s[i] == '1') one++;else two++;}for (int i = 1;i <= zero;i++) ans[l++] = '-';for (int i = 1;i <= one;i++) ans[r--] = '-';int res = n-zero-one;if (res <= two) for (int i = l;i <= r;i++) ans[i] = '-';else {for (int i = 1;i <= two;i++) ans[l++] = '?';for (int i = 1;i <= two;i++) ans[r--] = '?';for (int i = l;i <= r;i++) ans[i] = '+';}for (int i = 1;i <= n;i++) cout << ans[i];cout << "\n";
}int main () {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int _ = 1; cin >> _;while (_--) solve();return 0;
}

C

有意思的前缀和。

不难发现，我们假设有 \(cnt_a, cnt_b\)，题目的要求就是找到一段连续的子串使得当前这一段的 \(|cnt_a - cnt_b| == |cnt_{total_a} - cnt_{total_b}|\)。

所以我们可以考虑前缀和，用 \(O(n)\) 的复杂度统计，然后记录每一个前缀和的最近的出现位置，然后每看到一个前缀和 \(pre\)，我们就去找 \(k-pre\) 的位置，这样子可以以贪心的思想满足题目要求。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long longvoid solve() {int n; string s;cin >> n >> s;int cnta = 0, cntb = 0;for (int i = 0;i < n;i++) {if (s[i] == 'a') cnta++;else cntb++;}if (cnta == cntb) {cout << 0 << endl;return;}int need = cnta - cntb;unordered_map<int, int> pos;int tmp = 0;pos[0] = -1;int minn = INT_MAX;for (int i = 0; i < n; i++) {if (s[i] == 'a') tmp++;else tmp--; int needed = tmp - need;if (pos.count(needed)) {int len = i - pos[needed];if (len < n) minn = min(minn, len);}pos[tmp] = i;}if (minn == INT_MAX) cout << -1 << "\n";else cout << minn << "\n";return;
}int main() {ios::sync_with_stdio(false);cin.tie(NULL), cout.tie(nullptr);int _ = 1; cin >> _;while (_--) solve();return 0;
}

D

比较难的一道 dp，赛时也是被大佬指点迷津才做出来的。

首先分析题目的 反转值，发现只有递增的数组才不会有反转值的贡献，于是我们考虑有 \(m\) 个只递增的数组，每段的长度为 \(l_1, l_2, l_3 \dots l_m\)。

然后发现，总数组的子数组个数为 \(\frac{n\times(n+1)}{2}\)，而所有递增的子数组的子数组个数为 \(\sum_{i = 1}^m\frac{l_i\times(l_i+1)}{2}\)，于是想到容斥原理，该总数组的反转值就为 \(\frac{n\times(n+1)}{2} - \sum_{i = 1} ^ m\frac{l_i\times(l_i+1)}{2} = k\)。

发现这个思路可以试试 dp，于是开始考虑 dp 的状态，将其设为：

\(dp_{i, j}\) 表示用 \(i\) 个数字能否得到 \(j\) 个递增子数组。

\(g_{i, j}\) 表示上面那种情况时最后一段的长度，这可以方便后面的划分。

那么我们所需要的递增数组可以通过移项得到 \(\frac{n\times(n+1)}{2} - k\)，那么我们想到这样的转移方式：

对于每个i从1到n对于每个j从0到need对于每个len从1到icost = len*(len-1)/2如果j≥cost且dp[i-len][j-cost]存在则dp[i][j] = true, g[i][j] = len

那么我们继续想这种转移方程是否是正确的，发现 \(n \leq 30\)，完全不怕超时，直接拿下。

前面也说了 \(g_{i, j}\) 是状态 \(i, j\) 时最后一段的长度，所以我们可以考虑回溯构造，一遍遍回溯状态的同时将我们存储的长度存进去，因为是回溯，所以我们最后需要倒转一下：

vector<int> res;
int num = n;
for (int len : seg) {for (int j = num - len + 1; j <= num; j++) {res.push_back(j);}num -= len;
}for (int i = 0; i < n; i++) {cout << res[i];if (i < n - 1) cout << " ";
}
cout << endl;

最后就是完整代码：

#include <bits/stdc++.h>
using namespace std;const int N = 35;
const int S = 435;bool f[N][S + 5];
int g[N][S + 5];void solve() {int n, k;cin >> n >> k;int total = n * (n - 1) / 2;if (k > total) {cout << 0 << endl;return;}int need = total - k;memset(f, false, sizeof(f));memset(g, -1, sizeof(g));f[0][0] = true;for (int i = 1; i <= n; i++) {for (int j = 0; j <= need; j++) {for (int len = 1; len <= i; len++) {int cost = len * (len - 1) / 2;if (j >= cost && f[i - len][j - cost]) {f[i][j] = true;g[i][j] = len;break;}}}}if (!f[n][need]) {cout << 0 << endl;return;}vector<int> seg;int cur = n, val = need;while (cur > 0) {int len = g[cur][val];seg.push_back(len);cur -= len;val -= len * (len - 1) / 2;}reverse(seg.begin(), seg.end());vector<int> res;int num = n;for (int len : seg) {for (int j = num - len + 1; j <= num; j++) {res.push_back(j);}num -= len;}for (int i = 0; i < n; i++) {cout << res[i];if (i < n - 1) cout << " ";}cout << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int _ = 1; cin >> _;while (_--) solve();return 0;
}