欢迎来到 Pomelorin 和 Cool-breeze 的博客！希望我们能相互交流，共同进步～

图标是清爽葡萄柚汽水（确信）。

I. Version Number

题意简述

有 \(T\) 组测试数据。每组给出两个版本号 \(A\) 和 \(B\)，版本号由若干个数字段用点号分隔，且所有版本号的段数相同。

按顺序逐段比较 \(A\) 和 \(B\) 的对应数字段：若 \(A\) 的当前段大于 \(B\) 的当前段，则 \(A\) 更新；若小于，则 \(B\) 更新；若相等，则继续比较下一段。若所有对应段都相等，则输出 Equal；否则输出更新版本的编号 A 或 B。

数据范围

\(1 \le T \le 100\)；每个版本号最多包含 \(3\) 个点，即最多 \(4\) 个数字段；每个数字段的长度不超过 \(9\)，且不含前导零。

B. 出 Bug 的绘画软件I

题意简述

画布由若干有序图层组成，每层是 \(n\times m\) 的像素网格。像素值 \(0\) 表示透明，\(1\sim nm\) 表示不同颜色。某位置的合成可见值为所有图层中最上层非透明像素的值；若所有图层在该位置都透明，则可见值为 \(0\)。

初始没有图层。可以任意次执行：

• 免费在最上方新建图层，初始化为全为颜色 \(c\) 的常量层（\(1\le c\le nm\)），或全透明层；
• 花费 \(a\) 将任意图层中任意单个像素涂成颜色 \(c\)；
• 花费 \(b\) 将任意图层中任意单个像素变为透明。

给定目标可见矩阵 \(p_{i,j}\)，求使最终合成图像等于目标图像的最小总花费。

数据范围

\(1\le T\le 10^5\)，\(1\le n,m\le 500\)，\(1\le a,b\le 10^6\)，\(0\le p_{i,j}\le nm\)，且所有测试用例的 \(\sum nm\le 10^6\)。

模板——补充

数论分块、中缀表达式求值、string、在图中找环。

模板——树上算法

LCA，树的一些性质，点分治，树上莫队，DFS 序与欧拉序，树上启发式合并，Kruskal 重构树，树链剖分。

模板——数据结构2

线段树，树状数组，动态开点线段树，线段树合并，主席树，树套树，平衡树。

B. 梦中星河

给定非负整数 \(x\)，求三个非负整数 \(a,b,c\) 满足 \(a\times b+c=x\)，并使得 \(\max(a,b,c)−\min(a,b,c)\) 尽可能小。输出该最小值。要求约 \(O(\sqrt x)\)。

G. 炒股高手

已知 \(n\) 个交易日中股票的股价（所有价格均以自然对数的形式给出）。可以购买非整数份的股票。共有 \(m\) 个时间区间，本金均为 \(e^k\)。求每个时间区间进行买入卖出后得到的总资产。\(n\le 10^5,m\le 10^5\)。

D. 与或博弈

博弈规则如下：

• gsh 和 AI 轮流操作，gsh 先手。
• 他们操作两个非负整数 \(a\) 和 \(b\)，gsh 的目标是将其变为目标非负整数 \(x\) 和 \(y\)，而 AI 需要阻止 gsh 达成目标。
• gsh 在自己的回合可以执行以下两种操作之一：
  1. \(a := a \mathbin{\&} v\)（按位与某个非负整数 \(v\)）。
  2. \(b := b \mathbin{|} v\)（按位或某个非负整数 \(v\)）。
• AI 在自己的回合可以执行以下两种操作之一：
  1. \(a := a \mathbin{|} v\)（按位或某个非负整数 \(v\)）。
  2. \(b := b \mathbin{\&} v\)（按位与某个非负整数 \(v\)）。
• 允许选择的 \(v\) 满足 \(0 \leq v \lt 2^{60}\)。
• 双方都足够聪明，并且都会采取最优策略以赢得游戏。
• 若在 \(10^{100}\) 回合内，存在某一时刻 \(a = x\) 且 \(b = y\)，则 gsh 获胜；否则，AI 获胜。

请你判断 gsh 是否必胜，若必胜，输出 Yes，否则输出 No。

F. Inversion Pairs

只含有 01? 三种字符的字符串，可以把 ? 变成 0 或 1，求逆序对最多为多少。

逆序对 贪心 填法一定是左边都填 1，右边都填 0，枚举这个分界点即可。

预处理前缀 1 个数与后缀 0 个数，先假设都填 0，之后从左向右开始填 1。贡献变化为加后面 0 的个数减前面 1 的个数。