#dp #背包dp #多重背包 #算法优化 #经验总结

看到多重背包 -> 01 背包的转化操作中，使用了二进制拆分。第一眼觉得这种方法的正确性很难判断，就想了个把小时，总算是想明白了，写篇文纪念一下。  


## 多重背包问题是什么
> 为了防止误会，在原问题中的物品不加引号，在转换后的问题中的物品加引号

多重背包问题背景：存在容量为 $V$ 的背包和 $N$ 组物品，第 $i$ 组物品有 $K_i$ 个且每个价值都为 $V_i$，求背包能装下的物品价值和的最大值。  

> TODO: 使用二维 dp 写一下思路
## 朴素的优化方法
> 为了更好地表达，下面使用 `"物品"的数量` 来表示拆分后的"物品"于原问题中的等效数量

我们可以发现多重背包问题并没有这么多限制，即可以尝试把问题转化为 01 背包问题。  
最简单最朴素的方法就是把"组"的概念拆掉：把「每种物品选 $k_i$ 次」等价转换为「有 $k_i$ 个相同的物品，每个物品选一次」[^1]。  
那这样的话，可见的是复杂度爆炸（时间复杂度为 $O(V \sum_{i=1}^n K_i)$），且显然存在子问题重复（多个"物品"的价值相同）。  

显然，复杂度中的 $O(nV)$ 部分无法再优化了，我们只能从 $O(\sum K_i)$ 处入手。为了表述方便，我们**用 $A_{i,j}$ 代表第 $i$ 种物品拆分出的第 $j$ 个物品**。[^2]   
在朴素的做法中，$\forall j\leq K_i$，$A_{i,j}$ 均表示相同物品。而效率低的原因在于我们在后续跑 01 背包时进行了大量重复性的工作。  
举个栗子，这个算法实际上考虑了「同时选 $A_{i,1},A_{i,2}$」与「同时选 $A_{i,2},A_{i,3}$」这两个完全等效的情况。那么优化拆分方式就成为了解决问题的突破口。[^3]  

> TODO: 使用 01 背包写一下朴素优化的代码
## 思考
观察上面的操作，其正确性是显而易见的：上述的拆分操作不会影响到答案。即原先需要选择某个组中的 $X$ 个物品，在拆分后也会进行这样的选择（选择等效的 $X$ 个"物品"）。  

那么什么情况下会没有正确性呢？  
举个栗子，假设我们使用了某些奇怪的拆分操作，把某个有 $4$ 个物品（在朴素的做法中，这个组会被划分成 ${1, 1, 1, 1}$）的组划分成了 $\{2, 2\}$ 个物品的形式，而正解会选择这个组的 $3$ 个物品。显然，这种划分方式无论如何也没办法凑出来 $3$ 这个数字，而朴素的做法可以（$1+1+1=3$）。  

根据上面的例子，可以发现错误的划分方法会增加限制（比如对于某个组，拆分后的"物品"凑不出来正解中选择的物品数量），从而得不到正解。  
在这里可以看出一些端倪：如果我们对任意组（假设有 $Y$ 个物品）进行拆分，得到的"物品"们的数量可以凑出来任意 $[0, Y]$，那是不是不会增加限制呢？  

## 二进制拆分是什么
这里就可以尝试用 CS 中常用的二进制拆分操作，即对于某组中的 $Z$ 个物品，我们拆成下面的"物品"集合（下面是不太严谨的表述，意会即可）  
$$NewC=\set{2^0, 2^1, 2^2, ..., 2^k, Z-(2^{k+1}-1)}, k\in \mathbb{N}, Z<2^{k+1}$$
  
**注意，上面提到的集合 $NewC$ 是我们构造的有特殊性质的集合。**  
为什么要这么构造呢？我们可以简单看一下构造，可以简单地分为两部分：
1. $2^0, 2^1, 2^2, ..., 2^k$
2. $Z-(2^{k+1}-1)$

可以发现，只有 $Z-(2^{k+1}-1)$ 项是比较特殊的，为了方便，**在后面称呼 ta 为 $P$**。  
因为这个值的意义是某个"物品"的数量，后面会使用 $P$ "物品"来代指"物品"的数量为 $P$ 的"物品"。  

