Educational Codeforces Round 126
FallenGemini

A. Array Balancing

题意

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

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

思路

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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

题意

任给一个数

有两种操作:

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

思路

表示 需要经过多少步到达

考虑建立一个有向图,建边:

  • 指向
  • 指向

显然,可以通过 计算出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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() {
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 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。。。

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

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

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

时,我们没法操作了,

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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

题意

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

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

求最少次数

思路

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

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

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

简单模拟一下就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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