依据题意直接连边，判断有没有环即可。
复杂度 \(O(n)\)
我们可以发现，相对位置一定的选法不会对答案造成影响，所以我们可以考虑第一天必选。
然后就是一个很经典的 DP 了。
定义 \(f_i\) 为第 \(i\) 天选，前 \(i\) 天最大的工作量。\(sum_i\) 为 \(\sum\limits_{i=1}^{i}a_i\)。
其中：
最后枚举所选的最后一天，然后把剩下的一段加入贡献并取最大值即可。
复杂度 \(O(n^2)\)。
[ABC285F] Substring of Sorted String
有趣的好题。
对于这类问题，我们首先可以想到用线段树来维护。
区间 \([l,r]\) 满足要求，当且仅当满足以下两点：
-
不降。
-
区间 \([1,l)\) 和 \((r,n]\) 中的字符没有大于 \(c_l\) 且小于 \(c_r\) 的情况。
对于第一个条件，我们可以用线段树实时维护一个差分数组，每次查询 \((l,r]\) 中的最小值是否为负即可，注意 \(l\) 不取。
对于第二个条件，我们可以开 \(26\) 个树状数组分别记录每种字符的出现情况。枚举 \((c_l,c_r)\) 中的字符是否在 \([1,l)\) 或 \((r,n]\) 中出现过，如果出现过，则答案为 No。
复杂度 \(O(n\log n)\)。
有源汇上下界网络流。
首先我们要搞明白无源汇上下界网络流问题怎么处理。
以下部分参考 OI-wiki。
定义一条边的下界为 \(b(u,v)\)，上界为 \(a(u,v)\)。
不妨假设这条边已经流过了 \(b(u,v)\)，设其为初始流。然后我们要进行一些调整使得该图满足平衡条件，即每个点入流出流相同。
假设一个点初始流入流量减初始流出流量为 \(M\)。
若 \(M=0\)，此时流量平衡，不需要附加边。
若 \(M>0\)，此时入流量过大，需要新建附加源点 \(S'\)，\(S'\) 向其连流量为 \(M\) 的附加边。
若 \(M<0\)，此时出流量过大，需要新建附加汇点 \(T'\)，其向 \(T'\) 连流量为 \(-M\) 的附加边。
如果附加边满流，则说明平衡条件可以满足。
所以最后跑一边从 \(S'\) 到 \(T'\) 的最大流即可。
有源汇上下界网络流基本类似，只需要对于其初始原点 \(S\) 和汇点 \(T\) 连一条 \((T, S, inf)\) 即可。
回到这道题。
对于 \(1\)，我们直接不管。
对于 \(2\) 和 \(?\)，我们四个方向连边。
然后可以考虑给棋盘黑白染色，黑色连向 \(S\)，白色连向 \(T\)。
对于 \(2\) ，向 S 和 T 连边的时候设其下界为 \(1\)，顺便记录一下初始流 \(in\) 和 \(out\)。
最后对于每个点根据 \(in_i-out_i\) 的值添加附加边即可。
注意，一定要把 dinic 的所有优化加上，少一个都会 T，不要问我怎么知道的。
#include <bits/stdc++.h>
using namespace std;
const int N = 300 + 5, N2 = 3e6 + 5, inf = INT_MAX >> 2;
int n, m, s, t, head[N2], nex[N2], to[N2], val[N2], dep[N2], in[N2], out[N2], cur[N2];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
int tot = 1;
char c[N][N];
queue<int> q;
int d(int i, int j) {return (i - 1) * m + j;}
void add(int u, int v, int w) {
val[++tot] = w;
to[tot] = v;
nex[tot] = head[u];
head[u] = tot;
val[++tot] = 0;
to[tot] = u;
nex[tot] = head[v];
head[v] = tot;
}
int bfs() {
for (int i = 1; i <= t; ++i) dep[i] = 0;
dep[s] = 1; q.push(s); cur[s] = head[s];
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = nex[i]) {
int v = to[i];
if (val[i] > 0 && !dep[v]) {
dep[v] = dep[u] + 1;
cur[v] = head[v];
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u, int cc) {
if (u == t) return cc;
int out_ = 0;
for (int i = cur[u]; i && cc; i = nex[i]) {
cur[u] = i;
int v = to[i];
if (val[i] && dep[v] == dep[u] + 1) {
int tmp = dfs(v, min(val[i], cc));
val[i] -= tmp; val[i ^ 1] += tmp; cc -= tmp; out_ += tmp;
}
}
if (!out_) dep[u] = 0;
return out_;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m; s = n * m + 1; t = s + 1;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
cin >> c[i][j];
if (c[i][j] == '?') {
if (i + j & 1) add(s, d(i, j), 1);
else add(d(i, j), t, 1);
} if (c[i][j] == '2') {
if (i + j & 1) ++out[s], ++in[d(i, j)];
else ++out[d(i, j)], ++in[t];
}
}
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (c[i][j] != '1' && (i + j & 1)) {
for (int k = 0; k < 4; ++k) {
int tx = i + dx[k], ty = j + dy[k];
if (tx < 1 || ty < 1 || tx > n || ty > m || c[tx][ty] == '1') continue;
add(d(i, j), d(tx, ty), 1);
}
}
add(t, s, inf);
s = s + 2; t = t + 2;
int sum = 0;
for (int i = 1; i <= n * m + 2; ++i) {
if (in[i] > out[i]) sum += in[i] - out[i], add(s, i, in[i] - out[i]);
if (out[i] > in[i]) add(i, t, out[i] - in[i]);
}
int ans = 0;
while (bfs()) ans += dfs(s, inf);
if (ans >= sum) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}