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

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

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\)。

模板——补充

数论分块。

数论分块

求 \(\sum_{i=1}^n \lfloor n/i\rfloor\)，时间复杂度为 \(O(\sqrt n)\)。

1
2
3
4
5
6
7
8
9
10
11

long long H(int n) {
  long long res = 0;  // 储存结果
  int l = 1, r;       // 块左端点与右端点
  while (l <= n) {
    r = n / (n / l);  // 计算当前块的右端点
    // 累加这一块的贡献到结果中。乘上 1LL 防止溢出
    res += 1LL * (r - l + 1) * (n / l);
    l = r + 1;  // 左端点移到下一块
  }
  return res;
}

模板——树上算法

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 的个数。

CSP38 T4 月票发行

CSP38 T4 月票发行

题意：长度为 \(n\)（\(10^9\)）的字符串有 \(m\)（\(10^6\)）个固定为 #，其余能填任意小写字母。问至少有一个 ccf 和一个 cspark 子串，且至少有一个 ccf 出现在 cspark 前的字符串数量。