Educational Codeforces Round 158 (Rated for Div. 2)

Posted at 2023-11-25 # Competitive Programming # Codeforces

A. Line Trip

车从一条路的 0 点出发到达 $x$ ，然后再返回 $0$ 点。车每单位距离消耗 $1$ 升油，路上加油站的在 $a_i$ 。每次在加油站都会把油箱加满油。输出最小的油箱大小

找出两个相邻的加油站的最大距离，特别处理边缘即可

void solve() {
  int n, x;
  read(n, x);
  V<int> s(n+1);
  reads(all1(s));
  int max = 0;
  rep1(i, n){
    max = mmax(max, s[i] - s[i-1]);
  }
  max = mmax(max, (x - s[n]) * 2);
  std::cout << max;
}

B. Chip and Ribbon

有从 1 到 $n$ 共 $n$ 个单元格。每个单元格默认值为 $0$ 。

现在 Monocarp 将 chip 放到第一个单元格中，在每回合的结束时 chip 所在的单元格上的数字都会 $+1$ 。除了第一回合，每回合可以对 chip 进行以下一种操作：

将 chip 移动到下一个单元格

将 chip 转送到任意单元格

给出 $c_i$ ，要使 $a_i = c_i$ ，，输出最小传送次数

每次上升都需要往回传送一次，以把数字大的数字加上去

只需要逐项作差，统计上升数字的总合即可

void solve() {
  int n;
  read(n);
  V<int> s(n+1);
  reads(all1(s));
  V<int> p(n+1);
  int ans = 0;
  rep1(i, n){
    p[i] = s[i] - s[i-1];
    ans += p[i] > 0? p[i] : 0;
  }
  std::cout << ans - 1;
}

C. Add, Divide and Floor

输入一个整数数组 $a_i$ 。每次操作任选一个整数 $x(0 \le x \le 10^{18})$ ，并将 $a_i$ 中每个元素替换成 $\lfloor \frac{a_i + x}{2} \rfloor$

输出最小操作次数，使得数组中所有的元素相等

通过把玩样例可知：

如果一奇一偶两个数 $2n$ 和 $2n+1$ 两个数，操作的结果是 $\frac{4n + 1}{2}= 2n$ ; 或者是 $2n-1$ 和 $2n$ ，结果是 $\frac{4n - 1}{2} = 2n-1$ 。即如果选择的数 $x$ 比其他数小，总能使其他数减一
如果要使数 $a$ 变为 $b$ （ $b < a$ ），每次操作的能使当前的数字和 $b$ 的差缩小一半

那么只需要统计出数组中的最小值和最大值，操作次数即为 $log_2(max-min) + 1$

void solve() {
  int n;
  read(n);
  V<int> s(n+1);
  reads(all1(s));
  if(n == 1){
    std::cout << 0;
    return;
  }
  auto min = *std::min_element(all1(s));
  auto max = *std::max_element(all1(s));
  if(min == max){
    std::cout << 0;
    return;
  }
  int x = std::log2(max - min) + 1;
  std::cout << x;
  if(x <= n){
    std::cout << "\n";
    rep(i, x){
      std::cout << min << " ";
    }
  }
}

D. Yet Another Monster Fight

有 $i$ 个怪兽，每个怪兽的血量为 $a_i$ 。Vasya 会对第 $i$ 个怪兽，并施加攻击力为 $x$ 的魔法。魔法将每次攻击一个，总计攻击 $n$ 次怪兽。对于每次攻击，链法将会随机选择一个没有被攻击过且旁边被攻击过的怪兽进行攻击。第一次魔法攻击将造成 $x$ 伤害，第二次 $x-1$ ，依次类推

现在使用一次魔法，使的无论攻击顺序如何都能击杀所有的怪物，且魔法攻击最低，输出 $x$ 的值

既然不考虑攻击顺序，就一定存在最坏情况。

如果第一次攻击 $i$ ，之后选择：

右边的 $j$ ，那么攻击力最大将衰减 $(i - 1) + (j - i) = j - 1$
左边的 $j$ ，攻击力最大衰减 $(n - i) + (i - j) = n - j$

很容易就能求出对于每个元素 $j$ ，如果选择的 $i$ 在它左边时和在右边时的所需攻击力。

枚举首次攻击的怪兽 $i$ ，求出其左侧、右侧所需的最大攻击力和自身的最大值，每次取最小即可

#include<bits/stdc++.h>
template<class R, class A> R mmax(R x, A y){ return std::max(x, (R) y); } template<class R, class A, class... AS> R mmax(R x, A xx, AS... xxs){ return std::max(x, mmax((R)xx, xxs...));  }
template<class R, class A> R mmin(R x, A y){ return std::min(x, (R) y); } template<class R, class A, class... AS> R mmin(R x, A xx, AS... xxs){ return std::min(x, mmin((R)xx, xxs...));  }
int main(){
  #define int long long
  int n;
  std::cin >> n;
  std::vector<int> s(n+2);

  for(int i = 1; i <= n; i++){
    std::cin >> s[i];
  }

  std::vector<int> pre(s.size()), suf(s.size());
  for(int i = 1; i <= n; i++){
    pre[i] = n - i + s[i];
    suf[i] = i - 1 + s[i];
  }
  for(int i = 1; i <= n; i++) pre[i] = std::max(pre[i], pre[i-1]);
  for(int i = n; i >= 1; i--) suf[i] = std::max(suf[i], suf[i+1]);
  int atk = 0x3f3f3f3f;

  for(int i = 1; i <= n; i++){
    atk = mmin(
      atk,
      mmax(
        pre[i-1],
        suf[i+1],
        s[i]
      )
    );
  }
  std::cout << atk;
}

Mslxl

Integrate Life

Educational Codeforces Round 158 (Rated for Div. 2)

A. Line Trip

B. Chip and Ribbon

C. Add, Divide and Floor

D. Yet Another Monster Fight