SYOI2022 Round 2 Editorial

Task 1

使用网络流最小割。

考虑建图：将原矩阵黑白染色，黑格连源点，白格连汇点，弧容量为方格中的数。

为了让最小割满足题目中的含义，还要将相邻的黑白格连一条容量为无穷的边。

这样，为了让图不连通，就必须要割掉一些边，最小割可以求出来最小花费。

用总和减去最小割即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int INF = 0x3f3f3f3f;
const int maxn = 35;
int fx[] = {0 , -1 , 0 , 1},fy[] = {1 , 0 , -1 , 0};
using namespace std;
struct edge {
	int to,next,cap;
	edge() {
		to = next = cap = 0;
	}
	edge(int to,int next,int cap):to(to),next(next),cap(cap){}
}Edge[maxn * maxn * maxn];
int head[maxn * maxn << 1],num_edge = -1;
inline void add_edge(int from,int to,int flow) {
	Edge[++ num_edge] = edge(to , head[from] , flow);
	head[from] = num_edge;
}
int n,m;
inline bool judge(int x,int y) {
	return x >= 1&&x <= n&&y >= 1&&y <= m;
}
inline int get(int x,int y) {
	return (x - 1) * m + y;
}
queue<int> q;
int level[maxn * maxn << 1],cur[maxn * maxn << 1];
inline bool bfs(int s,int t) {
	memset(level , 0 , sizeof(level));
	q.push(s);
	level[s] = 1;
	while(!q.empty()) {                                         
		int u = q.front();
		q.pop();
		for(int i = head[u];~ i;i = Edge[i].next) {
			int v = Edge[i].to;                             
			if(!level[v]&&Edge[i].cap > 0) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return level[t] != 0;
}
inline int dfs(int x,int t,int maxflow) {
	if(x == t||!maxflow)return maxflow;
	int f,flow = 0;
	for(int i = cur[x];~ i;i = Edge[i].next) {
		int v = Edge[i].to;                                
		cur[x] = i;
		if(level[v] == level[x] + 1&&(f = dfs(v , t , min(Edge[i].cap , maxflow)))) {
			if(!f) {
				level[v] = 0;
			}
			Edge[i].cap -= f;
			Edge[i ^ 1].cap += f;             
			flow += f;
			maxflow -= f;
			if(!maxflow)break ;
		}
	}
	return flow;
}
inline int Dinic(int s,int t) {
	int flow = 0;
	while(bfs(s , t)) {
		memcpy(cur , head , sizeof(head));                   
		flow += dfs(s , t , INF);
	}
	return flow;
}
int main() {                   
	freopen("grid.in","r",stdin);
	freopen("grid.out","w",stdout);
	memset(head , -1 , sizeof(head));
	scanf("%d%d",&n,&m);
	int tot = 0;
	int s = n * m + 1,t = n * m + 2;
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= m;++ j) {
			int pos;
			scanf("%d",&pos);
			tot += pos;
			if((i + j) & 1) {
				add_edge(s , get(i , j) , pos);
				add_edge(get(i , j) , s , 0);
				for(int k = 0;k < 4;++ k) {
					int x = fx[k] + i,y = fy[k] + j;
					if(judge(x , y)) {
						add_edge(get(i , j) , get(x , y) , INF);
						add_edge(get(x , y) , get(i , j) , 0);
					}
				}
			}
			else {
				add_edge(get(i , j) , t , pos);                                                          
				add_edge(t , get(i , j) , 0);
			}
		}
	}
	printf("%d",tot - Dinic(s , t));
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Task 2

本题有两种解法。

首先，采用交换式的排序显然不可行，考虑桶排序。

Solution 1

建立 $26$ 棵线段树，分别存储 $a \sim z$ 在区间中出现的数量。

区间修改在线段树的板子上稍加修改即可。

区间排序就是用线段树统计出 $[l,r]$ 中 $a \sim z$ 的数量，再进行区间修改。

实现稍微有点复杂，可以参考我的代码。

Solution 2

注意到数据均为随机构造，那么可以使用珂朵莉树代替线段树。

这样写时间复杂度极低，比线段树快十几倍。

（珂朵莉树：[Willem, Chtholly and Seniorious]）

  代码

Task 3

懒得写了自己看洛谷上的题解叭QAQ

完整版实在是太长了，所有分析就列在博客里了，这里简述 AC 做法。

不难观察到最后一段和越小答案越小。

令 $dp(i)$ 为 $i$ 结尾时的最小取值，$pos_i$ 为 $i$ 取得最小值时所处段前一段的最后一个元素。

有 $dp(i) = dp(pos_i) + (s_i - s_{pos_i})^2$

求出 $a$ 的前缀和数组 $s$。

用一个单调队列维护 $2\times s_j - s_{pos_j}$，当队首和队首后一个元素都满足 $2 \times s_j - s_{pos_j} \le s_i$ 时，循环删除队首。

由于数据很大，只存储 $pos$ 数组，答案最后统一计算即可。

搬这题只是为了庆祝窝洛谷过审的第一篇题解awa

首先这种格式一看就是要用数据结构维护，但我们会发现由于 $a$ 数组和 $k$ 的值都是变化的，普通数据结构几乎难以维护。

遇到这种问题，我们可以尝试往分块或者根号分治上想。

顺着这个思路，考虑寻找一下答案的性质。

发现当 $k \gt \sqrt{N}$ 时，操作时间复杂度最多只有 $O(\sqrt{N})$。

那要是 $k \le \sqrt{N}$ 怎么办？

这个时候 $k$ 已经非常小了，我们可以把 $k \le \sqrt{N}$ 的每一种情况都预处理出来。

在询问时，若 $k \gt \sqrt{N}$ 时，直接暴力模拟，反之直接输出我们预处理的结果就好了。

相当于用空间换时间，二者复杂度均为 $O(N\sqrt{N})$。

根号分治的有趣运用还有很多，这道题基本上相当于模板，还有一道类似的题目 哈希冲突

可以尝试做一做，cb 大佬的题解

看到这道题，最朴素的想法是用 DFS 求解。

显然这样搜出来的状态数量非常庞大，时间复杂度无法承受，考虑换用 DP 遍历所有状态。

这里有两个方法。

法一：(60pts)

设 $f_i$ 表示正整数 $i(i \in N^+)$ 分解后的最大乘积。

这种情况下乍一看似乎无法转移，因为有后效性，前面的数分解出 $k$ 那么后面就不能分解出 $k$ 了。

既然如此，可以尝试改变状态，多加几维限制。

思考后得出：设 $f(i,j)$ 表示正整数 $i(i \in N^+)$ 分解出的最大整数为 $j$ 时的最大乘积。

初始状态：$\forall i \in [0,n],f(0,i) = 1$

状态转移方程：$f(i,j) = \max\limits_{k=1}^{j - 1} f(i - j,k) \times j$

最终状态 $\max\limits_{i=0}^n f(n,i)$

然而这样是 $O(N^3)$ 的，考虑优化。

令 $s(i,j) = \max\limits_{k=1}^j f(i,k)$

则状态转移方程会变成：$f(i,j) = s(i - j,j - 1) \times j$

初始 $\forall i \in [0,n],s(0,i) = 1$

答案为 $s(n,n)$

这样用 unsigned long long 可以过 $60%$ 的测试数据，但换成高精度则会出现一堆绿色的字母。

（upd:测试时发现，其实根据数学知识，每次转移的 $j$ 并不会太大，有兴趣的可以打个表把 $j$ 的范围缩小些，这样应该能直接 AC）

CODE

法二：

（此方法我暂时给不出严谨的证明，只能感性理解给个大概意思）

再仔细想一想，难道这个 DP 就一定要二维吗？

再想一想，假设我们把 $i$ 分解为 $\{a_1,a_2\ldots a_k \}$，要枚举一个 $a_j(1\le j \le k)$ 进行状态转移。

不难发现，每个数字分别顺序的先后并不影响它对答案的贡献。

换言之，不论枚举的顺序如何，最优状态也一定会被遍历到。

基于此，我们令 $f_i$ 为 $i$ 分解的最优答案，用 bitset 或者 bool 数组记录一下哪些数字被选上了，转移一下就好了。

这个转移方程相当简单，就不写了，详情见 AC 代码。

看到这题的数据规模，我的第一想法是树状数组离线统计。

毕竟 $5\times 10^5$ 对于线段树什么的会非常吃力，我对 CCF 的评测机并不抱信心。

（然而好像有人用莫队 $O(N\sqrt{N\log N})$ 硬卡过去了）

考虑将所有询问离线，按右端点递增排序，思考怎样快速计算每个点的贡献。

在尝试了很多办法后，不妨回到题目本身，“丹钓战”这个名字似乎在暗示我们使用单调栈。

于是尝试先 $O(N)$ 求出距每个点 $i$ 最近的不合法位置 $L_i$。

然后可以发现，对于每个询问，只需要计算 $\sum\limits_{i=l}^r [L_i \notin [l,r]]$ 即可。

这个问题就非常简单了，和 HH的项链 类似，树状数组离线统计即可。

当然也可以用莫队/主席树，但是效率会比较感人。

时间复杂度 $O(Q\log N+N)$。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500005;
int n,m,a[maxn],b[maxn],stk[maxn],top,L[maxn];
struct query {
	int x,y,id;
	query() {
		x = y = id = 0;
	}
	bool operator < (const query& p)const {
		return y < p.y;
	}
}Q[maxn];
int c[maxn];
int lowbit(int x) {
	return x & -x;
}
void add(int x,int y) {
	if(!x)return ;
	for(;x <= n;x += lowbit(x))c[x] += y;
	return ;
}
int query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))ans += c[x];
	return ans;
}
int ans[maxn];
int main() {
	freopen("noi_online2022_stack.in","r",stdin);
	freopen("noi_online2022_stack.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
	for(int i = 1;i <= n;++ i)scanf("%d",&b[i]);
	for(int i = 1;i <= n;++ i) {
		while(top&&(a[stk[top]] == a[i]||b[stk[top]] <= b[i]))stk[top --] = 0;
		L[i] = stk[top];
		stk[++ top] = i;
	}
	for(int i = 1;i <= m;++ i) {
		Q[i].id = i;
		scanf("%d%d",&Q[i].x,&Q[i].y);
	}
	sort(Q + 1 , Q + 1 + m);
	for(int i = 1,j = 1;i <= m;++ i) {
		for(;j <= Q[i].y;++ j) {
			if(!L[j])continue ;
			add(L[j] , 1);
		}
		ans[Q[i].id] = Q[i].y - Q[i].x + 1 - query(Q[i].y) + query(Q[i].x - 1); 
	}
	for(int i = 1;i <= m;++ i)printf("%d\n",ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
} 

题目数据规模不大，可选方法很多，考虑贪心。

本文中，称第 $i$ 行/列 的要求士兵数量为：第 $i$ 行/列 的名额。

很显然，对于第 $i$ 行第 $j$ 列的士兵，如果它可以放，并且能一次性占掉第 $i$ 行和第 $j$ 列的两个名额，称这样的士兵为 ”好士兵“。

根据贪心思路，我们当然希望“好士兵”的个数尽量的多，那么剩下的未被占掉的名额自然只能由一次性只占一个名额的士兵占掉。

那么：怎样让“好士兵”最多呢？

由题目可知，第 $i$ 行/列 的“好士兵”个数不能超过该 行/列 的名额总数。

这一点和网络流的容量限制很像，联想到网络流，进行建模：

设第 $i$ 行名额数为 $A_i$，对应点 $C_i$，第 $j$ 列名额数为 $B_j$，对应点 $D_j$。

分别建立两个顶点：起点 $S$，终点 $T$。

$S$ 向每个 $C_i$ 连一条容量为 $A_i$ 的边，每个 $D_j$ 向 $T$ 连一条容量为 $B_j$ 的边。

如果 $(i,j)$ 合法，由 $C_i$ 向 $D_j$ 引一条容量为 $1$ 的边。

这样，$S \to C_i \to D_j \to T$ 的一条路径就代表了 $(i,j)$ 上放置一名“好士兵”。

该图的最大流对应的即是最多的可放置的“好士兵”的个数，设为 $F$ ，则答案为

$\sum\limits_{i=1}^n A_i + \sum\limits_{j=1}^m B_j - F$

参考代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
const int maxn = 10005;
const int maxm = 1000005;
int L[maxn],R[maxn],sum1[maxn],sum2[maxn],tot;
bool legit[maxn][maxn];
int head[maxm],ver[maxm << 1],nxt[maxm << 1],cap[maxm << 1],cur[maxm],cnt = -1;
void add(int u,int v,int t) {
	ver[++ cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
	cap[cnt] = t;
	return ;
}
queue<int> q;
int level[maxn];
bool bfs(int s,int t) {
	memset(level , 0 , sizeof(level));
	q.push(s);
	level[s] = 1;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = head[u];~ i;i = nxt[i]) {
			int v = ver[i];
			if(cap[i]&&!level[v]) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return level[t] > 0;
} 
int dfs(int x,int t,int maxflow) {
	if(x == t||!maxflow)return maxflow;
	int flow = 0,f;
	for(int& i = cur[x];~ i;i = nxt[i]) {
		int v = ver[i];
		if(level[v] == level[x] + 1&&(f = dfs(v , t , min(maxflow , cap[i])))) {
			if(!f) {
				level[v] = 0;
				break ;
			}
			flow += f;
			maxflow -= f;
			cap[i] -= f;
			cap[i ^ 1] += f;
			if(!maxflow)break ;
		}
	}
	return flow;
}
int Dinic(int s,int t) {
	int flow = 0;
	while(bfs(s , t)) {
		memcpy(cur , head , sizeof(head));
		flow += dfs(s , t , 0x3f3f3f3f);
	}
	return flow;
}
int main() {
	freopen("occupy.in","r",stdin);
	freopen("occupy.out","w",stdout);
	memset(head , -1 , sizeof(head));
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1;i <= n;++ i)
		for(int j = 1;j <= m;++ j)legit[i][j] = true;
	for(int i = 1;i <= n;++ i)scanf("%d",&L[i]),sum1[i] = m,tot += L[i];
	for(int i = 1;i <= m;++ i)scanf("%d",&R[i]),sum2[i] = n,tot += R[i];
	for(int i = 1;i <= k;++ i) {
		int x,y;
		scanf("%d%d",&x,&y);
		legit[x][y] = false;
		-- sum1[x];
		-- sum2[y];
	}
	bool flag = true;
	for(int i = 1;i <= n;++ i) {
		if(sum1[i] < L[i]) {
			flag = false;
			break ;
		} 
	}
	for(int i = 1;i <= m;++ i) {
		if(sum2[i] < R[i]) {
			flag = false;
			break ;
		}
	}
	if(!flag) {
		puts("JIONG!");
		return 0;
	}
	int S = n + m + 1,T = n + m + 2;
	for(int i = 1;i <= n;++ i) {
		add(S , i , L[i]);
		add(i , S , 0);
	}
	for(int i = 1;i <= m;++ i) {
		add(i + n , T , R[i]);
		add(T , i + n , 0);
	}
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= m;++ j) {
			if(legit[i][j]) {
				add(i , j + n , 1);
				add(j + n , i , 0);
			}
		}
	}
	printf("%d\n",tot - Dinic(S , T));
	return 0;
}