痛诉：捆绑测试点毁我青春！！！

这几天考了好几场， 每一场发挥都不怎么样呢
真好意思说
所以就把这几天考试的题目和解法,思路, tip在一起写了.

Day 1

见以前的Blog

Day 2

小tip：看到棋盘可以联想二分图
T2：chess
给出一个$ n * m $的矩阵， 要求甲乙两方轮流移动棋子，不能移动的人判负
很明显，我们可以用二分图来尝试给这道题建模。
一个很明显的思路是给相邻的可行走的点连上边，然后考虑我们在棋盘上的走否如何映射到图上。

比如这个图

\(* .\)
\(. .\)

我们可以发现当我们A在\((1,2)\)的时候，B只能向\((2,2)\)走。反映在图上就是发现A只有一条边连向B。
我们不难再手摸几个二分图， 我们可以发现我们一定是沿着一条
左边 -> 右边 -> 左边 循环的方式走下去， 直到一方没有路为止。

是不是很熟悉？ 是的， 这个和我们的增广路十分相像。我们可以尝试套用增广路的算法来解决这个问题。
证明：我们可以沿着一条匹配边走， 对面只能走到非匹配边， 然后重复这一策略即可。

然后我们只需要找到不论如何都在最大匹配中的点即可。

T3 :

题意描述：

给出一个序列， 问你将其划分成x段的最大或和。
定义每一段的权值是这一段的元素的和。

思路：

首先考虑贪心：
我们知道这个式子是不成立的：
\((x | y) <= x | (y + 1)\)
所以我们可以知道我们无法通过整体的DP去高效的解决这个问题， 所以我们考虑逐数位的DP， 因为对于每一位上这个式子成立。

观察数据范围：
不难发现所有子任务的和是一百分， 说明做法一定和子任务条件强相关。（大部分题目都是如此）

我们发现子任务可以大致分为两种。一种N较小， 一种N较大但是对A有限制。我们先考虑N较小的情况。

我们考虑dp。因为高数位一定比低数位重要，所以我们需要尽可能地让高数位是0.
我们从高向低dp， 定义\(dp(i,j,k)\) 表示在第i位上前j个数中划分为k段且在k后断开来保持i位位0的方案是否存在。
（有点拗口，多读几遍）
dp式子非常好写， 而且可以剪枝。

如果对A有限制， 我们可以更换dp式子 ， 定义
\(dp(i,j)\) 在前i位中保持前j位为0所需要的最小段数。 dp即可。

T4：不会， 打暴力吧。