JXOI Round 1 文字题解

T1 农场

注意每次给你的是对角两个对角，所以共有四种可能，左上右下，左下右上，两个点交换又会产生两种情况。

我们枚举这四种情况，为了方便，统计最终答案的左下和右上角，输出结果即可。

注意赋初始值。

T2 游戏

既然 ，而且这题还是博弈论，那么可以猜测这题正解是 推结论。

对于博弈论的题，通常都是打表找规律，那么对于此题，我们也可以打一些范围比较小的表来得到结论。

设 ，这组数据有样例解释，先手动不了，所以无解。

设 ，可以发现先手只要进行操作三即可获得胜利。

设 ，此时先手向上移动一格即可获得胜利。

设 ，此时先手向右移动一格即可获得胜利。

设 ，此时操作三对先手不利，所以先手肯定是要向右或向上移动，对于后手，此时进行操作三是最优策略，移动后先手只能移动到 ，先手失败。

设 ，进行操作三移动到 ，此时的情况对于后手相当于是 时的情况，这种情况在上文已经推导过了，所以后手必输，即 时，先手进行操作三必胜。

设 ，容易发现向上移动则先手必胜。

设 ，此时相当于把上一种情况转了一下，先手向右移动可以必胜。

通过以上的打表，可以得到一下表格：

推测出结论：

结论一：

当 和 都为奇数时，无解，输出 −1。

结论二：

当 和 都为偶数时，输出 3。

结论三：

当 为奇数， 为偶数时，输出 1。

结论四：

当 为偶数， 为奇数时，输出 2。

T3 中位数

01 背包的思想 + bitset 优化

设 为用前 个数，能否组成数字

转移：

省去第一维，再用 bitset 进行整体的转移

再看中位数的选取

设所有数的总和为 ，如果 ，那一定有

所以 是对称的

直接从 开始扫即可

T4 二进制

可以想想，对于一个数 在什么情况下会对答案产生贡献？假设在二进制下 在 的基础 上产生了 个进位，也就是说 在二进制下第 位都由 变为了 , 而第 位则由 变为了 , 而其他位则不变。那么，也就是说，当 时，会对答案产生贡献。

所以，可以枚举进位个数 , 若 , 则答案会增加。那么会增加多少呢？用排列组合的思想，即在 位下已经确定了 位的数字个数，也就是对于第 位来说，可以 有两种选择：该位为 或者 , 所以这样的数字个数为 。由于题目要求用二进制的形式输出答案，所以在用二进制存储答案的数组的第 设为 即可。

还需注意判断边界，即 或 的情况，若它们满足条件，则各自会产生 的贡献，即答案的第 位增加 。由于第 位可能会增加两个 , 所以要处理下进位。