题解 - 2020 ICPC 亚洲区域赛 (南京) 热身赛

发表于 更新于 分类于 ， ， 本文字数： 651 阅读时长 ≈ 2 分钟

比赛链接

题目概览

题号 标题 做法 备注
A Algorithm Course 签到
B Best Grouping 贪心 牛客多校 , CodeForces
C Computer Science Ability Test 莽

A - Algorithm Course

题意简述

给一个字符串，问其中子串 cat 和 dog 的总数

解题思路

懂了，这就学 Python

代码参考

Show code

Aview raw
1
2
3
4
5
6
7
8
9
"""
@Author: Tifa
@Description: From <https://github.com/Tiphereth-A/CP-archives>
!!! ATTENEION: All the context below is licensed under a
  GNU Affero General Public License, Version 3.
  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
"""
s = input()
print(s .count('cat')+s .count('dog'))

B - Best Grouping

题意简述

在 \(1..n\) 中选出若干个数，两两一组，要求每一组均不互素，输出组数最大的一个方案

解题思路

首先我们 \(1\) 和大于 \(\lfloor\frac{n}{2}\rfloor\) 的素数肯定不会出现在结果里，之后剩下的数里我们从大到小枚举质数 \(p\), 统计所有之前没有匹配过的 \(p\) 的倍数，如果是偶数个就把 \(2p\) 剔除，接下来将其匹配就行 1

复杂度

\(O(n\log n)\)

代码参考

Show code

Bview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
bool vis[N];
int prime[N], cnt_prime;
void init_prime(int n = N - 1) {
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) prime[++cnt_prime] = i;
    for (int j = 1; j <= cnt_prime && i * prime[j] <= n; ++j) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
using pii = pair<int, int>;
vector<pii> ans;
queue<int> tmp;
int main() {
  init_prime();
  int kase;
  scanf("%d", &kase);
  while (kase--) {
    int n;
    scanf("%d", &n);
    if (n < 4) {
      puts("0");
      continue;
    }
    memset(vis, 0, sizeof(vis[0]) * (n + 1));
    int _ = upper_bound(prime + 1, prime + cnt_prime + 1, n / 2) - prime;
    for (int i = _; i; --i) {
      for (int j = 3; prime[i] * j <= n; ++j)
        if (!vis[prime[i] * j]) {
          tmp.push(prime[i] * j);
          vis[prime[i] * j] = 1;
        }
      if (tmp.size() % 2 == 0 && 2 * prime[i] <= n && !vis[2 * prime[i]]) {
        tmp.push(2 * prime[i]);
        vis[2 * prime[i]] = 1;
      }
      if (tmp.size()) tmp.push(prime[i]);
      while (!tmp.empty()) {
        int a = tmp.front();
        tmp.pop();
        ans.push_back(make_pair(a, tmp.front()));
        tmp.pop();
      }
    }
    printf("%d ", ans.size());
    for (auto it = ans.begin(); it != ans.end(); ++it)
      printf("%d %d%c", it->first, it->second, " \n"[it == ans.end() - 1]);
    ans.clear();
  }
  return 0;
}

C - Computer Science Ability Test

题意简述

提答题，判断十个命题的对错

  1. (线性代数) 向量 \(\overrightarrow{v_1}\), \(\overrightarrow{v_2}\) 线性相关当且仅当存在标量 \(k_1\), \(k_2\) 满足 \(k_1\overrightarrow{v_1}+k_2\overrightarrow{v_2}=\overrightarrow{0}\)
  2. (微积分) \({y\mathrm{d}x-x\mathrm{d}y\over x^2-y^2}=\mathrm{d}(\frac{1}{2}\ln|\frac{x-y}{x+y}|)\)
  3. (离散数学) \(\varnothing\subseteq\{\varnothing\}\)
  4. (物理) 在可逆绝热过程中，一摩尔理想气体从 \(V_0\) 膨胀到 \(2V_0\), 如果气体的温度降低 \(25\%\), 则该气体可能是一种单原子气体
  5. (数据结构) Fibonacci 堆插入操作的均摊时间复杂度为 \(O(1)\)
  6. (近似算法) 若 \(\texttt{P}\ne\texttt{NP}\), 则对于完全图上的旅行商问题，不存在 polynomial-time \(2\)-approximation 算法，但是存在 polynomial-time \(2^n\)-approximation 算法
  7. (量子算法) 存在一种基于比较的量子排序算法，其时间复杂度优于 \(\Omega(n\log n)\)
  8. (操作系统) 有一个由 4 个具有相同类型的资源组成的系统。假设最多有 3 个进程同时使用资源，每个进程最多使用 2 个资源，那么该系统是无死锁的
  9. (计算机理论) 假设 \(L(M)\) 是图灵机 \(M\) 接受的语言，则语言
    \(\{``M"|M\texttt{ is a Turing machine and }L(M)\texttt{ is uncountable}\}\)
    是递归可枚举而不是递归的
  10. (编译原理) 存在一种语法满足是 LL (1) 但不是 LALR (1)

解题思路

答案是 FTTFTFFTFT

  1. 参见 https://codeforces.com/blog/entry/13112↩︎