5.20 NOI 模拟

万年不更题解的鸽子来更题解了

\(T1\)矩阵

是个炒鸡恶心的推式子题

求\([x_1,x_2],[y_1,y_2]\)内部的数字和,把矩阵分成四份比较容易想到,差分也容易想到

\(Sum[x][y]\)表示以\((x,y)\)为右下角的矩形内部和

\(Ans=Sum[x_2][y_2]-Sum[x_1-1][y_2]-Sum[x_2][y_1-1]+Sum[x_1-1][y_1-1]\)

我们对于每个\(Sum[x][y]\)分别求出在四个三角形内部的值

对于每个区域我们可以把重合部分分成常数个等腰三角形,每个三角形内部的值可以用确定一个点的值还有边长算出来,这个值是一个函数,可以使用插值把函数插出来(也可以手推)

我们对于每个区域,只需要求出每个三角形的插值即可

\(T2\)汇合

讲题人\(:\)直接看题解就好了,不会证明

结论\(:\)在一个点能到达的所有位置上,分界线处附近的整点最优

首先比较显然的,我们能走的方向内部一定可以到达,题目上又证明必然有解,那么最优解肯定是在两者交点处比较优

\(T3\)连接

感觉这类题我见了不止一遍,但是问的东西每一遍都不一样\(aaa\)

首先考虑只连小于等于\(m\)条边能否连通,原图连通至少需要新增\(n+m-1-k\)条边

\(m+k>=n+m-1\ , n<=k+1\)

首先左边\(n\)个点和右边\(i%n=poz\)的点相连,我们只需要判断左边的点是否联通即可

如果前\(m\)条边不满足,我们现在连边\((u,v)\)由于前\(m\)条边已经让\(i->i\% n,\)那么我们可以视为\(u->v\%n\)

我们现在连边\(i+m,\)相当于左部内部\(i+m\%n->i\% n\)连边

我们现在新添一个右部,然后把左部看为右部,右部看为左部,那么我们这时候和原来匹配的效果是一样的

貌似可以用\(gcd(m,n)=gcd(n,m\%n)\)解释,其实画个图就很好解释了