题解 | #A-D#_牛客博客

出题人题解 Part I(A-D)

A 三子棋

题面简述

给定一个 $3 \times 3$ 的棋盘，共有 $3 \times 3 = 9$ 个格子，初始时每个格子均没有放置棋子。

A 和 B 轮流行动，每次行动的人，必须在当前棋盘上选择一个没有放置棋子的格子，然后在该格子放置一个棋子。

若某棋手放置一个棋子后，该棋子与另外两个棋子（不论是谁放置的都可以）达成三子连珠（即三个棋子连成一条线，水平、垂直、主副对角线均可），则该棋手获胜。

A 总是先手。

请判断，若 A 将第一个棋子放置于格子 $(x, y)$ 后，是否 A 最终会获胜（A，B 总是采取最优策略）。

下标从 1 开始，处在第 $x$ 行、第 $y$ 列的格子坐标为 $(x, y)$ 。

题解

简单博弈。

我们称 ”A 将第一个棋子放置于格子 $(x, y)$ 后，A 最终会获胜“ 这样的格子 $(x, y)$ 为 ”先手必胜的“。

手玩后发现，每一个格子都先手必胜。

首先，显然中间格子先手必胜。

接下来说明四个角也是先手必胜的：

alt

不失一般性，设 A 先在左上角落子，接下来，倘若 B 在上图中淡红色位置落子，那么 A 必然可以下一步达成三点共线，因此 B 只能于其中一处淡蓝色位置落子，紧接着 A 在另一处落子则可获胜。

接下来说明四个边上的点也是先手必胜的：

alt

不失一般性，设 A 现在第一行第二列落子，接下来，B 只能在 X，Y，P，Q 处四选一落子。若 B 在 X 处落子，则 A 接着在 Y 处落子则获胜，反之亦然，P，Q 同理。

代码

#include<bits/stdc++.h>

using namespace std;

int main() {
	
	cout << "YES\n";
	
	return 0;
}

B 药丸

题面简述

牛牛有 $n$ 个属性，第 $i$ 个属性的初始值为 $a_{i}$ ，牛牛想把第 $i$ 个属性的值变为目标值 $b_{i}$ 。

现在牛牛 $2 \times n$ 种不同颜色的药丸，吃一个药丸会产生一个效果。同种颜色的药丸效果相同，不同颜色的药丸效果不同。

每种颜色的药丸对应以下效果之一：

第 1 个属性值 + 1
第 1 个属性值 - 1
第 2 个属性值 + 1
第 2 个属性值 - 1
......
第 n 个属性值 + 1
第 n 个属性值 - 1

以上描述了 $2 \times n$ 种效果，它们与 $2 \times n$ 种颜色的药丸一一对应。

开始时牛牛并不知道药丸颜色与药丸效果的对应关系。若牛牛吃一个药丸，则会获得该颜色药丸对应的效果，并且知道该颜色的药丸对应的效果。

牛牛通过吃药丸来改变自己的属性值。求在最坏的情况下，牛牛要吃多少药丸才能将所有属性从初始值变为目标值。

题解

思维。

若 $a$ 数组与 $b$ 数组相同，则输出 0。

否则，牛牛每想要让一个属性往某个方向变换（增大或减小），在最坏的情况下，牛牛吃到的前 $n$ 个不同的药丸都将它的属性初始值往目标值的反方向变化（若初始值与目标值相等则往任意方向变化），但至此牛牛就再也不会去吃这些负面作用的药丸了，接下来的每个药丸都是有用的，因此答案为 $\sum\limits_i(|a_i - b_i| + 2)$ 。

上式子中的 + 2 表示最坏情况下，牛牛的属性值被远离目标值后，需要额外 1 个药丸“补”回来。

代码

代码 - XLor Paste

C 01树-简单版本

题面简述

注意，本题的简单版本与困难版本的区别在于，简单版本中 $n$ 为偶数，要求 0 和 1 的数量相等，而困难版本中 $n$ 为奇数，要求 0 和 1 的数量相差不超过 1。

现有一个 $n \times n$ 的方格，保证 $n$ 为偶数，初始时方格的每个格点都为空，你需要在方格的每个格点都填上 0、1 其中一个数字，然后考虑这样一张图：

方格中的每一个格点视为一个点。
两个数字相同的、以边相邻的方格之间视为存在一条边。

你需要构造一个填数方案并输出该 01 方格，满足：

这张图中，所有 0 所在格点相互连通，但不能出现环；所有 1 所在格点相互连通，但不能出现环。
方格中 0 的数量与方格中 1 的数量相等。

可以证明，对于任意合法的输入均保证有解。

题解

构造，实现。

思考题目条件，可以想到应该可以构造一个对称的结构，以下两种做法都基于对称的角度解题。

做法 1：构造一个类似于两把刷子镶嵌的结构：

alt

做法 2：构造一个螺旋的结构：

alt

接下来要做的事情就是实现这样一个图形的输出。

可以看到，对于做法 1，只需要逐行输出即可，首尾行全是 0 或 1，中间 01 交错。

对于做法 2，我们如果把图中的同***块视为点的运动轨迹，则会发现这个点从左上角出发，先向右移动 $n$ 步，顺时针转 90° 后向下移动 $n - 2$ 步，顺时针转 90° 后向下移动 $n - 2$ 步，顺时针转 90° 后向下移动 $n - 4$ 步，顺时针转 90° 后向下移动 $n - 4$ 步......把规律观察出来后依旧不难实现。