Codeforces Round #844 口胡题解 A, B, C, D

A. Parallel Projection

题面大意

长方体盒子里天花板和地上选定两点，找连接这两点的最短线。要求：

• 线必须与长方体的轴平行
• 线必须贴着长方体的边

两点水平面坐标为 $(f,g),(a,b)(f,\; g),\; (a,\; b)$，矩形大小为 $(w,d)(w,\; d)$，其中 $ww$ 是宽度。

分析

考虑布线的以下阶段：

1. 在天花板上的点
2. 到顶上矩形的边上
3. 到底部矩形的边上
4. 到地上的点

容易发现，如果在第 2, 3 步选取了平行于 $dd$ 的边，则在平行于 $dd$ 的线可以去到最小值 $\mathrm{\mid }g-b\mathrm{\mid }|g\; -\; b|$平行于 $hh$ 的线可以从左边下，也可以从右边下，因此平行于 $ww$ 的边可以取 $f+af\; +\; a$ 或者 $2w-f-a2w\; -\; f\; -\; a$。若在第 2, 3 步选取了平行于 $ww$ 的边，也可以使用类似的方法分析。最后对所有方案取最小值即可。

实现历程

总体比较顺畅，出 A 速度在同排位的人里面算较快的，只用了 6 分钟，打破了以往 A 题至少 15 分钟的尴尬局面。

AC 代码

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

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 100004;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int w, d, h;
    cin >> w >> d >> h;
    int a, b, f, g;
    cin >> a >> b >> f >> g;
    int result = h + abs(f - a) + g + b;
    result = min(result, h + f + a + abs(g - b));
    result = min(result, h + abs(f - a) + 2 * d - b - g);
    result = min(result, h + abs(g - b) + 2 * w - f - a);
    cout << result << endl;
  }
  return 0;
}

B. Going to the Cinema

大意

$nn$ 个人要去电影院，每个人对人数的预期是 $a_{i}a\_i$。假设最终去的人数是 $aa$，那么要让第 $ii$ 个人满意，分两种情况讨论：

• 去了：除自己之外去的人数大于或等于预期，即 $a-1\ge a_{i}a\; -\; 1\; \backslash geq\; a\_i$
• 没去：除自己之外去的人数小于预期，即 $a<a_{i}a\; \backslash lt\; a\_i$

思路

由于预期的数量级不大，考虑使用桶存储每种不同预期的人数。以下有几点洞察：

• 对于预期相同的所有人，不能一部分去、一部分不去
• 不能出现预期小的人没去，但预期大的人去了的情况
• 所有人去一定是可行解

因此，从最大预期开始往下枚举。最初，假设所有人都去，记为一种情况。如果枚举到的预期对应的人数非零，那么考虑在目前情况的基础上让此预期对应的所有人以及预期更高的人不去，维护最终去的人数 $aa$，判定是否符合标准。如果符合，则计入总数。该方法算法复杂度为 $O(n)O(n)$。

实现中的小遗憾

最初几分钟一直在考虑从所有人不去的情况开始递推，但由于这种情况有很强的不确定性，导致拖延了时间。以后做题时应当优先考虑确定的情况。

AC 代码

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

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 200004;
ll bucket[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    ll n;
    cin >> n;
    memset(bucket, 0, sizeof(ll) * n);
    ll cnt = n;
    while (cnt--) {
      ll a;
      cin >> a;
      bucket[a]++;
    }
    ll go = n;
    ll result = 1;
    for (ll i = n - 1; i >= 0; i--) {
      if (bucket[i] == 0) {
        continue;
      }
      if (go - 1 < i) {
        result--;
      }
      if (go - bucket[i] < i) {
        result++;
      }
      go -= bucket[i];
    }
    cout << result << endl;
  }
  return 0;
}

C. Equal Frequencies

大意

给定一个长度为 $nn$ 的字符串，改变最少的字母数量，使得出现了的字母有相同的出现频次。

思路

