Codeforces Round #554 (Div. 2)

A. Neko Finds Grapes

Description:

On a random day, Neko found $n$ treasure chests and $m$ keys. The $i$-th chest has an integer $a_i$ written on it and the $j$-th key has an integer $b_j$ on it. Neko knows those chests contain the powerful mysterious green Grapes, thus Neko wants to open as many treasure chests as possible.
The $j$-th key can be used to unlock the $i$-th chest if and only if the sum of the key number and the chest number is an odd number. Formally, $a_i + b_j \equiv 1 \pmod{2}$. One key can be used to open at most one chest, and one chest can be opened at most once.
Find the maximum number of chests Neko can open.

Input:

The first line contains integers $n$ and $m$ ($1 \leq n, m \leq 10^5$) — the number of chests and the number of keys.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the numbers written on the treasure chests.
The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \leq b_i \leq 10^9$) — the numbers written on the keys.

Output

Print the maximum number of chests you can open.

Sample Input:

5 4
9 14 6 2 11
8 4 7 20

Sample Output:

3

Sample Input:

5 1
2 4 6 8 10
5

Sample Output:

1

Sample Input:

1 4
10
20 30 40 50

Sample Output:

0

题目链接

求序列 $a$ 和序列 $b$ 元素之和为奇数的数量

$$ \because \texttt{only}\ odd+even=odd\\\\ \therefore ans=\min(odd\_num_{a},even\_num_{b})+\min(even\_num_{a},odd\_num_{b}) $$

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n, m; std::cin >> n >> m;
  std::vector<int> cnt(4);
  for (int i = 0, x; i < n; ++i) {
    std::cin >> x;
    if (x & 1) ++cnt[0];
    else ++cnt[1];
  }
  for (int i = 0, x; i < m; ++i) {
    std::cin >> x;
    if (x & 1) ++cnt[2];
    else ++cnt[3];
  }
  std::cout << std::min(cnt[0], cnt[3]) + std::min(cnt[1], cnt[2]) << '\n';
  return 0;
}

B. Neko Performs Cat Furrier Transform

Description:

Cat Furrier Transform is a popular algorithm among cat programmers to create longcats. As one of the greatest cat programmers ever exist, Neko wants to utilize this algorithm to create the perfect longcat.
Assume that we have a cat with a number $x$. A perfect longcat is a cat with a number equal $2^m - 1$ for some non-negative integer $m$. For example, the numbers $0$, $1$, $3$, $7$, $15$ and so on are suitable for the perfect longcats.
In the Cat Furrier Transform, the following operations can be performed on $x$:
(Operation A): you select any non-negative integer $n$ and replace $x$ with $x \oplus (2^n - 1)$, with $\oplus$ being a bitwise XOR operator. (Operation B): replace $x$ with $x + 1$. The first applied operation must be of type A, the second of type B, the third of type A again, and so on. Formally, if we number operations from one in the order they are executed, then odd-numbered operations must be of type A and the even-numbered operations must be of type B.
Neko wants to produce perfect longcats at industrial scale, thus for each cat Neko only wants to perform at most $40$ operations. Can you help Neko writing a transformation plan?
Note that it is not required to minimize the number of operations. You just need to use no more than $40$ operations.

Input:

The only line contains a single integer $x$ ($1 \le x \le 10^6$).

Output

The first line should contain a single integer $t$ ($0 \le t \le 40$) — the number of operations to apply.
Then for each odd-numbered operation print the corresponding number $n_i$ in it. That is, print $\lceil \frac{t}{2} \rceil$ integers $n_i$ ($0 \le n_i \le 30$), denoting the replacement $x$ with $x \oplus (2^{n_i} - 1)$ in the corresponding step.
If there are multiple possible answers, you can print any of them. It is possible to show, that there is at least one answer in the constraints of this problem.

Sample Input:

39

Sample Output:

4
5 3

Sample Input:

1

Sample Output:

0

Sample Input:

7

Sample Output:

0

题目链接

一个数字 $x$ 轮流进行两种操作

  1. $x=x\oplus(2^{n}-1)$
  2. $x=x+1$

最终使 $x=2^{n}-1$ ,输出所有操作 $1$ 的 $n$

$2^{n}-1$ 的意思就是在二进制下所有位均为 $1$ ,那么每次操作 $1$ 都将 $x$ 最高位的 $0$ 通过异或运算变为 $1$ 即可

AC代码:

#include <bits/stdc++.h>

int odd_cnt;
int ans[25];

void Odd(int &x) {
  int len = log2(x) + 1;
  for (int i = len - 1; i >= 0; --i) {
    if (x & (1 << i)) continue;
    else {
      int tmp = ((1 << (i + 1)) - 1);
      x = x ^ tmp;
      ans[odd_cnt] = i + 1;
      return;
    }
  }
}

std::set<int> set;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  for (int i = 0; i <= 30; ++i) set.insert((1 << i) - 1);

  int x; std::cin >> x;

  int cnt = 0; odd_cnt = 0;
  while (set.find(x) == set.end()) {
    ++cnt; ++odd_cnt;
    Odd(x);
    if (set.find(x) != set.end()) break;
    ++cnt;
    x += 1;
    if (set.find(x) != set.end()) break;
  }

  std::cout << cnt << '\n';
  for (int i = 1; i <= odd_cnt; ++i) std::cout << ans[i] << ' ';
  std::cout << '\n';
  return 0;
}

