UOJ Logo Rainbow_sjy的博客

博客

关于 Universal Online Judge 对于生成式 AI 的使用规则

2025-04-01 00:01:12 By Rainbow_sjy

以下规则适用于 Universal Online Judge(以下简称 UOJ)举办的比赛,包括但不限于 UOJ Round、UOJ Easy Round、UOJ NOI Round、UOJ Long Round 等。

  • 这些规则不适用于历史题目练习。

本公告所述规则是根据截至 2024 年 12 月的生成式人工智能(以下简称生成式 AI)的能力和使用情况制定的。我们计划根据 AI 技术的未来变化对规则进行相应修改。

规则

在 UOJ 比赛期间,原则上禁止使用生成式 AI。例外情况仅限于以下用途:

  • 题面翻译
    • 对于仅提供翻译功能的 AI 工具,您可以直接输入题面。
  • 代码补全工具(例如,Copilot):
    • 仅允许使用基于 AI 的代码补全工具来提高编码速度。
    • 不得使用它们来解决问题或子问题,或获取解题思路。
  • 编程语言转换(例如,将 Python 代码转换为 C++):
    • 原始代码必须作为注释包含在提交代码的开头。
    • 仅允许不改变算法的转换。特别是,不允许改变时间复杂度的转换。

什么是生成式 AI

  • 在这些规则中,“生成式 AI”被定义为“基于训练数据生成新数据(如文本或代码)的人工智能”。
  • 主要示例包括大型语言模型,如 GPT、Gemini、Gemma、Llama、Claude 等。

示例

禁止使用生成式 AI 替代您在问题理解、逻辑创建或决策中的推理:

  • 不得使用生成式 AI 总结题面。
  • 不得将题面、其摘要、摘录或子问题输入生成式 AI(包括代码补全工具)以输出代码或解决方案的自然语言解释。
  • 不得使用生成式 AI 诊断编译错误或漏洞。

如果您未使用生成式 AI,这些规则不适用。例如,允许使用以下工具:

  • 分析题面并生成输入/输出文件的工具
  • 分析题面并生成输入/输出处理代码的工具

在比赛开始前使用生成式 AI 创建的代码或其他材料,在比赛期间使用是被允许的。明确允许使用以下工具:

  • WolframAlpha、Mathematica
  • OEIS
  • Google 搜索

使用 Google 搜索时,您可以查看 Search Labs 中的 AI 生成摘要。

UOJ Easy Round #12 题解

2025-03-16 23:23:33 By Rainbow_sjy

电网检修

idea, solution, std, data by GeZhiyuan

这是一个结论题。假设树高为 $h$,我们对 $h$ 分类讨论:

当 $h < k$ 时:

  • 我们可以先假设 $k=n-1$ 即没有限制,然后两人在树上最终的位置分别是 $u, v$。此时不难发现两人最优情况下,相对于 $2(n-1)$ 能省去的总距离为 $u, v$ 间的距离 $d$。即我们要找到树的直径长度。
  • 然后我们考虑加上 $k$ 的限制。此时两人最终距离不会超出 $k$,因此省去的距离也不能超出 $k$。我们尝试证明答案能省去的距离即为 $\min(d, k)$。
  • 先找出直径两端点 $s, t$,然后不停将 $s$ 令为 $s$ 的父亲,直到 $s, t$ 距离小于等于 $k$,由于树高的限制,最终 $s$ 也不会成为 $t$ 的祖先,一定会有一时刻找到合适的 $s$。此时可以发现所有点和 $s$ 的距离都小于等于 $k$,而又有所有点和 $1$ 的距离都小于等于 $k$。因此只要先让伏特走,此时欧姆的位置一直在 $1$;再让欧姆走即,此时伏特的位置一直在 $s$。上述策略一定可以可满足题目限制。也就省去了 $\min(d, k)$ 的距离。

