QOJ_News的博客

博客

Goodbye Jiachen 公告

2024-03-04 16:35:54 By QOJ_News

再见,甲辰!

转眼间,魔幻的 2024 就结束了,蛇年到来了。

小青鱼敏锐地发现了这一点,于是决定越过高高的蛇门,成为大青蛇。但是仅凭小青鱼的力量是越不过蛇门的。你能帮帮他吗?

我们将于 2 月 8 日下午 13:00 到 18:00 举办一场 Goodbye Jiachen 比赛。比赛时间为 0.05 小时,共 8000 道题。

赛制采取 OI 赛制,这也意味着只计入最后一次提交结果。这场比赛有很多很趣味的题目,大家一定不要错过!

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

出题人:Kubic

这场成绩将计入 rating。

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


UPD: 恭喜前5名的选手!

  1. zhoukangynag
  2. orzdevinwang
  3. zh0ukangyang
  4. zky
  5. 周康阳
Qingyu@mainhost:~$ echo -n "非零得分倒数模998244353最大,如果有多个取罚时最大的" | sha256sum
9599bd93780fb9f736281be425b0ba0e92a74fbceb0dc2dfdb9069c186b2524a  -

恭喜 Kubic 获得 uoj 抱枕!

2021 牛客多校 部分题目

2022-06-13 00:40:41 By QOJ_News

flower 加训

1C

给一个带点权的树,你可以删去树上一个点,最小化所有子树最长上升子序列的长度最大值 。

$N \leq 100\,000$

1G

给定序列 A,B,需要交换恰好 $k$ 次 A 中两个不同的数,使得 A,B 每个位置的绝对差值和最大。

$N \leq 100\,000$

2A

给定一个序列,求所有子区间,满足排序后是等差数列的个数

$n \leq 10^5$

2H

给定一个长度为 $n$ 的01串,每次翻转一个两端为1的交替段

求连续翻转 $k$ 次的方案数

$n,k \leq 6 \times 10^5$

2L

给定 $n$ 个人之间的好友关系,每次单点增加一个人的步数

求每个人在自己列表里保持冠军的时间

3A

怎么模拟赛做了?

典中典猜数可以撒谎的题

不写了。

3D

怎么模拟赛做了?

3H

Thx so much huahua

https://loj.ac/p/6786

本题大致为 #2389. 「SHOI2007」书柜的尺寸 加强版,为减少无意义提交,题意略有不同.

千寻、眠雪给了你 $n$ 个「书本」,每个「书本」有四个「属性」$a_i,b_i,c_i,d_i$.

形式化地来说,你需要将「书本」划分为三个非空集合 $S_1,S_2,S_3$,最小化目标函数 $\mathbf{\Xi}$,定义为:

$$ \mathbf{\Xi}=\left(\max_{x=1}^3\max_{i\in S_x}a_i\right)\times\left(\sum_{x=1}^3\max_{i\in S_x}b_i\right)\times\left(\max_{x=1}^3\sum_{i\in S_x}c_i\right)\times\left(\sum_{x=1}^3\sum_{i\in S_x}d_i\right) $$

求出目标函数的最小可能值.

对于所有数据,$1\leq n\leq600$,$1\leq a_i,b_i,c_i,d_i\leq10^9$,$\max c_i\leq70$,$\sum c_i\leq1\times10^4$.

4A

有 n 个课程, 每门课有学分 (范围 1...5), 且每门课都可以选无数次, 现在求选了恰好 w 学分的方案数

题目还会给出一个培养方案 : 一个 n 个点的有根树, 每个限制是x的子树里的课的学分总和至少为 c[x].

$1 \leq n \leq 100, 1 \leq Q \leq 10, 0 \leq c_i \leq 150, 0 \leq w_i \leq 10^8$

4D

这不是五年前的CF题?

5A

给一张仙人掌。

Q 次询问,每次给定 $c_i, d_i, l_i$,找点 $x$ 使得存在 $c \to d$ 的最短路经过 $x$ 且存在 $c \to l$ 的最短路径过 $x$。若有多个,选与 $x$ 距离最远的,若还有多个,选编号最小的。

$N,Q \leq 10^5$。

5F

错题,做法假了

5I

给定序列 $A$,$Q$ 次询问,每次给定 $l, r, k$,计算

$$\sum_{i=0}^{k-1} f(A_{l-i},\cdots, A_l, A_{l+1},\cdots, A_r, \cdots, A_{r+i}) \times (n+1)^i \pmod {998244353}$$

其中 $f(S) = \max\{ len \mid \exists x, \forall u \in \{x, x+1,\cdots, x+len-1\}, u \in S \}$

$1 \leq N,Q \leq 10^5, \sum k \leq 10^7$

6A

几何不做

6B

给你一张图𝐺,每条边有一个出现概率𝑃_𝑖,求生成树个数的期望 特别地,𝑃_𝑖会随着天数变化 $P_i(t) = q_i + (p_i-q_i)a^{-(t-1)}$ 你需要求出第1至第𝑇天内答案的和

$1 \leq n \leq 300, 1 \leq T_i\leq 10^8, p_i \not\equiv q_i \pmod {998244353}$

6E

题意

给出一棵树,最开始只有一个根结点,编号为 1,有颜色 𝑐。要求 在线 完成 𝑚 次操作,每次操作是以下两种之一

给结点 𝑢 加一个叶结点 𝑛+1,颜色为 𝑐。

询问以 𝑢 为根的子树中颜色为 𝑐 的结点的个数。

$m \leq 5 \times 10^5$

6J

𝑛个点,𝑚条边的简单无向联通图,每个点一个权值 𝑎_𝑖;

一个连通块的贡献:$(−1)^\text{块内点数}⋅∑𝑎_𝑖 [\text{点 𝑖 在该连通块内}]$;

可任意删除一些边,求连通块贡献之和最大是多少。

1≤𝑛,𝑚≤10^6, 1≤𝑎_𝑖≤10^9

6K

???

Potyczki Algorytmiczne 2021 Finals 结束了

2022-01-27 14:33:31 By QOJ_News

新版 Problemset Rating System 简介

2022-01-12 13:43:00 By QOJ_News

在旧版 Problemset Rating System 中, 每道题目都有一个在 $[0, 1000]$ 中的难度值 $D_i$, 而一个人的 Rating 只是简单地 $S = \sum_{i \in \mathrm{Solved~ problems}} D_i$, 但这样会导致通过大量水题的用户反而排在前面.

因此, 在民主表决后, 新版的 Problemset Rating 将通过如下方式计算:

  • 设一个人通过的题目的难度为 $x_0,x_2,\cdots, x_{n-1}$, 其中难度数组进行了非升序排序 ( 即 $x_0 \geq x_1 \geq \cdots \geq x_{n-1}$ )

  • 则一个人的 Problemset Rating 为 $$S= \frac{1}{\lambda}\sum_{i=0}^{n-1} \left(1-\frac{1}{\lambda}\right)^i x_i$$

  • 其中 $\lambda$ 为一个常数, 目前取 $\lambda = 6$

新版的 Problemset Rating System 将更加看重难度较高的题目的权重. 同时容易发现, 与平均难度不同, 解决难度较低的题目并不会使得 Rating 降低, 因此不用担心做水题会对 Rating 造成影响.

你可以在这里找到完整的排行榜, 由于计算的代价较高, 该榜并非实时更新, 而是每天更新一次.

QOJ Goodbye 2021 Championship Results.

2021-12-31 21:06:58 By QOJ_News
QOJ_News Avatar