Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324) 赛后总结

可悲的是：我没来得及写题解。

T1 Same

秒切。

直接输入排一遍序再遍历即可。

#include <bits/stdc++.h>

using namespace std;

int n, a[101];

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for (int i = 2; i <= n; i++) {
    if (a[i] != a[i - 1]) {
      cout << "No";
      return 0;
    }
  }
  cout << "Yes";
  return 0;
}

T2 3-smooth Numbers

秒切。

直接暴力枚举。

注意：long long

#include <bits/stdc++.h>

using namespace std;

long long n;

int main() {
  cin >> n;
  unsigned long long sum1 = 1;
  for (int x = 0; x <= 64; x++, sum1 *= 2) {
    unsigned long long sum2 = 1;
    for (int y = 0; y <= 40; y++, sum2 *= 3) {
      if (sum1 * sum2 == n) {
        cout << "Yes";
        return 0;
      }
    }
  }
  cout << "No";
  return 0;
}

T3 Error Correction

赛时第一发出了一个很（好听的话）的问题，还好调出来了。

分 3 类讨论：

• s.size() == t.size() && t == s
• t.size() == s.size() - 1
• t.size() == s.size() + 1
• t.size() == s.size() && t != s

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 10;

int n, ans, a[MAXN];
string s;
string str[MAXN];

bool check(int ind) {
  if (str[ind].size() == s.size() && str[ind] == s) {
    return 1;
  }
  if (str[ind].size() == s.size() + 1) {
    int pos = -1;
    for (int i = 0; i < s.size(); i++) {
      if (s[i] != str[ind][i]) {
        pos = i;
        break;
      }
    }
    if (pos == -1) {
      return 1;
    }
    string s1 = s.substr(pos), s2 = str[ind].substr(pos + 1);
    return (s1.size() == s2.size() && s1 == s2);
  } else if (str[ind].size() == s.size() - 1) {
    int pos = -1;
    for (int i = 0; i < s.size() - 1; i++) {
      if (s[i] != str[ind][i]) {
        pos = i;
        break;
      }
    }
    if (pos == -1) {
      return 1;
    }
    string s1 = s.substr(pos + 1), s2 = str[ind].substr(pos);
    return (s1.size() == s2.size() && s1 == s2);
  } else if (str[ind].size() == s.size()) {
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
      if (s[i] != str[ind][i]) {
        cnt++;
      }
    }
    return cnt == 1;
  }
  return 0;
}

int main() {
  cin >> n >> s;
  for (int i = 1; i <= n; i++) {
    cin >> str[i];
    if (check(i)) {
      a[++ans] = i;
    }
  }
  cout << ans << '\n';
  for (int i = 1; i <= ans; i++) {
    cout << a[i] << ' ';
  }
  return 0;
}

T4 Square Permutation

赛时第一发没判前导零，导致 WA 了好多，第二发过了。

枚举平方数，但是是平方数的平方根。

注意：可能有前导 0。

#include <bits/stdc++.h>

using namespace std;

int n;
long long ans;
string s;
int cnt[10], cnt2[10];

int main() {
  cin >> n >> s;
  for (int j = 0; j < n; j++) {
    cnt2[s[j] - '0']++;
  }
  for (int i = 0; 1ll * i * i <= 9999999999999ll; i++) {
    long long x = 1ll * i * i;
    fill(cnt, cnt + 10, 0);
    for (; x; x /= 10) {
      cnt[x % 10]++;
    }
    bool flag = 0;
    for (int j = 0; j < 10; j++) {
      if ((j && cnt[j] != cnt2[j]) || (!j && cnt[j] > cnt2[j])) {
        flag = 1;
        break;
      }
    }
    ans += !flag;
  }
  cout << ans;
  return 0;
}