gyro永不抽风！ - gyro永不抽风
type: channel
link: https://gallery.gyrojeff.top/index.php/author/1/
description: gyro永不抽风
items: 深入理解 Zyzzyva 协议
items: 深入理解 PBFT 协议
items: 西瓜书 绪论 习题
items: PyTorch Data Augmentation 数据增广
items: 读论文——YOLO v1
items: P1363 幻象迷宫 - DFS
items: P3572 [POI2014] PTA-Little Bird - DP 单调队列
items: POJ 2823 滑动窗口 单调队列 - 致逝去的青春
items: leetcode 1787 使所有区间的异或结果为零 - DP - 随机跳题计划
items: P2210 Haywire - 状压 DP

深入理解 Zyzzyva 协议
type: item
date: 2023-02-18T15:30:01+00:00
description: Zyzzyva Paper 链接：http://www.cs.cornell.edu/lorenzo/papers/kotla07Zyzzyva.pdf Journal Version (Extended): https://www.cs.cornell.edu/lorenzo/papers/a7-kotla.pdf 回顾：PBFT 讲解链接：https://gyrojeff.top/index.php/archives/dive-into-pbft/ 动机 PBFT 的 $O(n^2)$ 开销太大，而且观察到大多数时候并会经历 Primary Fault 甚至大多数时候不会有 Fault。Zyzzyva 旨在提高没有 Fault 或者没有 Primary Fault 的情况下的协议效率。 Zyzzyva 流程 一些记号的说明 Checkpoint, CC, Speculative History 见上图 Order-Req 以及 Spec-Response阶段 $d = H(m)$，即消息 $m$ 的 Digest $h_n = H(h_{n-1}, d)$，描述截止到 $n$ 的历史记录，即 $$ h_n = H(H(H(\cdots (H(d_1), d_2)\cdots), d_{n-2}), d_{n-1}) $$ 注意到光靠 $h_n$ 就能判断历史记录了。正常的 Client 可以靠这个鉴别是否 Diverge。 Normal Case Operation 当有 Fault 存在 View Change View Change 的大体过程和 PBFT 相同： PBFT: Last Stable Checkpoint + Preprepare Messages Zyzzyva: Last Stable Checkpoint / Committed Certificate + Speculative History 区别在于对待 Speculative History 的处理上。 Zyzzyva 这里要分两种情况处理： 如果没有 Speculative History，那么就是普通的 PBFT View Change，没什么好讨论的 如果有 Speculative History，我们需要判断这个 History Diverge 了还是是属于 Fast Path 的正常 History。判断方法如下：如果在 View Change 的 $2f+1$ 个 Replica 当中，有 $\geq f+1$ 个 Replica 有 CC 之后的这样一条匹配消息，那么就认为这个消息是真实消息，即属于 Fast Path。我们会在之后的章节给予证明。 一些 Intuition 对于 Zyzzyva，简要而言可以理解如下 如果没有 Fault，那就非常快，Client 知道搞定就行了。这样的记录就是 Speculative 的 如果存在 Fault，那也要至少要求 $2f+1$ 个 Reply，这个时候 Client 会给所有 Replica Multicast Committed Certificate。注意：有了 Committed Certificate，之前的所有 Speculative 记录就自动转正了 Zyzzyva 的 View Change 和 PBFT 相比也有少许不同。最大的特点就是：如果 Suspect Primary Faulty，不会暂停消息的处理！ Replica 会继续处理消息，但是同时广播 I-Hate-The-Primary。只有当 I-Hate-The-Primary 的数量达到 $f+1$ 的时候，才会进入真正的 View Change。相比之下，PBFT 只要 trigger timeout 就立刻罢工，这就是 PBFT 的 In-Dark 问题。 Safety 是如何保证的？ View 内部的 Safety？ 注意到 Zyzzyva 没有 Pre-Prepare - Prepare - Commit 三个节点，没有 View 内的 Consensus，完全靠的是 CC 和 Speculative History。所以我们只需要分析这两个部分。 Committed Certificate 的 Safety Committed Certificate 的 $2f+1$ 个 Replica 和 View Change 时的 $2f+1$ 个 Replica 构成了 $f+1$ 个 Quorum，保证了 View Change 的时候至少有一个 non-faulty Replica。这个和 PBFT 的过程相同，原理也相同。 Speculative History 的 Safety 以及 View…

