行业知识
赛氪OJ评测 | CCF CAT- 全国算法精英大赛（2024第二场）往届真题练习 1 | 珂学家
前言
在赛氪OJ打过不少比赛，包括计算机挑战赛春季赛/秋季赛，大学生算法赛（清华社杯），CCF-CAT，智星算法赛等。
我感觉需要对这个平台，做一下评测，以帮助新生避下坑。
主要涉及
- 知识点和难度
- 编程语言优劣
主要以 CCF CAT- 全国算法精英大赛（2024第二场）往届真题练习 1 这场练习赛作为依据。
知识点和难度
一句话概括： 知识点属于竞赛范畴，团队赛难度 ≥ 个人赛难度 . 知识点属于竞赛范畴，团队赛难度 \ge 个人赛难度. 知识点属于竞赛范畴，团队赛难度≥个人赛难度.
如果你的算法水平，仅限于力扣水平，那这比赛会打得很吃力。
以练习赛的5道题为例
这场我做了4题，3道AC，1道被卡常（后面会解释），1题完全没思路。
整体而言，知识点考察广，覆盖字符串，单调栈，数论，图论等等，而且较为综合，不是单纯的板子和思维题。
对大部分的同学而言，需要提前做好挫折心理预期。
编程语言
这个OJ平台和其他平台不一样。
c + + 是 1 等公民， j a v a 是 3 等公民， p y t h o n 是 4 等公民，那为啥中间没有那个 2 呢？ c++是1等公民，java是3等公民，python是4等公民，那为啥中间没有那个2呢？ c++是1等公民，java是3等公民，python是4等公民，那为啥中间没有那个2呢？
因为实在差太多了，不是特别建议用python作为开发语言。
java版本好像是jdk8，切忌高版本的语法。
python没有使用pypy3，即运行时编译优化。
按照一般的约定
其他语言时限是 c + + 的 2 倍 其他语言时限 是c++的2倍 其他语言时限是c++的2倍
但是在这个平台显然并不成立，因此建议主委会放宽其他语言的时限，尤其是python。
以第3题为例 The diameter of a rectangle
这其实是一道单调栈的裸题
同样是O(n)的算法和思路，c++，java, python的对比就很有说服力。
- c++ 1秒内AC
- java 10秒内AC
- python 20秒 TLE
import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[][] pack = new int[n][2]; for (int i = 0; i = pack[i][0]) { mono1.pollLast(); } if (mono1.isEmpty()) { pre[i] = x; } else { pre[i] = x - mono1.peekLast()[0]; } x += pack[i][1]; mono1.offerLast(new int[]{x, pack[i][0]}); } x = 0; Deque mono2 = new ArrayDeque(); for (int i = n - 1; i >= 0; i--) { while (!mono2.isEmpty() && mono2.peekLast()[1] >= pack[i][0]) { mono2.pollLast(); } if (mono2.isEmpty()) { suf[i] = x; } else { suf[i] = x - mono2.peekLast()[0]; } x += pack[i][1]; mono2.offerLast(new int[]{x, pack[i][0]}); } int res = 0; for (int i = 0; i# coding=utf-8n = int(input())pack = []for _ in range(n): h, w = list(map(int, input().split())) pack.append((h, w))# 单调栈from collections import dequepre = [0] * nsuf = [0] * nmono1 = []x = 0for i in range(n): ps = pack[i] while len(mono1) > 0 and mono1[-1][h] >= ps[0]: mono1.popleft() if len(mono1) == 0: pre[i] = x else: pre[i] = x - mono1[-1][1] mono1.append((x, ps[0])) x += ps[1]mono2 = []x = 0for i in range(n - 1, -1, -1): ps = pack[i] while len(mono2) > 0 and mono2[-1][h] >= ps[0]: mono2.popleft() if len(mono2) == 0: suf[i] = x else: suf[i] = x - mono2[-1][1] mono2.append((x, ps[0])) x += ps[1]res = 0for i in range(n): l = (pre[i] + suf[i] + pack[i][1]) h = pack[i][0] res = max(res, min(l, h) ** 2)print (res)
所以javaer和pythoner一定要备好快读快写的板子，必要时切c++。
因为太容易卡常了，个人建议主委会
其他语言时限为 c + + 的 10 倍 其他语言时限为c++的10倍 其他语言时限为c++的10倍
当然这是平台，狠起来c++都卡常。
比如 第一题， 这么离谱的通过率，是因为卡常。
用了字符串hash的做法，时间复杂度在 O ( n 2 + m ) , n ≤ 1 e 3 , m ≤ 1 e 5 O(n^2+m), n\le 1e3, m\le 1e5 O(n2+m),n≤1e3,m≤1e5
能优化的手段都用了，还是过不了，T_T。
比赛评价
主要分两块
- 题目描述
- 赛时rejudge
这个比赛题目的题意描述，说真的，比其他平台还是差了一些，当然这个和赛氪OJ本身没啥关系。
打个预防针吧，记得赛时及时反馈
赛时如果遇到数据有问题，往往赛后才rejudge，这个需要同学注意。
练习赛1的题解
Mysterious Rune String
字符串hash(双hash)
被卡常，哎
s = input()m = int(input())class StringHash(object): def __init__(self, s, p, m): self.s = s self.p = p self.m = m n = len(s) arr = [0] * (n + 1) base = [1] * (n + 1) for i in range(n): arr[i + 1] = (arr[i] * p + (ord(s[i]) - ord('a') + 1)) % m base[i + 1] = base[i] * p % mod self.n = n self.arr = arr self.base = base def query(self, l, r): tmp = self.arr[r + 1] - self.arr[l] * self.base[r - l + 1] % self.m return (tmp % self.m + self.m) % self.mmod = 10 ** 9 + 7sh1 = StringHash(s, 13, mod)sh2 = StringHash(s, 17, mod)from collections import Countermp = Counter()hp = Counter()n = len(s)for i in range(n): for j in range(i, n): h1 = sh1.query(i, j) h2 = sh2.query(i, j) mp[(h1, h2)] ^= (j + 1)for (k, v) in mp.items(): hp[v] += 1def solve(l, r): h1 = sh1.query(l, r) h2 = sh2.query(l, r) k = mp[(h1, h2)] return hp[k]for _ in range(m): l, r = list(map(int, input().split())) l, r = l - 1, r - 1 print (solve(l, r))Card
因为任意点都可以到达
a 0 ∗ x 0 + . . . + a i ∗ x i + a n ∗ x n = 1 必然成立 a_0 * x_0 + ... + a_i * x_i + a_n * x_n = 1 必然成立 a0∗x0+...+ai∗xi+an∗xn=1必然成立
- 裴蜀定理 Bézout’s 定理 + 最优化剪枝BFS
# coding=utf-8n = int(input())arr = list(map(int, input().split()))brr = list(map(int, input().split()))from math import gcd, inffrom collections import Counterdef solve(): g = 0 for v in arr: g = gcd(v, g) if g != 1: return -1 dp = Counter() dp[0] = 0 res = inf for i in range(n): dp2 = Counter() for (k, v) in dp.items(): g = gcd(k, arr[i]) if g == 1: res = min(res, v + brr[i]) if g not in dp2: if v + brr[i]
Tourist
不会
The diameter of a rectangle
单调栈，代码在上面
Mystery Sailing Challenge
图论板子题，dijkstra算法的变体
但是需要对节点引入额外的状态, 包括上一条边，以及是否选择
n, m = list(map(int, input().split()))g = [[] for _ in range(n)]for _ in range(m): u, v, w = list(map(int, input().split())) u, v = u - 1, v - 1 g[u].append((v, w)) g[v].append((u, w))from math import infimport heapqres = [[inf] * n for _ in range(2)]hq = []heapq.heapify(hq)heapq.heappush(hq, (0, 0, -1, 0)) # cost, source, edgeres[0][0] = 0while len(hq) > 0: cost, source, edge, flag = heapq.heappop(hq) if res[flag][source] = cost + tw: res[1][v] = cost + tw heapq.heappush(hq, (res[1][v], v, w, 1)) if res[0][v] >= cost + w: res[0][v] = cost + w heapq.heappush(hq, (res[0][v], v, w, 0))res2 = [-1 if min(v1, v2) == inf else min(v1, v2) for (v1, v2) in zip(res[0], res[1])]print (*res2)
写在最后
- 裴蜀定理 Bézout’s 定理 + 最优化剪枝BFS
