Codeforces Round 906 (Div.2)

题目链接

Problem A: Doremy’s Paint 3

时间限制：1秒
内存限制：256 MB

题目描述

　　本题定义一种数组是“好数组”，只要该数组满足某条件：对于数组中的任意两个相邻的元素之和都会得到同一个结果。更数学化一点的描述就是：$$\forall i \forall j (i,j \in [1, n-1] \cap \mathbb{Z}) \rightarrow a_i + a_{i+1} = a_j + a_{j+1}$$ 其中 $\mathbb{Z}$ 是整数域。
　　现在给定一个长度为 $n$ 的数组 $A_n$ ，你可以将它任意排序，问是否能够将它变为“好数组”，如果能，输出“YES”，否则输出“NO”。

输入描述
　　第一行，一个正整数 $t$ ，表示接下来有 $t (1\le t\le 100)$ 组数据。
　　对于每组数据，第一行，一个正整数 $n (2 \le n \le 1000)$ ，表示数组的长度。
　　第二行， $n$ 个整数，表示数组 $a_1,a_2,…,a_n(1\le a_i \le 10^5)$。
输出描述
　　对于每组数据，输出一行“YES”或“NO”。

解题思路

　　很容易得出，“好数组”的各元素要么都是同一个值，要么是两个不同的值交替出现。可以考虑统计一下有多少个数出现，出现的次数是多少，简单判断一下就可以了。

解题代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> count(100001, 0);
    set<int> nums;
    for (int i = 0; i < n; ++i)
    {
        int val;
        cin >> val;
        count[val]++;
        nums.insert(val);
    }
    if (nums.size() == 1 ||
        (nums.size() == 2 && abs(count[*nums.begin()] - count[*(--nums.end())]) <= 1))
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Problem B: Qingshan Loves Strings

时间限制：1秒
内存限制：256 MB

题目描述

　　本题中定义一个字符串是“好字符串”，如果该字符串满足：不存在两个相同且位置上相邻的字符。现给定两个仅由’0’和’1’组成的字符串 $S,T$ ，由于它不一定是一个“好字符串”，因此你可以将字符串 $T$ 插入到 $S$ 的任意位置从而得到新的 $S$ ，而这样的操作你可以执行任意次(也可以不执行)。问：是否有可能让 $S$ 成为“好字符串”？如果可能，输出“YES”，否则输出“NO”。

输入描述
　　第一行，一个正整数 $t$ ，表示接下来有 $t(1\le t \le 2000)$ 组数据。
　　对于每组数据，第一行，两个正整数 $n,m(1\le n,m \le 50)$ ，分别表示字符串 $S,T$ 的长度。
　　第二行，一个长度为 $n$ 的字符串 $S$ ，数据保证该字符串仅由’0’,’1’组成。
　　第三行，一个长度为 $m$ 的字符串 $T$ ，数据保证该字符串仅由’0’,’1’组成。
输出描述
　　对于每组数据，输出一行“YES”或一行“NO”。

解题思路

　　如果 $s$ 最初就已经是“好字符串”了，那么就可以直接输出“YES”。如若不然，判断一下 $T$ 是否是“好字符串”，如果不是，那么无论操作多少次，都会存在一个完整的 $T$ 在 $S$ 内部，那么无论如何也构造不出“好字符串”。如果是，那么就需要考虑它的两头(当然，也有可能它就只有一个字符)，如果最左边是’0’，最右边也是’0’ (下文简写为 (L, R) )，那么可以解决 $S$ 中的 “11” 部分，(‘0’,’1’) 按理可以插入到 “10” 当中，但是 “10” 并不需要被解决，它不会违反“好字符串”的规定。总之，固定不变的两个头决定了 $T$ 只能解决四种情况中的一种。简单判断一下 $S$ 中是否存在超出了 $T$ 所能解决的范围的连续字符就行了。

解题代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    bool ans = true;
    set<string> types;
    for (int i = 0; i + 1 < s.size(); ++i)
    {
        if (s[i] == s[i + 1])
        {
            ans = false;
            string tmp = "";
            tmp += s[i];
            tmp += s[i + 1];
            types.insert(tmp);
        }
    }
    if (ans)
    {
        cout << "YES\n";
        return;
    }
    for (int i = 0; i + 1 < t.size(); ++i)
    {
        if (t[i] == t[i + 1])
        {
            cout << "NO\n";
            return;
        }
    }

    string type = "";
    type += t[0];
    type += t[t.size() - 1];
    if (types.size() > 1 || type[0] != type[1] || types.find(type) != types.end())
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n";
    }
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Problem C: Qingshan Loves Strings 2

时间限制：1秒
空间限制：256 MB