深入理解 PBFT 协议
type: item
date: 2023-02-11T20:08:53+00:00
description: PBFT - Practical Byzantine Fault Tolerance BFT PBFT 的重要概念 PBFT 的大致流程 Normal Case Operation 即 Primary 不出问题的情况下 Checkpoint Protocol View Change Protocol Fault 的分类 为什么达成 Prepared 状态需要 $2f+1$ 个 Matching Prepared 保证了什么？ 反例构造 证明 Commit Phase 的必要性 Commit Phase 能够保证什么？ 反例构造 理解 为什么达成 Committed 状态需要 $2f+1$ 个 Prepared 估算 反例构造 为什么 New Primary 需要 $2f$ 个 View Change 为什么 Reply 需要 $f+1$ 个 Matching Checkpoint (Garbage Collection) 的必要性 Checkpoint 为什么在数字签名模式下只需要 $f+1$？ View Change 和 Liveness 之间的关系 Primary 作恶带来的 In-Dark 问题 Network Recovery 的流程 Misc PBFT - Practical Byzantine Fault Tolerance 论文链接：https://pmg.csail.mit.edu/papers/osdi99.pdf BFT BFT (Byzantine Fault Tolerant) 拜占庭容错，指的是在一个分布式系统当中，在有节点可能出现任意行为（包括但不限于崩溃、发送错误数据、出现恶意行为等）的情况下，仍可以正常运行即达成共识。 Wikipedia Link. PBFT 的重要概念 PBFT 可以保证在一个大小为 $3f+1$ 的分布式网络下，容忍至多 $f$ 个节点的拜占庭错误。 Primary (Leader): PBFT 是一个 leader-based 的协议，即在任意时刻，都有一个 leader 主导协议的走向。 视图 View: 在 Primary 不发生改变的一段时间我们称之为 View。注意到：View 的编号是单调递增的。给定一个视图编号 $v$，我们就可以唯一确定这个视图的 Primary 编号 $p = v \bmod |\mathcal R|$，其中 $\mathcal R$ 是所有节点的集合，即所有 Replica 的集合。 Replica: 可以理解为服务器节点。 目标: 达成 Consensus。即在每一个 Replica 上，所有的 transaction 内容和顺序都保证一致。 View Change: 视图改变。正因为协议由一个 Leader 主导，那在 leader 出现 malicious behaviour 的时候，协议可以保证触发 View Change，即更换 leader，来保证 liveness。具体内容后文会详细说明。 PBFT 的大致流程 Normal Case Operation 即 Primary 不出问题的情况下 [REQUEST] 客户端向 Primary 发送 $\langle Request, o, t, c \rangle _{\sigma_c}$ 请求 $o$: Operation $c$: Client $t$: Timestamp - 这是用来保证执行的 exactly-once semantics [PREPREPARE] Primary 将请求 Multicast 给所有 Replica: $\langle \langle Preprepare, v, n, d \rangle _{\sigma_p}, m \rangle$ $v$: view $n$: Primary 给这个请求分配的 Sequence Number 【关于 Sequence Number: 一个正常的 Replica 只会按顺序 (Sequence Number) 处理消息。即若其收到了 127 号消息但始终没有收到 125、126 号消息，127 号消息便一直不会处理。】 $d$: $d = D(m)$ 消息 $m$ 的 digest (摘要) [PREPARE] 每个 Replica $i$ 收到请求之后，如果选择接受请求（原文有更详细的描述），就会向所有 Replica 广播 Prepare: $\langle Prepare, v, n, d, i \rangle _ {\sigma_i}$ [COMMIT] 接下来，如果每个 Replica $i$ 收到了其他 Replica (包括自己在内) 一共 $2f+1$ 个 Prepare 请求，这个时候…

