规律：当第一行和第一列的元素确定之后，整个矩阵的元素也就确定了，而第一行和第一列的元素有 2h+w种可能


设两个点间第一种斜线有n1条，第二种斜线有n2条，答案是max(n1,n2)，路径上尽量走直线交点
a>=2    2a>=4    因此相交得到的正方形对角线>=4    每次有足够的移动空间
为了计算间隔的直线数目，采用坐标系变换，令x'=x+y, y'=x-y
这样计算比较方便
标程：
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (100+10)
#define max2 (1000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (998244353)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
int a,b,x1,y1,x2,y2;
RD2(a,b),RD2(x1,y1),RD2(x2,y2);
int x,y;
x=x1,y=y1;
x1=x+y,y1=x-y;
x=x2,y=y2;
x2=x+y,y2=x-y;
a<<=1,b<<=1;

x1=x1/a+(x1>0);//非负半平面含有直线x=0，y=0
y1=y1/b+(y1>0);
x2=x2/a+(x2>0);
y2=y2/b+(y2>0);
printf("%d",max(abs(x2-x1),abs(y2-y1)));
return 0;
}

图论综合题
当完全子图的时候无法再压缩
铺垫：二分图判定的充要条件有两个，一个是能否二染色，另一个是不含边数为奇数的环

借助dfs判断能否二染色，得出是否有奇环，如果有奇环则无解
粗略证明:压缩奇环，最后至少会剩一个三角形，无法压缩；
奇环外的点压缩到奇环上不改变奇环的长度
所以最后总要压缩奇环

借助dfs同时将联通块标号，
分别bfs求出每个连通块的直径（任意两点之间最短路的最大值），
沿着直径压缩总能压缩得到最长链（不知如何证明）
相加，得到答案


已知一棵树的前序，并且相同深度的地方优先输出较小数字，问这样的树有多少种。
区间记忆化搜索
设dp[i][j]代表序列第i位到第j位的方案数。
第i位必然是树的根，i+1位是最左子树的根，
首先可以枚举属于最左子树的区间，起点是i+1 , 终点是i+1，i+2...一直到j，得到区间[i+1,i+1], [i+1,i+2],.....[i+1,j]
设最左子树的右端点end_of_left
子问题1：（i+1，end_of_left）
剩下的点变成了，以i为根，区间为[end_of_left+1, j ]的子问题
注意，序列[end_of_left+1, j ]不含根节点，和上面的形式不符。
解决方法是把根节点看成end_of_left。以i为根，区间为[end_of_left+1, j ]的子问题，数值上等于end_of_left以为根，区间为[end_of_left+1, j ]的子问题
子问题二：（end_of_left，j）
dp[i][j]=dp[i+1][end_of_left]*dp[end_of_left][j]




算贡献的简单题