#include<iostream>

#include<algorithm>

using namespace std;

//协助计算马所能到达点

int fx[9]={0,-2,-1,1,2,2,1,-1,-2},fy[9]={0,1,2,2,1,-1,-2,-2,-1};

int ax,ay,mx,my;

long long ans;

long long f[30][30];

bool v[30][30];

int main()

{   freopen("pj024.in","r",stdin);

freopen("pj024.out","w",stdout);

   cin>>ax>>ay>>mx>>my;

   ax++;ay++;mx++;my++;

   //设置原点的路径数为1

   f[1][1]=1;

   //标记马所能走到的点

   v[mx][my]=1;

   for(int i=1;i<=8;i++)

   v[mx+fx[i]][my+fy[i]]=1;

   for(int i=1;i<=ax;i++)

       for(int j=1;j<=ay;j++)

       {

        //如果是马能走到的点，则跳过此次循环

           if(v[i][j])continue;

           //如果不是，则将能到达该点的路径数赋值为能到达它左边那点的路径数和能到达它上面那点的路径数之和（典型dp思想）

           f[i][j]=max(f[i][j],f[i-1][j]+f[i][j-1]);

       }

   //最终输出能到达B点的路径数

   cout<<f[ax][ay];

   cin>>ax;

   return 0;

}

对于一个「可调整的」 $n\times n$ 的 $01$ 矩阵，考虑在每一行与每一列的两个点间连一条边。

那么我们将得到一个 $2n$ 个点，$2n$ 条边的无向图，图中的每个连通块都是一个边数为偶数的简单环

https://blog.csdn.net/yanshannan/article/details/77453049 给出了一个图示。

可以发现，对于一个连通块，交换任意两行或两列之后，这些点仍然保持联通。

因此，每个连通块的大小确定了一个「可调整的」矩阵的等价类。

现在相当于把 $2n$ 个点拆分成若干连通块，求方案数。可以发现这里连通块的大小必须 $\ge 4$。

显然这等价于把 $n$ 无序地拆分成若干个 $\ge 2$ 的数。

考虑 DP，设 $f(i,j)$ 表示将 $i$ 无序地拆分成 $j$ 个 $\ge 2$ 正整数的方案数（其中 $i\ge 2j$），则有：

$$f(i,j)=f(i-2,j-1)+f(i-j,j)$$

其含义为，若拆分出的最小数为 $2$，那么相当于将除去 $2$ 后剩下的 $i-2$ 分成 $j-1$ 份；否则我们把拆出的每个数都减一，这部分的方案数就与 $f(i-j,j)$ 一一对应。

初值为 $f(0,0)=1$，答案为 $\sum_{2j\le n} f(n,j)$。

于是就做完了，时间复杂度 $O(n^2)$。

#include<bits/stdc++.h>//万能头文件

using namespace std;

int main(){

freopen("aplusb.in","r",stdin);//输入文件

freopen("aplusb.out","w",stdout);//输出文件

int a,b,c;//定义变量

cin>>a>>b;//输入

c=a+b;

cout<<c;//输出

fclose(stdin);

fclose(stdout);//关闭文件

return 0;//养成好习惯

}

（测试题解）

(注：此文设题中输入的图为 $G_1$，对应的完全图为 $G_2$，对应的补图为 $G_3$)

首先不难想到暴力思路：直接将 $G_2$ 建出来，跑一遍 MST 即可。

然而这样时间显然无法承受。

但是这道题显然有别的思路，考虑从特殊的边长：$0$ 和 $1$ 入手。

题中所给的边长为 $1$ 的边视为断边，建出 $G_3$，不难发现，答案就是补图的连通块数量减 $1$。

我们只需要算出连通块的数量即可，可以用并查集处理。

然而边数仍然很多，直接暴力求连通块很容易 TLE/MLE。

这时这个题目巧妙的地方就来了：我们可以将求解拆成两块，再合并答案。

首先发现，在原图 $G_1$ 中，设点 $i$ 的度数为 $deg_i$，不难发现$\sum\limits_{i=1}^n deg_i =2m$

那么根据抽屉原理，其中度数最小的点度数不超过 $\frac{2m}{n}$ ，设该点为 $u$ .

则可以先将 $G_1$ 中与 $u$ 没有连边的点和 $u$ 暴力合并，和 $u$ 有连边的点存储下来，暴力合并。

其中暴力合并的复杂度为 $O(N)$，则整体的时间复杂度为 $O(N+N\times \frac{2m}{N})=O(N+M)$.

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