在赛氪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秒内ACjava 10秒内ACpython 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 = 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 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≤1e3,m≤1e5O(n^2+m), n\le 1e3, m\le 1e5O(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 = sself.p = pself.m = mn = 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)) % mbase[i + 1] = base[i] * p % modself.n = nself.arr = arrself.base = basedef query(self, l, r):tmp = self.arr[r + 1] - self.arr[l] * self.base[r - l + 1] % self.mreturn (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 - 1print (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 = 0for v in arr:g = gcd(v, g)if g != 1:return -1dp = Counter()dp[0] = 0res = inffor 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]