1. 题目链接

Kickstart Round H 2019 B. Diagonal Puzzle

2. 题目描述

有一个 $N\times N$ 的正方形棋盘，棋盘上每个位置要么是黑子，要么是白子。现在需要用最少的步数将白子全部编程黑子。

每一步你可以任意选择一条该正方形的对角线，然后将对角线上的所有棋子都翻转 (白变黑 or 黑变白)。

下面是 $3\times 3$ 正方形的10种对角线：

1
2
3
4
5
6
7
8

/..      ./.      ../      ...      ...
...      /..      ./.      ../      ...
...      ...      /..      ./.      ../


...      ...      \..      .\.      ..\
...      \..      .\.      ..\      ...
\..      .\.      ..\      ...      ...

3. 解题思路

对于 $N\times N$ 的正方形来说，共存在 $\mathbf{4N-2}$ 条对角线。然后，对于一条对角线，多次翻转是没有意义的（翻转 2 次跟翻转 0 次没有区别），就是说每条对角线只有两种状态：翻转、不翻转。

然后对于棋盘中的每一个位置，都存在 2 条对角线经过该位置：

• 当这个位置为白子时，这两条对角线的状态必须是互斥的；
• 当这个位置为黑子时，这两条对角线的状态必须是相同的。

这样，整个问题就是变成了对 对角线的2-SAT/二染色问题。而上述两种情况，可以看成染色的限制条件。

那我们对每个连通块进行 dfs 进行二染色，然后统计染色为 0、1 的节点个数。如果染色为 0 的节点个数较少，我们则翻转连通块中所有染色为 0 的节点；反之，则翻转染色为 1 的节点。

1. 题目链接

Kickstart Round G 2019 C. Shifts

2. 题目描述

Aninda 和 Boon-Nam是一个小型美术馆的保安。他们的工作包括 $N$ 个班次 $(1\le N\le 20)$。在每个班次中，两个警卫中的至少一个必须工作。

两位后卫对每个班次都有不同的偏好。对于第 $i$ 个班次，如果 Aninda 工作，她将获得 $A_i$ 幸福点，而如果 Boon-Nam 工作，她将获得 $B_i$ 幸福点。

如果两个警卫都获得至少 $H$ 个快乐点，他们将感到高兴。守卫会感到高兴的班次有几种不同的分配方式？

如果 Aninda 在一个作业中工作而不是另一工作，或者 Boon-Nam 在一个作业中工作而在另一工作中不工作，则认为两个作业是不同的。

3. 解题思路

3.1 中途相遇+线段树

把 $N$ 天等分成 前 $\frac{N}{2}$ 天、后 $(N-\frac{N}{2})$ 天。然后分别枚举前 $\frac{N}{2}$ 天、后 $(N-\frac{N}{2})$ 天的所有可能的组合，并对每种组合计算 Aninda 和 Boon-Nam 的幸福分数。

然后对于每个后$(N-\frac{N}{2})$ 天中的 $(\mathrm{right}_A, \mathrm{right}_B)$ ，我们计算前 $\frac{N}{2}$ 天的幸福点对 $(\mathrm{left}_A, \mathrm{left}_B)$的个数，其中 $\mathrm{left}_A\ge (H-\mathrm{right}_A)$，$\mathrm{left}_B\ge (H-\mathrm{right}_B)$。

我们对前 $\frac{N}{2}$ 天、后 $(N-\frac{N}{2})$ 天的幸福点对都进行一次升序排序，先排序第一维，再排序第二维。

然后，从小打大枚举排序后的后 $(N-\frac{N}{2})$ 天的幸福点对。对于每个后$(N-\frac{N}{2})$ 天中的 $(\mathrm{right}_A, \mathrm{right}_B)$ ，找到所有第一维符合 $\mathrm{left}_A\ge (H-\mathrm{left}_B)$ 的幸福点对，将改点对的 第二维 $\mathrm{right}_A$ 插入到线段树中。然后统计线段树中，第二维的幸福值在 $[H-\mathrm{left}_B, +\infty)$ 区间的个数（线段树的单点更新，区间查询）。

复杂度是 $\mathcal{O}(\frac{N}{2}\times 3^{\frac{N}{2}})$。

3.2 暴力枚举+剪枝

先枚举 $A$，再枚举 $B$，复杂度可以达到 $\mathcal{O}(2^{\frac{3N}{2}})$。

也可以直接枚举所有组合，复杂度可以达到$\mathcal{O}(3^N)$。

加几个剪枝，也许就过了。

1. 题目链接

Kickstart Round F 2019 C. Spectating Villages

2. 题目描述

有 $V$ $(2\le N\le 10^5)$ 个村庄，他们由 $V-1$ 条无向边直接或间接相连，无重边，无自环。每个村庄有一个漂亮值(即点权)，编号为 $i$ 的村庄的漂亮值为 $B_i$ $(-10^5\le B_i \le 10^5)$。
你可以选择在一些村庄安装电灯，如果你在一个村庄安装了电灯，那么这个村庄以及与这个村庄直接相连的所有村庄也将被点亮。
现在你可以在一些村庄上安装电灯（也可以都不安装），求被点亮的村庄的漂亮值之和的最大值。

