Educational Codeforces Round 160 (Div. 2) A~E

A.Rating Increase（思维）

题意：

给出一个仅包含数字的字符串 $s$ ，要求将该字符串按以下要求分成左右两部分 $a, b$ ：

两个数字均不包含前导 $0$
两个数字均大于 $0$
$b > a$

如果有多个答案，输出任意一个均可。

分析：

既然题目要求 $b > a$ ，且不能包含前导 $0$ ，那么，将字符串中第一个数字以及之后的连续的 $0$ 分配给 $a$ ，剩余部分属于 $b$ ，然后判断 $b$ 是否大于 $a$ 即可。

注：使用字符串比较时要注意不能直接使用 $>$ 进行比较，否则比较的是两个字符串的字典序，而不是数字大小。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5e2;vector<int> V[30];void solve() {string s;cin >> s;string a = "", b = "";int i, len = s.size();for (i = 0; i < len; i++) {if (i != 0 && s[i] != '0') break;a.push_back(s[i]);}for (; i < len; i++) {b.push_back(s[i]);}if (b.size() > a.size() || (b.size() == a.size() &&  a < b)) {cout << a << ' ' << b << endl;} else {cout << "-1" << endl;}
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

B.Swap and Delete（思维）

题意：

给出仅包含 $01$ 的字符串 $s$ ，在若干次操作该字符串变为字符串 $t$ :

花费一个金币，并删除字符串中一个字符
免费操作，任意交换字符串中的字符

问，最少花费多少金币，能够使得最后的得到的字符串 $t$ 与原字符串 $s$ 中等长的前缀字符串相同下标的元素全部不同。

分析：

既然操作2不需要花费金币，那么肯定要尽可能的使用操作二。

因此，先记录字符串 $s$ 中 $1$ 和 $0$ 的数量，然后从前往后判断，如果当前 $s_i = 1$ ，那么就把后面的 $0$ 交换过来，并将记录的 $0$ 数量减一，如果交换前发现此时后面已经没有 $0$ 了，那么无论怎么交换，均无法使得这个位置上的元素与原字符串 $s$ 不同，因此所有后面的字符均需使用操作 $1$ 删除，共消耗 $n - i$ 个金币。

$s_i = 0$ 的情况同理。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5e2;void solve() {string s;cin >> s;int n = s.size();int one = 0, zero = 0;int ans = n;for (int i = 0; i < n; i++) {if (s[i] == '0') {zero++;} else {one++;}}for (int i = 0; i < n; i++) {if (s[i] == '1') {if (zero == 0) {cout << n - i << endl;return;}zero--;} else {if (one == 0) {cout << n - i << endl;return;}one--;}}cout << 0 << endl;
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

C.Game with Multiset（数学）

题意：

给出一个允许装下重复元素的集合，并有以下两种操作：

ADD x:将 $2^{x}$ 放入集合
GET w:询问能否取出集合中的若干元素，满足这些元素的总和为 $w$

分析：

对于操作 $1$ ，使用数组 $c n t [i]$ 表示存放的 $2^{i}$ 的元素数量。

对于操作 $2$ ，从大到小遍历集合中的元素，通过运算得到当前剩余数字还能减去多少 $2^{i}$ ，并尽可能多的减去 $2^{i}$ 。如果遍历结束后剩余数字为 $0$ 表示可以组成，不为 $0$ 表示不能组成。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5e2;int mul_set[35];void add(int x) {mul_set[x]++;
}void get(int x) {for (int i = 29; i >= 0; i--) {int cnt = x / (1 << i);//计算最多能减去多少个x -= min(cnt, mul_set[i]) * (1 << i);//注意减去的数量不能比集合中存的数量多}if (x == 0) cout << "Yes" << endl;else cout << "No" << endl;
}int main() {int Case;cin >> Case;while (Case--) {int op, x;cin >> op >> x;if (op == 1) add(x);else get(x);}return 0;
}

D.Array Collapse(DP，前缀和)

题意：

给出一个序列，你可以对序列进行若干次以下操作：

选择一段连续的子段，删除除了子段中最小元素外的所有元素

问：进行若干次操作后（可以不进行操作），能剩下多少种不同的序列？

分析：

考虑DP。

由于每次操作剩下的只有子段中最小的数字，那么可以将情况分为以下两种：

一：当前数字 $p [j]$ 为 $\sim p[j]$ 中最小的，那么有两种方案：
- 1. 只操作前面部分，将 $p [j]$ 拼在前面所有方案后面
- 1. 使用 $p [j]$ 将前面所有数字消除，此时只剩下一种方案
二：当前数字 $p [j]$ 不是 $\sim p[j]$ 中最小的，那么从右往左找到第一个小于 $p [j]$ 的元素 $p [i]$ ,若想在最后的序列中保留 $p [j]$ ，那么能操作的区域只有 $[i + 1, j]$ ，此时的方案相当于在情况一的操作，但区域从 $[1, j]$ 变为 $[i + 1, j]$ 。

使用前缀和以及单调栈优化操作，即可在规定时间内完成本题。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int N = 3e5 + 5e2;
const int MOD = 998244353;int n, a[N], dp[N], pre[N];
stack<int> st;void solve() {while (!st.empty()) st.pop();cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];dp[i] = pre[i] = 0;}int sum = 0;for (int i = 1; i <= n; i++) {while (!st.empty() && a[st.top()] > a[i]) {//维护一个递减的单调栈sum = (sum - dp[st.top()]+MOD) % MOD;st.pop();}if (st.empty()) {dp[i] = (pre[i - 1] + 1) % MOD;}else {dp[i] = ((pre[i - 1] - pre[st.top()] + MOD) % MOD + sum) % MOD;}st.push(i);pre[i] = (pre[i - 1] + dp[i]) % MOD;sum = (sum + dp[i]) % MOD;}cout << (sum + MOD) % MOD << endl;
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

E.One-X(网络流)

题意：

给一个 $n$ 行 $m$ 列的矩阵 $a$ ，矩阵的每个元素为 $0$ 或 $1$ 。

可以执行以下操作任意次数（可能为零次）：选择矩阵中的一个元素并用 $0$ 或 $1$ 替换它。

给出两个数组 $A$ 和 $B$ （长度分别为 $n$ 和 $m$ ）。执行上述操作后，矩阵应满足以下条件:

对于每个 $i \in [1, n]$ ，矩阵第 $i$ 行 $1$ 的个数恰好为 $A_i$ 。
对于每个 $j \in [1, m]$ ，矩阵第 $j$ 列 $1$ 的个数恰好为 $B_j$ 。

计算满足条件的最少操作数。

分析：

本题为网络流中的最小费用最大流，设置一个源点，源点到达每一行的路径容量为 $A_i$ ，费用为 $0$ ，相同的，源点到达每一列的路径容量为 $B_i$ ，费用为 $0$ 。

用边代表矩阵中的元素，一条边的流量为 $1$ ，若一个边是 $0$ （即这个元素是 $0$ ），想要通过这个边流过去（即将这个元素变为 $1$ ），需要 $1$ 的费用，若不流过去，需要 $0$ 的费用。若一个边是 $1$ （即这个元素是 $1$ ），想要通过这个边流过去，需要 $0$ 的费用，若不流过去（将其变为 $0$ ），需要 $1$ 的费用。本题为便于处理，实现网络流，将边是 $1$ 的情况下，想要通过这个边需要的费用设置为 $- 1$ ，若不流过去需要的费用设置为 $0$ 。

注意需要特判总流量，即 $\sum\limits A_i$ 和 $\sum\limits B_i$ ，若 $\sum\limits A_i \neq \sum\limits B_i$ ，则不可能实现，输出 $- 1$ 。

代码：

#include<bits/stdc++.h>using namespace std;
const int MOD = 998244353;
const int MAXN = 1e5 + 5;
const int INF_MAX = 0x3f3f3f3f;
typedef long long LL;struct edge {int v, w, c, ne;
} e[MAXN];int cnt = 1;
int las[MAXN], cur[MAXN];
int dis[MAXN];
bool inq[MAXN], vis[MAXN];
int n, m, s, t, suma, sumb, sum;
int p, q, a[55][55], ls[55], rs[55];
queue<int> q1;void add(int u, int v, int w, int c) {++cnt;e[cnt].v = v;e[cnt].w = w;e[cnt].c = c;e[cnt].ne = las[u];las[u] = cnt;return;
}void Add(int u, int v, int w, int c) {add(u, v, w, c);add(v, u, 0, -c);
}bool SPFA() {for (int i = 1; i <= n; i++) {dis[i] = INF_MAX;inq[i] = 0;}dis[s] = 0;q1.push(s);while (!q1.empty()) {int u = q1.front();q1.pop();inq[u] = 0;for (int i = las[u]; i; i = e[i].ne) {int v = e[i].v;int val = e[i].w;int cost = e[i].c;if (val && dis[v] > dis[u] + cost) {dis[v] = dis[u] + cost;if (!inq[v]) {inq[v] = true;q1.push(v);}}}}return dis[t] < 1e8;
}int dfs(int u, int flow) {vis[u] = true;if (u == t)return flow;int rmn = flow;for (int i = cur[u]; rmn && i; i = e[i].ne) {cur[u] = i;int v = e[i].v;int val = e[i].w;int cost = e[i].c;if (val && dis[v] == dis[u] + cost && !vis[v]) {int fl = dfs(v, min(val, rmn));rmn -= fl;e[i].w -= fl;e[i ^ 1].w += fl;}}vis[u] = false;return flow - rmn;
}LL min_cost() {LL ans = 0;LL res = 0;while (SPFA()) {for (int i = 1; i <= n; i++) {cur[i] = las[i];vis[i] = 0;}LL flow = dfs(s, 1e9);ans += flow;res += flow * dis[t];}if (ans != suma) {cout << "-1" << endl;exit(0);}return res;
}int main() {cin >> p >> q;s = ++n;t = ++n;for (int i = 1; i <= p; i++) {for (int j = 1; j <= q; j++) {cin >> a[i][j];sum += a[i][j];}}for (int i = 1; i <= p; i++) {int x;cin >> x;ls[i] = ++n;Add(s, ls[i], x, 0);suma += x;}for (int i = 1; i <= q; i++) {int x;cin >> x;rs[i] = ++n;Add(rs[i], t, x, 0);sumb += x;}if (suma != sumb) {cout << "-1" << endl;return 0;}for (int i = 1; i <= p; i++) {for (int j = 1; j <= q; j++) {if (a[i][j])Add(ls[i], rs[j], 1, -1);elseAdd(ls[i], rs[j], 1, 1);}}cout << sum + min_cost() << endl;return 0;
}