比赛链接
题目概览 A Algorithm Course 签到 B Best Grouping 贪心 牛客多校 , CodeForces C Computer Science Ability Test 莽
A - Algorithm Course 题意简述 给一个字符串，问其中子串 cat 和 dog 的总数
解题思路 懂了，这就学 Python
代码参考
Show code
A view 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\) 剔除，接下来将其匹配就行
复杂度 \(O(n\log n)\)
代码参考
Show code
B view 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 #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 题意简述 提答题，判断十个命题的对错
(线性代数) 向量 \(\overrightarrow{v_1}\) , \(\overrightarrow{v_2}\) 线性相关当且仅当存在标量 \(k_1\) , \(k_2\) 满足 \(k_1\overrightarrow{v_1}+k_2\overrightarrow{v_2}=\overrightarrow{0}\) (微积分) \({y\mathrm{d}x-x\mathrm{d}y\over x^2-y^2}=\mathrm{d}(\frac{1}{2}\ln|\frac{x-y}{x+y}|)\) (离散数学) \(\varnothing\subseteq\{\varnothing\}\) (物理) 在可逆绝热过程中，一摩尔理想气体从 \(V_0\) 膨胀到 \(2V_0\) , 如果气体的温度降低 \(25\%\) , 则该气体可能是一种单原子气体 (数据结构) Fibonacci 堆插入操作的均摊时间复杂度为 \(O(1)\) (近似算法) 若 \(\texttt{P}\ne\texttt{NP}\) , 则对于完全图上的旅行商问题，不存在 polynomial-time \(2\) -approximation 算法，但是存在 polynomial-time \(2^n\) -approximation 算法 (量子算法) 存在一种基于比较的量子排序算法，其时间复杂度优于 \(\Omega(n\log n)\) (操作系统) 有一个由 4 个具有相同类型的资源组成的系统。假设最多有 3 个进程同时使用资源，每个进程最多使用 2 个资源，那么该系统是无死锁的 (计算机理论) 假设 \(L(M)\) 是图灵机 \(M\) 接受的语言，则语言\(\{``M"|M\texttt{ is a Turing machine and }L(M)\texttt{ is uncountable}\}\) (编译原理) 存在一种语法满足是 LL (1) 但不是 LALR (1) 解题思路 答案是 FTTFTFFTFT