接下来就应该尝试证明这种拆分能表示的答案区间了。在这里进行分类讨论，分别是 一定不选 $P$ "物品"的情况 和 一定选 $P$ "物品" 的情况。  

可以发现，一定不选 $P$ "物品"时，数量和最大为 $2^{k+1}-1$。（提一嘴没啥用的，这能很容易地证明这个集合的数量和为 $Z$。）  

**在理解下面这一句的时候，请使用组合排列与代数的方法思考！**  
在一定不选 $P$ "物品"时，剩下的"物品"的数量的子集的和 $S\in[0, 2^{k+1}-1]$。  
在一定选 $P$ "物品"时，其子集的和 $S'\in[Z-(2^{k+1}-1), Z]$。  

在这里，因为 $Z<2^{k+1}$，我们可以证明 $Z-(2^{k+1}-1) \leq 2^{k+1}-1$  
所以，在这里 $S$ 和 $S'$ 的并集可以覆盖整个区间，即
$$S\cap S'=[1, Z]$$  
而在 01 背包问题中，子问题是可重复贡献问题，所以这两个子问题完全可以合并，得到完整的答案区间（和倍增 ST 表的子问题合并的可行性证明比较接近）。    

总结一下，使用这种方法，我们可以做到：  
1. 让拆分后的"物品"数量和等效地表示选择某个组中的物品数，不会破坏答案空间
2. 相比朴素的拆分方法，对于有 $Z$ 个物品的组，最多只会得到 $\lfloor \log_2{Z} \rfloor+1$ 个"物品"，优化效果理应不错