当 $h \geq k$ 时:

  • 不难发现,此时对于子树树高大于 $k$ 的点,两人都必须经过。因为对于一个深度大于等于 $k$ 的点,当两人中的某人到达这个叶子时,另一个人必定在其 $k$ 级祖先的子树内。也就是两人都经过了这个 $k$ 级祖先。 那么这样的 $k$ 级祖先所构成的点集即为子树树高大于 $k$ 的点构成的点集。
  • 假设子树树高大于 $k$ 的点构成的点集大小为 $m$。我们让两人分别去遍历整棵树,和子树树高大于 $k$ 的点构成的树。两树树高分别为 $h$ 和 $h-k$,根据经典结论相对于 $2(n-1)+2(m-1)$ 至多可以省去 $2h-k$ 的距离,并且发现可以轻松构造出一种移动策略达到这个值。此时答案即为 $2(n+m-2)-2h+k$。
  • 最后我们尝试证明其他策略一定不优于 $2h-k$。即对于一种其他的遍历到的点的分配方式。首先对于子树树高大于 $k$ 的点构成的树,一定都要被两人经过的点覆盖。而相当于其他的点我们要去分配给两个人。而我们有两人最终位置距离不超过 $k$。首先对于子树树高大于 $k$ 的点构成的树,两人省去的路径长度不超其树高两倍,即不超 $2h-2k$。而对于不在这个树内省去的距离,由于两人距离不超 $k$,因此也至多省去 $k$。综省去的距离不超 $2h-k$。

于是此题就在 $O(n)$ 内得以解决。

If there exists maxdep >= k, consider the component formed by the k-th ancestors of all nodes. Volt walk through all the tree, Ohm walk through the component. The answer is: 2*(n-1)-maxdep-(maxdep-k).

Otherwise, the two people can move to two leaves within some subtree, reducing the distance by min(diameter,k). The answer is: 2*(n-1)-min(diameter,k).

电子运动

idea, solution, std, data by Rainbow_sjy

算法 I

分析电子掉出去后,最终的结构是什么。

假设电子是从左边掉出去的(如果是右边则把所有操作反一下)。

假设电子一开始放在 $i$ 位置,$[1,i]$ 中有 $x$ 个 +,$[i+1,n]$ 中有 $y$ 个 -

若 $x\le y$,此时电子是从左边掉出去的,且 $[1,i]$ 全部变成 +,$[i+1,n]$ 中的前 $c$ 个 - 变成 +,其中 $c$ 是 $[1,i]$ 中初始的 + 个数。

枚举初始位置,枚举往右边碰到的最远位置,用组合数计算。

对于右边掉出去的情况就反过来做一遍。时间复杂度 $O(n^2)$,期望得分 $64$。

算法 II

这个模型的结构是十分对称的,可以观察更多性质。

考虑电子从左边掉出去,且最后变成全是 + 的情况,此时需要满足:$[1,i]$ 的 + 个数等于 $[i+1,n]$ 的 - 个数。我们可以发现,此时初始序列里需要恰好有 $i$ 个 - 和 $n-i$ 个 +。(这个过程类似范德蒙德卷积)

进一步,考虑 $i$ 向左的第一个 - 和向右的第一个 +,设为位置 $x$ 和 $y$。那么电子走 $i\to x\to y\to i$ 的路径,恰好交换了 $x$ 和 $y$ 的符号。

当 $[1,i]$ 全部变为 - 后,可以随意交换 $[i+1,n]$ 中的 +

通过等价交换之后,可以把字符串看作一个前缀全是 -,一个后缀全是 +。于是我们可以发现一个神奇的结论:字符串是否等价只和其中 + 的总个数相关。

进一步讨论可以得到:初始位置是 $i$,有 $\ge n-i+1$ 个 +,则会减少 $n-i$ 个 +;否则会增加 $i$ 个 +

那么对于初始位置是 $i$,初始有 $j$ 个 +,则最终会有 $(i+j) \bmod (n+1)$ 个 +。于是用一次卷积即可解决问题,时间复杂度 $O(n\log n)$,期望得分 $100$。

电阻匹配

idea, solution, std, data by Kubic

算法 I

考虑 kth-minmax 容斥:

$$ \operatorname{kthmin}(S,k)=\sum\limits_{T\subseteq S,|T|\ge k}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\max(T) $$

转化为对于每个 $k$ 求出如下问题的答案;

  • 先将 $a_{1\dots 2n}$ 两两匹配,一对匹配的权值为两个元素之和。然后在 $n$ 对匹配中选出恰好 $k$ 对,一组方案的权值为选出的匹配的最大权值。求所有方案的权值和。