3. 解题思路

图是一个棵无根树。可以选择某一个顶点作为根节点进行树形DP。
状态定义为 ：

• $dp[u][0]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 没有安装电灯，同时村庄 $u$ 不被点亮的条件下的最大漂亮值之和。
• $dp[u][1]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 安装了电灯的条件下的最大漂亮值之和。
• $dp[u][2]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 没有安装电灯，同时村庄 $u$ 被点亮的条件下的最大漂亮值之和。

对于村庄 $u$ 为根节点的子树中，有：

• 当村庄 $u$ 没有安装电灯，同时村庄 $u$ 不被点亮：其子节点一定不能安装电灯。
• 当村庄 $u$ 安装了电灯：其子节点可以随意。
• 当村庄 $u$ 没有安装电灯，同时村庄 $u$ 被点亮：他的子节点中至少有一个安装了电灯。我们这里可以选$\arg\max_\limits{v \in son(u)}\lbrace dp[v][1]-\max\lbrace dp[u][0],dp[u][1]\rbrace\rbrace$ 被点亮，其他子节点可以随意。

具体的转移方程可以见代码。

1. X or What?

1.1 题目链接

[Kickstart Round D 2019 A. X or What?]

1.2 题意描述

Problem A. X or What

1.3 解题思路

xor-even 是指在二进制表示中，1的个数为偶数。

可以发现：两个数的异或和是不是 xor-even 跟这两个数本身是不是 xor-even 有关。换言之，如果两个数都有偶数个1或者都有奇数个1，那么他们异或和的二进制表示一定是偶数个1；当一个数有偶数个1，另一个数有奇数个1，那么异或和的二进制表示中一定是奇数个1。

所以，只需要维护 最左、最右的二进制表示中有奇数个1的数。

1. 题目链接

Kickstart Round C 2019 C. Catch Some

2. 题目描述

3. 解题思路

由题可知，除了最后一次需要走单程之外，其他每次都需要走双程（即需要回家)。

令 $dp_{(c,i,0)}$ 表示前 $c$ 种颜色，总共选出 $i$ 个人，并且前面 $c$ 种颜色 都是走的双程 的情况下的 最小花费时间；
$dp_{(c,i,1)}$ 表示前 $c$ 种颜色，总共选出 $i$ 个人，并且前面 $c$ 种颜色 存在一次走单程 的情况下的 最小花费时间。

记 $pos_{(c,i)}$ 表示第 $c$ 种颜色的狗中，距离家第 $i$ 近的狗的位置。

那么，可以写出状态转移方程如下：
$$
\begin{split}
dp_{(c,i+j,0)} &= \min \lbrace dp_{(c,j,0)} + 2 * pos_{(c,i)}\rbrace ;\
dp_{(c,i+j,1)} &= \min \lbrace dp_{(c,j,1)} + 2 * pos_{(c,i)},\ dp_{(c,j,0)} + pos_{(c,i)}\rbrace , \quad \text{for any } c,i,j.\
\end{split}
$$

因此， $ans=dp_{(M,K,1)}$。这里 $M$ 表示颜色种类数。

1. 题目链接

Kickstart Round C 2019 B. Circuit Board

2. 题目描述

3. 解题思路

$dp_{(i,j,k)}$ 表示右下角坐标为 $(i,j)$，高度为 $k$ 的子矩阵的最大宽度。假设下标从 $1$ 开始，那么有:

$$\begin{align}
dp_{(i,j,k)}=\min \lbrace dp_{(i,j,1)}, dp_{(i-1,j,k-1)}\rbrace, \quad \text{for any }i,k > 1.
\end{align}$$

因此， $ans=\max\lbrace dp_{(i,j,k)}*k\rbrace$

摘要：目标检测，作为计算机视觉研究中最基础的并且最富有挑战性的任务之一，一直以来备受研究人员的关注。深度神经网络可以从数据中学习特征，具有强大的表征能力。随着深度神经网络的发展，特别是深度卷积网络，目标检测领域迎来了突破性的进展。本文将主要介绍近几年主流的基于深度学习的目标检测算法及其主要的算法原理。

内网穿透 (NAT 穿透，NAT Penetration)，是指通过流量转发/代理，使得没有公网IP的内网服务器能够被外网访问。为了实现内网穿透，我们需要一台内网服务器和一台公网中转服务器。公网中转服务器是用来做流量转发的。

通过内网穿透，我们还可以绕过跳板机，访问内网服务。

内网穿透的基本原理就是：

• 首先，内网服务器向公网服务器主动建立一条持续的TCP通路，用于内网和公网服务器之间的数据传输；
• 然后，外网机器如果需要访问内网服务器，那么可以先连接到公网中转服务器，然后公网服务器通过上一步建立的TCP通路，把请求转发到内网服务器。

常见的内网穿透工具有autossh、ngrok、frp、花生壳等。

实验背景: 在 2 台机器上，进行了小规模分布式训练的验证实验。主要是为了验证代码能够在分布式环境下运行。实验配置如下：

视觉任务基本包括以下四类，难度基本是递增，且本质上都可以归类为分类任务。