西瓜书 绪论 习题
type: item
date: 2022-05-17T11:44:35+00:00
description: 注：本文为《机器学习》（周志华）第一章的作业笔记。 1.1 表 1.1 的编号为 1, 4 的两个样例： 色泽 根蒂 敲声 好瓜 青绿 蜷缩 浊响 是 乌黑 稍蜷 沉闷 否 因为只有两个样本，我们只要能够保证： $$ s_好 \in S, s_坏 \notin S $$ 1.2 首先我们可以将决策看作一棵树，而每一个取式其实就是一棵子树或者叶子节点。会过来看合取式的析合范式，其实就是在一整棵树中取 $k$ 个互相不包含的子树或者叶子节点。 这里不能直接确定答案，因为题目并没有说决策树能不能给出形如下面的节点： $$ (色泽\in\{青绿，乌黑\}; 根蒂=*; 敲声=*) $$ 我们先假设题目不允许上述的情况出现，那我们可以断言，包含 $n$ 个并列条件的决策，整棵树的深度为 $n + 1$，因为每一个父子关系其实就是析构 $*$ 和具体内容。 这个问题其实不能简单估算，但是我们可以用树形动态规划来解决。设状态 $f[u][p]$ 代表以节点 $u$ 为根的子决策树有 $p$ 个合取式的析合范式情况数。同时我们注意到书上的旁注：会有冗余的等价情况，那么我们还需要去除这样的等价情况，即在本题中我们需要去除 $$ \bigcup_{v \in u.sons} v = u $$ 的情况。 下面是递推方程： $$ f[u][p] = \sum_{\sum_{1 \leq i \leq |u.sons|} p_i = p, p_i \geq 0} f[v_i][p_i] $$ 减去冗余情况： $$ f[u][|u.sons|] := f[u][|u.sons|] - 1 $$ 1.3 举例：线性回归。 1.4 $$ E_{ote} (\mathfrak L_a | X, f) = \sum_h \sum_{\boldsymbol x \in \mathcal X - X} P(\boldsymbol x) \ell (h(\boldsymbol x), f(\boldsymbol x)) P(h | X, \mathfrak L_a) $$ $$ \begin{aligned} \sum_f E_{ote} &= \sum_f \sum_h \sum_{\boldsymbol x \in \mathcal X - X} P(\boldsymbol x) \ell (h(\boldsymbol x), f(\boldsymbol x)) P(h | X, \mathfrak L_a) \\ &=\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x)\sum_h P(h | X, \mathfrak L_a) \sum_f \ell (h(\boldsymbol x), f(\boldsymbol x)) \end{aligned} $$ 注意到最后一部分为与 $\mathfrak L$ 无关的常数。不妨设 $$ L = \sum_f \ell (h(\boldsymbol x), f(\boldsymbol x)) $$ 故原式等于 $$ L\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x)\sum_h P(h | X, \mathfrak L_a) = L\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x) \cdot 1 $$ Q.E.D. 1.5 略。

