A. Array Balancing

题意

给两个数组，可以进行若干次交换和

令 $\sum{i=2}^n (|a_i - a{i-1}|+|bi-b{i-1}|)$ 最小

思路

不难发现，每对值只与前面的数字有关系

那么只需要考虑当前是否交换

#include<bits/stdc++.h>
void solve() {
	int n;
	std::cin >> n;
	std::vector<int> a(n),b(n);
	for(int i = 0; i < n; i++) std::cin >> a[i];
	for(int i = 0; i < n; i++) std::cin >> b[i];
	long long ans = 0;
	for(int i = 1; i < n; i++) {
		long long x,y;
		x = std::abs(a[i] - a[i - 1]) + std::abs(b[i] - b[i - 1]);
		y = std::abs(a[i] - b[i - 1]) + std::abs(b[i] - a[i - 1]);
		ans += std::min(x,y);
	}
	std::cout << ans << '\n';
}
int main() {
}

B. Getting Zero

题意

任给一个数

有两种操作:

求最少进行多少次操作使得

思路

令表示需要经过多少步到达，

考虑建立一个有向图，建边：

指向
指向

显然，可以通过计算出

#include<bits/stdc++.h>
void solve() {
	std::vector<std::vector<int>> v(32768);
	for(int i = 0; i < 32768; i++) {
		int x = (i + 1) % 32768;
		v[x].push_back(i);
		x = (i * 2) % 32768;
		v[x].push_back(i);
	}
	std::vector<int> f(32768);
	std::vector<bool> vis(32768);
	f[0] = 0;
	std::queue<int> q;
	q.push(0);
	vis[0] = true;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i : v[u]) {
			if(vis[i]) continue;
			f[i] = f[u] + 1;
			vis[i] = true;
			q.push(i);
		}
	}
	int n;
	std::cin >> n;
	for(int i = 0; i < n; i++) {
		int x;
		std::cin >> x;
		std::cout << f[x] << ' ';
	}
}
int main() {
}

也可以考虑不将边记录下来，而是实时计算，这样写的话代码会简洁多了

// code form jiangly
    while (!q.empty()) {
        int x = q.front();
        q.pop();

        for (auto y : { (x + 32767) % 32768,
                       x & 1 ? 0 : (x >> 1 | 16384),
                       x & 1 ? 0 : (x >> 1) }) {
            if (f[y] == -1) {
                f[y] = f[x] + 1;
                q.push(y);
            }
        }
    }

C. Water the Trees

题意

给一个数组，通过轮流进行操作和操作（开始是操作），让所有数相同

操作：选择一个数字，给它；或者跳过
操作：选择一个数字，给它；或者跳过

求最少操作多少次

思路

比赛的时候犯蠢了，认为对最大值进行操作无意义。。。

比赛结束后去问了万能的群友，三分钟改完代码AC。。。

考虑到最终所有数字相同，不妨设最终的值或

定义为操作的次数，定义为操作的次数

遍历一遍数组，对于每个数字，为了让它变成，用贪心的思想去理解，容易发现能进行操作就进行操作

当时，我们没法操作了，

当时，，不一定为最优解。考虑将变小，变大

对于减少，则增加。不难发现时，最优

这时回过来思考一下，为什么对最大值进行操作存在意义？

这么做是不是相当于令，。此时我们可以将的情况转换成的情况，哪怕添加的总值会变大，但我们可以通过采取更优的来减少操作次数。可以结合例子去理解为什么要考虑增加最大值

#include<bits/stdc++.h>
#define LL long long
LL cal(LL Max,std::vector<int> &a) {
	LL c1 = 0, c2 = 0, ans = 0;

	for(int x : a) {
		c1 += (Max - x) % 2;
		c2 += (Max - x) / 2;
	}
	if(c1 > c2) ans = 2 * c1 - 1; 
	else {
		LL sum = c1 + 2 * c2;
		c2 = sum / 3;
		c1 = sum - c2 * 2;
		ans = c1 + c2;
	}
	return ans;
}
void solve() {
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; i++) std::cin >> a[i];
	int Max = *std::max_element(a.begin(),a.end());
	std::cout << std::min(cal(Max, a),cal(Max + 1, a)) << '\n';
}
int main(){
}

D. Progressions Covering

题意

给定数组，对于一个初值为的数组，进行操作使任意成立：

选择起点，对于 $，，$ 分别 $，$ 。如果，对于越界下标不考虑

求最少次数

思路

不难发现，第个点的最优情况就是每次，此时对也会产生贡献，能确定的是，这么操作一定不会更劣。（可以自己去想想，也是贪心的思路

那么我们考虑从后往前依次处理

定义是目前对已经有的贡献，是目前有多少次操作覆盖了，是对当前点还需要做多少次操作，表示有多少个操作在出结束

简单模拟一下就行

#include<bits/stdc++.h>
#define LL long long
void solve() {
	int n,k;
	std::cin >> n >> k;
	std::vector<LL> a(n),b(n);
	for(int i = 0; i < n; i++)
		std::cin >> a[i];

	LL ans = 0,sum = 0, cnt = 0, Num = 0, delta;
	for(int i = n - 1; i >= 0; i--) {
		sum -= Num;
		cnt = 0,
		delta = std::min(k,i + 1);
		if(a[i] > sum) {
			cnt = (a[i] - sum + delta - 1) / delta;
			if(i > k) b[i - k] += cnt;
			sum += 1ll * delta * cnt;
		}
		Num = Num - b[i] + cnt;
		ans += cnt;
	}
	
	std::cout << ans << '\n';
}
int main() {
}

E. Narrow Components

挖坑

F. Teleporters

挖坑

总结 & 吐槽

Rating 变化：

表现分：

Rank:

A 题手速题，没什么好说的

B 题开始想的方向有点不对，打算的是用记忆化搜索，结果程序死循环了，然后研究了十几分钟发现记忆化搜索会自循环，然后又想了会应该怎么建边，最后花了二十几分钟才写完

C 题，心态裂开的地方。除了考虑其他的地方都挺顺利了（虽然考虑优化和那里想成了倍增。。。而不是数学计算）WA了三四次就去做 D 题了。之后回来做 C 题还是没想明白。

D 题，感觉比较水了，或者说，确实比较水，只是我太蒻了（看着 jly 十分钟切掉 D 的记录陷入沉思）

然后就是关于写总结与代码重构部分

能够明显感觉到比赛时的思路有一些乱，然后代码又臭又长又难改。重构之后发现前四题的核心代码没有超过三十行的。。。或者说，我总是容易把问题复杂化，没能看出这些问题的本质。。。

还得加练QAQ