牛客国庆集训day1

A. ABB

题意

在给定的字符串后面最少添加多少个字符可以让整个字符串变成一个回文字符串$(n \in [1, 4e5])$。

Solution

等价于求包含最后一个字符的最长回文子串，可以用前后遍历两次哈希解决。

Code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull base = 13331;
const int N = 5e5 + 5;
int n, len, res;
char s[N];
ull r, l[N], b[N];
int main() {
  scanf("%d%s", &n, s + 1);
  b[0] = 1;
  for (int i = 1; i <= n; i++) b[i] = b[i - 1] * base;
  for (int i = 1; i <= n; i++) l[i] = l[i - 1] * base + s[i];
  for (int i = n; i >= 1; i--) {
    r = r * base + s[i];
    len++;
    if (i >= len) {
      ull now1 = l[i] - l[i - len] * b[len];
      if (now1 == r) res = max(res, len * 2 - 1);
    }
    if (i >= len + 1) {
      ull now2 = l[i - 1] - l[i - 1 - len] * b[len];
      if (now2 == r) res = max(res, len * 2);
    }
  }
  printf("%d\n", n - res);
  return 0;
}

C. Bob in Wonderland

题意

把一棵树变为一条链的最少操作次数$(n \in [1, 3e5])$。

Solution

其实就是不断把度大于2的点转移到头或者尾，因此答案就是所有度数大于2的点减去2的和。

Code

#include <bits/stdc++.h>
using namespace std;
int n, x, y, res, d[500005];
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    d[x]++;
    d[y]++;
  }
  for (int i = 1; i <= n; i++) res += max(d[i] - 2, 0);
  printf("%d\n", res);
  return 0;
}

E. Zeldain Garden

题意

求给定区间内所有数的因子个数和$(n \in [1, 1e12])$。

Solution

打表发现 $1-n$ 内因子个数和就是 $n / i$ 的和 $(i \in [1, n])$，然后用除法分块解决。

Code

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

ll solve(ll n) {
  ll sum = n;
  for (ll i = 2; i <= n;) {
    ll x = n / i;
    ll y = min(n / x, n);
    sum += x * (y - i + 1);
    i = y + 1;
  }
  return sum;
}

int main() {
  ll a, b;
  cin >> a >> b;
  cout << solve(b) - solve(a - 1) << endl;
  return 0;
}

F. Light Emitting Hindenburg

题意

从 $n$ 个正整数中选出k个数字使得进行按位与操作得到的结果最大$(n \in [1, 2e5])$。

Solution

考虑二进制位，当且仅当 $k$ 个数字该位都为1，位与结果才为1。因此从高位开始枚举二进制位，当该位为1的数量超过 $k$ 时，剔除所有不为1的数，最后剩下的数即为可以选择的数，且这些数无论怎么选择 $k$ 个，位与结果都相同。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, k, a[N], vis[N];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 30; i >= 0; i--) {
    int cnt = 0;
    for (int j = 0; j < n; j++) {
      if ((a[j] >> i) & 1 && !vis[j]) cnt++;
    }
    if (cnt >= k) {
      for (int j = 0; j < n; j++) {
        if (!((a[j] >> i) & 1)) vis[j] = 1;
      }
    }
  }
  int res = -1;
  for (int i = 0; i < n; i++) {
    if (!vis[i]) res &= a[i];
  }
  printf("%d\n", res);
  return 0;
}

H. Ponk Warshall

题意

两个字符串s, t仅包含ATCG，求s最少经过多少次交换可以变为t$(n \in [1, 1e6])$。

Solution

按四种优先级讨论：

1. 同一个位置字符相同，直接跳过无需交换。
2. 交换一次，使得两个字符直接匹配。
3. 交换两次，使得三个字符直接匹配。
4. 交换三次，使得四个字符直接匹配。

数组 $cnt[i][j]$ 表示每个字符的对应关系，按优先级计算累加答案即可。

Code

#include <bits/stdc++.h>
using namespace std;
int n, res, mp[200], cnt[4][4];
int main() {
  string s, t;
  cin >> s >> t;
  n = s.size();
  mp['A'] = 0, mp['T'] = 1, mp['C'] = 2, mp['G'] = 3;
  for (int i = 0; i < n; i++) {
    if (s[i] != t[i]) cnt[mp[s[i]]][mp[t[i]]]++;
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < i; j++) {
      int x = min(cnt[i][j], cnt[j][i]);
      res += x;
      cnt[i][j] -= x, cnt[j][i] -= x;
    }
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < i; j++) {
      for (int k = 0; k < j; k++) {
        int x = min(cnt[i][j], min(cnt[j][k], cnt[k][i]));
        int y = min(cnt[i][k], min(cnt[k][j], cnt[j][i]));
        res += (x + y) * 2;
        cnt[i][j] -= x, cnt[j][k] -= x, cnt[k][i] -= x;
        cnt[i][k] -= y, cnt[k][j] -= y, cnt[j][i] -= y;
      }
    }
  }
  for (int i = 0; i < 4; i++) res += cnt[0][i] * 3;
  cout << res << endl;
  return 0;
}