PyTorch Data Augmentation 数据增广
type: item
date: 2022-05-02T15:15:26+00:00
description: Data Augmentation 这个词其实很容易误导人，因为 Augmentation 是增广的意思。数据增广，自然而然就会让人理解为：“增加了新的数据”。然而在实现的过程中，不一定是这样。 我们会给定一些随机化的参数，在每个 epoch 内生成随机增广后的图片。 比方说，每个 epoch 都按照一定的 random rule 来 crop 图片、调整色调，便是图像增广。 PyTorch 实现 这里拿 Fashion-MNIST 举例，同样我们会给出例子来证明我们的做法是行之有效的。 首先引入包： %matplotlib inline %config InlineBackend.figure_formats = ['svg'] from matplotlib import pyplot as plt import torch import torchvision from torch.utils import data 加载 FashionMNIST 数据集，并且禁用 shuffle，这样保证我们每个 epoch 图片顺序都是相同的，方便我们验证： def load_data_fashion_mnist(batch_size, dataloader_worker_count, resize=None): trans = [torchvision.transforms.ToTensor()] if resize: trans.insert(0, torchvision.transforms.Resize(resize)) trans.append(torchvision.transforms.RandomCrop((28, 28))) trans = torchvision.transforms.Compose(trans) mnist_train = torchvision.datasets.FashionMNIST( root="../data", train=True, transform=trans, download=True) mnist_test = torchvision.datasets.FashionMNIST( root="../data", train=False, transform=trans, download=True) return (data.DataLoader(mnist_train, batch_size, shuffle=False, num_workers=dataloader_worker_count), data.DataLoader(mnist_test, batch_size, shuffle=False, num_workers=dataloader_worker_count)) 辅助渲染的函数： def get_fashion_mnist_labels(labels): ''' 返回Fashion-MNIST数据集的文本标签 ''' text_labels = ['t-shirt', 'trouser', 'pullover', 'dress', 'coat', 'sandal', 'shirt', 'sneaker', 'bag', 'ankle boot'] return [text_labels[int(i)] for i in labels] def show_images(imgs, num_rows, num_cols, titles=None, scale=1.2): ''' 绘制图像列表 ''' figsize = (num_cols * scale, num_rows * scale) _, axes = plt.subplots(num_rows, num_cols, figsize=figsize) axes = axes.flatten() for i, (ax, img) in enumerate(zip(axes, imgs)): if torch.is_tensor(img): # 图片张量 ax.imshow(img.numpy()) else: # PIL图片 ax.imshow(img) ax.axes.get_xaxis().set_visible(False) ax.axes.get_yaxis().set_visible(False) if titles: ax.set_title(titles[i]) return axes 测试三个 epoch，看每次 epoch 第一个 batch 的数据： train_iter, test_iter = load_data_fashion_mnist(18, 4, resize=40)…

读论文——YOLO v1
type: item
date: 2022-04-30T14:48:20+00:00
description: 论文链接：https://arxiv.org/abs/1506.02640 Abstract 以前都是用 Classifiers 来做 detection 现在：we frame object detection as a regression problem to spatially separated bounding boxes and associated class probabilities end-to-end FAST! Fast YOLO: 155 fps, double mAP of other real-time detectors YOLO: 45 fps Introduction Related works Deformable Parts Models (DPM): sliding window approach where the classifier is run at evenly spaced locations over the entire image R-CNN: first generate potential bounding boxes in an image then run a classifier on these proposed boxes post-processing: refine the bounding boxes, eliminate duplicate detections, and rescore the boxes based on other objects in the scene YOLO Fast, realtime simple architecture see the entire image => less background error learn generalizable representations of objects accuracy 不行, 虽然识别率高，但是定位精准度相对低 Architecture Unified Detection 描述大致的识别思路。 先划分成 $S\times S$ 方格，每个方格需要检测是否有物体的中心在这个方格内，产生 $B$ 个 bounding box 每个 bounding box 会产生五个预测量 $x, y, w, h, \text{confidence}$。注意：$x,y$ 是相对于 cell 的，$w, h$ 是相对于整个图像的。 confidence 描述这个区域有物体的置信度。confidence 的定义： $$ P(\text{Object}) \times \text{IoU}_{\text{pred}}^{\text{truth}} $$ 每个方格产生一个还会对 $C$ 个类别判断的概率，判断这个方格内是否含有类别 $C_i$ $$ P(\text{Class}_i \mid \text{Object}) $$ 测试的时候每个 bounding box 的置信概率就是 $$ P(\text{Class}_i \mid \text{Object}) \times P(\text{Object}) \times \text{IoU}_{\text{pred}}^{\text{truth}} = P(\text{Class}_i) \times \text{IoU}_{\text{pred}}^{\text{truth}} $$ Network Design 我们取 $B=2$，每个区域生成两个 bounding box，区域数量（边） $S=7$，然后分类的类别是 $C=10$。所以最后的输出 $$ S \times S \times (5B + C) = 7 \times 7 \times 30 $$ Training Pretrain ImageNet 数据集 前 20 个卷积层（去掉最后四个卷积层和两个全连接层）再加上一个平均池化层和一个全连接层 Activation 出最后一个层外，使用 Leaky ReLU $$ \phi(x) = \begin{cases} x & x > 0 \\ 0.1x & \text{otherwise} \end{cases} $$ 最后一层文章中说用的是 linear activation function 除此之外，因为最后的结果应该在 $[0,1]$ 范围之内，查到一个 stackoverflow 的问题说最后可能对 output 逐元素做了 sigmoid. https://stackoverflow.com/questions/49707542/yolo-v1-bounding-boxes-during-training-…