C. Neko does Maths

Description:

Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.
Neko has two integers $a$ and $b$. His goal is to find a non-negative integer $k$ such that the least common multiple of $a+k$ and $b+k$ is the smallest possible. If there are multiple optimal integers $k$, he needs to choose the smallest one.
Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?

Input:

The only line contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$).

Output

Print the smallest non-negative integer $k$ ($k \ge 0$) such that the lowest common multiple of $a+k$ and $b+k$ is the smallest possible.
If there are many possible integers $k$ giving the same value of the least common multiple, print the smallest one.

Sample Input:

6 10

Sample Output:

2

Sample Input:

21 31

Sample Output:

9

Sample Input:

5 10

Sample Output:

0

题目链接

两个数字 $a\ b$ ,求一个最小 $k$ 使得 $lcm(a+k,b+k)$ 最小

$lcm(a,b)=\frac{a\times b}{gcd(a,b)}$ ,那么使 $gcd(a,b)$ 尽可能的小即可,又因为 $b-a$ 是一个定值且 $b-a=n\times gcd(a,b)$

所以只要枚举 $b-a$ 的因子及其倍数作为 $k​$ 找到最小值即可

AC代码:

#include <bits/stdc++.h>
typedef long long ll;

std::vector<ll> vec;

void Div(ll x) {
  for (ll i = 1; i * i <= x; ++i) {
    if (i * i == x) vec.push_back(i);
    else if (x % i == 0) {
      vec.push_back(i);
      vec.push_back(x / i);
    }
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  ll a, b; std::cin >> a >> b;
  if (a > b) std::swap(a, b);

  ll diff = b - a;
  if (diff == 0) {
    std::cout << 0 << '\n';
    return 0;
  }

  Div(diff);
  std::sort(vec.begin(), vec.end());

  ll k = 0;
  if (a <= vec.back()) {
    int pos = std::lower_bound(vec.begin(), vec.end(), a) - vec.begin();
    k = vec[pos] - a;
    std::cout << k << '\n';
    return 0;
  }

  ll cnt = 2;
  while (true) {
    ll tmp = diff * cnt++;
    if (tmp < a) continue;
    k = tmp - a;
    break;
  }

  std::cout << k << '\n';
  return 0;
}

D. Neko and Aki's Prank

Description:

Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...
It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length $2n$.
The definition of correct bracket sequence is as follows:

  • The empty sequence is a correct bracket sequence,
  • If $s$ is a correct bracket sequence, then $(\,s\,)$ is a correct bracket sequence,
  • If $s$ and $t$ are a correct bracket sequence, then $st$ is also a correct bracket sequence.

For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.
Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo $10^9 + 7$.

Input:

The only line contains a single integer $n$ ($1 \le n \le 1000$).

Output

Print exactly one integer — the size of the maximum matching in the trie. Since the answer can be quite large, print it modulo $10^9 + 7$.

Sample Input:

1

Sample Output:

1

Sample Input:

2

Sample Output:

3

Sample Input:

3

Sample Output:

9

题目链接

将长度为 $2n$ 共 $n$ 对的合法括号序列建立 $Trie$ ,统计最多可以取多少条不相交树边

这道题目甚至可以用记忆化搜索直接爆过去

$dp[l][m][0/1]$ 表示当前括号序列长度为 $l$ ,左括号比右括号多 $m$ 个,是否取当前点与其父节点树边( $0/1$ )

在搜索的时候分两种情况

  1. 取当前点与其父节点树边,那么当前点与其子节点的树边则均不可取
  2. 不取当前点与其父节点树边,那么当前点与其两子节点(一定是两个子节点,因为只有左右两种括号)一个可取一个不可取,都搜出来取最大值再 $+1$ (取当前点与子节点树边)即可

AC代码:

#include <bits/stdc++.h>
const int maxn = 2e3 + 5;
const int mod = 1e9 + 7;

int n;
int dp[maxn][maxn][2];

int Dfs(int l, int m, int f) {
  if (l == 2 * n && m == 0) return 0;
  if (m < 0 || l + m > 2 * n) return -f;
  if (dp[l][m][f] != -1) return dp[l][m][f];
  int ret = 0;
  if (f == 0) ret = std::max((Dfs(l + 1, m - 1, 1) + Dfs(l + 1, m + 1, 0) + 1) % mod, (Dfs(l + 1, m - 1, 0) + Dfs(l + 1, m + 1, 1) + 1) % mod);
  else ret = (Dfs(l + 1, m - 1, 0) + Dfs(l + 1, m + 1, 0)) % mod;
  dp[l][m][f] = ret;
  return ret;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  memset(dp, -1, sizeof(dp));

  std::cin >> n;

  std::cout << Dfs(0, 0, 0) << '\n';
  return 0;
}
Last modification:April 26th, 2019 at 01:42 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment