【复习笔记】Week 5 冬令营准备

# 绪言 我知道 THW 和 PKW 的申请不容易通过。不过，既然大家都已经为我付出了这么多，假如真的有机会参加冬令营，我绝不能浪费如此沉重的机会。仅仅 10 天，我究竟能做到什么？我真的能在不放弃文化课的同时，把自己提升到省选水平吗？我不知道，但我必须前进。 **希望与绝望并存，梦想与现实抗争。** 最美的愿望 一定最疯狂 我就是我自己的神 在我活的地方 我和我最后的倔强 握紧双手绝对不放 下一站是不是天堂 就算失望 不能绝望 我和我骄傲的倔强 我在风中大声地唱 这一次为自己疯狂 就这一次 我和我的倔强 # DAY 1 ## 网络最大流 残量网络：一系列反边，其存在对原图没有任何影响，但可以利用类似 独木桥 的思路，使得流量能够反悔。 ### EK **思路：** 每次通过 bfs 找到一条增广路，然后对增广路上的边维护残量网络。 复杂度：$O(n\cdot m^2)$ ```cpp inline bool bfs() { memset(vis, 0, sizeof(vis)); while (!q.empty()) q.pop(); // 每次清空信息 flow[s] = 0x7fffffff; vis[s] = true; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (register int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (vis[v] || w <= 0) continue; vis[v] = true; flow[v] = min(flow[u], w); fa[v] = u; path[v] = i; // 记录增广路 if (v == t) return true; q.push(v); } } return false; } inline void EK() { while (bfs()) { for (register int u = t; u != s; u = fa[u]) { edge[path[u]].w -= flow[t]; edge[path[u] ^ 1].w += flow[t]; } // 维护残量网络 maxflow += flow[t]; } return ; } ``` ### Dinic **思路：** 利用 bfs 获得一个增广图（包含当前状态下经过节点数最少的所有增广路），然后在搜索图上进行 dfs 增广，利用递归维护残量网络。 复杂度：$O(n^2\cdot m)$ 可以看出 Dinic 在稠密图上的性能优于 EK 算法。 #### 弧优化 **思路：** 由于在同一个增广图中，一条边被 dfs 之后就无法继续增广（因为经过该点的所有增广路容量已经流满），因此可以不再考虑这条边。 ```cpp inline bool bfs() { memset(dep, 0, sizeof(dep)); memcpy(cur, head, sizeof(cur)); // 记得每次 bfs 都需要初始化 dep[s] = 1; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (dep[v] || w <= 0) continue; dep[v] = dep[u] + 1; q.push(v); } } return dep[t]; } // bfs 用于生成增广图 int dfs(int u, int flow) { if (u == t) return flow; int used = 0; // used 保存从增广图上的 u 出发能够获得的增广流量 for (int i = cur[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; cur[u] = i; // 弧优化 if (dep[v] == dep[u] + 1 && w > 0) { int inc = dfs(v, min(flow, w)); // inc 表示经过 <u, v> 可以获得的增广流量 if (inc > 0) { edge[i].w -= inc; edge[i ^ 1].w += inc; // 维护残量网络 used += inc; flow -= inc; if (!flow) return used; // flow 全部流满，则直接 return } } } return used; } inline void dinic() { while (bfs()) maxflow += dfs(s, 0x7fffffff); return ; } ``` #### ISAP 优化 **思路：** 分析 Dinic 算法的过程，可以发现每次 bfs 分层以生成增广图的本质是 放宽增广路所经过点数的限制。也就是说，Dinic 算法中获得的增广路所经过的点数是递增的。因此考虑如何不重新分层而实现放宽限制：只用从汇点$t$开始反向 bfs 分层，获得每个点的深度，每次对一个点$u$进行 dfs 增广以后，就执行 `dep[u]++`，从而达到了 Dinic 中重新分层而想要达到的目的。同时，`gap[]` 优化掉了无意义的增广尝试。 一些细节： 1. ISAP 中 `dfs()` 函数的前一半和 Dinic 是一摸一样的，而且 ISAP 也可以进行弧优化； 2. 还需要记录 `gap[i]` 表示深度为 `i` 的点的个数。如果图中某 `gap[i] == 0`，也就是说增广图出现了断层，则一定无法继续增广，直接结束程序； 3. 由于 `dep[t] = 1`，因此执行 `dfs(s, 0x7fffffff)` 的条件是 `dep[s] <= n`； 4. 由于是反向分层，因此 dfs 路径上的点一定满足深度连续递减，而非连续递增。 ```cpp inline void bfs() { dep[t] = 1; gap[1] = 1; q.push(t); while (!q.empty()) { int u = q.front(); q.pop(); for (register int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (dep[v]) continue; dep[v] = dep[u] + 1; gap[dep[v]]++; // 维护 gap[] q.push(v); } } return ; } int dfs(int u, int flow) { if (u == t) return flow; int used = 0; for (register int i = cur[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; cur[u] = i; if (dep[u] == dep[v] + 1 && w > 0) { int inc = dfs(v, min(flow, w)); if (inc > 0) { edge[i].w -= inc; edge[i ^ 1].w += inc; used += inc; flow -= inc; if (!flow) return used; } } } // 与 Dinic （弧优化）一摸一样 gap[dep[u]]--; if (!gap[dep[u]]) dep[s] = n + 1; // 等价于结束 ISAP() 函数 dep[u]++; gap[dep[u]]++; // 升层操作 return used; } inline void ISAP() { bfs(); while (dep[s] <= n) { memcpy(cur, head, sizeof(cur)); maxflow += dfs(s, 0x7fffffff); } return ; } ``` ### HLPP（究极最大流算法） **思路：** 往$s$处疯狂灌水，只要不超过容量就推流，然后入队进行 bfs，最后$t$处的余流就是网络最大流。 这样朴素的想法正确性显然，不过由于残量网络的存在，会出现两个点相互推流从而陷入死循环的尴尬局面。为了防止这种情况，可以引入一个高度$h[u]$，规定推流时只能由高处推向低处。特殊地，$h[s]=n$，$h[t]=0$且固定不变。若一个点推流后还有余流，则将其高度改为与其相邻的最低点高度$+1$，然后入队；若没有余流，则什么也不做。很明显，如果一个点无法向$t$推流，则其余流最终会经过残量网络还给$s$。 但是即使做了高度优化，预推流算法依然很慢。此时需要再引入 `gap[]` 优化、优先队列优化。设$h[t]=0$，先从$t$开始 bfs，给每个点一个初始高度，并且规定只能在高度差为$1$的点之间推流，然后执行下面的步骤： 1. 从 `s` 开始向外推流，将有余流的点放入优先队列； 2. 不断从优先队列里取出最高的点 `u` 进行推流； 3. 若 `u` 还有余流，更新 `h[u]`，放入优先队列；若高度出现断层，则直接把所有高于 `u` 的点的高度设为 `n + 1`（也就是 `gap[]` 优化）。 当出现断层时，高度更高的点永远无法再被推流，需要把余流推回$s$，所以 `gap[]` 优化保证了不会出现无意义的推流；而优先队列优化保证了每次都是取出最高的节点进行推流，使得高度更新次数尽量减少。 复杂度：$O(n^2\sqrt m)$，但常数较大。 ```cpp struct cmp { bool operator () (const int &lhs, const int &rhs) const { return h[lhs] < h[rhs]; } }; queue<int> q; priority_queue<int, vector<int>, cmp> pq; inline void bfs() { memset(h, 0x3f, sizeof(h)); // 需要初始化为 0x3f3f3f3f 以排除不连通的点 h[t] = 0; q.push(t); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (h[v] != 0x3f3f3f3f) continue; h[v] = h[u] + 1; q.push(v); } } return ; } // 初始化高度 inline void push(int u) { // 推流函数 for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (w > 0 && h[u] == h[v] + 1) { // 满足推流条件 int flow = min(w, tmp[u]); // 计算可推流 edge[i].w -= flow; edge[i ^ 1].w += flow; tmp[u] -= flow; tmp[v] += flow; // 推流，并且维护残量网络 if (v != s && v != t && !vis[v]) { // 注意 s 和 t 不能入队 vis[v] = true; pq.push(v); } if (!tmp[u]) break; // 余流为 0，跳出循环 } } return ; } inline void relable(int u) { h[u] = 0x3f3f3f3f; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (w > 0 && h[v] + 1 < h[u]) h[u] = h[v] + 1; // 寻找相邻最低点，并更新自己的高度 } return ; } int HLPP() { bfs(); if (h[s] == 0x3f3f3f3f3f) return 0; // 连通性判无解 h[s] = n; for (int i = 1; i <= n; i++) if (h[i] != 0x3f3f3f3f) gap[h[i]]++; // gap[] 统计 for (int i = head[s]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (w > 0) { edge[i].w -= w; edge[i ^ 1].w += w; tmp[s] -= w; tmp[v] += w; if (v != s && v != t && !vis[v]) { vis[v] = true; pq.push(v); } } } // 预处理与 s 相邻的点 while (!pq.empty()) { int u = pq.top(); pq.pop(); vis[u] = false; // 一定记得出队清空 vis[] push(u); if (tmp[u]) { // 还有余流 gap[h[u]]--; if (!gap[h[u]]) { for (int i = 1; i <= n; i++) if (h[i] > h[u] && h[i] < n + 1) h[i] = n + 1; } // gap[] 优化 relable(u); gap[h[u]]++; vis[u] = true; pq.push(u); } // 没有余流则什么也不做 } return tmp[t]; } ``` ## 最小费用最大流 ### MCMF **思路：** ~~顾名思义~~ 就相当于把 bfs 替换为 SPFA 的 EK 算法。其中的 `dis[]` 即是最小单位费用。尝试经过 $<u,v>$ 增广的条件为： 1. `w > 0`（满足最大流）； 2. `dis[u] + c < dis[v]`（满足最小费用）。 剩余的部分和 EK 算法没有区别。 ```cpp bool SPFA() { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[s] = 0, flow[s] = 0x7fffffff; vis[s] = true; fa[t] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; // SPFA 总是容易忘记这一步 for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w, c = edge[i].c; if (w > 0 && dis[u] + c < dis[v]) { // 尝试增广的两个条件 flow[v] = min(flow[u], w); dis[v] = dis[u] + c; fa[v] = u; path[v] = i; if (!vis[v]) { vis[v] = true; q.push(v); // SPFA 中的入队 } } } } return fa[t]; } inline void MCMF() { while (SPFA()) { for (register int u = t; u != s; u = fa[u]) { edge[path[u]].w -= flow[t]; edge[path[u] ^ 1].w += flow[t]; } maxflow += flow[t]; mincost += flow[t] * dis[t]; // 记得统计 mincost } return ; } ``` ### 类 Dinic **思路：** 顾名思义，就是用 SPFA 跑出残量网络的费用最短路以进行分层，然后跑 Dinic 算法。可以理解为 SPFA 跑出最小费用增广图，然后再让 Dinic 在增广图上跑最大流进行增广。当然，Dinic 仍然可以加上弧优化，不过由于费用的限制，此处不能使用 ISAP 优化。 **注意：** 由于存在负权边，并且增广图不是一棵树，因此 dfs 的时候不能够处理为只判断 `dis[u] + c == dis[v]`，**还必须判 `vis[v] == false`**，否则会陷入由负权边带来的死循环当中。 ```cpp inline bool SPFA() { memcpy(cur, head, sizeof(cur)); memset(dis, 0x3f, sizeof(dis)); dis[s] = 0; vis[s] = ++cnt; // 为加速，vis 改为使用时间戳 q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (register int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w, c = edge[i].c; if (w > 0 && dis[u] + c < dis[v]) { // SPFA 只用于跑出残量网络的最短路 dis[v] = dis[u] + c; if (vis[v] != cnt) { vis[v] = cnt; q.push(v); } } } } return dis[t] != 0x3f3f3f3f; } int dfs(int u, int flow) { if (u == t) return flow; stp[u] = cnt; // stp[u] 记录当前增广图上 u 是否已被搜过 // 只要一搜到 u 就必须记录 stp[u] int used = 0; for (register int i = cur[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w, c = edge[i].c; cur[u] = i; // 弧优化 if (stp[v] != cnt && dis[u] + c == dis[v] && w > 0) { // 必须满足 v 没有被搜过才能继续搜 v int inc = dfs(v, min(flow, w)); if (inc > 0) { edge[i].w -= inc; edge[i ^ 1].w += inc; used += inc; flow -= inc; if (!flow) return used; } } } return used; } inline void dinic() { cnt = 0; while (SPFA()) { cnt++; int inc = dfs(s, 0x7fffffff); // inc 为流量增量 maxflow += inc; mincost += inc * dis[t]; } return ; } ``` # DAY 2 ## 有上下界的网络流 **参考资料 [CSDN](https://blog.csdn.net/Regina8023/article/details/45815023)** 三张图描述基本思想：    其中，图 3 中的绿色节点是 附加源$x$（6 号节点） 以及 附加汇$y$（5 号节点），为引入的两个额外节点。对于一条边 $<u,v>:w\in[l,r]$，把这条边拆成： $$\begin{aligned}<u,v>:w&=l;\\<x,v>:w&=l;\\<u,v>:w&=r-l.\end{aligned}$$ 假设与 $x,y$ 相连的所有边都是满流，那么只要剩下的节点满足流量平衡（流入 $=$ 流出），整张图就存在可行流。 等价转化以后，可知： $$\text{存在可行流}\Leftrightarrow f_{max}(x,y)=\sum_{<u,x>\in E} c(u,x).$$ ### 无源汇网络流 **定义：** 没有源点和汇点，图上所有点都必须满足流量平衡（$\forall u,\forall v,f(u,v)+f(v,u)=0$）。这种图没有最大流 / 最小流的说法，但是可以判断是否存在可行流：增加一个源点和汇点，按照上述方法等价转化，然后跑最大流即可。 ### 有源汇网络流 **定义：** 有源点和汇点，可以看作是在无源汇图上加上了一条特殊边$<t,s>:w=\infty$。那么在跑出$f_{\max}(x,y)$之后，残量网络中$<t,s>$的反向边$<s,t>$上的流量（也就是$c(s,t)$）即为整张图的一个可行流大小。 #### 最小流 考虑先跑出$F_1=f_{\max}(x,y)$，在$<s,t>$上获得一个可行流；然后断掉所有与$x,y$相连的边（实际操作中，由于可行流已经把这些边流满，因此可以不用管这一步）以及$s,t$之间的边，在残量网络上跑出$F_2=f_{\max}(t,s)$（注意是$t\rightarrow s$），表示可以退回的流量。则对于原图： $$F_{\min}=F_1-F_2$$ #### 最大流 与最小流类似，先跑出$F_1=f_{\max}(x,y)$；然后断掉额外边，跑出$F_2=f_{\max}(s,t)$（注意是$s\rightarrow t$），表示在可行流基础上可以再流的流量。则对于原图： $$F_{\max}=F_1+F_2$$ ## 最大流最小割定理 **定义：** 对于一个网络图$G$，若能把图上的点划分为两个点集$S,T=V-S$，其中$s\in S,t\in T$，则这个划分方式$(S,T)$为图的一个割。用$c(s,t)=\sum_{u\in S,v\in T}c(u,v)$来表示割的容量，最小割即$c_{\min}(s,t)$。 **定理：** $$c_{\min}(s,t)=f_{\max}(s,t)$$ **简单证明：** 显然任意流$\leq$任意割。当达到最大流，由于$s,t$之间已经无法增广（没有通路），因此一定能够构造出一个割$(S,T)$使得$c(S,T)=f_{\max}(s,t)$。此时，割的容量达到最小值。 ### 输出方案 得到最大流以后，在残量网络中从$s$开始跑出一个联通块，那么这个连通块内的点组成的集合就是$S$。 # DAY 3 ## 欧拉定理 $$e^{i\theta}=\cos\theta+i\cdot \sin\theta$$ ## 虚数的相关概念 任取复数$a,b$，辐角分别是$\alpha,\beta$，则： $$a=|a|\cdot e^{i\cdot \alpha},b=|b|\cdot e^{i\cdot \beta}.$$ $$a\times b=|a|\cdot |b|\cdot e^{i\cdot(\alpha+\beta)}.$$ 所以复数乘法的几何意义是向量的伸缩和旋转。$a\times b$ 的几何意义是使复平面上$a$所对应的向量 $\vec{a}$ 的模长变为原来的 $|b|$ 倍，并逆时针旋转角度 $\beta$ 所得到的向量。 用极坐标表示，设$\vec{a}=(r_1,\alpha),\vec{b}=(r_2,\beta)$，复数$a\times b=c$，则有： $$\vec{c}=(r_1\cdot r_2,\alpha+\beta).$$ ## 单位复根 将单位圆等分成$n$个部分（以单位圆与实轴正半轴的交点为第一个等分点），以原点为起点，圆的这$n$个$n$等分点为终点，作出$n$个向量。 其中幅角为正且最小的向量称为$n$次单位向量，记为$\omega_n^1$。其余的向量就分别为$\omega_n^2,\omega_n^3,\cdots,\omega_n^n$。 那么显然有以下性质： $$\omega_n^n=\omega_n^0=1,$$ $$\omega_n^k=e^{2\pi\cdot\frac kni}=\cos(2\pi\cdot\frac kn)+\sin(2\pi\cdot\frac kn).$$ $$\omega_{2n}^{2k}=\omega_n^k\Rightarrow \omega_{mn}^{mk}=\omega_n^k.\text{（折半引理）}$$ $$\omega_n^{k+\frac 2n}=-\omega_n^k.\text{（消去引理）}$$ ## 快速傅里叶变换 ### DFT 设一个$n-1$（其中$n=2^k,k\in \text{N}$）阶多项式$f(x)=\sum_{i=0}^{n-1} a_i\cdot x^i$。如果在曲线上取$n$个互不相同的点，就可以由 **高斯消元法** 唯一确定所有项的系数。 以$7$阶多项式（8 个项）为例，设 $$f(x)=a_0+a_1x^1+a_2x^2+\cdots+a_7x^7.$$ 再设 $$\begin{aligned}h(x)=a_0+a_2x^1+a_4x^2+a_6x^3,\\g(x)=a_1+a_3x^1+a_5x^2+a_7x^3.\end{aligned}$$ $$\Rightarrow f(x)=h(x^2)+x\cdot g(x^2).$$ 假设带入的自变量$x=\omega_n^k$，则 $$f(\omega_n^k)=h(\omega_n^{2k})+\omega_n^k\cdot g(\omega_n^{2k}).$$ $$\begin{aligned}\Rightarrow f(\omega_n^k)&=h(\omega_{\frac n2}^k)+\omega_n^k\cdot g(\omega_{\frac n2}^k),\\f(\omega_n^{k+\frac n2})&=h(\omega_{\frac n2}^k)-\omega_n^k\cdot g(\omega_{\frac n2}^k)\end{aligned}$$ 由于$k,k+\frac n2$取遍了$[0,n-1]$中的所有整数，也就是说取了互不相同的$n$个自变量$x_i$的值带入$f(x)$，所以根据获得的$y_i=f(x_i)$，一定可以反算出所有项的系数。 所以对于多项式$f(x)=\sum_{i=0}^{n-1}a_i\cdot x^i$，把它转化为$n$个值$y_k=f(\omega_n^k)$的过程就叫 DFT。 再观察上面的表达式，可以发现$h(x),g(x)$的规模都是$f(x)$的一半（观察$\omega$的下标可得），因此可以递归成两个子问题求解，DFT 的复杂度由朴素代入的$O(n^2)$降为$O(n\log n)$。  $$\footnotesize\text{图源：OI Wiki}$$ 观察规律：原来序列，每个数的下标用二进制表示，然后把二进制翻转对称一下，就是最终那个位置的下标。这个方法可以把递归变为循环。 实现时需要预处理 `rev[i]` 表示 `i` 的二进制为翻转后的值： ```cpp rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1)); ``` ### IDFT 在 DFT 以后，设$y_i=f(w_n^i)$，则系数方程可以用下面这样一个矩阵运算式表示：  $$\footnotesize\text{图源：OI Wiki}$$ 简化为：$Y=X\times A$ 那么为了求得$A$，只需要左右同时左乘$X$的逆矩阵（设为$X^{-1}$），也就是说： $$A=Y\times X^{-1}$$ 代入$X\times X^{-1}=D\text{（单位矩阵）}$可得： $$X^{-1}_{j,k}\cdot X_{j,k}=\frac 1n$$ 观察矩阵运算式，于是有： $$X_{j,k}^{-1}=\frac 1nw_n^{-k\cdot j}$$ $$\Rightarrow a_j=\frac 1n\sum_{k=0}^{n-1}y_k\cdot w_n^{-k\cdot j}$$ 可以发先这个式子等价于把$\omega_n$换为$\omega_n^{-1}$，并且再乘上$n^{-1}$的 DFT，所以就可以合二为一，用一个 `fft()` 函数一起写。 ```cpp #include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); const int MAXN = 3e6 + 10; // 开 2 倍空间似乎不够，多多益善 struct Complex { double x, y; Complex(double src_x, double src_y) { x = src_x; y = src_y; } Complex() {} Complex operator + (const Complex &b) const { return Complex(x + b.x, y + b.y); } Complex operator - (const Complex &b) const { return Complex(x - b.x, y - b.y); } Complex operator * (const Complex &b) const { return Complex(x * b.x - y * b.y, x * b.y + y * b.x); } }; Complex a[MAXN], b[MAXN]; int rev[MAXN]; // 用于保存 i 二进制翻转以后的数 int n, m, l = 0; inline void fft(Complex y[], int len, int flag) { for (int i = 0; i < len; i++) if (i < rev[i]) swap(y[i], y[rev[i]]); // 预处理 for (int h = 2; h <= len; h <<= 1) { // h: 合并区间的长度 Complex wn(cos(pi * 2 / h), sin(pi * 2 * flag / h)); // 计算单位复根 for (int j = 0; j < len; j += h) { Complex w(1, 0); // w 保存当前代入的值 for (int k = j; k < j + (h >> 1); k++, w = w * wn) { Complex u = y[k]; Complex v = w * y[k + (h >> 1)]; y[k] = u + v; y[k + (h >> 1)] = u - v; } } } if (flag == -1) for (int i = 0; i < len; i++) y[i].x /= len; // IDFT 中的 1 / n 系数 return ; } inline int read() { register int res = 0, flag = 0; register char ch = getchar(); while (!isdigit(ch)) ch == '-' ? flag = 1, ch = getchar() : ch = getchar(); while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ '0'), ch = getchar(); return flag ? -res : res; } int main() { n = read(), m = read(); while ((1 << l) <= n + m) l++; for (int i = 0; i <= n; i++) a[i].x = read(); for (int i = 0; i <= m; i++) b[i].x = read(); for (int i = 0; i < (1 << l); i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1)); // 预处理 rev[] fft(a, 1 << l, 1); fft(b, 1 << l, 1); for (int i = 0; i <= (1 << l); i++) a[i] = a[i] * b[i]; // DFT 完成以后，合并 f(x) 与 g(x) 信息供 IDFT 使用 fft(a, 1 << l, -1); for (int i = 0; i <= n + m; i++) printf("%d ", int(a[i].x + 0.5)); // 四舍五入排除精度损失 return 0; } ``` --- # DAY 4 **退役了**