P1363 幻象迷宫 - DFS
type: item
date: 2022-04-09T13:55:57+00:00
description: 题面 https://www.luogu.com.cn/problem/P1363 题解 先说正解。 怎么样才能判断可以无限延伸呢？那就是如果存在一条路径 $$ P \rightsquigarrow P' $$ 其中 $P'$ 为任意一个虚幻棋盘中 $P$ 的对应点。 证明十分容易。 充分性证明：记坐标 $P$ 为 $P(x, y), 0 \leq x < n, 0 \leq y < m$。那么： $$ P'(x + na, y + mb), a, b \in \mathbb Z, a,b 不同时为0 $$ 所以根据假设存在下面的路径： $$ P(x, y) \rightsquigarrow P(x + na, y + mb) $$ 则亦存在： $$ P(x + na, y + mb) \rightsquigarrow P(x + 2na, y + 2mb) $$ 我们将路径记作下面这种映射： $$ f(x, y) = (x + na, y + mb) $$ 故我们可以不断应用： $$ f^{(t)}(x, y) = \underbrace{f(f(\cdots f}_{t}(x, y) \cdots)) = (x + tna, y + tmb) $$ 故 $$ \lim_{t \rightarrow \infty} f^{(t)}(x, y) = \begin{cases} (\infty, \infty) & ab \neq 0 \\ (0, \infty) & a = 0 \\ (\infty, 0) & b = 0 \end{cases} $$ 必要性证明可以通过反证法证得： 向无穷远处延伸代表存在长度为无穷的路径。接下来应用反正：若存在长度为无穷的路径，且不存在形如题设的 $P \rightsquigarrow P'$ 的路径。 若不存在形如 $P \rightsquigarrow P'$ 的路径，那么路径长度必然是有限的，因为我们能够构造出来的路径都形如下式： $$ S \rightsquigarrow T = S \rightsquigarrow A_1 \rightsquigarrow A_2 \rightsquigarrow \cdots \rightsquigarrow A_p \rightsquigarrow T $$ 其中等式右侧的每条路径都不存在中间点。我们不难发现集合 $A$ 是有限的，因为原棋盘是有限的，故 $|A \cup \{S, T\}| \leq nm$。故长度必然为有限，与长度为无限矛盾。证毕。 下面是一些错误结论： 错误结论 1：向上下左右各拓展一个棋盘，如果一个点被等价走到了两次，那么就可以到达无穷。 反例： 代码 #include <iostream> #include <cstring> using namespace std; const int maxn = 1505; const int dx[4] = {-1, 0, 0, 1}; const int dy[4] = {0, -1, 1, 0}; int n, m, sx, sy, vx[maxn][maxn], vy[maxn][maxn]; bool map[maxn][maxn], vis[maxn][maxn], ans; void dfs(int x, int y, int lx, int ly) { if (ans) return; if (vis[x][y]) { if (vx[x][y] != lx || vy[x][y] != ly) ans = 1; return; } vis[x][y] = 1; vx[x][y] = lx; vy[x][y] = ly; for (int i = 0; i < 4; i ++) { int xx = (x + n + dx[i]) % n; int yy = (y + m + dy[i]) % m; int lxx = lx + dx[i], lyy = ly + dy[i]; if (map[xx][yy]) dfs(xx, yy, lxx, lyy); } } int main() { char in; while (cin >> n >> m) { for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) { cin >> in; map[i][j] = (in != '#'); if (in == 'S') sx = i, sy = j; } memset(vis, 0, sizeof(vis)); memset(vx, 0, sizeof(vx)); memset(vy, 0, sizeof(vy)…

