牛客小白月赛 71 题解

A 猫猫与广告

由于是签到题所以只考虑矩形平行的情况，如果选手多考虑了，出题人表示十分抱歉。

先通过交换令 $a\leq b,c\le d$ ，然后判断是否 $c\geq a$ 且 $d\geq b$ 。

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(a > b)
    swap(a, b);
  if(c > d)
    swap(c, d);
  cout << (c >= a && d >= b ? "YES" : "NO") << endl;
  return 0;
}

B 猫猫与密信

查看 $t$ 中是否存在 love lov loe lve 或 ove。

int main() {
  string s;
  cin >> s;
  if(s.find("ove") != -1 || s.find("lve") != -1|| s.find("loe") != -1 || s.find("lov") != -1) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

C 猫猫与数列

由于 $p\geq 2,q\geq 2$ ，会指数爆炸， $n$ 不会特别大，直接依次计算 $a_{3}, a_{4}, . . .$

问题转化为已知 $x,y\leq M$ ，如何判断 $x^y\leq M$ 是否满足。

先取 ln 得到 $y \ln x \le \ln M$ ，先用小数判断。假设通过了小数判断，记小数误差是 $\varepsilon$ ，实际结果误差不超过 $e^{\varepsilon}$ 倍内，此时再用 long long 判断。不过由于本题的特殊性，直接小数判断也可以过。

赛时发现适用 C++ int128 或者 Python 高精度等会更加方便。

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
using ll = long long;

const ll lim = (ll)1e18;
ll p, q;
ll Pow(ll x, ll y) {
  ll ans = 1;
  rep(i, 1, y)
    ans *= x;
  return ans;
}
const double eps = 1e-5;
bool ok(ll x, ll y) { //x^y <= M ?
  return y * log(x) <= log(lim) + eps && Pow(x, y) <= lim;
}
int main() {
  cin >> p >> q;
  int n = 2;
  while(ok(p, q)) {
    ll r = Pow(p, q);
    p = q; q = r;
    n ++;
  }
  printf("%d\n", n);
  return 0;
}

D 猫猫与主人

每只猫猫只需判断能接受它的主人中友善度最大的是否满足它的要求，不满足就是 $- 1$ ，否则就是答案。

类似双指针的思想，我们把主人按 $d$ 从小到大排序，猫猫按 $a$ 从小到大排序。然后枚举猫猫 $i = 1$ 到 $n$ ，同时维护一个指针 $p$ (初始为 $0$ )，表示 $[1, p]$ 的主人接受猫猫 $i$ 。那么当 $i$ 增加时，猫猫的友善值增加，可能会有更多的主人接受猫猫 $i + 1$ ，则 $p$ 可以增加。我们预先预处理好 $b$ 的前缀最大值，设为 $b^{'}$ ，那么猫猫 $i$ 能获得的最友善值就是 $b^{'} [p]$ 。

时间复杂度为排序的复杂度 $\mathcal O(n\log n)$ 。

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
const int N = 2e5 + 5;
int n, m, a[N], c[N], b[N], d[N];
int host[N], cat[N], ans[N];
int main() {
  scanf("%d%d", &n, &m);
  rep(i, 1, n) scanf("%d", a + i);
  rep(i, 1, n) scanf("%d", c + i);
  rep(i, 1, m) scanf("%d", b + i);
  rep(i, 1, m) scanf("%d", d + i);
  rep(i, 1, m) host[i] = i;
  rep(i, 1, n) cat[i] = i;
  sort(host + 1, host + m + 1, [&](int x, int y) {
    return d[x] < d[y];
  });
  sort(cat + 1, cat + n + 1, [&](int x, int y) {
    return a[x] < a[y];
  });
  int p = 0, mx = 0;
  rep(i, 1, n) {
    int u = cat[i];
    while(p < m && d[host[p + 1]] <= a[u]) {
      mx = max(mx, b[host[++ p]]);
    }
    ans[u] = mx >= c[u] ? mx : -1;
  }
  rep(i, 1, n)
    printf("%d%c", ans[i], " \n"[i == n]);
  return 0;
}

E 猫猫与数学

不妨令 $a\le b$ 。

$\gcd(a+c,b+c) = \gcd(a+c,b-a)$ 。

枚举 $b - a$ 的所有质因数 $p$ ，我们试图让 $p\mid a+c$ 。若 $p\mid a$ 则 $c = 0$ ，否则 $c = p - (a\bmod p)$ ，更新答案即可。时间复杂度 $\mathcal O(\sqrt {|b-a|})$ 。

由此可见直接暴力枚举复杂度不对，比如 $a = 2, b = 1 0^{9} + 9$ ，答案 $c = 1 0^{9} + 5$ 。

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
using ll = long long;
ll a, b, ans;
ll gcd(ll a, ll b) {
  return b ? gcd(b, a % b) : a;
}
int main() {
  cin >> a >> b;
  if(a > b) swap(a, b);
  if(gcd(a, b) > 1) {
    cout << 0 << endl;
    return 0;
  }
  b -= a;
  if(!b) {
    cout << 1 << endl;
    return 0;
  }
  if(b == 1) {
    cout << -1 << endl;
    return 0;
  }
  ll ans = 1e18;
  for(ll d = 2; d * d <= b; d ++) {
    if(b % d == 0) {
      ans = min(ans, d - a % d);
      while(b % d == 0) b /= d;
    }
  }
  if(b > 1) {
    ans = min(ans, b - a % b);
  }
  printf("%lld\n", ans);
  return 0;
}

F 猫猫与宝石

考虑一次询问怎么做。根据期望的线性性 (本质就是拆项)，我们只需考虑每个宝石的贡献。通过组合恒等式化简，有

\dfrac{1}{2^n}\sum_{k = 1}^n a_k \sum_{i = 0}^{n-1} {n-1\choose i} (i+1) \\ = \dfrac{1}{2^n}\sum_{k = 1}^n a_k \left(\sum_{i = 1}^{n-1} {n-1\choose i} i+ 2^{n-1}\right) \\ = \dfrac{1}{2^n}\sum_{k = 1}^n a_k \left(\sum_{i = 1}^{n-2} {n-2\choose i-1}(n-1)+ 2^{n-1}\right) \\ = \dfrac{1}{2^n}\sum_{k = 1}^n a_k \left((n-1)2^{n-2}+ 2^{n-1}\right)

当然，有更加简单的推导方法，考虑其余 $n - 1$ 个元素都会以 $0.5$ 的概率出现并让 $a_{k}$ 的贡献次数多一次，故答案为

\sum_{k = 1}^n \dfrac{1}{2} a_k\left(\dfrac{n-1}{2} + 1\right) \\ =\dfrac{n+1}{4}\sum_{k = 1}^n a_k

对于每个前缀的询问，记录前缀和即可。

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
const int mod = 998244353;
const int inv2 = (mod + 1) / 2;
const int inv4 = 1LL * inv2 * inv2 % mod;
const int N = 2e5 + 5;
int n, a[N];
int main() {
  scanf("%d", &n);
  rep(i, 1, n) scanf("%d", a + i);
  rep(i, 1, n) (a[i] += a[i-1]) %= mod;
  rep(i, 1, n) printf("%d%c", int((i + 1ll) * a[i] % mod * inv4 % mod), " \n"[i == n]);
  return 0;
}