前言

在赛氪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等公民,java3等公民,python4等公民,那为啥中间没有那个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 < n; i++) {  
            pack[i][0] = scanner.nextInt(); // 高度  
            pack[i][1] = scanner.nextInt(); // 宽度  
        }  
          
        int[] pre = new int[n];  
        int[] suf = new int[n];  
          
        Deque<int[]> mono1 = new ArrayDeque<>();  
        int x = 0;  
        for (int i = 0; i < n; i++) {  
            while (!mono1.isEmpty() && mono1.peekLast()[1] >= 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<int[]> 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 < n; i++) {  
            int l = pre[i] + suf[i] + pack[i][1];  
            int h = pack[i][0];  
            res = Math.max(res, Math.min(l, h) * Math.min(l, h));  
        }  
          
        System.out.println(res);  
        scanner.close();  
    }  
}
# coding=utf-8
n = int(input())

pack = []
for _ in range(n):
  h, w = list(map(int, input().split()))
  pack.append((h, w))

# 单调栈

from collections import deque

pre = [0] * n
suf = [0] * n

mono1 = []
x = 0
for 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 = 0
for 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 = 0
for 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),n1e3,m1e5

能优化的手段都用了,还是过不了,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.m

mod = 10 ** 9 + 7
sh1 = StringHash(s, 13, mod)
sh2 = StringHash(s, 17, mod)

from collections import Counter
mp = 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] += 1

def 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 必然成立 a0x0+...+aixi+anxn=1必然成立

  • 裴蜀定理 Bézout’s 定理 + 最优化剪枝BFS
# coding=utf-8

n = int(input())

arr = list(map(int, input().split()))
brr = list(map(int, input().split()))

from math import gcd, inf
from collections import Counter

def 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] < res:
                    dp2[g] = v + brr[i]
            elif v + brr[i] < dp2[g]:
                dp2[g] = v + brr[i]

            if v < res and (k not in dp2 or v < dp2[k]):
                dp2[k] = v
        dp = dp2
    return res

print (solve())

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 inf
import heapq

res = [[inf] * n for _ in range(2)]
hq = []

heapq.heapify(hq)
heapq.heappush(hq, (0, 0, -1, 0)) # cost, source, edge
res[0][0] = 0

while len(hq) > 0:
    cost, source, edge, flag = heapq.heappop(hq)
    if res[flag][source] < cost:
        continue

    for (v, w) in g[source]:
        tw = w
        if edge != -1 and w % edge == 0:
            tw = (w // edge - 1) * edge
        if flag == 0 and res[1][v] >= 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)


写在最后

在这里插入图片描述


Logo

欢迎加入西安开发者社区!我们致力于为西安地区的开发者提供学习、合作和成长的机会。参与我们的活动,与专家分享最新技术趋势,解决挑战,探索创新。加入我们,共同打造技术社区!

更多推荐