P3572 [POI2014] PTA-Little Bird - DP 单调队列
type: item
date: 2022-04-08T15:50:37+00:00
description: 题面 https://www.luogu.com.cn/problem/P3572 题解 首先，不难列出方程：$f[i]$ 代表跳到 $i$ 的最小疲劳值 $$ f[i] = \min_{i - k \leq j < i} \{f[j] + (a[i] \geq a[j])\} $$ 时间复杂度为 $O(qn^2)$，不理想。但是不难发现，这道题可以用单调队列进行优化。为什么？ 如下状态一定是更优的：随着 index 递增 $f$ 不下降（第一维比较） $f$ 若相同，同时有 $a$ 不上升（第二维比较） 所以我们就可以用单调队列来维护 index，时间复杂度为 $O(qn)$ 注意： 初值的设定，详见代码 写的顺序和单调队列的模板稍微有一点不同，因为 $i - k \leq j < i$，右边的小于号不是小于等于号，即 $f[i]$ 不能被自己更新，所以调整了一下逻辑块的顺序。 代码 #include <iostream> using namespace std; const int maxn = 1e6+5; int qq, n, k, head, tail, a[maxn], f[maxn], q[maxn]; int main() { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; cin >> qq; while (qq --> 0) { cin >> k; head = 1; tail = 1; q[1] = 1; for (int i = 2; i <= n; i ++) { while (head <= tail && q[head] < i - k) head ++; f[i] = f[q[head]] + (a[i] >= a[q[head]]); while (head <= tail && ( f[i] < f[q[tail]] || ( f[i] == f[q[tail]] && a[i] >= a[q[tail]] ) )) tail --; q[++ tail] = i; } cout << f[n] << endl; } return 0; }

POJ 2823 滑动窗口 单调队列 - 致逝去的青春
type: item
date: 2022-04-08T15:03:59+00:00
description: Preface 三年前的四月，第一次接触 OI。初三下，小教室里听着 fcx 讲着滑动窗口单调队列，放学后去本部蹭了第一节斜率优化的课，随即拉开了我长达两年的竞赛摆烂之旅。 记忆犹新。第一个注册的 OJ 账户就是 POJ，第一道 AC 的题便是 POJ 2823 滑动窗口。 多年过去，今天再看这个基础中的基础，茫然。只能说这是究极摆烂的下场罢。总之就好好写一下题解。 题面 https://www.luogu.com.cn/problem/P1886 题解 接下来只讨论求最小值的情况。设 $f[i]$ 代表终止于位置 $i$ 的滑动窗口的最小值： $$ f[i] = \min_{i - k < j \leq i} a[j] $$ 如果暴力做的话时间复杂度为 $O(n^2)$。这里我们需要使用单调队列来优化。 对于最小值：单调队列内的元素值递增，同时 index 也是递增的。为什么这样做？思考一个情况：index 递增的情况下，如果一个 $a[i] > a[j], i < j$，那么在 $i,j$ 都有效的范围内，$a[i]$ 永远不可能作为答案。 这里有一句经典的话：如果一个选手年龄比你小，但却比你强，那你就可以退役了。我们把 index 比作出生年份，$a[]$ 比作能力，那么这句话就维护了一个求最大值的单调队列。 接下来是代码中需要注意的一些问题： head, tail 不是左闭右开，而是 $[head, tail]$。这样做的原因是访问 head 和 tail 的元素就可以简单的：q[head], q[tail] 队列里存的是 index （pos） 注意：第二个 while 可以修改为 if，因为每次 i ++ 且 q 内的 pos 递增，写成 while 是习惯。 代码 #include <iostream> using namespace std; const int maxn = 1e6+5; int n, k, a[maxn], q[maxn], head, tail; int main() { cin >> n >> k; for (int i = 1; i <= n; i ++) cin >> a[i]; // min head = 1, tail = 0; for (int i = 1; i <= n; i ++) { while (head <= tail && a[i] <= a[q[tail]]) tail --; q[++ tail] = i; while (head < tail && q[head] <= i - k) head ++; if (i >= k) cout << a[q[head]] << " "; } cout << endl; // max head = 1, tail = 0; for (int i = 1; i <= n; i ++) { while (head <= tail && a[i] >= a[q[tail]]) tail --; q[++ tail] = i; while (head < tail && q[head] <= i - k) head ++; if (i >= k) cout << a[q[head]] << " "; } cout << endl; return 0; }