考虑朴素方法，若有相同的出现频次，必然存在 $mm$ 和 $tt$，使得涉及 $mm$ 种字母，每种字母出现 $tt$ 次，并且 $m\ast t=nm\; *\; t\; =\; n$。然而，我们有 $m\le 26m\; \backslash le\; 26$，因此只需要枚举 $m\in [1,26]m\; \backslash in\; [1,\; 26]$ 的情况即可。

对于每种 $mm$ 和 $tt$，我们希望改变的字母数尽可能少，因此考虑使用桶记录每个字母出现的次数后降序排序，优先保留出现次数第 $[1,m][1,\; m]$ 高的字母。

考虑目标出现词频和实际出现词频的差值，对于每个字母有三种情况：

• 实际出现次数更多，那么超出的部分要替换成某个目标出现次数大于实际出现次数的字母，并且要记录我们已经补了这个字母一次。当补的次数达到目标次数与实际次数的差值时，不能再补。
• 实际出现次数和目标出现次数相同，那么保持原形。
• 实际出现次数小于目标出现次数，则会被用于第一种情况。

实现时的一些小遗憾

我记录的东西有些混乱，并且意义不明，导致调了很久。以后遇到这种情况，应当优先维护一些意义清晰明确的变量。虽然为此可能需要维护更多数组，但可以减少调试时间，从而为后续的题目节约时间和能量。

AC 代码

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

#define ll long long
#define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 100004;

struct node {
  ll index;
  ll value;
};

node cnt[26];
ll rawCnt[26];
ll keep[26];

bool cmp(node a, node b) { return a.value > b.value; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    ll n;
    cin >> n;
    char s[N];
    cin >> s;
    memset(cnt, 0, sizeof(node) * 26);
    memset(rawCnt, 0, sizeof(ll) * 26);
    memset(keep, 0, sizeof(ll) * 26);
    for (ll i = 0; i < 26; i++) {
      cnt[i].index = i;
    }
    for (ll i = 0; i < n; i++) {
      cnt[s[i] - 'a'].value++;
    }
    for (ll i = 0; i < 26; i++) {
      rawCnt[i] = cnt[i].value;
    }
    sort(cnt, cnt + 26, cmp);
    ll maxSame = 0;
    ll maxI = 0;
    for (ll i = 1; i <= 26; i++) {
      ll same = 0;
      if (n % i == 0) {
        ll h = n / i;
        for (ll j = 0; j < i; j++) {
          same += min(h, cnt[j].value);
        }
      }
      if (same > maxSame) {
        maxSame = same;
        maxI = i;
      }
    }
    cout << n - maxSame << endl;
    ll maxH = n / maxI;
    for (ll i = 0; i < maxI; i++) {
      keep[cnt[i].index] = maxH;
    }
    for (ll i = 0; i < n; i++) {
      char ch = s[i];
      if (keep[s[i] - 'a']) {
        cout << ch;
        keep[s[i] - 'a']--;
        rawCnt[s[i] - 'a']--;
      } else {
        for (ll i = 0; i < 26; i++) {
          if (keep[i] > rawCnt[i]) {
            cout << (char)(i + 'a');
            rawCnt[i]++;
            break;
          }
        }
      }
    }
    cout << endl;
  }
  return 0;
}

D. Many Perfect Squares

题目大意

给定一个数组 $a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash dots,\; a\_n$，找到一个 $x\in [0,10^{18}]x\; \backslash in\; [0,\; 10^\{18\}]$，使得给数组所有数加上 $xx$ 之后产生的完全平方数最多。

数据范围：$1\le n\le 501\; \backslash le\; n\; \backslash le\; 50$，$1\le a_1<a_2<\cdots <a_n\le 10^{9}1\; \backslash le\; a\_1\; \backslash lt\; a\_2\; \backslash lt\; \backslash dots\; \backslash lt\; a\_n\; \backslash le\; 10^9$

思路

考虑能否缩小 $xx$ 的候选范围，但由于相邻平方数 $a,ba,\; b$ 的差是 $\sqrt{b-a}\backslash sqrt\{b\; -\; a\}$ 数量级的，我们可以使用最小的 $a_{1}a\_1$ 和最大的 $a_{2}a\_2$ 构造出需要 $xx$ 接近 $10^{18}10^\{18\}$ 数量级的情况。即使复杂度在 $\sqrt{10^{18}}\backslash sqrt\{10^\{18\}\}$ 也无法接受，因此考虑平方数序列的性质。

