Codeforces Round 991 (Div. 3)

打过的最难的div3

A.Line Breaks

Line Breaks

题目描述

Kostya has a text s consisting of n words made up of Latin alphabet letters. He also has two strips on which he must write the text. The first strip can hold m characters, while the second can hold as many as needed.

Kostya must choose a number x and write the first x words from s on the first strip, while all the remaining words are written on the second strip. To save space, the words are written without gaps, but each word must be entirely on one strip.

Since space on the second strip is very valuable, Kostya asks you to choose the maximum possible number x such that all words s1,s2,…,sx fit on the first strip of length m.

一段文本有 $n$ 个单词，现将这段文本写在纸上，单词间无间隔，在第一页纸能写 $m$ 个字符，但是一个单词必须出现在同一页纸上。
问：第一页纸能写多少个单词

解题思路

模拟

参考代码

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

void solve() {
  int n, m, f = 1;
  std::cin >> n >> m;
  std::vector<std::string> s(n);
  for(int i = 0; i < n; i++) {
    std::cin >> s[i];
  }

  int su = 0, ct = 0;
  for(int i = 0; i < n; i++) {
    if (su + s[i].size() <= m) {
      ct++;
      su += (int) s[i].size();
    } else {
      break;
    }
  }
  std::cout << ct << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

B.Transfusion

Transfusion

题目描述

You are given an array a of length n. In one operation, you can pick an index i from 2 to n−1 inclusive, and do one of the following actions:

  • Decrease $a_{i-1}$ by 1, then increase $a_{i+1}$ by 1.

  • Decrease $a_{i+1}$ by 1, then increase $a_{i-1}$ by 1.

After each operation, all the values must be non-negative. Can you make all the elements equal after any number of operations?

给定长度为 $n$ 的数组可以执行以下操作：

  • $a_{i-1}=a_{i-1}-1,a_{i+1}=a_{i+1}+1$;
  • $a_{i-1}=a_{i-1}+1,a_{i+1}=a_{i+1}-1$;

问：是否可以通过以上操作将数组的所有元素变为相等。

解题思路

可以发现每次修改的下标奇偶性相同，我们可以分别记录下奇数下标和偶数下标的 $sum$ 和 $ct$。
那么能实现的判断条件也很简单，如下：

  • $\frac{sum_{奇}}{ct_{奇}} = \frac {sum_{偶}}{ct_{偶}}$
  • $\frac{sum_{奇}}{ct_{奇}}=0 ，\frac{sum_{偶}}{ct_{偶}} =0$

参考代码

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int, int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  int ct[2]{}, sum[2]{}; 
  int s = 0;
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    sum[i % 2] += a[i];
    ct[i % 2] ++;
  }

  if(sum[0] % ct[0] || sum[1] % ct[1] || sum[0] / ct[0] != sum[1] / ct[1]) {
    std::cout << "NO" << endl;
  }else {
    std::cout << "YES" << endl;
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

C.Uninteresting Number

Uninteresting Number

题目描述

You are given a number n with a length of no more than 105.

You can perform the following operation any number of times: choose one of its digits, square it, and replace the original digit with the result. The result must be a digit (that is, if you choose the digit x, then the value of x2 must be less than 10).

Is it possible to obtain a number that is divisible by 9 through these operations?

给你一个长度不超过 $10^5$ 的数字 $n$ 。

你可以多次进行下面的运算：选择其中一个数字，将其平方，然后用运算结果替换原来的数字。结果必须是一位数字(也就是说，如果您选择数字 $x$ ，那么 $x^2$ 的值必须小于 $10$ )。

通过这些运算，有可能得到一个能被 $9$ 整除的数吗？

解题思路

数字必须是数字这一要求对变换有如下限制：我们可以将 $0$ 变换为 $0$ ，将 $1$ 变换为 $1$ ，将 $2$ 变换为 $4$ ，将 $3$ 变换为 $9$ 。任何其他数字的平方都会超过 9，因此无法变换。涉及 $0$ 和 $1$ 的变换都是无用的，因此我们有两种可能的操作：将数字 $2$ 或数字 $3$ 平方。

我们将使用 $9$ 的可除规则。它规定，当且仅当一个数字的数位之和能被 $9$ 整除时，这个数字才能被 $9$ 整除。让我们看看数字的位数之和在可能的变换中会发生怎样的变化。如果我们对 $2$ 进行平方运算，数位之和将增加 $2^2 - 2 = 2$ ；如果我们对 $3$ 进行平方运算，数位之和将增加 $3^2 - 3 = 6$ 。

我们将计算数字中 $2$ 的位数和数字中 $3$ 的位数。我们可以从可用的数位 $2$ 和 $3$ 中选择转换的个数。变换超过 8 个 2 和超过 8 个 3 的余数是没有意义的，因为它们的变换加到总和中的余数模 $9$ 会重复。

因此，最终的解法是这样的：我们计算数字的位数之和，数出 $2$ 和 $3$ 的位数。我们将遍历改变 $2$ 的位数（可能为 0，但不超过 8 位），以及改变 $3$ 的位数（可能为 0，但也不超过 8 位）。假设我们改变了 $x$ 位数 $2$ 和 $y$ 位数 $3$ ，那么这个数的位数总和就增加了 $x * 2 + y * 6$ 。如果新的和能被 $9$ 整除，那么答案就是 “是”。如果在迭代过程中从未出现过这种情况，则答案为 “否”。

参考代码

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int, int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  std::string s;
  std::cin >> s;
  int sum = 0, ct1 = 0, ct2 = 0;
  for (auto i : s) {
    sum += i - '0';
    ct1 += (i == '2' ? 1 : 0);
    ct2 += (i == '3' ? 1 : 0);
  }

  for (int i = 0; i <= std::min(9ll, ct1); i++) {
    for (int j = 0; j <= std::min(9ll, ct2); j++) {
      if ((sum + i * 2 + j * 6) % 9 == 0) {
        std::cout << "YES" << endl;
        return;
      }
    }
  }

  std::cout << "NO" << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

D.Digital string maximization

Digital string maximization

题目描述

You are given a string s, consisting of digits from 0 to 9. In one operation, you can pick any digit in this string, except for 0 or the leftmost digit, decrease it by 1, and then swap it with the digit left to the picked.

For example, in one operation from the string 1023, you can get 1103 or 1022.

Find the lexicographically maximum string you can obtain after any number of operations.

给你一个由 0 到 9 的数字组成的字符串 s。在一次操作中，您可以选取该字符串中除 0 或最左边数字之外的任意一个数字，将其减少 1，然后将其与左边的数字对调。

例如，从字符串 1023 中进行一次运算，可以得到 1103 或 1022。

找出任意多次运算后可以得到的词性最大的字符串。

解题思路

让我们看看数字 $s_i$ 。我们可以看到，我们不能将它向左移动超过 $s_i$ 次，因为它之后将是 $0$ 。因此，我们可以说，只有从 $i$ 到 $i+9$ 的指数上的数字才能位于指数 $i$ 上，因为最大的数字 $9$ 向左移动的次数不超过 $9$ 。

因此，我们可以对每个 $i$ 从 $s_i$ 到 $s_{i+9}$ 的所有数字进行暴力推理，选出 $j$ 中 $s_j - (j - i)$ 最大的数字；如果有多个最大选项，我们将最小化 $j$ 。之后，我们将 $s_j$ 向左移动，直到它位于索引 $i$ 上。

参考代码

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int, int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  std::string s;
  std::cin >> s;
  for (int i = 0; i < s.size(); i++) {
    int x = s[i] - '0', pos = i;
    for (int j = i; j < std::min(i + 10, (int)s.size()); j++) {
      if (s[j] - '0' - (j - i) > x) {
        x = s[j] - '0' - (j - i);
        pos = j;
      }
    }
    while (pos > i) {
      std::swap(s[pos], s[pos - 1]);
      pos--;
    }
    s[i] = x + '0';
  }
  std::cout << s << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}