leetcode 1787 使所有区间的异或结果为零 - DP - 随机跳题计划
type: item
date: 2022-04-07T14:16:08+00:00
description: Preface 好耶，少见的难题。 题面 https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/ 题解 大部分题解已经提到了：就是下面这个结论。 结论：最终构造出来的数列以 $k$ 为一个周期 证明： 由题设： $$ a[1] \oplus a[2] \oplus \cdots \oplus a[k] = a[2] \oplus a[3] \oplus \cdots \oplus a[k + 1] $$ 所以我们有： $$ (a[1] \oplus a[2] \oplus \cdots \oplus a[k]) \oplus (a[2] \oplus a[3] \oplus \cdots \oplus a[k + 1]) = 0 $$ 根据异或的交换律与结合律： $$ a[1] \oplus a[k + 1] = 0 $$ 故 $a[1] = a[k + 1]$。易证，此结论可以将 $1$ 替换为任意定义域内的数。 接下来思考一下最终构造出来的数列满足什么特征： 以 $k$ 为一个周期 第一个周期异或和为 0 接下来看图说话: 在上图中 $n = 13, k = 3$，我们就是需要让 $$ a[1] = a[4] = a[7] = a[10] = a[13] $$ $$ a[2] = a[5] = a[8] = a[11] $$ $$ a[3] = a[6] = a[9] = a[12] $$ $$ a[1] \oplus a[2] \oplus a[3] = 0 $$ 那么我们不妨一组一组按列处理，接下来是状态的设法：$f[i][j]$ 代表处理完第 $i$ 列，使得前 $i$ 列的异或和为 $j$ 的最少修改次数。 思考转移方程：都是从上一列转移，但是有两种转移方式： 第 $i$ 列全部修改 第 $i$ 列部分修改，部分保留 设 $cnt$ 为第 $i$ 列的个数，$t[j]$ 代表第 $i$ 列 $j$ 出现的次数，那么： $$ f[i][j] = \min (f[i][j], cnt + \min_{k} f[i - 1][k]) $$ $$ f[i][j] = \min_{k \in \text{column }i} \{f[i][j], f[i - 1][j \oplus k] + cnt - t[k]\} $$ 注意：全部修改仍然有可能比部分修改更优，这是因为本题不是简单的贪心。具体可以见下一小节，我们可以构造出反例，证明贪心是错误的。 此外，我们还需要注意初值的设定。 构造贪心的反例 贪心？怎么贪心？那当然是每一列选择相同数量最多的，再把这个数量排序，相同数量最少的一列全部改变，使得最后异或值为 0。 但是这个反例是非常容易构造的。 第一列： $$ a, a, b, b, b, c, c $$ 第二列： $$ d, d, d, d, e, e, e $$ 第三列： $$ f,f,g,g,h,h,i $$ 按照之前说的贪心，我们会选保留 $b, d$，然后第三列适应答案使得异或为 $0$。但是如果很不巧，我们的构造在这样的情况下其他元素全部需要改变，那么此时的改动数量为 $4 + 5 + 7 = 16$。然而如果 $a \oplus e \oplus f = 0$，那么如果我们选择 $a, e, f$，改动的数量就是 $5 + 4 + 5 = 14 < 16$，更优。构造完毕。 代码 const int maxn = 2e3+5; const int maxl = 10; class Solution { int f[maxn][1 << maxl]; int g[maxn], a[maxn], t[1 << maxl]; public: int minChanges(vector<int>& nums, int k) { int n = nums.size(); for (int i = 0; i < n; i ++) a[i + 1] = nums[i]; memset(f, 0x7f, sizeof(f)); memset(g, 0x7f, sizeof(g)); memset(t, 0, sizeof(t)); int cnt = 0; for (int j = 1; j <= n; j += k) t[a[j]] ++, cnt ++; for (int j = 0; j < 1024; j ++) { f[1][j] = min(f[1][j], cnt - t[j]); g[1] = min(g[1], f[1][j]); } for (int i = 2; i <= k; i ++) { memset…

P2210 Haywire - 状压 DP
type: item
date: 2022-04-06T16:26:00+00:00
description: 题面 https://www.luogu.com.cn/problem/P2210 题解 一开始没反应出来是状压，看了少数题解才知道可以状压。今天姑且 A 掉状压的写法，明天写写看模拟退火。 首先，我们来设状压的状态方程： $$ f[i] $$ $i$ 代表 $i$ 表示成二进制的时候有 $1$ 那些位所代表的牛组成的集合 比方说 $i = 6 = (110)_2$ 代表有 $2, 3$ 号牛组成的集合 $f[i]$ 代表牛的集合为 $i$ 时对答案产生的贡献。 什么是贡献？这个说法很模棱两可。其实是这样的：两个朋友都在集合里面，那答案必然要包括这对朋友连线的贡献。但是如果只有一头牛在集合里呢？很简单，贡献就是：按照某种最佳排列时，这头牛所处的位置到集合队尾的距离。这么说很抽象，我们举个例子： $$ ~ * ~ * ~ * ~ \triangle ~ * ~ * $$ 上图中，$*$ 代表无所谓的某头牛，$\triangle$ 代表我们现在考察的单个朋友，在这个状态下，$\triangle$ 对答案的贡献就是 $2$，因为 $\triangle$ 之后还有两头牛. 而如果在这个队列之后紧跟就是 $\triangle$ 的朋友：另一个 $\triangle$，那么在增加前 $\triangle$ 给出的贡献 $2$ 就是这对朋友对答案的贡献了： $$ ~ * ~ * ~ * ~ \triangle ~ * ~ * ~ \triangle $$ 好。赘述完关于状态的定义，我们来思考状态怎么转移。对于集合 $i$，我们可以枚举位于队列尾端的到底是哪头牛。每次转移我们只需要加上原来的集合中孤立朋友的数量即可。最终给出的代码是做了一些小的优化，稍微难以理解，所以下面给出一个等价的形式，但是时间复杂度多一个 $n$，为 $O(n^22^n)$： for (int i = 1; i < (1 << n); i ++) { for (int j = 0; j < n; j ++) { if ((1 << j) & i) { int pending_links = 0; int ii = i & ~(1 << j); for (int k = 0; k < n; k ++) if ((1 << k) & ii) pending_links += 3 - (((ii >> nbr[k][0]) & 1) + ((ii >> nbr[k][1]) & 1) + ((ii >> nbr[k][2]) & 1)); f[i] = min(f[i], f[ii] + pending_links); } } } 代码 最终给出的代码时间复杂度为 $O(n2^n)$： #include <iostream> #include <cstring> using namespace std; const int maxn = 12; int f[1 << maxn], nbr[maxn + 5][3]; int main() { int n; cin >> n; for (int i = 0; i < n; i ++) { cin >> nbr[i][0] >> nbr[i][1] >> nbr[i][2]; nbr[i][0] --; nbr[i][1] --; nbr[i][2] --; } memset(f, 0x7f, sizeof(f)); f[0] = 0; for (int i = 1; i < (1 << n); i ++) { int pending_links = 0; for (int j = 0; j < n; j ++) if ((1 << j) & i) pending_links += 3 - (((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1)); for (int j = 0; j < n; j ++) { if ((1 << j) & i) { f[i] = min(f[i], f[i & ~(1 << j)] + pending_links - (3 - (((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1))) + ((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1)); } } } cout << f[(1 << n) - 1] << endl; return 0; }