> TODO: 写一下代码



  
[^1]: 此句述来自 OI-Wiki ([OI-wiki/docs/dp/knapsack.md at master · OI-wiki/OI-wiki (github.com)](https://github.com/OI-wiki/OI-wiki/blob/master/docs/dp/knapsack.md))
[^2]: 此段描述改写自 OI-Wiki
[^3]: 此段描述改写自 OI-Wiki

多重背包优化中二进制拆分的合理性证明

#dp #线性dp #经验总结

# 题目
[0Frog - 蓝桥云课 (lanqiao.cn)](https://www.lanqiao.cn/problems/3601/learning/)

简化版题目：
给定路径长度 $N$，初始位置为 $0$，可以选择静止或向前移动若干单位，移动范围在 $A$ 到 $B$ 之间。最多可以移动 $K$ 次。路径上每个位置有若干数量的物品。求最多可以收集到的物品数量。  



第一行包含一个整数 $T$ ($1 \leq T \leq 10$)，表示测试用例的数量。  
对于每个测试用例：  
- 第一行包含四个整数 $N, A, B, K$ ($1 \leq A \leq B \leq N \leq 100$，$1 \leq K \leq N$)。
- 第二行包含 $N$ 个整数 $a_1, a_2, ..., a_N$ ($1 \leq a_i \leq 1000$)，描述路径上每个位置的物品数量。

## 题目分析
### 观察
1. 数据范围很水，写 $O(n^3)$ 都能随便过
2. 搜索看起来能过这个题目
3. 存在很显然的子问题拆分方法：如果已经通过 $K'$ 次移动到达位置 $N'$，此时子问题为 对于路径 $[N', N]$ / 最多可以移动 $K-K'$ 次 / 求最多可以收集到的物品数量
4. 对于 3. 提到的子问题，很显然无后效性且子问题重叠，那么这个题显然可以用 dp
5. 题目貌似只规定了起点，没规定终点（很重要，因为~~我交的第一发挂在这里了~~）
### 分析搜索和 dp 哪个好写
看起来写 dp 是愉快的选择~  
#### 搜索
因为子问题重叠，所以可以写个记忆化搜索。感觉答案空间还是比较好搜的（容易遍历），估计搜索函数部分 20 行以内可以解决。  
#### dp
显然这个题目只需要写几个循环就行了，那不会超过 10 行。  
## dp 写法
最优状态很显然是可以收集到的物品的最大值。  
我们先筛一下哪些状态对我们有用：到达某个点 $i$ 时，使用过 $j$ 次跳跃，此点的获得值应该为 $j-1$ 跳跃时的值加上此点的值。  
那么很显然，这一切都与目前的位置 $i$ / 目前使用过跳跃的次数 $j$ 有关系，那就可以顺理成章的打出 $f_{i, j}$ 表示目前位置的状态。  
转移方程可以先口胡一下再验证：
$$f_{i, j}=\max_{o=a}^{b}(f_{i-o, j-1})$$  
可以发现，这个题好像已经做完了（逃）  
然后看到 $i-o$，就要注意一下越界的问题。最开始我写了这么样的代码：  
```cpp
int p=max(0, i-o);
```
试图给 $i-o<0$ 的部分进行转移，这显然是没有办法解释的操作（~~人类迷惑行为~~），实际上只需要不处理这部分即可：  
```cpp
if(i-o<0) continue;
```

## 总结
感觉这个题目主要难度还是在设计状态上面，太久不做 dp 题，根本没这种感觉 XD。

蓝桥云课 3601 青蛙吃虫 题解

> Last Edit: 2024/1/16 16:32

> 一个搜索题目，比较神奇



## 题目分析
### 第一眼的感觉
欸？一看到下面几个要点：
- 数据范围不大不小，看起来不能搜索（搜索需要 $N<=30$），但可以 DP（$O(N^2)$ 的 DP 需要 $N<=1e4$ ）
- 存在最优子结构：如果我们任意选择 $x$ 个砝码（$x<n$），我们可以得到子问题的解（可以被认为是局部最优解），多个子问题的解可以合并
- 决策无后效性："选择某个砝码"这个决策不影响之前已有的决策
- 存在"有限的容量"（天平最大承重能力 $C$），需要满足限制条件（每个砝码只取一次），最大化某些价值（选择的砝码质量和）

那看起来很可以用 01 背包（DP）来做！那来设计一下 DP 方程吧！
DP 状态的设计：令 $F_{i, j}$ 表示用前 $i$ 个物品填满容量为 $j$ 的背包时能达到的最大价值（选择的砝码质量和）
DP 转移方程的设计：
- 存在两种情况，我们进行分类讨论：
	- 使用第 $i$ 个砝码：我们需要从容量最合适的位置（即容量为 $j-weights_i$ 处）获取处理第 $i-1$ 个砝码后的状态（子问题解）
	- 不使用第 $i$ 个砝码：这样不会对容量产生影响，可以直接从 $i-1$ 处继承处理第 $i-1$ 个砝码时的状态
- 可以写出 $F_{i, j} = max(F_{i-1, j} , F_{i-1, j-weights_i} + weights_i)$
- 根据单调性，可以去掉第一维，写出  $F_{j} = max(F_{j} , F_{j-weights_i} + weights_i)$

那就开始写...欸！不对啊，这么说的话，$j<=C$ ，而 $C\in[1, 2^{30}]$。
如果直接开数组，如：
```cpp
const int C=(1<<30);
int f[C];
```
这不直接爆内存（125MB）了嘛。

那看来 DP 不是一个很好的方案。

### 再看一眼
继续读题，可以发现一个有意思的条件：`这一行中从第 3 个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。`
那么我们可以推测出，最特殊的砝码质量序列应该为斐波那契数列（从第三个砝码开始，每个砝码的质量等于前两个砝码质量的和）。
而当砝码质量序列为斐波那契数列时，显然这是让每个砝码质量都最小的情况。
如果上面可以用 DP，那么这个条件显然是多余的——01 背包不需要序列满足什么性质；显然，这个条件可以改善我们窘迫的情况。
回到最初我们分析问题的时候，我们对 $N$ 的大小进行了分析，而我们都知道，斐波那契数列的增长速率是惊人的。当 $N=1e3$ 时，${Fib}_{1e3}>2^{30}$（可以使用 Binet 公式 ${Fib}_n=\frac{(1+\sqrt{5})^n}{2^n \sqrt{5}}$ 和对数计算来估计）。
那么这个 $N$ 的大小显然是不符合条件的的，所以我们可以估算最大的 $N$
可以写出下面的代码（不会有人觉得我要用 Binet 公式来算吧？）
```cpp
#include <cstdio>
#include <algorithm>

int main() {
	int n=30, cnt=2;
	int x=1, y=1;
	while(y<(1<<n)) {
		int t=x+y;
		x=y;
		y=t;
		++cnt;
	}
	printf("N=%d Fib_N=%d C=%d\n", cnt, y, (1<<n));
	return 0;
}
```
输出为
```plain
N=45 Fib_N=1134903170 C=1073741824
```

那么我们就愉快的发现，$N$ 原来超级小！

### 分析一下另一条赛道
那么是不是可以重新考虑一下搜索算法的可行性了呢，毕竟搜索破万法！（搜索算法的适用范围十分广泛）
但 $N$ 的范围还是有一些大，我们使用 $O(2^{N})$（$N=45$）的搜索算法肯定会爆时间，但不妨先写一下看看情况。

#### 朴素搜索
题目条件提到 `砝码的质量是一个不下降序列`，那么我们可以从根据质量从大到小进行选择。
根据 `每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和`，我们似乎不需要回溯地去考虑曾经做过决策的砝码——这其实是无后效性的表现。

那么我们只需要对于第 $x$ 个砝码（$x \le N$）考虑两种情况：
- 使用第 $x$ 个砝码：加上第 $x$ 个砝码的重量
- 不使用第 $x$ 个砝码：直接跳过
那么可以写出这样的代码：
```cpp
#include <cstdio>
#include <algorithm>

using std::max;

typedef long long ll;

const int N=1e3+11;

int n, c;
int a[N];

ll ans=0;
ll curr=0;
int b[N];

void dfs(int x) {
	if(!x) return;
	
	if(curr+a[x]<=c) {
		// select one
		curr+=a[x];
		ans=max(ans, curr);
		dfs(x-1);
		curr-=a[x];
	}
	
	// select none
	dfs(x-1);
}

int main() {
	scanf("%d%d", &n, &c);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	dfs(n);
	printf("%lld\n", ans);
	return 0;
}
```
很显然，TLE 了（[Luogu 评测记录](https://www.luogu.com.cn/record/143018540)）。

#### 剪枝搜索
可以考虑一下剪枝能否解决问题。
我们可以发现这个题目的解法存在这些性质
- 当 $C$ 较小时，我们需要用很多小砝码来得到答案
- 当 $C$ 略小于 $\sum_{i=1}^{n}{weights_i}$ 且不太小时，我们需要几个大砝码和很多小砝码来得到答案
- 当 $C$ 大于等于 $\sum_{i=1}^{n}{weights_i}$ 时，答案为所有砝码的重量和

注意到，大部分解法需要用到很多小砝码。而在上面的代码，对于所有砝码的处理过程相同。我们是否可以用某些办法批量地使用小砝码呢？

一种方法是，使用前缀和 $Sum_i=\sum_{j=1}^{i}{weights_i}$。我们可以在处理第 $i$ 个砝码时，把序号在 $[1, i]$ 的砝码当作某个特殊的砝码来处理，尝试一次使用多个砝码。如果可以使用，那便没有必要再去尝试分开处理这些砝码了——此时已经得到了局部最优解。
注意，虽然 $weights_i\in[1, 2^{30}]$，但 $\sum_{i=1}^{N}{weights_i}\in[1, 45*2^{30}]$。而 $45*2^{30} \le 64*2^{30} = 2^{36} < 2^{63}-1$（在 `long long` 类型的范围内），我们有必要给 `sum` 数组使用 `long long` 类型。

```cpp
#include <cstdio>
#include <algorithm>

using std::max;

typedef long long ll;

const int N=1e3+11;

int n, c;
int a[N];
ll sum[N];

ll ans=0;
ll curr=0;
int b[N];

void dfs(int x) {
	if(!x) return;
	
	// 1. select all
	if(curr+sum[x]<=c) {
		ans=max(ans, curr+sum[x]);
		return;
	}
	
	if(curr+a[x]<=c) {
		// 2. select one
		curr+=a[x];
		ans=max(ans, curr);
		dfs(x-1);
		
		curr-=a[x];
	}
	// 3. select none
	dfs(x-1);
}

int main() {
	scanf("%d%d", &n, &c);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	for(int i=1; i<=n; i++) sum[i]=sum[i-1]+a[i];
	dfs(n);
	printf("%lld\n", ans);
	return 0;
}
```

woc，居然能过，~~有点水~~（[评测记录](https://www.luogu.com.cn/record/143003296)）

Luogu P5194 题解

这通折腾的起因是想给博客配一个更加合适的图床，下面是我对结果的希望：
1. 价格优惠，最好有一定免费额度，计费项、付费方式要阳间：毕竟是个人博客用的图床
2. 速度较快，尤其是在中国大陆地区：考虑访问者主要地区
3. 不想备案：备案太麻烦了，而且要牵扯上一整个域名



## 探索路程
下面是目前（2023 年以后）做过的一些探索，如果更希望看目前最优方案请跳过。  

在 2023 年以前，曾经尝试过又拍云对象储存、阿里云 OSS、SMMS、路过图床。前两者因为备案问题而被我抛弃，后面两者生怕服务不稳定、跑路而被我抛弃。  
### 腾讯云 COS 国内
虽然仍然有备案的问题，但这段时间我薅到了朋友的备案域名的子域，所以稍长地使用了腾讯云 COS。  
COS 的计费项是挺少的，但和阿里云 OSS 一样，储存桶的公网访问流量费用超级贵，也没办法做限流什么的，估计很容易被刷爆钱包——即使我不拉仇恨、小站没人访问。  
这就带来了最大的一个问题，想用必须要套个腾讯云 CDN：
1. 配置麻烦：腾讯云 CDN 的配置项相比 COS 多太多了
2. 计费项多：腾讯云 CDN 的计费项太多了
3. 费时费力：在配置过程中有很多需要等待的环节（DNS 解析生效 / SSL 证书申请 / CDN 配置部署 / CDN 缓存刷新）。如果某个环节出了问题，就更糟心了。更糟糕的是，不能一劳永逸，对于每一个桶都需要重新配置一次，只能刷熟练度，累死了都。

好处是挺多，最大的就是访问速度极快。可对于个人博客，好像没有追求极快加载速度的刚需。相比于折腾，我宁愿抛弃一些所谓“好处”。

### 腾讯云 COS 国外
鉴于腾讯云也加入了 [Cloudflare 带宽联盟](https://www.cloudflare.com/zh-cn/bandwidth-alliance/)，简单来说就是腾讯云 COS 部分地区（国外）套用 Cloudflare CDN 可以免除流量费用。  
一打眼是挺好的，但有一句话是“套了 CF 众生平等”，我都要套 CF CDN 了，我干嘛不去用其他对象储存呢？  
再说，腾讯云 COS 的国外地区单单储存费用就不低，还基本不能用储存容量资源包来抵扣，也不太实惠啊。

### 本地部署 MinIO
MinIO 确实是一个好项目，无论是生态的完整性还是本身的性能，都值得称赞。部署上也没有很多的槽点，Docker 镜像一拉就好了。  
但让我犹豫的是以下几点：
1. 安全性和运维难度不好权衡。单点部署无法保证服务的可用性，也很容易导致“数据火葬场”。倘若使用集群部署，那运维难度直线上升，或许要需要套 K8s 之类更更更复杂的东西才能用着舒服，学习成本太高昂了。
2. 服务器成本本身就不低。搭建 MinIO 的服务器（集群）要有较大的储存空间、较大的上传带宽、不错的线路——别说三条同时满足了，满足一条就~~可以疯狂爆米了~~。
于是还没开始大规模部署，我就抛弃这个方案了，除非我已经搭建好了一个 K8s 集群，并且各个节点基本满足上面的条件。

### Wasabi
这家很早就以“$5/TB/mo” “No Fees for Egress”著名。但不好的是，付款方式没那么阳间，出口流量虽然不收费，但的确是有限制的，每月出口量大抵和总储存量相当。  
也就是说，存储大量低频访问的文件时，才能算得上实惠。  
近几年各家也推出了类似价格 / 更低价格的对象储存方案，好像也没啥必要选择这家厂的产品了。

### Cloudflare R2
这就是目前使用的方案，完全符合最开始提到的期望。  
下面是一些零散的补充：
1. 感觉 R2 套了 CF CDN 后的访问速度十分快，~~甚至快到让你怀疑人生~~
2. CF 可以绑定银联卡信用卡 / Paypal 银联卡
3. 10 GB 的免费额度

## 最终方案
Cloudflare R2 作为 S3 对象储存的提供方；在 PC 上使用 Picgo 来上传图片，使用 Rclone 来同步文件、管理云端文件；在 Vanblog 上使用 PicgoCore 来上传、管理图片。  
> Tip：PicgoCore 是 Picgo 的命令行版本，共用一套插件体系和大部分配置项

## 教程
### Cloudflare R2 + Rclone
> 教程：[rclone · Cloudflare R2 docs](https://developers.cloudflare.com/r2/examples/rclone/)

十分建议仔细阅读上面的教程，并且注意下后面提到的坑点。
### Picgo 客户端配置
#### Picgo Plugin Rclone
这个插件的配置项的提示较少，没那么容易配置。但主要难点还是在配置 Rclone 上面。  
放张图欣赏一下（可以参考一下我的填法）：
![Picgo Plugin Rclone 界面.png](https://github.com/CornWorld/CornWorld/assets/43746030/929b9436-39d9-455c-b101-a02384b1d6f0)

反正我刚看到这界面是有点懵的，迷迷糊糊填完后发现不能跑，一直怀疑是自己填错了，而不是出了什么其他问题。  
实际上是下一个坑点所致。  
#### Picgo Plugin S3
其实和配置 Rclone 大差不差，只是有一个需要注意的点：文件路径指的是文件的绝对路径，而不是文件所在的目录。  
比如：上面的图片中“上传路径”填写的是 `{year}{month}/`，在这个插件中的“”填写的是`{year}{month}/{md5}.{fileName}.{extName}`。

## 坑点
### Rclone Copy / Sync S3 储存源的时候默认不检查 Bucket 是否存在，而是始终带一个 `CreateBucket` 指令，在 Token 权限不够时导致 HTTP 403
放张图看看 CF 新建 R2 API Token 的时候允许的权限，我按直觉选了`Object Read & Write`，显然没有 `CreateBucket` 权限。

![Cloudflare R2 API 权限列表.png](https://github.com/CornWorld/CornWorld/assets/43746030/4afee41e-16bd-40f8-a0a5-86d77bcdfa56)

直接得到了类似如下报错（随便找个文件复现的）：
```plain
C:\Users\cornw\Pictures>rclone sync -P Background.png CornWorldR2:static
2023-10-12 01:14:33 ERROR : Background.png: Failed to copy: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
2023-10-12 01:14:33 ERROR : Attempt 1/3 failed with 1 errors and: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
2023-10-12 01:14:36 ERROR : Background.png: Failed to copy: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
2023-10-12 01:14:36 ERROR : Attempt 2/3 failed with 1 errors and: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
2023-10-12 01:14:38 ERROR : Background.png: Failed to copy: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
2023-10-12 01:14:38 ERROR : Attempt 3/3 failed with 1 errors and: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
Transferred:              0 B / 0 B, -, 0 B/s, ETA -
Errors:                 1 (retrying may help)
Elapsed time:         6.4s
2023/10/12 01:14:38 Failed to sync: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
```
根本看不懂是啥问题啊 orz，摸索半天总算是开开了调试信息输出，得到了这样的报错：
```plain
C:\Users\cornw\Pictures>rclone sync -P Background.png CornWorldR2:static -vv --dump requests --retries 1
2023/10/12 01:09:45 DEBUG : rclone: Version "v1.64.0" starting with parameters ["rclone" "sync" "-P" "Background.png" "CornWorldR2:static" "-vv" "--dump" "requests" "--retries" "1"]
......
2023-10-12 01:09:45 DEBUG : >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2023-10-12 01:09:45 DEBUG : HTTP REQUEST (req 0xc000962700)
2023-10-12 01:09:45 DEBUG : HEAD /static/Background.png HTTP/1.1
Host: <account_id>.r2.cloudflarestorage.com
User-Agent: rclone/v1.64.0
Authorization: XXXX
X-Amz-Content-Sha256: e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
X-Amz-Date: 20231011T170945Z
2023-10-12 01:09:45 DEBUG : >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2023-10-12 01:09:47 DEBUG : <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2023-10-12 01:09:47 DEBUG : HTTP RESPONSE (req 0xc000962700)
2023-10-12 01:09:47 DEBUG : HTTP/1.1 404 Not Found
Connection: close
Cf-Ray: 8148b6734e547bbc-LAX
Connection: keep-alive
Content-Type: text/plain;charset=UTF-8
Date: Wed, 11 Oct 2023 17:09:46 GMT
Server: cloudflare
2023-10-12 01:09:47 DEBUG : <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2023-10-12 01:09:47 DEBUG : Background.png: Need to transfer - File not found at Destination
2023-10-12 01:09:47 DEBUG : >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2023-10-12 01:09:47 DEBUG : HTTP REQUEST (req 0xc000962b00)
2023-10-12 01:09:47 DEBUG : PUT /static HTTP/1.1
Host: <account_id>.r2.cloudflarestorage.com
User-Agent: rclone/v1.64.0
Content-Length: 148
Authorization: XXXX
X-Amz-Content-Sha256: 5c78745b2e361d17109544a85201b4a8be4fd50d6e777f81ffaca6fd5f60024e
X-Amz-Date: 20231011T170947Z
Accept-Encoding: gzip


<CreateBucketConfiguration xmlns="http://s3.amazonaws.com/doc/2006-03-01/"><LocationConstraint>apac</LocationConstraint></CreateBucketConfiguration>
2023-10-12 01:09:47 DEBUG : >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2023-10-12 01:09:48 DEBUG : <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2023-10-12 01:09:48 DEBUG : HTTP RESPONSE (req 0xc000962b00)
2023-10-12 01:09:48 DEBUG : HTTP/1.1 403 Forbidden
Transfer-Encoding: chunked
Cf-Ray: 8148b677ca8a7bbc-LAX
Connection: keep-alive
Content-Type: application/xml
Date: Wed, 11 Oct 2023 17:09:46 GMT
Server: cloudflare
Vary: Accept-Encoding
2023-10-12 01:09:48 DEBUG : <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2023-10-12 01:09:48 ERROR : Background.png: Failed to copy: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
2023-10-12 01:09:48 ERROR : Attempt 1/1 failed with 1 errors and: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
Transferred:              0 B / 0 B, -, 0 B/s, ETA -
Errors:                 1 (retrying may help)
Elapsed time:         2.6s
2023/10/12 01:09:48 INFO  :
Transferred:              0 B / 0 B, -, 0 B/s, ETA -
Errors:                 1 (retrying may help)
Elapsed time:         2.6s

2023/10/12 01:09:48 DEBUG : 5 go routines active
2023/10/12 01:09:48 Failed to sync: failed to prepare upload: AccessDenied: Access Denied
        status code: 403, request id: , host id:
```
注意其中某个请求有这样的东西：
```plain
<CreateBucketConfiguration xmlns="http://s3.amazonaws.com/doc/2006-03-01/"><LocationConstraint>apac</LocationConstraint></CreateBucketConfiguration>
```
我看到就明白了，如题，Token 的权限不足了。  
于是找到了解决办法：添加 `--s3-no-check-bucket` 参数。
下面是正常上传时候的输出：
```
C:\Users\cornw\Pictures>rclone sync -P Background.png CornWorldR2:static --s3-no-check-bucket
Transferred:          476 KiB / 12.512 MiB, 4%, 95.090 KiB/s, ETA 2m9s
Transferred:            0 / 1, 0%
Elapsed time:         6.5s
Transferring:
 *                                Background.png:  3% /12.512Mi, 95.099Ki/s, 2m9s
```

显然这是一处设计失误——Bucket 不存在的可能性极小。  
也就是说，完全可以默认 Bucket 存在，反而添加一个用于检查 Bucket 是否存在的参数 `--s3-check-bucket(?)` / 用于始终发送创建 Bucket 的参数 `--s3-always-create-bucket(?)`，而不是 `--s3-no-check-bucket` 参数。  

心累，好在可以解决了。  

目前已经对`picgo-plugin-rclone`项目提起相关 issue（[rclone 在 s3 源的判断上有缺陷，望适配 · Issue #8 · yabostone/picgo-plugin-rclone (github.com)](https://github.com/yabostone/picgo-plugin-rclone/issues/8)） 以期解决此问题。  
在上述 issue 中也有提及暂时的解决方案，修改`picgo-plugin-rclone` npm 包中 `/dist/index.js` 关于生成 `rclone sync` 指令的代码，加入 `--s3-no-check-bucket` 参数。

> 参考自：[AccessDenied on copy to S3 bucket (due to calling CreateBucketConfiguration on existing bucket) · Issue #5119 · rclone/rclone (github.com)](https://github.com/rclone/rclone/issues/5119)


### PicgoCore 的配置项是 Picgo 图形客户端的配置项的子集
自己删减有点累，于是写了个小网页，用于提取 Picgo 图形客户端的配置项中适用于 PicgoCore 的部分。
[Picgo 客户端配置文件转 Picgo-Core 配置文件 (corn.li)](https://corn.li/c/picgo-config-to-picgo-core-config)
### Vanblog 开启图像压缩后提供给 PicgoCore 的文件名自带 md5 前缀
本来我是想这么命名文件的：`{sha1}.{fileName}.{extName}`，但发现实际存进去的文件是这样的：`{sha1}.{md5}.{fileName}.{extName}`。  
多次尝试后发现是 Vanblog 的机制。  
那就接受吧~

折腾图床的经历和最终方案（Cloudflare R2 + Rclone + Picgo）

Windows 下的 Outlook 在默认情况下关闭窗口时就关闭应用了，不会默认在后台常驻，很麻烦。
搜索了一下，有两个修改方案可用：ReliefJet 和 KeepOutlookRunning。





## ReliefJet
这软件操作很傻瓜式，只需要安装、修改设置即可，但太太太贵了（十几欧元一年，和抢钱没区别了），遂抛弃。

## KeepOutlookRunning
开源软件万岁！
这软件年代久远，但仍然可用，只是网上教程与实际情况有些许初入，可参照下方方法操作。
不知道为什么，在我的 64 位系统和 64 位软件上只能使用 `KeepOutlookRunning.dll`。

1. 下载相应的 dll 文件（`KeepOutlookRunning-64bit.dll` 或 `KeepOutlookRunning.dll`），[Github 镜像](https://github.com/Ourselp/KeepOutlookRunning) | [SourceForge 官网](https://sourceforge.net/projects/keepoutlook/)
2. 根据 dll 文件，在资源管理器中打开 `%SystemRoot%/System32` 或 `%SystemRoot%/SysWOW64` 目录，放入文件。
3. 用管理员模式打开终端，进入上述目录，执行 `regsvr32 KeepOutlookRunning.dll` 或 `regsvr32 KeepOutlookRunning-64bit.dll`
4. 打开 Outlook，按照下方操作提示操作
    >(左上角)文件->(左下角)选项->(左下角)加载项->(下方 在 COM 加载项右边)转到->(在列表中)找到 `Keep Outlook Running Com Addin`->(在列表中)选中->(右侧菜单)确定
5. 再次按照上述步骤打开加载项菜单，选中此拓展，查看下方显示是否有异常，如果是"启动时加载"则正常
6. 现在就可以放心地点击窗口右上角的 x 按钮了！