设 $V$ 为一个足够大的值。则有:

$$ \max(S)=V-\sum_{w=0}^{V-1}\prod_{i\in S} [i\le w] $$

考虑枚举 $w$ 计算这个 $w$ 对答案的贡献。可以发现本质不同的 $w$ 只有 $O(n^2)$ 种。

我们将数分为 $\le\dfrac{w}{2}$ 和 $>\dfrac{w}{2}$ 两种,分别设为序列 $p,q$。

我们需要关注选出恰好 $k$ 对 $\le w$ 的匹配的方案数,剩余的 $n-k$ 对匹配可以在剩余的 $2(n-k)$ 个元素之间任意进行,方案数容易计算。

不妨设 $p$ 不降,$q$ 不增。

显然一个 $q$ 中的元素能匹配的一定是 $p$ 的一段前缀,而 $p$ 中的元素之间可以任意匹配。

设 $r_i$ 表示最大的数满足 $p_{r_i}+q_i\le w$。

设 $f_{i,j}$ 表示考虑 $q_{1\dots i}$,其中共进行了 $j$ 对 $p,q$ 间的匹配的方案数。

显然有转移方程:

$$ f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times (r_i-j+1) $$

设从 $i$ 个数种任意选出 $j$ 对匹配的方案数为 $c_{i,j}$。显然有:

$$ c_{i,j}=\dfrac{i!}{j!(i-2j)!2^j} $$

则一个 $w$ 对答案的贡献为:

$$ \sum f_{|p|,i}\times c_{|q|-i,k-i} $$

这两部分的时间复杂度均为 $O(n^2)$,而我们需要对每个 $w$ 做一遍。于是我们得到了一个总时间复杂度 $O(n^4)$ 的算法。

算法 II

考虑优化上述算法。

可以发现,第二部分中我们可以将 $|q|$ 相同的 $w$ 对应的 $f$ 放到一起计算贡献,而一共只有 $O(n)$ 种不同的 $|q|$。因此这一部分的时间复杂度容易优化到 $O(n^3)$。

现在的瓶颈在于对每个 $w$ 计算 $f$。

设 $g_{i,j}=f_{i,i-j},G_i(x)=\sum g_{i,j}x^j$。则有:

$$ g_{i,j}=g_{i-1,j-1}+g_{i-1,j}\times(r_i-i+j+1) $$

$$ G_i(x)=(x+r_i-i+1)G_{i-1}(x)+xG'_{i-1}(x) $$

设 $H_i(x)=e^xG_i(x)$。则有:

$$ H_i(x)=(r_i-i+1)H_{i-1}(x)+xH'_{i-1}(x) $$

$$ [x^j]H_i(x)=(r_i-i+j+1)[x^j]H_{i-1}(x) $$

因此我们可以在 $O(n)$ 的时间复杂度内计算出 $H_{|p|}(x)$。

但是通过 $H_{|p|}(x)$ 得到 $f_{|p|,*}$ 是 $O(n^2)$ 的,我们不能对于每个 $w$ 都进行处理。

与之前类似地,对于 $|q|$ 相同的 $w$,我们可以先将它们对应的 $H_{|p|}(x)$ 叠加起来得到 $H(x)$,然后计算 $G(x)=\dfrac{H(x)}{e^x}$,进一步得到 $f_{|p|,*}$ 叠加的结果。

这样我们就能在 $O(n^3)$ 的时间复杂度内得到转化后问题的答案。

UOJ Easy Round #12 公告

2025-03-08 14:39:52 By Rainbow_sjy

UOJ Easy Round #12 将于 3 月 16 日星期日晚上 19:00 举行!比赛将进行 3 个小时,共三道题。

这是 UOJ 第十二场 UOJ Easy Round,一如既往的 NOIP-省选难度,欢迎大家来玩!

1789 年 3 月 16 日,物理学家乔治·西蒙·欧姆诞生,他的欧姆定律揭示了电流与电压、电阻的深刻联系——伏特(电压)驱动电荷流动,欧姆(电阻)则平衡着电路的能量。

最近,跳蚤国正在尝试建设跳蚤国智能电网,于是跳蚤国王找到了得力助手伏特。你能不能帮助伏特完成建设电网的任务?

比赛链接:https://uoj.ac/contest/95