题目描述

　　本题中定义一个字符串是“好字符串”，如果该字符串 $S$ 满足(假设其长度是 $n$ )：
$$
\forall i (i \in [1, n]\cap \mathbb{Z}) \rightarrow S_{i} = S_{n-i+1}
$$ 其中 $\mathbb{Z}$ 是整数域。
　　现给定一个仅由’0’和’1’组成的字符串 $S$ ，你可以执行某种操作0~300次：将“01”插入到字符串 $S$ 的任意位置，得到新的 $S$ 。问：是否有可能在经过若干次(或0次)操作之后让 $S$ 成为“好字符串”？如果不可能，那么输出“-1”，否则输出你给出的插入位置。

输入描述
　　第一行，一个正整数 $t(1\le t\le 100)$ ，表示接下来有 $t$ 组数据。
　　对于每组数据，第一行，一个正整数 $n(1\le n\le 100)$ ，表示字符串的长度。
　　第二行，一个长度为 $n$ 的字符串 $S$ ，仅由’0’和’1’组成。
输出描述
　　对于每组数据，如果不存在能够构造出“好字符串”的可能性，那么只输出“-1”。
　　否则在该组数据的第一行输出一个正整数 $P$ ，表示你要进行插入操作的次数(应满足 $0\le P\le 300$)。
　　然后在第二行输出 $P$ 个非负整数，表示依次插入的位置。如果 $P=0$ ，那么该行为空行。
　　注意，当进行第 $i$ 次插入时，插入的位置是相对于前 $i-1$ 次插入完成之后的字符串而言的。如果插入位置 $P_i = 0$ ，那么表示插入到开头，否则表示插入到当前的 $S$ 的第 $P_i$ 个字符之后。

解题思路

　　这道题的解法我想得不知道偏到哪个地方去了，这里就放一下官方的题解吧。
　　First, there is no solution when the number of 0’s and 1’s are different.
　　Otherwise, the construction follows:
if $s_1 \neq s_n$ now, we can ignore $s_1$ and $s_n$ , and consider $s_{2…n-1}$ as a new $s$ . If $s$ is empty, the algorithm ends.
　　Now $s_1 = s_n$ . If they are $1$ , insert $01$ to the front; otherwise , insert $01$ to the end. Look at this example:
　1. “$110010$”
　2. “$1001$”
　3. “$\underline{01}1001$”
　4. “$1100$”
　5. “$10$”
　6. “”
　　This operation is actually equivalent to moving the last $1$ to the front or moving the first $0$ to the end. For example, in step 2 to 4 above, we succeed moving the last $1$ to the front. So in the worst case, every character in the string are moved, and we need $n$ moves.
　　Actually, we don’t need $n$ moves but $n/2$ moves. Because for the $0$ and $1$ deleted in the same operation, at most one of them need to be moved.

解题代码(官方)

// By Imakf

#include <bits/stdc++.h>

bool ok(std::string s) {
  for (size_t i = 1; i < s.length(); ++i)
    if (s[i] == s[i - 1])
      return false;
  return true;
}


std::string s;
void solve() {
  int n; std::cin >> n;
  std::cin >> s;
  int cnt0 = 0, cnt1 = 0;
  for (int i = 0; i < s.length(); ++i) {
    cnt0 += s[i] == '0';
    cnt1 += s[i] == '1';
  }
  if (cnt0 != cnt1) {
    std::cout << -1 << std::endl;
    return;
  }
  std::vector<int> z;
  std::deque<char> q;
  for (int i = 0; i < s.length(); ++i)
    q.push_back(s[i]);
  
  int d = 0;
  while (!q.empty()) {
    if (q.front() == q.back()) {
      if (q.front() == '0') {
        q.push_back('0');
        q.push_back('1');
        z.push_back(n - d);
      } else {
        q.push_front('1');
        q.push_front('0');
        z.push_back(0 + d);
      }
      n += 2;
    }
    while (!q.empty() && q.front() != q.back()) {
      q.pop_back();
      q.pop_front();
      ++d;
    }
  }

  std::cout << z.size() << std::endl;
  for (int i = 0; i < z.size(); ++i) {
    std::cout << z[i];
    if (i + 1 == z.size()) std::cout << std::endl;
    else std::cout << " ";
  }
}

int main() {
  int t;
  std::cin >> t;
  while (t--) solve();
  return 0;
}

Codeforces

#编程

Codeforces Round 906 (Div.2)

https://mxx23.github.io/2023/11/03/Codeforces-Round-906-Div-2/

作者

mxx

发布于

2023年11月3日

许可协议

Codeforces Round 924 (Div.2) 上一篇

矩阵快速幂算法下一篇