• 最终形成的平方数序列不一定相连，所以从相连平方数的角度考虑大概率得不到正解
• 修改后的序列中任意两个数的差维持恒定。

考虑平方差公式 $a^2-b^2=(a+b)(a-b)a^2\; -\; b^2\; =\; (a+b)(a-b)$，由于分解乘积的复杂度是 $\sqrt{a^2-b^2}\backslash sqrt\{a^2\; -\; b^2\}$，最大为 $\sqrt{10^9}\backslash sqrt\{10^9\}$，因此可以接受。这时，我们对序列中任意两个数 都可以算出所有可能的 $a_i-a_{j}a\_i\; -\; a\_j$ 的分解方式。对于某种分解方式，我们可以还原出 $a^{2}a^2$ 和 $b^{2}b^2$，这时我们应当有 $a^2-b^2=a_i-a_{j}a^2\; -\; b^2\; =\; a\_i\; -\; a\_j$。这时，只要 $b^2\ge a_{j}b^2\; \backslash ge\; a\_j$，则 $b^2-a_{j}b^2\; -\; a\_j$ 可以作为一个 $xx$ 值。

考虑使用标准库的 multiset 记录每个 $xx$ 值的方案数。如果外层遍历左端点 $jj$，内层遍历右端点 $ii$，那么每次内层遍历完都涉及了其后的所有元素。考虑以下两种情况：

• 后续内层遍历到的 $xx$ 值在过去的外层遍历从未出现过，那么这样的 $xx$ 无法使得前面的元素为完全平方数，故不需要统计过去的元素
• 如果出现过，那么在过去的外层遍历已经处理过。

因此考虑直接每次内层遍历后清空 multiset 避免重复计数。当然也可以考虑在 multiset 中对每个 $xx$ 值记录其能使哪些数变为完全平方数，这样更符合直觉。

实现时的小遗憾

本题消耗了我 54 分钟，基本等同于前三题的耗时（57 分钟），难度较前面的题有较大提升。

我花了过多时间思考相连平方数的性质，实际上可以根据题目不要求平方数相连直接否决掉，这一思维上的剪枝至少可以节约我 15 分钟的时间。同时，我也没能正确地确认 $xx$ 的范围，导致花了约 20 分钟实现暴力算法，其中甚至花了几分钟测试 sqrt 函数的常数。sqrt 在我的机器上运行 $10^{8}10^8$ 次大约需要 0.3 秒，常数较小，可近似认为 $O(1)O(1)$ 完成。

实现时最初忘了 $aa$ 和 $bb$ 的意义，导致将 $b^2\ge a_{j}b^2\; \backslash ge\; a\_j$ 写成 $b\ge a_{j}b\; \backslash ge\; a\_j$，但最后 $xx$ 的算法又写对了，造成 WA2，花了 10 分钟找 bug，相当不愉快。

同时，写代码的时候 for 循环最初重复使用 i，导致隐蔽的 bug，找了几分钟。

如果没有犯以上错误，大约可以在 10 分钟内完成本题。

AC 代码

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

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << endl;
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 100004;

ll a[54];
multiset<ll> option;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    // find factorial
    int maxCount = 1;
    for (int i = 0; i < n - 1; i++) {
      option.clear();
      for (int j = i + 1; j < n; j++) {
        ll delta = a[j] - a[i];
        ll rt = sqrt(delta);
        for (int k = 1; k <= rt; k++) {
          if (delta % k == 0) {
            ll another = delta / k;
            ll a2 = k + another;
            if (a2 % 2 == 1) {
              continue;
            }
            ll b2 = another - k;
            if (b2 % 2 == 1) {
              continue;
            }
            ll b = b2 >> 1;
            if (b * b >= a[i]) {
              valln(b);
              option.emplace(b);
              int count = option.count(b);
              if (count + 1 > maxCount) {
                maxCount = count + 1;
              }
            }
          }
        }
      }
    }
    cout << maxCount << endl;
  }

  return 0;
}