2019年安徽大学ACM/ICPC实验室新生赛题解

A. 素数分布

对于给定的 ，求出不超过 的素数的个数。

卡掉了最最暴力的做法，但是你只需要记录一个1000以内的素数表，然后每次在这个素数表里面统计就不会超时了。

#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<bool> isPrime(1001);
  isPrime[2] = true;
  for (int i = 3; i <= 1000; i++) {
    int sqt = sqrt(i);
    bool flag = true;
    for (int j = 2; flag && j <= sqt; j++)
      if (i % j == 0) flag = false;
    if (flag) isPrime[i] = true;
  }
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 2; i <= n; i++)
      if (isPrime[i]) ans++;
    cout << ans << endl;
  }
  return 0;
}

难度定位：codeforces rating 800

B.食物分配

给定四个正整数，判断这四个正整数能否被恰好划分成三组，每一组数的和相等。

设这四个数分别为 ，如果满足划分条件，则必然有 且 ，因此只需要对这四个数排序后判断即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int T;
  cin >> T;
  while (T--) {
    vector<int> nps(4);
    for (auto& i : nps) cin >> i;
    sort(nps.begin(), nps.end());
    if (nps[0] + nps[1] == nps[2] && nps[2] == nps[3])
      cout << nps[2] << endl;
    else
      cout << -1 << endl;
  }
  return 0;
}

难度定位：codeforces rating 1000

C.AHUICPC(Easy Version)

询问只会有10种情况（1到10），其中只有10的情况下暴力构造的长度会超过15，对于这种情况只需要2个A和5个H就可以构造出10个子序列"AH"，然后再后面补"UICPC"即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  if (n <= 9) {
    for (int i = 0; i < n; i++) cout << 'A';
    cout << "HUICPC\n";
  } else {
    cout << "AAHHHHHUICPC\n";
  }
  return 0;
}

难度定位：codeforces rating 800

D.不定方程

根据题意， 即为 的最小公倍数 ，于是有 。可见 一定是互质的，即 。而此时只需要令 即可构造出答案。

注意因为 最大会到 ，所以两者之积有可能超过int的范围。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int T;
  cin >> T;
  while (T--) {
    long long x, y;
    cin >> x >> y;
    if (__gcd(x, y) != 1)
      cout << -1 << endl;
    else
      cout << y << ' ' << x << ' ' << x * y << endl;
  }
  return 0;
}

难度定位：codeforces rating 1400

E.蕊蕊识数

因为数据量极大，所以直接用python暴力计算是会超时的。

注意到对于任意的 ，其被3除的余数都是1，因此 和 对3同余。

任何十进制非负整数都可以表示成 的多项式形式，其中 恰好是该十进制数的各个数位。因此任意十进制非负整数被3除的余数，都等于将它的各个十进制位的数相加后被3除的余数。换而言之，3满足所有情况的 ，而比3小的可能的答案只有2。

所以只需要判断一下2是否是答案，如果不是输出3即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int T;
  cin >> T;
  int _max = 0;
  while (T--) {
    string str;
    cin >> str;
    int num = 0;
    for (auto &i : str) num += i - '0';
    int check = (str.back() - '0') % 2;
    bool flag = true;
    while (num >= 10) {
      if (num % 2 != check) {
        flag = false;
        break;
      }
      str = to_string(num);
      num = 0;
      for (auto &i : str) num += i - '0';
    }
    if (flag && num % 2 == check)
      cout << 2 << endl;
    else
      cout << 3 << endl;
  }
  return 0;
}

python的AC代码

T = int(input())
while T:
    T -= 1
    n = input()
    check = int(n[-1]) % 2
    n = sum([int(i) for i in n])
    flag = True
    while n > 9:
        if n % 2 != check:
            flag = False
            break
        n = str(n)
        n = sum([int(i) for i in n])
    if flag and n % 2 == check:
        print(2)
    else:
        print(3)

难度定位：codeforces rating 1700

F.蕊蕊乘车去上学

题目所求即为等车的时间期望，我们设该期望为 ，其中 表示遇到发车间隔为 的公交车的概率， 表示遇到发车间隔为 的公交车的概率。

注意到这个概率是时间上的概率，假设一辆公交车刚刚离开，那么距离下一辆公交车到达需要 分钟，而在这段时间内等车遇到的公交车的发车间隔都是 。由于两种发车间隔出现的可能性是相等的，因此遇到的公交车发车间隔是 的概率为 ，遇到的公交车发车间隔是 的概率为 。最终的答案是 。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  cout << fixed << setprecision(2) << (double)(a * a + b * b) / (a + b) << endl;
  return 0;
}

难度定位：codeforces rating 1600

G.AHUICPC(Hard Version)

我们令 ，且 ，如果我们构造出所有的恰好有 个“AH”的字符串，并且它们之间互不影响，然后再在其后面接上"UICPC"，那么就可以得到答案。且长度为 数量级。

事实上我们每一次都用 个A和 个H来构造，由于我们保证了 ，所以我们可以把较小的 放在后面，把较大的 放在前面，这样我们可以重复利用较小的 的“H”。更形象地说，我们先取最后一项 ，此时会有 个A和 个H，接下来考虑前一项 ，我们在恰好其后有 个H的位置插入 个A。如此不断重复。

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> res;
int main() {
  int num;
  cin >> num;
  while (num > 0) {
    int tmp1 = sqrt(num), tmp2 = num / tmp1;
    while (tmp1 * tmp2 <= num) {
      tmp2++;
    }
    while (tmp1 * tmp2 > num) {
      tmp2--;
    }
    res.push_back(make_pair(tmp1, tmp2));
    num -= tmp1 * tmp2;
  }
  string str = "UICPC";
  res.push_back(make_pair(0, 0));
  for (int i = 0; i < res.size() - 1; i++) {
    for (int j = 0; j < res[i].second; j++) {
      str = "H" + str;
    }
    for (int j = 0; j < res[i].first - res[i + 1].first; j++) {
      str = "A" + str;
    }
  }
  cout << str << endl;
  return 0;
}

难度定位：codeforces rating 1900

H.无尽大军

抽象来说，对于起始的数字1，可以消耗2使其翻倍，即乘以2；而后既可以选择消耗2使其再乘以2，也可以消耗1使得上一次乘以 的操作变为乘以 。

因此对于 ，我们的操作其实是构造一个等式 ，而操作的总消耗即等于 。

不难发现对于最小的总消耗， 恰好为 的全体质因数，因此将 质因数分解之后把所有因子相加即可得到答案。

 #include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> res;
int main() {
  long long n;
  cin >> n;
  long long sqt = sqrt(n);
  long long ans = 0;
  for (long long i = 2; i <= sqt; i++) {
    while (n % i == 0) {
      ans += i;
      n /= i;
    }
  }
  if (n != 1) ans += n;
  cout << ans << endl;
  return 0;
}

难度定位：codeforces rating 2000