¶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 台机器上，进行了小规模分布式训练的验证实验。主要是为了验证代码能够在分布式环境下运行。实验配置如下：

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

Common Used

1. https://tool.lu
2. Colaboratory: Online Jupyter Notebook
3. OEIS: 整数序列的在线百科全书
4. 排列组合计算器
5. Emoji Homepage

考点 贝叶斯 SVM 对偶形式 K-L 变换/PCA Logistic Regression AdaBoost 概率图模型、HMM BP/CNN No Free Lunch: 没有最好的算法/学习器,不存在一个与具体应用无关的、普遍适用的“最优分类器/回归器”！仅在学习算法与问题align或mat ...

1. 题目链接

[loj 6226. 「网络流 24 题」骑士共存问题]

2. 题目描述

3. 解题思路

题目中要求如果一个顶点被选择，那么8个方向上的顶点就不能被选择。显然，这很像二分图的染色问题。
将每个非障碍的顶点与其8个方向上的非障碍顶点连一条边，那么本题就是一个求最大独立集的问题，而且是一个求二分图的最大独立集的问题。
为什么是二分图呢？可以从下面两条性质来分析：

• 对于任意节点$u$，不可能经过奇数步回到节点$u$，实际上，这就是 匈牙利算法 Hungary 的进行二分图的判断的主要思想；
• 按照题目中那个图，将所有顶点划分成红色、黄色两类节点，可以发现同色的节点之间没有边。

而二分图上有很好的性质，比如：

• 最大匹配数 = 最小点覆盖；
• 最大独立集 = 最小边覆盖 = 顶点数 $\lvert V \lvert$ - 最大匹配数；
• DAG 的最小路径覆盖数 = DAG 图中的节点数 - 相应二分图中的最大匹配数。
  • DAG 的最小路径覆盖是指找最小数目的互相不相交的有向路径，满足 DAG 的所有顶点都被覆盖。
  • DAG 对应的二分图这样构造：对于 DAG 中的一个顶点 $p$，二分图中有两个顶点 $p$ 和 $p’$，对应 DAG 中的一条有向边 $p\to q$，二分图中有 $p\to q’$ 的一条无向边。二分图中 $p$ 属于 $S$ 集合，$p’$ 属于 $T$ 集合.
• ……

求二分图的最大匹配数的方法有 匈牙利算法（复杂度$\mathcal O(VE)$） 和 网络流（代表算法就是Dinic/Hopcroft-carp 算法，复杂度$\mathcal O(\sqrt{V}E)$）。