出题人:GeZhiyuan, Rainbow_sjy, Kubic

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的 SHA256 码是 c0d1037ef76091969573bbd53c9b575c4710cdf0377cd5661709b96d828c1492。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。


UPD: 恭喜前 5 名的选手!

  1. hos_lyric
  2. Nesraychan
  3. fansizhe
  4. xuanxuan001
  5. paul2008

UER#2 是第一次发放 UOJ 抱枕的 UOJ Round! 本次抱枕获奖条件为:对于 UER#2~UER#11 的所有 10 个获奖条件,符合条件的选手获得一张签,中签数最高的选手获得 UOJ 抱枕,如有多个取排名最高的。

  • 本次比赛的第二名将获得UOJ抱枕一个:Nesraychan
  • 本次比赛得分超过200的选手中得分最低的人。如果没有这样的人那么取比赛的第一名:zhaohaikun
  • 比赛中最后一个提交得分非0的代码的:maspy
  • B题最短的AC代码,如果有多个取最早提交的:xuanxuan001
  • 罚时最接近6小时6分钟6秒的选手,如有多个,取排名最高的:zhaohaikun
  • 第一次参加UOJ比赛的选手中排名最靠前的:UKBwyx
  • 最后一次计入总分的提交和第一次计入总分的提交时间差最大的,如有多个取排名最高的:JohnAlfnov
  • 有分且罚时(以秒为单位)模分数最大的选手,如果有多个,取排名最高的:lgvc
  • 非0分的计分提交中代码长度极差最大的,如有并列取排名最高的:Rubikun
  • 所有罚时大于 1h 的参赛者中,罚时最接近的一对参赛者中的罚时较大者,如有多对则取罚时最大的一对:Williamxzh

其中 zhaohaikun 获得了两张签,让我们恭喜他以“绝对”优势获得 UOJ 抱枕!

UOJ 940 黑桃国王 题解

2025-02-09 21:15:51 By Rainbow_sjy

曾经有人反映说看不懂这题题解,我来写一个(

一些基础观察

首先可以只保留强连通分量里的边,考察每个强连通分量,可能有几种情况:

  1. 是一个“循环”,存在一个 $k$ 使得距离 $\bmod k$ 相同的点字符相同。此时生成的字符串数量是有限的 $k$ 个。
  2. 包含至少两个“循环” $A$ 和 $B$,可以生成 $A^{\infty},(AB)^{\infty},(AAB)^{\infty},(AAAB)^{\infty},\cdots$,此时有一个在集合中的下界 $A^{\infty}$。
  3. 可以生成 $(ABC)^{\infty},(ABBC)^{\infty},(ABBBC)^{\infty},\cdots$,此时有一个不在集合里的下界 $(AB^{\infty}C)^{\infty}$。

假设我们已经特判掉了第 1 种情况,考虑 2 和 3,我们可以求出一个最终集合的“上界”,再把情况 1 的串判断能否小于上界。

为了求出 2 和 3 的最小字符串,想做的是求出每个点开始,走一个字典序最小的无限环 是什么样的路径。

设 $f(u,i)$ 表示 $u$ 开始,走 $i$ 步得到的字符串,最小是什么。这里只记所有 $f(u,i)$ 之间的大小关系。

转移每步从 $i\to i+1$ 可以递推,并且只要做 $O(n)$ 轮,直到 $f(u,i)$ 不再变化。

然后建一张新的有向图,图上的每个点表示一个 $f(u,i)$ 的值,每个点仅有一条出边,指向它在原图中最小的出边的 $f$ 值。

考虑一个强连通分量中的最小字符串:

  1. 如果走的是一个 $\rho$ 形,对应情况 3。
  2. 如果走的是一个 $o$ 形,且一个强连通分量中有 $\ge 2$ 个不同的环,对应情况 2。
  3. 否则,对应情况 1。

这样可以得到 $O(nm)$ 做法。

这里看似需要一些后缀数据结构来比较,但实际上,我们可以把所有点一起做这个过程,这样就同时维护了所有点 $f$ 的值的大小关系。

优化

下面考虑优化求出 $f$ 的过程。

我们不再考虑一轮一轮递推出 $f$,而是维护当前所有点 $f$ 的相对大小关系。此时所有点会根据 $f$ 分为若干等价类,同时维护每个等价类的最小出边。

考虑一个“等价类分裂”操作:假设一开始某个集合 $S$ 中所有点的 $f$ 是相等的,现在把集合 $S$ 分成两个集合 $S_0,S_1$,其中 $f(u) < f(v) (u\in S_0,v\in S_1)$。

这会造成 $S$ 中所有点的前驱的 $f$ 值可能发生变化。从而发生更多的“等价类分裂”的连锁反应。

初始把所有点当成一个等价类,然后每次把最小的字母分裂出去,并且处理所有“等价类分裂”的连锁反应。

如果每次暴力处理分裂,直到不再分裂,能求出所有点的 $f$。时间复杂度仍为 $O(nm)$。

但是这里可以“启发式分裂”:选择 $S_0,S_1$ 中 size 更小的那一边,遍历 $S_i$ 的所有前驱,只考虑这些前驱的等价类的变化。

具体过程如下:

  • 维护一个队列,存储所有分裂操作 $S\to S_0,S_1$。
  • 一开始插入所有“分裂一个最小字母”的操作,这部分大小 $\le n$ 个。
  • 若 $|S_0| \le |S_1|$:
    • 遍历所有 $u\in S_0$ 的入边。
    • 假设有 $x\to u,x\in T$,且 $T\to S$,则 $T$ 的出边可能会修改。
    • 由于 $S_0$ 更小,对于所有 $x$,等价类都会修改为 $T_0$,其中 $T_0 < T$。
  • 若 $|S_0| > |S_1|$:
    • 若对于 $x$,所有 $x$ 向 $S$ 的出边都指向 $S_1$,则等价类会修改为 $T_1$,其中 $T_1 > T$。
  • 遍历所有被影响的等价类 $T$,可能被分裂成两个集合 $\{T_0,T\}$ 或 $\{T,T_1\}$。若两个集合都不为空,则需要分裂。
    • 取出两个集合中更小的那一个,建立一个新的等价类。
    • 以分成 $\{T_0,T\}$ 为例:
      • $|T_0| \le |T|$:建立一个 $T_0$ 的等价类。
      • $|T_0| > |T|$:遍历整个 $T$,求出 $T\setminus T_0$,建立 $T\setminus T_0$ 的等价类。此时原来的 $T$ 大小减半。
    • 然后在队列中 push 一个分裂操作。

时间复杂度 $O(m\log n)$。

UOJ Round #29 公告

2025-02-09 13:02:04 By Rainbow_sjy

UOJ Round #29 将于 2 月 16 日星期日晚上 18:00 举行!比赛将进行 4 个小时,共三道题。

这是 UOJ 第二十九场 UOJ Round,还是一如既往的省选及以上难度,欢迎大家来玩!

公元 2024 年 2 月 8 日,小青鱼越过高高的龙门,成为大青龙。而一年后,公元 2025 年 2 月 8 日,跳蚤王国的一社区由于龙太唐而倒闭。

面对这一突如其来的变故,跳蚤国王决定建立一个全新的“多元、开放与包容”的学术讨论社区“跳蚤宇宙”,让所有热爱编程与竞赛的跳蚤们继续在这里交流思想、碰撞智慧、共同进步。

然而,在建设社区的过程中,伏特遇到了一些技术难题。你能否帮助伏特攻克技术难关,共同打造跳蚤王国新的学术讨论社区?

比赛链接:https://uoj.ac/contest/94

出题人:GeZhiyuan, zhoukangyang, dead_X, xyf007

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的 SHA256 码是 622bf5d6173d427945b34efba3b00589b8b93525d703294f81441be508611bdd。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD: 恭喜前5名的选手!

  1. liuhengxi
  2. hhoppitree
  3. lgvc
  4. zjy0001
  5. cmk666
输入要计算 SHA-256 的字符串: 最后一发使得得分变高的提交的时间减去第一发使得得分变高的提交的时间最大的(精确到秒),若有多个相同的则取排名最高的。
SHA-256 哈希值: 622bf5d6173d427945b34efba3b00589b8b93525d703294f81441be508611bdd

恭喜 hhoppitree(3:40:24, 18:08:06 ~ 21:48:30) 获得 UOJ 抱枕!

Rainbow_sjy Avatar